Process Scheduling

1.	Goal: What characterizes a "fair internal policy?"  Which process is given the CPU next? This is the province of 
schedulers.

2.	Schedulers

a.	long-term

b.	medium-term

c.	short-term

3.	Scheduling Considerations and Overview

a.	metrics: throughput, turnaround, response, resource use, waiting time, consistency

b.	distingishing characteristics of processes such as priority, anticipated resource need (including running 
time), running time, resources used so far, interactive/non-interactive, frequency of I/O requests, time spent 
waiting for service

4.	The Scheduling Algorithms

a.	First Come, First Served (FCFS)

b.	Shortest Job Next (SJN), Shortest Job First (SJF), Shortest Process Next (SPN)

c.	Shortest Remaining Time (SRT), Preemptive Shortest Process Next (PSPN)

d.	Highest Response Ratio Next (HRRN, HRN)

e.	Round Robin (RR) with Quantum q

f.	Multilevel Feedback Queues (MLF, MLFB) with n different priority levels each of priority Tp

5.	External Priority Methods

a.	worst service next

b.	response ratio guarantee

c.	deadline scheduling

d.	fair-share scheduling

Types of Schedulers

Introduction

This chart shows the function of each of the three types of schedulers (long-term, short-term, and medium-term) for 
each of three types of operating systems (batch, interactive, and real-time).

Chart

	batch
	interactive
	real-time

long-term
	job admission based on

characteristics and resource 
needs
	sessions and processes
normally accepted unless 
capacity reached
	processes either permanent or 
accepted at once

medium-term
	usually none-jobs remain in 
storage until done
	processes swapped when
necessary
	processes never swapped

short-term
	processes scheduled by
priority; continue until wait 
voluntarily, request service, 
or are terminated
	processes scheduled on rotat-
ing basis; continue until ser-
vice requested, time quantum 
expires, or pre-empted
	scheduling based on strict
priority with immediate pre-
emption; may time-share pro-
cesses with equal priorities


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

Multilevel Feedback (MLFB)

The variant of this class of scheduling algorithms uses three levels:

o	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.

o	processes at level 2 are scheduled round robin; the quantum is 4, and processes are allowed 2 quanta before being 
moved to level 3.

o	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)

	time	level 1	level 2	level 3		comments

	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