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