Week 14: Operating Systems

1. Process Management & CPU Scheduling

A process moves through states: new → ready → running → (waiting ↔ running) → terminated, tracked via a Process Control Block (PCB). Scheduling algorithms: FCFS (First-Come-First-Served — simple, but suffers the convoy effect where a long process delays everyone behind it); SJF (Shortest Job First — optimal for minimising average waiting time, but needs to know burst times in advance and can starve long processes); Round Robin (fixed time quantum per process, cycling through a ready queue — fair, good for time-sharing systems, but performance is very sensitive to quantum size); Priority scheduling (highest-priority process runs first, can starve low-priority processes without aging, which gradually raises a waiting process's priority).

Turnaround time = completion time − arrival time. Waiting time = turnaround time − burst time. These two formulas are the basis of nearly every scheduling numeric problem — get comfortable building a Gantt chart from a process table first, then reading times off it directly rather than trying to compute them algebraically from scratch each time.

Process   Burst Time
  P1          6
  P2          8
  P3          7
  P4          3

SJF execution order (shortest burst first): P4, P1, P3, P2

Gantt chart:  | P4 | P1  | P3   | P2   |
              0    3    9     16    24

Completion:  P4=3   P1=9   P3=16   P2=24
Turnaround:  P4=3   P1=9   P3=16   P2=24   (arrival=0, so turnaround=completion)
Waiting:     P4=0   P1=3   P3=9    P2=16

Average waiting time = (0+3+9+16)/4 = 7

2. Process Synchronization & Deadlocks

A race condition occurs when multiple processes/threads access shared data concurrently and the outcome depends on timing. A critical section is the code segment accessing shared data that must run with mutual exclusion. Semaphores (a counter with atomic wait/signal, or P/V, operations) and mutex locks are the standard synchronization primitives; the classic Producer-Consumer, Readers-Writers and Dining Philosophers problems are the standard scenarios used to test whether you understand how to apply them correctly.

Deadlock requires all four Coffman conditions simultaneously: mutual exclusion (resources aren't shareable), hold and wait (a process holds a resource while waiting for another), no preemption (resources can't be forcibly taken away), and circular wait (a cycle of processes each waiting on the next). Breaking any single one of these four prevents deadlock — which is exactly the principle behind deadlock prevention strategies. Deadlock avoidance takes a different approach: the Banker's Algorithm checks, before granting a resource request, whether the resulting state is still "safe" (a sequence exists in which all processes can eventually finish), refusing requests that would lead to an unsafe state.

3. Memory Management & File Systems

Paging divides physical memory into fixed-size frames and logical memory into same-sized pages, eliminating external fragmentation (but allowing internal fragmentation within the last page). Segmentation divides a program into logical, variable-sized units (code, stack, heap) matching how a programmer thinks about the program, but reintroduces external fragmentation. Address translation uses a page table (with a TLB, translation look-aside buffer, caching recent translations for speed).

When physical memory is full and a new page must be brought in, a page-replacement algorithm decides what to evict: FIFO (evict the oldest-loaded page — simple, but can suffer Belady's anomaly, where adding more frames actually increases page faults), LRU (evict the Least Recently Used page — a strong practical approximation of the unimplementable optimal algorithm, which would evict whichever page is used furthest in the future), and Optimal (the theoretical best, used as a benchmark, not implementable since it requires future knowledge).

4. Hands-on Exercise

5. Exam-Style Practice (UGC NET Pattern)

Five NTA-pattern questions on scheduling, deadlock and memory management.