Quick Revision Notes — Operating Systems

Introduction

These notes are designed for rapid revision before an exam. Each section captures the essential points — the concepts most likely to appear in questions. Read through these in 30-45 minutes to refresh your memory on all major topics.

Process Management — Key Points

• A process is a program in execution with its own address space
• Process states: New → Ready → Running → Waiting → Terminated
• PCB stores everything the OS needs to manage a process
• fork() creates a child process; exec() replaces process image
• Context switch saves/restores state — overhead includes register save, TLB flush
• Threads share code/data/files but have separate stacks and registers
• User-level threads are invisible to kernel (fast but no true parallelism)
• Kernel-level threads are scheduled by OS (true parallelism on multicore)
• IPC mechanisms: Shared memory (fast, no kernel involvement) vs Message passing (kernel mediated, safer)

CPU Scheduling — Key Points

• FCFS: Simple, non-preemptive, suffers convoy effect
• SJF: Optimal average waiting time (non-preemptive), needs burst prediction
• SRTF: Preemptive SJF, best average waiting time, causes starvation
• Priority: Can be preemptive or non-preemptive, starvation solved by aging
• Round Robin: Time quantum based, good for interactive systems, no starvation
• MLQ: Multiple queues with fixed priorities between them
• MLFQ: Processes move between queues based on behavior

Remember: Non-preemptive means process keeps CPU until it voluntarily gives up (I/O or terminates). Preemptive means OS can forcibly take CPU away.

Scheduling Criteria (what we optimize):

• Maximize: CPU utilization, throughput
• Minimize: Turnaround time, waiting time, response time

Process Synchronization — Key Points

• Race condition = outcome depends on execution order of concurrent processes
• Critical Section solution needs: Mutual Exclusion + Progress + Bounded Waiting
• Peterson's Solution works for 2 processes (not on modern hardware without memory barriers)
• Semaphore: wait() decrements (blocks if 0), signal() increments (wakes one)
• Mutex: Binary semaphore with ownership (only acquirer can release)
• Monitor: Encapsulates shared data + procedures with automatic mutual exclusion

Classic Problems:

• Producer-Consumer: Bounded buffer with full/empty semaphores + mutex
• Readers-Writers: Multiple readers OR single writer (read-write lock)
• Dining Philosophers: 5 philosophers, 5 chopsticks — solutions include resource ordering, asymmetric approach

Deadlock — Key Points

Four Necessary Conditions (ALL must hold):

1. Mutual Exclusion — resource not shareable
2. Hold and Wait — holding one resource, waiting for another
3. No Preemption — resources cannot be forcibly taken
4. Circular Wait — circular chain of processes waiting

Handling:

• Prevention: Break any one condition (e.g., order resources to prevent circular wait)
• Avoidance: Banker's Algorithm — only allocate if safe state maintained
• Detection: Check for cycles in Resource Allocation Graph (single instance) or use matrix algorithm (multiple instances)
• Recovery: Kill processes (one at a time or all), or preempt resources

Banker's Algorithm:

• Need[i] = Max[i] - Allocation[i]
• State is safe if a safe sequence exists
• On request: pretend to allocate → check safety → grant or deny

Memory Management — Key Points

• Contiguous: First Fit, Best Fit, Worst Fit — all cause external fragmentation
• Paging: Fixed-size pages eliminate external fragmentation; possible internal fragmentation on last page
• Page Table: Maps page number → frame number; stored in main memory (slow → use TLB)
• TLB: Cache for page table entries; hit = 1 memory access, miss = 2 accesses
• Multi-level paging: Reduces page table size for large address spaces
• Segmentation: Logical divisions (code, stack, heap) with different protections

Virtual Memory:

• Demand paging = load page only when accessed (lazy loading)
• Page fault = referenced page not in memory → OS loads from disk
• Dirty bit = page modified → must write back to disk on replacement
• Reference bit = page accessed → used by clock algorithm

Page Replacement Algorithms:

• FIFO: Simple, Belady's Anomaly possible
• LRU: Near-optimal, expensive to implement exactly
• Optimal: Replace page used farthest in future (theoretical benchmark)
• Clock: Approximation of LRU using reference bit (practical choice)

Thrashing: Occurs when working set > available frames. Solution: reduce multiprogramming, use working set model.

Key Formula: EAT = (1-p) × memory_time + p × page_fault_time

File Systems — Key Points

• File = named collection of related information stored on secondary storage
• Operations: Create, Open, Read, Write, Seek, Delete, Truncate
• Allocation Methods:
• Contiguous: fast access, external fragmentation, file size must be known
• Linked: no fragmentation, poor random access (must traverse links)
• Indexed: fast random access, index block overhead
• Directory Structures: Single-level → Two-level → Tree → Acyclic graph
• Free Space: Bit vector (efficient lookup), Linked list (no extra space)

I/O Systems — Key Points

• Programmed I/O: CPU polls device status (busy waiting)
• Interrupt-driven: Device interrupts CPU when ready (efficient)
• DMA: Device controller transfers data directly to memory (no CPU per byte)
• Disk Scheduling: FCFS, SSTF (greedy, starvation), SCAN (elevator), C-SCAN (uniform wait), LOOK, C-LOOK

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

Security — Key Points

• Authentication: Verify identity (what you know/have/are)
• Authorization: What you can do (ACLs, RBAC, capabilities)
• Protection Rings: Ring 0 (kernel) → Ring 3 (user) — higher ring = less privilege
• Threats: Viruses (attach to programs), Worms (self-replicate over network), Trojans (disguised malware), Rootkits (hide in kernel)

Important Distinctions to Remember

Last-Minute Exam Checklist

1. Can you draw a process state diagram?
2. Can you calculate average waiting time for each scheduling algorithm?
3. Can you trace through Banker's algorithm with a given state?
4. Can you run a page replacement algorithm on a reference string?
5. Can you identify deadlock conditions in a scenario?
6. Can you solve a Producer-Consumer problem using semaphores?
7. Can you calculate effective access time with TLB hit ratio?
8. Can you draw a Resource Allocation Graph and identify cycles?