CPU Scheduling

Key Terms

Term	Formula
Turnaround time (TAT)	Completion time − Arrival time
Waiting time (WT)	TAT − Burst time
Response time	First run time − Arrival time
Throughput	Processes completed per unit time

Algorithms

Algorithm	Preemptive?	Note
FCFS	No	Simple; suffers the convoy effect
SJF	No	Minimum average WT; needs burst estimates; can starve long jobs
SRTF	Yes	Preemptive SJF
Priority	Either	Starvation solved by aging
Round Robin	Yes	Time quantum; good response time
Multilevel (feedback) queue	Yes	Separate queues per class; processes move between them

Worked Example: Round Robin (q = 2)

Text

Process  Arrival  Burst
P1       0        5
P2       1        3
P3       2        1

Gantt chart:
| P1 | P2 | P3 | P1 | P2 | P1 |
0    2    4    5    7    8    9

Process  CT  TAT=CT-AT  WT=TAT-BT
P1       9   9          4
P2       8   7          4
P3       5   3          2
Average WT = (4 + 4 + 2) / 3 = 3.33

FCFS in C

#include <stdio.h>
int main() {
    int n = 3, bt[] = {24, 3, 3}, wt[3] = {0}, tat[3];
    float awt = 0, atat = 0;
    for (int i = 1; i < n; i++) wt[i] = wt[i - 1] + bt[i - 1];
    for (int i = 0; i < n; i++) {
        tat[i] = wt[i] + bt[i];
        awt += wt[i]; atat += tat[i];
        printf("P%d  BT=%d  WT=%d  TAT=%d\n", i + 1, bt[i], wt[i], tat[i]);
    }
    printf("Avg WT = %.2f, Avg TAT = %.2f\n", awt / n, atat / n);
}

P1 BT=24 WT=0 TAT=24 P2 BT=3 WT=24 TAT=27 P3 BT=3 WT=27 TAT=30 Avg WT = 17.00, Avg TAT = 27.00

Track your progress through the Operating System course

← Prev Next →