Reference topics: MIT 6.S081 ยท independent study notes, not affiliated

Operating Systems

Processes, threads, scheduling, virtual memory, file systems, and xv6 kernel implementation.

5Lectures
1Assignments
1Exams
45hDuration
1

Introduction to Operating Systems

What is an Operating System? An OS is software that manages hardware resources and provides services to applications. It's the layer between your code and the bare metal. Components: Kernel: the...

โฑ 50 min read

What is an Operating System?

An OS is software that manages hardware resources and provides services to applications. It's the layer between your code and the bare metal.

Components:

  • Kernel: the core, runs in privileged mode
  • Shells and utilities: user-facing tools
  • Libraries: standard functions (libc)
  • System calls: interface from user to kernel

Examples: Linux, Windows, macOS, FreeBSD, xv6 (teaching OS).

Why Do We Need an OS?

Multiple programs want to run simultaneously. They compete for:

  • CPU time
  • Memory
  • Disk space
  • Network bandwidth
  • I/O devices

The OS multiplexes these resources, ensures isolation, and provides abstractions.

The Three Big Ideas

Virtualization: each process thinks it has the machine to itself. The OS multiplexes the CPU, memory, disk.

Concurrency: many activities happen at once. The OS must coordinate them safely.

Persistence: data survives across crashes and reboots. The OS provides filesystems.

Kernel Mode vs User Mode

CPUs have at least two privilege levels:

  • Kernel mode (Ring 0): can execute any instruction, access any memory
  • User mode (Ring 3): limited instruction set, restricted memory

System calls transition from user to kernel mode. The CPU switches privilege, jumps to the kernel's handler, then returns.

This protects the kernel from misbehaving applications.

Processes

A process is a running program with:

  • Address space (virtual memory)
  • Threads of execution
  • Open file descriptors
  • Registers, stack, heap
  • PID, parent, children

The OS switches between processes using a context switch: save one process's state, load another's.

Context switch overhead: 1-5 microseconds typically.

System Calls

The interface from user programs to the kernel:

  • Process: fork, exec, wait, exit, getpid
  • File: open, read, write, close, lseek, stat
  • Memory: mmap, brk, sbrk
  • Network: socket, bind, listen, accept
  • IPC: pipe, shmget, msgget

POSIX defines a standard API implemented by most Unix-like systems.

Example: Running ls

  1. Shell forks a child process
  2. Child calls exec("ls")
  3. Kernel loads ls binary, sets up its address space
  4. ls runs, opens the current directory (open syscall)
  5. ls reads directory entries (getdents syscall)
  6. For each entry, ls calls stat to get metadata
  7. ls writes output to stdout (write syscall)
  8. ls exits, kernel notifies parent
  9. Shell prints prompt

Hundreds of syscalls for a simple command.

The Kernel Interface

Applications should never call the kernel directly. They use libc wrappers:

// C code
fd = open("/etc/passwd", O_RDONLY);

// Assembly equivalent (x86-64)
mov $2, %rax ; SYS_open
lea filename(%rip), %rdi
mov $0, %rsi ; O_RDONLY
syscall

The wrapper handles the syscall instruction and error return.

Monolithic vs Microkernel

Monolithic kernel: all OS services in kernel space. Linux, Windows, xv6.

Pros: fast (no message passing). Cons: less isolation, harder to debug.

Microkernel: only essential services (scheduling, IPC, memory) in kernel. Servers in user space. QNX, L4, Mach.

Pros: better isolation, more modular. Cons: slower IPC.

Hybrid: most in kernel, some as servers. macOS (XNU).

Layered OS Structure

Modern OS architecture (bottom to top):

  1. Hardware
  2. Kernel (memory, processes, drivers)
  3. System calls
  4. Libraries (libc, libc++)
  5. Applications

Each layer trusts the one below, provides services to the one above.

Key Takeaways

  • OS = manager of hardware + provider of services
  • Virtualization, concurrency, persistence are the three big ideas
  • Kernel mode vs user mode protects the system
  • Processes are isolated execution contexts
  • System calls are the interface
  • Monolithic vs microkernel trade-offs
  • Layered architecture scales from phone to server
2

Processes and Scheduling

