Operating System

When you double-click Chrome, the OS creates a process. It gets its own memory space, file handles, security context — completely isolated from other processes. If Chrome crashes, your Word document stays safe. That's isolation.

Now inside Chrome, there are many threads — one for UI, one for network, one for each tab's JavaScript. They all share Chrome's memory, so they can easily talk to each other (just read/write shared variables). But they each have their own stack and registers, so they can run independently.

The key insight: OS allocates resources to processes, but schedules threads. A process with 4 threads can use 4 CPU cores simultaneously. A single-threaded process wastes 3 cores. That's why multi-threading matters for performance.

Creating a process is expensive — OS must copy or allocate entire address space, file descriptors, etc. Creating a thread is cheap — just allocate a new stack and register set. Thread switching within the same process is also faster than process switching (no need to change page tables).

Imagine a chef cooking 5 dishes simultaneously. Each time they switch from biryani to pasta, they must: remember where they left off with biryani, put away those spices, pull out pasta ingredients, recall what step they were on. That mental load is context switching.

When a context switch happens, the CPU must: save program counter (where were we?), save all registers, save stack pointer, save memory mappings pointer, update PCB. Then load all these values for the next process. This takes 1-10 microseconds typically — sounds small, but if you're switching thousands of times per second, it adds up.

Thread context switch is faster than process context switch because threads share the same address space — no need to flush TLB (translation lookaside buffer) or switch page tables. That's why servers often use threads instead of processes.

Single-threaded program is like a restaurant with one chef. Multithreaded is like having 4 chefs in the same kitchen. They can cook multiple dishes in parallel, share ingredients, but need to coordinate — or they'll grab the same knife at the same time.

Why use multithreading? (1) Utilize multiple CPU cores — a 4-core CPU with single-threaded code wastes 75% of its power. (2) Keep UI responsive — heavy computation in background thread while UI thread stays smooth. (3) Handle I/O efficiently — while one thread waits for disk, another can do CPU work.

The catch: shared memory makes communication easy but creates problems. Two threads modifying the same variable? Race condition. Two threads waiting for each other's locks? Deadlock. Multithreading is powerful but tricky to get right.

FCFS (First Come First Serve): Simple queue — whoever comes first, runs first. Problem: convoy effect. One long job makes everyone behind wait. Average waiting time can be terrible.

SJF (Shortest Job First): Pick the process with shortest burst time. Mathematically optimal for average waiting time. Problem: starvation of long processes, and how do you even know the burst time in advance? (Answer: predict using exponential averaging of past bursts.)

Round Robin: Each process gets a fixed time slice (quantum), then goes to back of queue. Fairest algorithm — everyone gets a turn. Tuning the quantum is key: too small = too many context switches, too large = behaves like FCFS.

Priority Scheduling: Higher priority runs first. Problem: low-priority processes starve. Solution: aging — increase priority of waiting processes over time. Can be preemptive or non-preemptive.

MLFQ (Multi-Level Feedback Queue): Multiple queues with different priorities and time quanta. New processes start at top (high priority, small quantum). If they use full quantum, they're CPU-bound → demote to lower queue. Interactive processes (short bursts) stay at top. Adapts to process behavior. Most real OS use variants of this.

Two cars on a narrow bridge, coming from opposite sides, meeting in the middle. Neither can move forward, neither wants to reverse. They wait for each other... forever. That's deadlock.

In OS terms: Process A holds Resource 1 and wants Resource 2. Process B holds Resource 2 and wants Resource 1. Neither releases what they have. Both wait indefinitely. Classic example: two threads each trying to acquire two locks in different orders.

Four Necessary Conditions (Coffman, 1971): ALL four must exist simultaneously for deadlock to occur:

1. Mutual Exclusion: At least one resource is non-shareable (only one process can use it at a time)
2. Hold and Wait: Process holds some resources while waiting for others
3. No Preemption: Resources can't be forcibly taken away
4. Circular Wait: A→B→C→A cycle of waiting

Break ANY one of these conditions and deadlock becomes impossible.

Restaurant analogy: VIP customers always get seated first. A regular customer arrives, but VIPs keep coming. Hours pass. The regular customer is never served — not because the restaurant is closed, but because they're always deprioritized. That's starvation.

Starvation happens in: (1) Priority Scheduling — low-priority process waits forever if high-priority processes keep arriving. (2) SJF — long jobs starve because short jobs keep coming. (3) Reader-Writer Problem — if readers keep arriving, writer starves.

Solution: Aging. Gradually increase priority of waiting processes. Eventually even the lowest priority becomes high enough to run.

Two people editing the same Google Doc cell simultaneously without seeing each other's changes. Person A reads "50", adds 10, writes "60". Person B reads "50" (before A's write), adds 20, writes "70". Expected: 80. Got: 70. That's a race condition — the outcome depends on who "wins" the race.

The classic example: incrementing a shared counter. counter++ looks atomic but it's actually: (1) load counter value, (2) add 1, (3) store result. If two threads do this simultaneously, they might both load the same value, both add 1, both store — result: only incremented once instead of twice.

The code region where shared resources are accessed is called the critical section. Race conditions are fixed by ensuring mutual exclusion in the critical section — only one thread at a time.

A bathroom with a lock. One person enters, locks the door. Others wait outside. When done, unlocks the door. Next person enters. That's a mutex — only the owner can unlock it.

How it works: Thread calls lock(). If mutex is free, thread acquires it and continues. If mutex is held by another thread, calling thread blocks (sleeps) until mutex is released. Thread calls unlock() when done — wakes up one waiting thread.

