CPU and I/O scheduling

Scheduling goals and metrics

Definition. CPU scheduling chooses a ready process or thread to run. Common metrics include CPU utilization, throughput, turnaround time, waiting time, response time, fairness, and deadline satisfaction. Turnaround is completion minus arrival; waiting is turnaround minus CPU burst time when there is no I/O blocking.

Example. A job arriving at 2 and finishing at 9 has turnaround 7 time units.

Exam point. Response time is first service minus arrival, not completion minus arrival.

Solved examples

Example 1 — metrics. A process arrives at time 3, first runs at 5, completes at 12, and needs 4 CPU units.

1. Turnaround=12−3=9.
2. Response=5−3=2.
3. Waiting=turnaround−CPU burst=9−4=5 if no I/O blocking.
4. Metrics: TAT 9, response 2, waiting 5.

Example 2 — averages. Completion times for three processes are 8,10,15; arrivals are 0,2,5; bursts are 4,3,5.

1. Turnaround values: 8,8,10.
2. Waiting values: 8−4=4, 8−3=5, 10−5=5.
3. Average waiting=(4+5+5)/3=14/3.
4. Average turnaround=26/3; average waiting=14/3.

FCFS scheduling

Definition. First-come, first-served runs ready processes in arrival order and is nonpreemptive. It is simple and can be fair by arrival order, but a long job at the front can delay many short jobs (convoy effect).

Example. If P1 needs 10 units and P2 needs 1, P2 waits 10 units when both arrive together and P1 is first.

Exam point. Break ties using the stated arrival or process ordering.

Solved example — schedule and metrics

Processes: P1(arrival 0, burst 5), P2(1,3), P3(2,1).

1. P1 arrives first and runs 0–5.
2. P2 is next by arrival and runs 5–8.
3. P3 runs 8–9.

Process	Arrival	Burst	Start	Completion	Waiting	Turnaround
P1	0	5	0	5	0	5
P2	1	3	5	8	4	7
P3	2	1	8	9	6	7

4. Average waiting=(0+4+6)/3=10/3; average turnaround=(5+7+7)/3=19/3.
5. Gantt chart: P1 [0,5), P2 [5,8), P3 [8,9).

Shortest-job-first and shortest-remaining-time

Definition. Nonpreemptive SJF selects the ready process with smallest next CPU burst. SRTF is its preemptive version, selecting the smallest remaining burst at each decision point. If future bursts are known, SJF minimizes average waiting among nonpreemptive schedules with all jobs available; practical systems estimate bursts.

Example. With equal arrivals, bursts 2,4,7, SJF orders the jobs 2,4,7.

Exam point. Under SRTF, a newly arriving short job can preempt the running process.

Solved examples

Example 1 — nonpreemptive SJF. Use P1(0,5), P2(1,3), P3(2,1).

1. At time 0, only P1 is ready, so it runs 0–5.
2. At 5, P2 and P3 are ready; choose P3 (burst 1), running 5–6.
3. P2 runs 6–9.
4. Waiting: P1=0, P3=5−2=3, P2=6−1=5. Average=8/3.
5. Turnaround: P1=5,P3=4,P2=8; mean=17/3.

Example 2 — SRTF preemption. P1 arrives at 0 with burst 8; P2 arrives at 3 with burst 2.

1. P1 runs from 0 to 3, leaving 5.
2. P2 arrives with 2, which is less than P1's remaining 5; preempt P1.
3. P2 runs 3–5 and completes; P1 resumes 5–10.
4. Completion times: P2=5, P1=10. TAT: P2=2, P1=10.
5. Waiting: P2=0; P1=10−8=2. Mean waiting=1.

Interval	Running	Event
0–3	P1	P1 remaining 5
3–5	P2	P2 completes
5–10	P1	P1 completes

Priority scheduling and aging

Definition. Priority scheduling selects the highest-priority ready process; it may be preemptive or nonpreemptive. Priority can be numeric with either lower or higher values meaning more urgent, so the convention must be stated. Aging gradually improves a waiting process's priority to limit starvation.

Example. If smaller number means higher priority, priority 1 runs before priority 4.

Exam point. Specify tie-breaking and whether arrivals preempt the current process.

Solved examples

Example — priority with preemption. P1 arrives 0, burst 6, priority 3; P2 arrives 2, burst 2, priority 1; lower number is higher. Preempt on a higher-priority arrival.

1. P1 runs 0–2, leaving 4.
2. P2 arrives with priority 1 and preempts P1.
3. P2 runs 2–4 and completes.
4. P1 resumes 4–8.
5. P2 waiting=0; P1 waiting=2; response for P2=0.

Round-robin scheduling

Definition. Round robin gives each ready process at most quantum q before moving it to the queue tail if it remains unfinished. It is preemptive and supports responsiveness; too-large q approaches FCFS, while very small q increases context-switch overhead.

Example. If q=2 and a process needs 5 CPU units, it needs three turns absent blocking or earlier completion.

Exam point. State whether new arrivals at a quantum boundary enter before or after the preempted process is requeued.

Solved example — full queue trace

Processes: P1(0,5), P2(1,3), P3(2,1), quantum=2. New arrivals join the queue before the expired process is requeued at the same boundary.

1. P1 runs 0–2, remaining 3; queue becomes P2,P3,P1.
2. P2 runs 2–4, remaining 1; queue becomes P3,P1,P2.
3. P3 runs 4–5 and completes.
4. P1 runs 5–7, remaining 1; P2 runs 7–8 and completes.
5. P1 runs its final remaining unit from 8–9 and completes.
6. Completion: P3=5,P2=8,P1=9.

Time	Process	Remaining after slice
0–2	P1	3
2–4	P2	1
4–5	P3	0
5–7	P1	1
7–8	P2	0
8–9	P1	0

7. Turnaround P1=9,P2=7,P3=3; waiting=TAT−burst gives P1=4,P2=4,P3=2. Average waiting=10/3.

Multilevel queue and feedback queue

Definition. A multilevel queue separates ready processes into classes with fixed scheduling rules and may reserve CPU shares per class. A multilevel feedback queue allows processes to move between queues based on behavior or waiting time; interactive or short CPU bursts often receive higher priority.

Example. A process using its full quantum repeatedly may be demoted; a process waiting too long may be promoted.

Exam point. Queue policy must specify both within-queue scheduling and between-queue selection.