What is a Process? A process is a program in execution. It has: Address space: virtual memory, code, data, heap, stack Thread of control: PC, registers, stack Resources: open files, sockets, ...

โฑ 50 min read

What is a Process?

A process is a program in execution. It has:

  • Address space: virtual memory, code, data, heap, stack
  • Thread of control: PC, registers, stack
  • Resources: open files, sockets, signals
  • Metadata: PID, parent PID, owner, priority, state

The kernel maintains a process table (or list of task_struct in Linux).

Process States

  • New: being created
  • Ready: waiting for CPU
  • Running: executing on CPU
  • Blocked: waiting for I/O or event
  • Terminated: finished

Transitions:

  • New โ†’ Ready: admitted
  • Ready โ†’ Running: scheduled
  • Running โ†’ Ready: preempted (time slice)
  • Running โ†’ Blocked: I/O request or wait
  • Blocked โ†’ Ready: I/O complete or event
  • Running โ†’ Terminated: exit

Context Switch

When the OS switches from process A to process B:

  1. Save A's registers to its PCB (process control block)
  2. Restore B's registers from its PCB
  3. Switch page tables (memory management)
  4. Flush TLB (unless tagged)
  5. Resume B

Cost: 1-10 ยตs, depending on architecture. Heavy in virtualized environments.

fork() โ€” Creating a Process

fork() creates a copy of the calling process. Both parent and child continue from the same instruction.

pid_t pid = fork();
if (pid == 0) {
// child
} else if (pid > 0) {
// parent (pid is child's PID)
} else {
// error
}

The child gets a copy of the parent's address space (copy-on-write optimization). File descriptors are duplicated.

exec() โ€” Replacing the Program

exec() replaces the current process's image with a new program:

execl("/bin/ls", "ls", "-l", NULL);

The address space is replaced. Only the PID, open file descriptors, and some signals survive.

The fork-exec Pattern

To run a program:

  1. fork() to create a child
  2. Child calls exec() to replace itself
  3. Parent wait()s for the child to finish

This is how the shell runs commands.

wait() โ€” Reaping Children

int status;
pid_t pid = wait(&status);

Blocks until a child exits. Returns the child's PID and exit status.

Zombies: children that exited but weren't waited for. Occupy a process slot. Must be reaped.

Orphans: children whose parent exited first. Reparented to init (PID 1).

Scheduling Algorithms

FCFS (First-Come First-Served): simple, non-preemptive. Convoy effect โ€” long jobs block short ones.

SJF (Shortest Job First): optimal average wait time. Requires knowing execution time (impossible in advance).

Round Robin: each process runs for a time slice (quantum). Fair, responsive.

Priority: higher priority runs first. Starvation risk โ€” aging fixes it.

Multilevel Feedback Queue: multiple queues with different priorities. Process moves between queues based on behavior. Used in general-purpose OSes.

CFS (Completely Fair Scheduler): Linux's current scheduler. Uses a red-black tree keyed by virtual runtime. O(log n) per decision.

Scheduling Metrics

  • Throughput: jobs completed per unit time
  • Turnaround time: from submission to completion
  • Waiting time: time spent ready, not running
  • Response time: from submission to first output
  • Fairness: how evenly CPU is distributed

Different systems optimize different metrics. Batch systems want throughput, interactive systems want response time.

Threads

A thread is a lightweight unit of execution. Multiple threads share the process's address space.

Benefits:

  • Concurrency (overlap I/O with compute)
  • Parallelism (use multiple cores)
  • Responsiveness (UI thread stays free)

Costs:

  • Race conditions (shared data)
  • Lock overhead
  • Debugging complexity

Kernel threads vs user threads vs hybrid (most common).

Context Switching Cost

Direct cost: saving/restoring registers (~100 ns).

Indirect cost: cache pollution. Switching between processes touches different memory, evicting cached data. Can cost microseconds in cache misses.

Reducing context switches is a key optimization.

Key Takeaways

  • Process = running program + address space + resources
  • fork, exec, wait are the basic primitives
  • fork creates, exec replaces, wait reaps
  • Many scheduling algorithms, each with trade-offs
  • CFS uses virtual runtime and a red-black tree
  • Threads share address space, process switch is heavier
  • Context switch cost includes cache pollution
