CSS Optional — Paper-II, Section-A · P-II.III.II · One of the two highest-yield OS subtopics (with Deadlocks) — expect at least one full numerical.

1. Process vs Program

A program is a passive entity — code sitting on disk. A process is a program in execution: an active entity with its own program counter, register values, and memory (code, data, heap, stack). One program can spawn several processes (e.g. opening two browser windows).

2. Process States

graph LR
    New --> Ready
    Ready -->|"dispatch"| Running
    Running -->|"time-slice expiry / preemption"| Ready
    Running -->|"I/O or event wait"| Waiting
    Waiting -->|"I/O or event completion"| Ready
    Running --> Terminated

3. Process Control Block (PCB)

The PCB is the data structure the OS maintains per process, holding everything needed to manage and later resume it — it is the process's representation inside the OS.

Components: Process ID (PID) · Process State · Program Counter · CPU registers · CPU scheduling info (priority, queue pointers) · Memory management info (base/limit registers or page tables) · Accounting info (CPU time used) · I/O status info (allocated devices, open file list).

On a context switch, the OS saves the running process's state into its PCB and loads the next process's state from its own PCB — this save/restore cost (pure overhead, no useful work done) is why excessively frequent switching hurts throughput.

Worked Numerical (context-switch overhead, CSS 2018 Paper-I): time slice = 50 ms, context switch = 1 microsecond. How many processes can the machine service in one second?

  1. Convert to the same unit: time slice = 50 ms = 50,000 μs.
  2. Time spent per process per turn = time slice + context switch = 50,000 + 1 = 50,001 μs.
  3. Processes serviced in 1 second (= 1,000,000 μs) = 1,000,000 ÷ 50,001 ≈ 19.9996.
  4. Since a partial turn doesn't count as a fully serviced process, answer ≈ 19 processes per second (20 full turns would need 1,000,020 μs, just over the 1-second budget).

This is the concrete numeric version of the "quantum too small → context-switch overhead dominates" trade-off named in the CPU Scheduling Algorithms table below — here the overhead is tiny (1 μs vs a 50 ms slice) so it barely dents throughput, but shrinking the time slice while keeping the same 1 μs switch cost would eat into it fast.

4. CPU Scheduling Algorithms

Algorithm Rule Preemptive? Weakness
FCFS First come, first served (queue order) No Convoy effect — short jobs stuck behind one long job
SJF Shortest burst time next Can be either Needs to know burst time in advance; can starve long jobs
Priority Scheduling Highest priority runs next Can be either Starvation of low-priority jobs (fixed by <i>aging</i>)
Round Robin (RR) Fixed time quantum, cyclic queue Yes Too-large quantum → behaves like FCFS; too-small quantum → excessive context-switch overhead
Multilevel Queue Several permanent queues (e.g. foreground/background), each with its own algorithm Depends on queue Rigid — a process cannot move between queues; can starve low queues
Multilevel Feedback Queue (MLFQ) Like Multilevel Queue, but processes can be promoted/demoted between queues based on behaviour Yes Most complex to design/tune correctly

📐 Every algorithm above, worked through a full Gantt-chart numerical:

CPU Scheduling Algorithms — Deep Dive & Solved Numericals