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 name arrival time service time start time finish time turnaround time waiting time response time
A010010100 1.0
B12910393891.3
C233942403713.3
D37424946396.6
E412496157454.8
mean    38265.4

Shortest Job Next (SJN)

This policy services the shortest job next.
job name arrival time service time start time finish time turnaround time waiting time response time
A0100101001.0
B129326160312.1
C2310131183.7
D37132017102.4
E412203228162.3
mean    25132.3

Pre-emptive Shortest Job Next (PSJN)

This policy services the shortest job next, pre-emptively. 8
job name arrival time service time start time finish time turnaround time waiting time response time
A01002pre-empted by C
122020102.0
B129326160312.1
C2325301.0
D37512921.3
E412203228162.3
mean    24121.7

Highest Response Ratio Next (HRN)

This policy services the job with the highest response ratio next.
job name arrival time service time start time finish time turnaround time waiting time response time
A0100101001.0
B129326160312.1
C2310131183.7
D37132017102.4
E412203228162.3
mean    25132.3

Round Robin (RR)

This policy services jobs for a fixed quantum (here, 5). >
job name arrival time service time start time finish time turnaround time waiting time response time
A01005end of quantum; B starts
5232828182.8
B129510end of quantum; C starts
242833end of quantum; D starts
194045end of quantum; E starts
14476160312.1
C2310131183.7
D371318end of quantum; E starts
2333532254.6
E4121823end of quantum; A starts
73540end of quantum; B starts
2454743313.5
mean    35233.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.
(at end of interval)
new queue
(at end of interval)
0-1AA(2)B(0)
1-2AA(4)B(3), C(0)
2-3AB(6), A(6)C(3), D(0)
3-4BA(8), B(8)C(6), D(3), E(0)
4-5AB(10),A(10)C(9), D(6), E(3)
5-6BA(12), C(12), B(12)D(9), E(6)
6-7AC(14), B(14), A(14)D(12), E(9)
7-8CB(16), A(16), C(16)D(15), E(12)
8-9BA(18), C(18), D(18), B(18)E(15)
9-10AC(20), D(20), B(20), A(20)E(18)
10-11CD(22), B(22), A(22), C(22)E(21)
11-12DB(24), A(24), C(24), E(24), D(24)
... round robin from here on ...
The relevant numbers (ignoring start and finish time) are:

job name arrival time service time start time finish time turnaround time waiting time response time
A010......27172.7
B129......60312.1
C23......15125.0
D37......33264.7
E412......44323.7
mean    35.823.63.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.
0A----A(10) arrives, runs
1AB----B(29) arrives, A continues quantum
2BCA--C(3) arrives, A's quantum expires (8), moves to level 2, B runs
3BCDA--D(7) arrives, B continues quantum
4CDEAB--E(12) arrives, B's quantum expires (27), moves down, C runs
6DEABC--C's quantum expires (1), moves down, D runs
8EABCD--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)
13FABCDE--F(1) arrives, A's quantum continues
14FABCDE--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--DEBB's quantum expires (19), moves down, D runs
37--EBD finishes, E runs

41----BEE's quantum expires (2), moves down, B runs from level 3 (since there is nothing in higher levels)
50G--BEG arrives(11), B continues to run
60G--EB finishes, G runs (since it is in the highest level)
62--G G's quantum expires (9), moves down, G runs from level 2
66--GEG's quantum expires (5), G runs
70----EGG's quantum expires (1), moves down, E runs
72----GE finishes, G runs
73------G finishes
The relevant numbers (ignoring start and finish time) are:
job name arrival time service time start time finish time turnaround time waiting time response time
A01002preempted by B
81014preempted by F
4283232223.2
B12924preempted by C
271519preempted by C
233236preempted by D
19416059302.0
C2346preempted by D
1192018156.0
D3768preempted by E

52024preempted by E
1363734274.9
E412810preempted by A
102428preempted by A
63741preempted by B
2707268565.7
F1311415212.0
G50116070preempted by E
1727323122.1
mean    33.723.33.7

Send email to cs150@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562