Operating Systems Complete Academic Curriculum & Revision Guide
Operating Systems act as the intermediary between hardware resources and user applications. This guide provides comprehensive notes on process management, CPU scheduling algorithms, synchronization primitives, deadlock handling, virtual memory architectures, and disk scheduling algorithms.
Unit-by-Unit Theoretical Revision
Unit 1: OS Structures, System Calls & Process Management
An Operating System is resource-management software providing abstraction, isolation, and hardware multiplexing.
- Dual-Mode Operation: Hardware user mode and kernel mode managed by mode bits to prevent user processes from executing privileged instructions (I/O, halt).
- Process Control Block (PCB): Kernel data structure containing Process ID (PID), Program Counter (PC), CPU registers, scheduling priority, memory management pointers, and open file lists.
- Process Lifecycle States: New → Ready → Running → Waiting (Blocked) → Terminated. Transitions triggered by scheduler dispatches, I/O requests, and timer interrupts.
- Context Switching: Saving state of the running process into its PCB and restoring the state of the scheduled process. Pure overhead handled via hardware register switching.
Unit 2: CPU Scheduling & Inter-Process Communication (IPC)
- Scheduling Metrics: Turnaround Time (Completion - Arrival), Waiting Time (Turnaround - Burst Time), Response Time, and CPU Throughput.
- Preemptive vs Non-Preemptive Scheduling:
- First-Come First-Served (FCFS): Non-preemptive, suffers from Convoy Effect where short processes wait behind long CPU-bound tasks.
- Shortest Job First (SJF / SRTF): Minimizes average waiting time. Preemptive SJF is Shortest Remaining Time First (SRTF). Vulnerable to starvation of longer bursts.
- Round Robin (RR): Preemptive algorithm using fixed time quantum
q. Ifqis too large, degrades to FCFS; if too small, high context-switch overhead. - Priority Scheduling & Aging: Aging gradually increases waiting process priorities to prevent indefinite starvation.
- IPC Models: Shared Memory (high speed, requires explicit user synchronization) vs Message Passing (pipes, message queues, sockets via kernel system calls).
Unit 3: Process Synchronization & Deadlocks
Cooperating processes sharing data require mutual exclusion to avoid race conditions.
- Critical Section Criteria: Mutual Exclusion, Progress, and Bounded Waiting.
- Peterson’s Solution: Software-based two-process synchronization using shared variables
flag[2]andturn. - Semaphores: Integer synchronization variables accessed only via atomic operations:
wait()(P) andsignal()(V). Counting semaphores control resource pools; Binary semaphores act as Mutexes. - Classical Synchronization Problems: Producer-Consumer problem (using empty, full, mutex semaphores), Readers-Writers problem, and Dining Philosophers problem.
- Deadlock Conditions (Coffman Conditions): (1) Mutual Exclusion, (2) Hold and Wait, (3) No Preemption, and (4) Circular Wait.
- Banker’s Algorithm: Deadlock avoidance algorithm calculating Safety State using matrices:
Allocation,Max,Available, andNeed = Max - Allocation.
Unit 4: Memory Management & Virtual Memory
- Logical vs Physical Address Space: Memory Management Unit (MMU) translates logical addresses generated by CPU to physical RAM addresses.
- Paging Architecture: Divides logical address space into fixed-size Pages and physical RAM into Frames. Logical address
(p, d)maps page numberpto frame base via Page Table, with offsetdunchanged. Eliminates external fragmentation; minor internal fragmentation. - Translation Lookaside Buffer (TLB): High-speed associative cache storing recent page table entries. Effective Access Time
EAT = h · (t_tlb + t_mem) + (1 - h) · (t_tlb + 2 · t_mem)wherehis hit ratio. - Page Replacement Algorithms:
- FIFO: Subject to Belady’s Anomaly (increasing frames can increase page faults).
- Optimal (OPT): Replaces page that will not be used for longest future duration. Benchmark only.
- Least Recently Used (LRU): Replaces page unused for the longest past time. Implemented via hardware counters or stack.
- Thrashing: High paging activity where OS spends more time swapping pages than executing instructions, caused by insufficient allocation of working set frames.
Unit 5: Storage Management, File Systems & Disk Scheduling
- File Allocation Methods: Contiguous allocation (fast sequential access, severe external fragmentation), Linked allocation (no external fragmentation, slow random access), and Indexed allocation (uses inode blocks, supports fast random access).
- Disk Arm Scheduling Algorithms: FCFS, SSTF (Shortest Seek Time First - starvation prone), SCAN (Elevator algorithm scanning back and forth), C-SCAN (Circular SCAN serving requests in one direction only), and LOOK / C-LOOK.
CPU & Disk Scheduling Comparison Sheet
| Algorithm | Category | Preemptive? | Starvation Risk? | Core Advantage |
|---|---|---|---|---|
| FCFS | CPU Scheduling | No | No | Simplest FIFO queue logic |
| SJF / SRTF | CPU Scheduling | Yes (SRTF) | Yes (Long jobs) | Minimizes average waiting time |
| Round Robin | CPU Scheduling | Yes | No | Guaranteed response time fairness |
| Priority + Aging | CPU Scheduling | Both | No (with Aging) | Accommodates urgent real-time tasks |
| SSTF | Disk Scheduling | N/A | Yes (Outer tracks) | Minimizes head seek time |
| C-SCAN | Disk Scheduling | N/A | No | Uniform wait distribution across platter |
High-Frequency University Exam Questions
Q1: What are the four necessary Coffman conditions for a deadlock to occur?
A deadlock can occur if and only if all four conditions hold simultaneously: (1) Mutual Exclusion: At least one resource is held in a non-shareable mode. (2) Hold and Wait: A process holds at least one resource while waiting to acquire additional resources held by other processes. (3) No Preemption: Resources cannot be forcibly seized from a process; they can only be released voluntarily. (4) Circular Wait: A closed chain of processes exists where each process holds a resource needed by the next.
Q2: Explain Belady’s Anomaly and identify which page replacement algorithm experiences it.
Belady’s Anomaly is the counter-intuitive phenomenon where increasing the number of physical page frames allocated to a process results in an increased number of page faults for a specific reference string. It occurs in FIFO (First-In-First-Out) page replacement because FIFO is not a stack-based algorithm. Algorithms like LRU and Optimal are immune to Belady's Anomaly.
Q3: Explain the working of the Translation Lookaside Buffer (TLB) and Effective Access Time (EAT).
The TLB is a high-speed associative hardware cache residing in the CPU memory management unit. When the CPU generates a virtual address, it first searches the TLB for the page number. On a TLB hit (probability h), physical frame lookup takes t_tlb + t_mem. On a TLB miss, a full page table walk is required, taking t_tlb + 2 · t_mem. The Effective Access Time is computed as EAT = h · (t_tlb + t_mem) + (1 - h) · (t_tlb + 2 · t_mem).