Job Scheduling Algorithms
Introduction
This handout shows how the various job scheduling algorithms work.
First Come, First Serve (FCFS)
This policy services jobs in the order they arrive.
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 10 10 0 1.0
B 1 29 10 39 38 9 1.3
C 2 3 39 42 40 37 13.3
D 3 7 42 49 46 39 6.6
E 4 12 49 61 57 45 4.8
mean 38 26 5.4
Shortest Job Next (SJN)
This policy services the shortest job next.
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 10 10 0 1.0
B 1 29 32 61 60 31 2.1
C 2 3 10 13 11 8 3.7
D 3 7 13 20 17 10 2.4
E 4 12 20 32 28 16 2.3
mean 25 13 2.3
Pre-emptive Shortest Job Next (PSJN)
This policy services the shortest job next, pre-emptively.
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 2 pre-empted by C
8 12 20 20 10 2.0
B 1 29 32 61 60 31 2.1
C 2 3 2 5 3 0 1.0
D 3 7 5 12 9 2 1.3
E 4 12 20 32 28 16 2.3
mean 24 12 1.7
Highest Response Ratio Next (HRN)
This policy services the job with the highest response ratio next.
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 10 10 0 1.0
B 1 29 32 61 60 31 2.1
C 2 3 10 13 11 8 3.7
D 3 7 13 20 17 10 2.4
E 4 12 20 32 28 16 2.3
mean 25 13 2.3
Round Robin (RR)
This policy services jobs for a fixed quantum (here, 5).
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 5 end of quantum; B starts
5 23 28 28 18 2.8
B 1 29 5 10 end of quantum; C starts
24 28 33 end of quantum; D starts
19 40 45 end of quantum; E starts
14 47 61 60 31 2.1
C 2 3 10 13 11 8 3.7
D 3 7 13 18 end of quantum; E starts
2 33 35 32 25 4.6
E 4 12 18 23 end of quantum; A starts
7 35 40 end of quantum; B starts
2 45 47 43 31 3.5
mean 35 23 3.3
Selfish Round Robin (SRR)
This policy services jobs for a fixed quantum (here, 1). The priority of new processes increases at a rate of 3 per
quantum, of accepted processes at a rate of 2 per quantum. Note that new process promotions from the new queue to
the ready queue precede quanta expirations.
time job ready queue new queue
running (at end of interval) (at end of interval)
0-1 A A(2) B(0)
1-2 A A(4) B(3), C(0)
2-3 A B(6), A(6) C(3), D(0)
3-4 B A(8), B(8) C(6), D(3), E(0)
4-5 A B(10),A(10) C(9), D(6), E(3)
5-6 B A(12), C(12), B(12) D(9), E(6)
6-7 A C(14), B(14), A(14) D(12), E(9)
7-8 C B(16), A(16), C(16) D(15), E(12)
8-9 B A(18), C(18), D(18), B(18) E(15)
9-10 A C(20), D(20), B(20), A(20) E(18)
10-11 C D(22), B(22), A(22), C(22) E(21)
11-12 D B(24), A(24), C(24), E(24), D(24)
- round robin from here on -
The relevant numbers (ignoring start and finish time) are:
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 - - 27 17 2.7
B 1 29 - - 60 31 2.1
C 2 3 - - 15 12 5.0
D 3 7 - - 33 26 4.7
E 4 12 - - 44 32 3.7
mean 35.8 23.6 3.6
Multilevel Feedback (MLFB)
The variant of this class of scheduling algorithms uses three levels:
Ö processes at level 1 are scheduled round robin; the relevant quantum is 2, and when a quantum expires the job is
moved to level 2.
Ö processes at level 2 are scheduled round robin; the quantum is 4, and processes are allowed 2 quanta before being
moved to level 3.
Ö processes at level 3 are serviced first come first serve.
The jobs A, B, C, D, and E have been augmented by F, a 1-second job arriving at time 13, and G, an 11-second job
arriving at time 50. These are to demonstrate that quanta are usually not interrupted.
In what follows, the number in parentheses in the comment field is the remaining service time for the job.
time level 1 level 2 level 3 comments
0 A - - A(10) arrives, runs
1 AB - - B(29) arrives, A continues quantum
2 BC A - C(3) arrives, A's quantum expires (8), moves to level 2, B runs
3 BCD A - D(7) arrives, B continues quantum
4 CDE AB - E(12) arrives, B's quantum expires (27), moves down, C runs
6 DE ABC - C's quantum expires (1), moves down, D runs
8 E ABCD - D's quantum expires (5), moves down, E runs
10 - ABCDE - E's quantum expires (10), moves down, A runs from level 2 (level 1 is
empty)
13 F ABCDE - F(1) arrives, A's quantum continues
14 F ABCDE - A's quantum expires (4), F runs (at level 1)
15 - ABCDE - F finishes, B runs from level 2 (level 1 is empty)
19 - ABCDE - B's quantum expires (23), C runs
20 - ABDE - C finishes, D runs
24 - ABDE - D's quantum expires (1), E runs
28 - ABDE - E's quantum expires (6), A runs
32 - BDE - A finishes, B runs
36 - DE B B's quantum expires (19), moves down, D runs
37 - E B D finishes, E runs
41 - - BE E's quantum expires (2), moves down, B runs from level 3 (since there is
nothing in higher levels)
50 G - BE G arrives(11), B continues to run
60 G - E B finishes, G runs (since it is in the highest level)
62 - G E G's quantum expires (9), moves down, G runs from level 2
66 - G E G's quantum expires (5), G runs
70 - - EG G's quantum expires (1), moves down, E runs
72 - - G E finishes, G runs
73 - - - G finishes
The relevant numbers (ignoring start and finish time) are:
job arrival service start finish turnaround waiting response
name time time time time time time ratio
A 0 10 0 2 preempted by B
8 10 14 preempted by F
4 28 32 32 22 3.2
B 1 29 2 4 preempted by C
27 15 19 preempted by C
23 32 36 preempted by D
19 41 60 59 30 2.0
C 2 3 4 6 preempted by D
1 19 20 18 15 6.0
D 3 7 6 8 preempted by E
5 20 24 preempted by E
1 36 37 34 27 4.9
E 4 12 8 10 preempted by A
10 24 28 preempted by A
6 37 41 preempted by B
2 70 72 68 56 5.7
F 13 1 14 15 2 1 2.0
G 50 11 60 70 preempted by E
1 72 73 23 12 2.1
mean 33.7 23.3 3.7