3

Virtual Memory and Paging

The Problem Each process wants its own private address space. Physical memory is shared and limited. Solution: virtual memory. The CPU translates virtual addresses to physical addresses. Each process...

โฑ 50 min read

The Problem

Each process wants its own private address space. Physical memory is shared and limited.

Solution: virtual memory. The CPU translates virtual addresses to physical addresses. Each process sees a large, contiguous, private space.

Benefits

  • Isolation: process A can't read B's memory
  • Protection: read-only regions enforced by hardware
  • Flexibility: programs don't need physical layout
  • Overcommit: sum of virtual spaces > physical RAM
  • Sharing: libraries mapped read-only into many processes

Pages and Frames

Virtual memory is divided into fixed-size pages (typically 4 KB).
Physical memory is divided into frames of the same size.

Virtual address: [ VPN | offset ]
Physical address: [ PFN | offset ]

The offset is copied directly. The page number is translated via the page table.

On x86-64: 48-bit virtual (256 TB), 52-bit physical (4 PB). 4 KB pages.

Page Tables

A page table is an array of page table entries (PTEs). Each PTE contains:

  • Physical frame number
  • Valid bit
  • Read/write/execute permissions
  • Accessed and dirty bits
  • Cache control bits

Flat page table for 48-bit virtual with 4 KB pages: 2^36 ร— 8 bytes = 512 GB. Impossible.

Multi-Level Page Tables

Split the virtual address into pieces. Each level indexes a smaller table.

For 48-bit addresses, 4-level page table:
[ PGD 9b | PUD 9b | PMD 9b | PTE 9b | offset 12b ]

Each table has 512 entries ร— 8 bytes = 4 KB (one page).

Sparse allocation: unused address ranges have null pointers. Typically a few MB per process.

The TLB

Every memory access requires a page table walk (4 reads). That's 4x slower.

Solution: the Translation Lookaside Buffer. A small cache of recent translations. Typically 32-2048 entries, fully associative.

TLB hit: translation is essentially free.
TLB miss: walk the page table (~20-100 cycles).

Hit rate >99% typical because of locality.

Page Faults

If the VPN has no valid PTE:

  1. CPU raises page fault exception
  2. Kernel's page fault handler runs
  3. If page is in swap: allocate frame, read from disk, update PTE, return
  4. If page is illegal: send SIGSEGV to process

Page fault cost: ~1-10 microseconds (dominated by disk I/O).

Demand Paging

Don't load pages until accessed. Lazy allocation.

Advantages:

  • Faster program startup
  • Less memory used
  • Allows overcommit

Disadvantages:

  • Page faults during execution
  • Must track which pages are on disk

Page Replacement

When physical memory is full, evict a page.

OPT (Belady): evict page used furthest in future. Optimal but unimplementable.

LRU: evict least recently used. Good but expensive to track.

Clock: approximate LRU with a reference bit. Used in Linux.

FIFO: simple but can exhibit Belady's anomaly.

Linux uses a variant of LRU with active/inactive lists.

Working Set

The set of pages a process is actively using. If physical memory โ‰ฅ sum of working sets, no thrashing. If < , thrashing โ€” pages are evicted before they're reused.

Detect: high page fault rate. Fix: reduce multiprogramming (swap out processes) or add memory.

Copy-on-Write (COW)

When fork() is called, don't copy all pages. Mark them read-only and shared. On write, copy the page and update the PTE.

Benefits:

  • fork is fast
  • Memory shared until modified
  • Used by Linux, macOS, Windows

Memory-Mapped Files

Map a file into the address space:

void *addr = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, offset);

Access the file like memory. Kernel handles paging.

Used for:

  • Executables (text and data sections)
  • Shared libraries
  • Databases (SQLite uses mmap)
  • Shared memory between processes

Huge Pages

Standard 4 KB pages require many TLB entries. Huge pages (2 MB or 1 GB) cover more memory per entry.

Used for:

  • Databases (MySQL, PostgreSQL)
  • Virtual machines
  • Scientific computing

Trade-off: internal fragmentation (page is allocated whole).

Swapping

When memory is overcommitted, evict pages to disk. Linux uses swap files or partitions.

