Process Management & CPU Scheduling

What is an Operating System?

Analogy: An OS is like a hotel manager. You (programs) are guests. The manager decides which room (CPU) you get, how long you can stay, and handles fights over shared facilities (printers, files, memory). Without the manager, everything would be chaos.

---

Process — A Running Program

Program = recipe written on paper (just code on disk) Process = recipe being cooked right now (program in execution with CPU, memory, etc.)

A process needs: CPU time, memory, open files, I/O devices.

Process States

                 ┌─── scheduler picks ───┐
                 ↓                       │
  New ──→  [READY] ──────────────→ [RUNNING] ──→ Terminated
                 ↑                       │
                 │   ← I/O finishes      │ I/O request / waiting for event
                 │                       ↓
                 └──────────────── [WAITING]

Transition	Cause
Ready → Running	Scheduler dispatches the process
Running → Waiting	Process requests I/O (disk, network)
Running → Ready	Preemption (timer fires, higher-priority process arrives)
Waiting → Ready	I/O completes

---

PCB — The Process's Identity Card

Each process has a Process Control Block stored in OS memory:

PCB contains:
├── Process ID (PID)
├── Current state (ready/running/waiting)
├── Program Counter (next instruction to execute)
├── CPU Registers (saved when preempted)
├── Memory info (page table, base/limit)
└── Open files, I/O status

When you switch from Process A to Process B (context switch), the OS saves A's PCB and loads B's PCB.

---

Scheduling Metrics — How Do We Measure?

Turnaround Time (TAT) = Completion Time − Arrival Time
    "Total time from arrival to completion"

Waiting Time (WT) = TAT − Burst Time
    "Time spent in ready queue doing nothing"

Response Time = First CPU time − Arrival Time
    "Time until first response (important for interactive systems)"

Throughput = processes completed / unit time
CPU Utilisation = CPU busy time / total time

---

Scheduling Algorithms

FCFS — First Come First Served

Analogy: A checkout queue — whoever arrived first gets served first. Simple but unfair when a slow person is at the front.

Convoy effect: Short processes wait behind a long one

Example: Processes arrive at time 0: P1(24ms), P2(3ms), P3(3ms)
Gantt: |──P1(24)──|─P2(3)─|─P3(3)─|
         0        24       27       30

WT:  P1=0,  P2=24, P3=27
Avg WT = (0+24+27)/3 = 17ms  ← BAD!

If order was P2,P3,P1:
Gantt: |P2(3)|P3(3)|──P1(24)──|
         0    3     6          30
Avg WT = (0+3+6)/3 = 3ms  ← MUCH BETTER!

SJF — Shortest Job First (Non-Preemptive)

Analogy: A doctor sees the patient whose appointment will take the least time next.

• Gives optimal average waiting time among all non-preemptive algorithms
• Problem: you cannot know the future burst time exactly (estimated using exponential averaging)

SRTF (Shortest Remaining Time First) = preemptive SJF: - When a new process arrives with shorter remaining burst → preempt current process - Gives optimal average waiting time overall

Burst prediction: τ_{n+1} = α × t_n + (1-α) × τ_n
(α=0.5 means equal weight to recent and historical burst)

Round Robin (RR)

Analogy: Everyone at a meeting gets exactly 2 minutes to speak, then the microphone passes to the next person.

Time quantum q: each process runs for at most q ms, then preempted

If q is very large → behaves like FCFS
If q is very small → huge context-switch overhead (bad!)
Ideal q: slightly larger than typical CPU burst

Good for: interactive/time-sharing systems (fair, good response time)

Worked Example (RR, q=2):

Processes: P1(5ms), P2(3ms), P3(2ms) — all arrive at 0

Gantt: |P1(2)|P2(2)|P3(2)|P1(2)|P2(1)|P1(1)|
        0     2     4     6     8     9    10

TAT: P1=10-0=10, P2=9-0=9, P3=6-0=6
WT:  P1=10-5=5,  P2=9-3=6, P3=6-2=4

Priority Scheduling

• Each process has a number (lower number = higher priority, OR higher number = higher priority — check convention)
• Can be preemptive or non-preemptive

Starvation problem: Low-priority process may NEVER run (high-priority ones keep arriving).

Solution — Ageing: Every N minutes, increase the priority of waiting processes by 1. Eventually even low-priority processes get to run.

MLFQ — Multilevel Feedback Queue

The best practical scheduler. Works like this:

Queue 1 (highest priority, q=2ms):   new processes start here
Queue 2 (medium priority, q=4ms):    demoted after using full quantum in Q1
Queue 3 (lowest priority, FCFS):     demoted after using full quantum in Q2

Short jobs finish quickly in Q1 (interactive response)
Long CPU-bound jobs sink to Q3 (batch-like)
Ageing: long-waiting Q3 process promoted back up

---

Gantt Chart — Draw This First!

For any GATE scheduling question: 1. List processes with arrival time and burst time 2. Draw the Gantt chart step by step (especially for SJF/SRTF) 3. Calculate completion times from chart 4. Compute TAT = completion - arrival 5. Compute WT = TAT - burst 6. Average the results

---

Quick Check

Q1. P1(AT=0, BT=8), P2(AT=1, BT=4), P3(AT=2, BT=2). SRTF. Find avg WT.

At t=0: Only P1 ready → P1 runs
At t=1: P2 arrives (remaining P1=7, P2=4). P2 shorter → preempt P1
At t=2: P3 arrives (remaining P2=3, P3=2). P3 shorter → preempt P2
At t=4: P3 done. P2 remaining=3 < P1 remaining=7 → P2 runs
At t=7: P2 done. P1 runs.
At t=13: P1 done.

Gantt: P1[0-1], P2[1-2], P3[2-4], P2[4-7], P1[7-13]
TAT: P1=13-0=13, P2=7-1=6, P3=4-2=2
WT:  P1=13-8=5,  P2=6-4=2, P3=2-2=0
Avg WT = (5+2+0)/3 = 2.33ms