Ownership: Mutex has owner. Only the thread that locked it can unlock it. This is THE key difference from binary semaphore. If thread A locks mutex, thread B cannot unlock it.

In C++, use std::lock_guard or std::unique_lock — RAII wrappers that automatically unlock when scope ends. Prevents forgetting to unlock on exceptions or early returns.

Counting Semaphore: A parking lot with N spaces. Counter shows available spots. Car enters → wait() → counter decrements. Car leaves → signal() → counter increments. When counter is 0, new cars must wait.

Binary Semaphore: Counter is 0 or 1. Works like a lock but without ownership — any thread can signal it, not just the one that waited. Useful for thread-to-thread signaling.

Classic operations: P() or wait() or down() — decrement and block if would go negative. V() or signal() or up() — increment and wake one blocked thread. These operations are atomic.

Classic problems solved by semaphores: Producer-Consumer (bounded buffer), Readers-Writers (shared data access), Dining Philosophers (resource allocation), and synchronizing execution order.

Imagine a book (your process) with 100 pages. The library (RAM) has shelf slots (frames). Pages can go into ANY available slot — they don't need to be next to each other. A table of contents (page table) tells you which page is in which slot. Page 1 might be in slot 47, page 2 in slot 3, etc.

Address translation: Logical address = page number + offset. CPU generates logical address, MMU (Memory Management Unit) looks up page number in page table to find frame number, combines with offset to get physical address. This happens for every memory access.

Page table overhead: Each process needs its own page table. With 4KB pages and 4GB address space, you need 1 million entries. Each entry is ~4 bytes → 4MB just for page table! Solution: multi-level page tables (only allocate what's needed) or inverted page tables.

TLB (Translation Lookaside Buffer): Page table is in main memory. Accessing it for every address is too slow. TLB is a small, fast cache of recent page→frame mappings. TLB hit = fast. TLB miss = slow (access page table, update TLB).

While paging blindly chops memory into equal-size pages (like cutting a pizza into identical slices without looking at toppings), segmentation respects the logical structure of your program. Code is one segment, data is another, stack is another. Each has a different size based on need.

Segment table: Each entry has: base (starting physical address) + limit (segment size). Logical address = segment number + offset. If offset > limit → segmentation fault! This is protection built into the hardware.

Modern systems use segmented paging: segments are further divided into pages. You get logical grouping of segments + no external fragmentation of paging. x86 supports both, but modern OS (Linux, Windows) use flat segmentation (all segments have base=0, limit=max) and rely entirely on paging.

Every process believes it owns the entire memory — say, 4GB on 32-bit system. But your machine might only have 2GB RAM. How? Virtual memory. Each process has a virtual address space. OS maps only the pages actually being used to physical RAM. Rest stays on disk (swap space).

Demand paging: Don't load entire program at startup. Load pages only when accessed. First access to a page → page fault → OS loads it from disk. Subsequent accesses → fast (already in RAM).

Key benefits: (1) Run programs larger than physical memory. (2) Process isolation — process A can't access process B's memory because they have different page tables. (3) Memory protection — pages can be read-only, no-execute, etc. (4) Shared libraries — multiple processes can share the same code pages.

Thrashing: If working set (frequently used pages) exceeds RAM, system spends all time swapping pages in and out. CPU utilization drops, system becomes unusable. Solution: add RAM, reduce multiprogramming degree, or use working set model.

Every process has a memory layout (from low to high address): Text (code) → Data (initialized globals) → BSS (uninitialized globals) → Heap (grows ↑) → ... free space ... → Stack (grows ↓) → Kernel space.

Stack: LIFO structure. Each function call pushes a frame (local vars, return address, params). Function return pops the frame. Super fast allocation (just move stack pointer). Limited size (1-8MB typically). Stack overflow = too deep recursion or huge local arrays.

Heap: Dynamic memory — you request (malloc/new), you release (free/delete). Managed by allocator, can fragment. Slower than stack (must find free block). No size limit (well, virtual memory limit). Memory leak = forgetting to free.

First Fit: Scan from beginning, pick first hole big enough. Fast (stops early). Problem: fragments the beginning of memory.

Next Fit: Like First Fit, but start from where last allocation ended. Distributes allocation more evenly. Slightly better than First Fit in practice.

Best Fit: Search entire list, pick smallest hole that fits. Minimizes wasted space per allocation. Problem: leaves tiny unusable fragments, slow (full scan).

Worst Fit: Pick largest hole. Theory: leftover will be big enough to be useful. Practice: quickly fragments large blocks, performs worst overall.

Buddy System: Memory divided into power-of-2 blocks. Request for 70KB? Allocate 128KB block. To allocate, split larger block into two "buddies." To free, merge buddies back. Used in Linux kernel. Fast and limits fragmentation.

In C/C++, you allocate memory, you free it. Forget to free → memory leak. Free twice → crash. In garbage-collected languages, you just allocate. The GC periodically finds unreachable objects and frees them. You don't call free/delete.

Mark and Sweep: (1) Start from "roots" (stack, globals, registers). (2) Mark all reachable objects. (3) Sweep: free all unmarked objects. Problem: needs to pause program ("stop the world"). Modern GCs use incremental/concurrent marking to reduce pauses.

Reference Counting: Each object has a counter — how many references point to it. When counter = 0, free immediately. Problem: circular references (A→B→A, both have count 1, neither freed). Solution: combine with mark-sweep or use weak references.

Generational GC: Observation: most objects die young. Divide heap into generations: young (Eden), old (Tenured). Collect young generation frequently (fast, most garbage is here). Collect old generation rarely (slow but infrequent). Objects that survive young collections get promoted to old. Java uses this.