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
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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
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. 8

job name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
A	0	10	0	2	pre-empted by C
			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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
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 running	ready queue (at end of interval)	new queue (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 name arrival time service time start time finish time turnaround time waiting time response time

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

job name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
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		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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response time
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

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

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

Page last modified on 5/13/99