Cost: 1-10 ms per page (SSD) to 10-100 ms (HDD). Minimize swapping for performance.

Key Takeaways

  • Virtual memory gives isolation and flexibility
  • Multi-level page tables save memory
  • TLB makes translation fast in the common case
  • Page faults handle missing pages
  • Demand paging allows overcommit
  • LRU/Clock for replacement
  • COW speeds up fork
  • mmap for file-backed memory
  • Huge pages reduce TLB pressure
  • Swapping is expensive
4

Concurrency and Synchronization

Why Concurrency? Multiple threads or processes need to coordinate access to shared resources: memory, files, devices. Without synchronization, race conditions occur โ€” the result depends on timing....

โฑ 50 min read

Why Concurrency?

Multiple threads or processes need to coordinate access to shared resources: memory, files, devices.

Without synchronization, race conditions occur โ€” the result depends on timing.

Race Condition Example

Two threads increment a shared counter:

counter = counter + 1;

In assembly:
load r1, [counter]
add r1, r1, 1
store r1, [counter]

If both threads execute simultaneously:

Thread A Thread B counter
load r1 = 0
load r1 = 0 0
add r1 = 1
add r1 = 1
store [counter] = 1
store [counter] = 1 1 (lost update!)

Expected: 2. Got: 1. Classic race condition.

Critical Section

The part of code that must run atomically (no interleaving).

Solution properties:

  • Mutual exclusion: only one thread in CS at a time
  • Progress: if no thread in CS and one wants in, it gets in
  • Bounded waiting: a waiting thread eventually enters

Locks (Mutexes)

lock(m);
// critical section
unlock(m);

A mutex ensures only one thread in the CS.

Implementation requires hardware support:

  • Test-and-set: atomically sets a flag and returns old value
  • Compare-and-swap (CAS): atomically compares and swaps

while (test_and_set(&lock)) { /* spin */ }
// critical section
lock = 0;

Spinlock: busy-wait. Good for short critical sections on multicore.

Blocking lock: put waiting threads to sleep, wake on release. Better for long CS.

Semaphores

Dijkstra's semaphore: an integer with two atomic operations:

P(s): wait until s > 0, then s-- (Dutch: proberen)
V(s): s++ (Dutch: verhogen)

Used for:

  • Mutual exclusion (s initialized to 1)
  • Signaling between threads (s initialized to 0)
  • Resource counting (s initialized to N)

Condition Variables

Wait for a condition to become true:

pthread_mutex_lock(&m);
while (!condition) {
pthread_cond_wait(&c, &m);
}
// condition is true
pthread_mutex_unlock(&m);

// In another thread:
pthread_mutex_lock(&m);
condition = 1;
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);

Always wait in a loop. Spurious wakeups are allowed.

Monitors

Higher-level abstraction: a lock + condition variables bundled with data. Languages like Java provide synchronized methods.

public synchronized void deposit(int amount) {
balance += amount;
notifyAll();
}

The compiler inserts lock/unlock automatically.

Classic Problems

Producer-Consumer:

  • Bounded buffer
  • Producers wait if full, consumers wait if empty
  • Uses a mutex + two condition variables

Readers-Writers:

  • Multiple readers can access simultaneously
  • Writers need exclusive access
  • Variants: reader-priority, writer-priority

Dining Philosophers:

  • Five philosophers, five forks
  • Each needs two forks to eat
  • Deadlock if all grab left fork simultaneously

Deadlock

Four conditions for deadlock (all must hold):

  1. Mutual exclusion
  2. Hold and wait
  3. No preemption
  4. Circular wait

Break any one to prevent deadlock.

Solutions:

  • Prevention: eliminate one of the four conditions
  • Avoidance: Banker's algorithm (rarely used)
  • Detection and recovery: find cycles, kill a process
  • Ignore: most OSes do this

Atomic Operations

Hardware provides primitives:

  • Compare-and-swap (CAS)
  • Fetch-and-add
  • Load-linked / store-conditional (LL/SC, ARM, RISC-V)

Lock-free data structures use these to avoid locks entirely. Powerful but tricky.

Memory Barriers

Modern CPUs reorder memory operations for performance. A barrier forces ordering:

store x
barrier
store y

Ensures store to y doesn't happen before store to x from another core's view.

