Operating Systems

What an OS Does
• Process Management: create, schedule, and terminate processes
• Memory Management: allocate and protect RAM, virtual memory paging
• File System: organize files and directories on storage
• I/O Management: abstract hardware devices (disk, network, keyboard)
• Security: user accounts, permissions, system calls

Process vs Thread | | Process | Thread | |---|---|---| | Memory | Own address space | Shared memory | | Cost | Expensive to create | Lightweight | | Communication | IPC (pipes, sockets) | Shared variables | | Crash isolation | Isolated | Crashes process |

System Calls the OS API ``c // User space → kernel space pid_t pid = fork(); // create process int fd = open("file"); // open file read(fd, buf, n); // read bytes write(STDOUT, msg, n); // write to stdout exit(0); // terminate ``

Scheduling Algorithms

FCFS (First Come First Served)
• Processes run in arrival order
• Simple but poor average waiting time (convoy effect)

SJF (Shortest Job First)
• Run shortest burst-time process next
• Optimal average wait time but requires knowing burst time
• Can starve long processes

Round Robin (RR)
• Each process gets a fixed time quantum (e.g. 10ms)
• Preempted if not done, goes to back of queue
• Default in most modern OSes (combined with priority)

Multilevel Queue
• Separate queues for interactive (high priority) vs batch (low)
• Foreground apps get CPU preference over background tasks

Real-World: Linux CFS (Completely Fair Scheduler)
• Each process gets a fair share of CPU time proportional to weight
• Uses a red-black tree sorted by virtual runtime
• Interactive processes naturally get lower virtual time → scheduled more

Context Switch saving and restoring CPU registers when switching processes. Overhead ~110μs.

Virtual Memory Every process sees its own isolated address space (e.g. 04GB on 32-bit). The OS maps virtual → physical pages.

Virtual Address Space (per process):
  0x0000 → Stack (grows down)
  ...
  Heap  (grows up)
  BSS   (uninitialized globals)
  Data  (initialized globals)
  Text  (code read-only)

Paging
• Memory divided into fixed-size pages (4KB typical)
• Page Table maps virtual page → physical frame
• TLB (Translation Lookaside Buffer): cache of recent translations

Page Replacement Algorithms | Algorithm | Strategy | Note | |---|---|---| | FIFO | Evict oldest page | Simple, poor performance | | LRU | Evict least recently used | Near-optimal, expensive | | Clock | Approximate LRU | Used in Linux | | LFU | Evict least frequently used | Works well for read-heavy |

Thrashing when the system spends more time paging than executing. Solution: reduce degree of multiprogramming.

Memory Leaks process allocates heap memory but never frees it. Tools: Valgrind (C/C++), heaptrack, jmap (Java).

File System Structure `` Disk → Partitions → File System ├── Superblock (FS metadata: size, free blocks) ├── Inode Table (file metadata: size, permissions, block pointers) └── Data Blocks (actual file content) ``

Common File Systems | FS | OS | Strengths | |---|---|---| | ext4 | Linux | Journaling, large files, mature | | APFS | macOS | Snapshots, encryption, SSD-optimized | | NTFS | Windows | Permissions, large files, journaling | | ZFS | Linux/BSD | Copy-on-write, checksums, snapshots | | btrfs | Linux | Subvolumes, compression, RAID |

I/O Scheduling
• CFQ (Completely Fair Queuing): fair bandwidth per process
• Deadline: ensures requests complete within time limit
• NOOP: no reordering, best for SSDs (no seek time)

Buffered vs Direct I/O
• Buffered (default): OS caches reads/writes in page cache
• Direct (O_DIRECT): bypass page cache, write straight to disk
• mmap: map file directly into process address space

Journaling write-ahead log prevents corruption on crash. ext4 journals metadata; full-data journaling journals content too.

Race Conditions two processes read-modify-write shared state concurrently, producing wrong results.

Critical Section code accessing shared resource that must be atomic.

Mutex (Mutual Exclusion) ``c pthread_mutex_t lock; pthread_mutex_lock(&lock); // critical section pthread_mutex_unlock(&lock); ``

Semaphore integer counter for resource control.
• Binary semaphore = mutex
• Counting semaphore = manage N instances of a resource

Deadlock four conditions (Coffman): 1. Mutual exclusion: resource held exclusively 2. Hold and wait: holding resource while waiting for another 3. No preemption: can't take resource from process 4. Circular wait: A waits for B, B waits for A

Prevention: break one condition (e.g., always acquire locks in same order).

Monitor / Condition Variables ``c pthread_cond_wait(&cond, &mutex); // release lock and wait pthread_cond_signal(&cond); // wake one waiter pthread_cond_broadcast(&cond); // wake all waiters ``