Critical for lock-free code and device drivers.

Concurrency Bugs

  • Race condition: timing-dependent result
  • Deadlock: circular wait
  • Livelock: threads keep retrying, no progress
  • Starvation: a thread never gets to run
  • Priority inversion: low-priority thread holds lock needed by high-priority

Careful design and tools (ThreadSanitizer, Helgrind) help.

Key Takeaways

  • Race conditions arise from unsynchronized access
  • Locks, semaphores, condition variables synchronize
  • Monitors for higher-level abstraction
  • Classic problems: producer-consumer, readers-writers, dining philosophers
  • Deadlock: four conditions, break any one
  • Atomics and barriers for lock-free code
  • Many concurrency bugs; use tools
5

File Systems and Persistence

What is a File System? A file system organizes data on persistent storage (disk, SSD). It provides: Named files Hierarchical directories Byte-addressable files Metadata (permissions, timestamps) At...

โฑ 50 min read

What is a File System?

A file system organizes data on persistent storage (disk, SSD). It provides:

  • Named files
  • Hierarchical directories
  • Byte-addressable files
  • Metadata (permissions, timestamps)
  • Atomic operations (rename)

The filesystem is an abstraction over block devices.

Block Devices

Disks expose a linear array of fixed-size blocks (typically 512 B or 4 KB).

Operations:

  • Read a block
  • Write a block

The filesystem maps file operations to block operations.

The File Abstraction

A file is a sequence of bytes with a name. The kernel maintains:

  • inode: metadata (size, permissions, timestamps, block pointers)
  • dentry: directory entry (name โ†’ inode)
  • file descriptor: per-process open file handle (offset, mode)

Directory Structure

A directory is a special file that maps names to inodes.

/home/alice/Documents/report.pdf

Lookup: start at root inode, find "home", then "alice", then "Documents", then "report.pdf".

Each lookup is a filesystem operation. Path walk can be slow. Caches (dentry cache) help.

inodes

The inode stores:

  • File type (regular, directory, symlink, device)
  • Size in bytes
  • Owner, group, permissions
  • Timestamps (atime, mtime, ctime)
  • Link count
  • Pointers to data blocks

In ext4: 12 direct pointers + 1 single indirect + 1 double indirect + 1 triple indirect.

Small files (โ‰ค12 blocks) fit entirely in direct pointers. Large files use indirect blocks.

Block Allocation

Contiguous: simple, fast, but fragmentation. Rare in practice.

Linked: each block points to next. Simple but slow random access.

Indexed: inode points to blocks. Common (ext, XFS).

Extent-based: inode stores extents (start block + length). Reduces metadata for large files. Used in ext4, XFS, btrfs.

Free Space Management

Track which blocks are free:

  • Bitmap: one bit per block. Simple, fast.
  • Free list: linked list of free blocks.

Bitmaps are common in modern filesystems.

Journaling

A crash during a write can leave the filesystem inconsistent. Journaling prevents this.

Write the intended change to a journal (log) first, then apply to the actual location.

On crash, replay the journal โ€” the change is either fully done or not at all.

Modes:

  • writeback: journal only metadata
  • ordered: metadata journaled, data written before metadata
  • journal: everything journaled (slowest, safest)

ext4, XFS, NTFS use journaling.

Log-Structured File Systems

Alternative: never overwrite. Always write to fresh locations. Old versions become garbage, collected later.

Benefits:

  • Sequential writes (good for SSD)
  • Fast crash recovery (only check the tail)
  • Snapshots easy

Used in: NILFS2, F2FS, and (partially) in ZFS.

Copy-on-Write (CoW) Filesystems

Modify by writing new copies, never overwrite existing blocks.

Benefits:

  • Atomic updates (write new tree, swap root pointer)
  • Easy snapshots
  • Data integrity (checksums)

Used in: ZFS, btrfs.

SSD-Specific Optimizations

SSDs have unique characteristics:

  • No seek time (random = sequential)
  • Limited write cycles per cell
  • Must erase blocks before writing
  • Wear leveling: spread writes evenly

Filesystems for SSD: F2FS (Flash-Friendly File System), designed by Samsung.

TRIM: OS tells SSD which blocks are free. Improves performance and longevity.

The Read/Write Path

When you call read(fd, buf, n):

  1. Look up fd in process's file table โ†’ file struct
  2. Get offset from file struct
  3. Look up inode in inode cache
  4. Translate offset to block numbers
  5. Check page cache for those blocks
  6. If hit: copy from page cache to buf
  7. If miss: read from disk into page cache, then copy

The page cache is critical for performance. Most reads hit it.

Writes go to the page cache first ("write-back" caching). Synced to disk later.

fsync() and Durability

By default, writes are not immediately durable. To force:

fsync(fd); // flush file data to disk
fdatasync(fd); // flush data, skip metadata if safe

Essential for databases, editors.

fsck โ€” File System Check

After a crash, run fsck to verify consistency:

  • inode link counts
  • Block allocation bitmaps
  • Directory structure
  • Free inode counts

Journaling filesystems avoid long fsck โ€” replay is faster.

Modern Filesystems

  • ext4: Linux default. Stable, mature.
  • XFS: Linux, high-performance parallel.
  • btrfs: Linux, CoW, snapshots, checksums.
  • ZFS: Solaris, FreeBSD, Linux. Powerful, complex.
  • APFS: macOS. Snapshots, encryption.
  • NTFS: Windows. Journaling, ACLs.

Distributed Filesystems

  • NFS: network file system, POSIX-like
  • SMB/CIFS: Windows file sharing
  • HDFS: Hadoop distributed file system
  • Ceph: scalable distributed storage
  • S3: object storage (not a filesystem)

Key Takeaways

  • File systems abstract block devices
  • inodes + dentries + file descriptors
  • Block allocation: indexed, extent-based
  • Journaling for crash consistency
  • Log-structured and CoW for special cases
  • SSD-optimized: F2FS, TRIM, wear leveling
  • Page cache is critical for performance
  • fsync for durability
  • Many filesystems for different needs

๐Ÿ“ Problem Set 1: Processes, Scheduling, VM

Q1. Explain what fork() returns to parent and child, and how the OS uses copy-on-write to optimize it.

Show Solution

Parent: returns child PID (>0). Child: returns 0. On error: returns -1. COW: after fork, all pages marked read-only and shared. On first write by either process, a page fault triggers a copy of that page. Only modified pages are duplicated โ€” saves memory and time.

Q2. Trace through SJF scheduling: processes A(8ms), B(4ms), C(2ms), D(1ms), arriving at t=0. Calculate average waiting time.

Show Solution

Order: D(1), C(2), B(4), A(8). Wait times: D=0, C=1, B=3, A=7. Average = (0+1+3+7)/4 = 2.75 ms.

Q3. A 32-bit virtual address uses 4 KB pages and 2-level page table (10-bit each level). How many page table entries per table?

Show Solution

Each level has 2^10 = 1024 entries. Offset = log2(4096) = 12 bits. VPN = 32 - 12 = 20 bits, split into 10+10. Each PTE = 4 bytes, so each table = 4 KB (fits exactly in one page).

๐ŸŽฏ Midterm 1: Processes, Scheduling, Memory

Q1. Compare round-robin (quantum=4ms) vs FCFS for processes A(8ms), B(2ms), C(6ms) all arriving at t=0. Which has lower average waiting time?

Show Solution

FCFS: A waits 0, B waits 8, C waits 10. Avg = 6 ms. RR(q=4): A runs 0-4, B 4-6, C 6-10, A 10-14, C 14-16. Wait times: A=6, B=4, C=10. Avg = 6.67 ms. FCFS wins here but has worse worst-case.

Q2. A system has 3 frames and the reference string 1,2,3,4,1,2,5,1,2,3,4,5. How many page faults with LRU vs FIFO?

Show Solution

LRU: 10 page faults. FIFO: 15 page faults. Belady's anomaly: for some reference strings, adding frames can increase faults in FIFO, but not LRU.

Q3. Explain how two threads both executing 'counter++' can lose an update, and how to fix it with a mutex.

Show Solution

counter++ decomposes to load, add, store. If T1 loads 0, T2 loads 0, both compute 1, both store 1 โ†’ counter = 1 instead of 2. Fix: lock mutex before incrementing, unlock after. Ensures load-add-store is atomic.