ECS 150 Winter 2000: Process Scheduling

Process Scheduling

Goal: What characterizes a "fair internal policy?" Which process is given the CPU next? This is the province of schedulers.
Schedulers
1. long-term
2. medium-term
3. short-term
Scheduling Considerations and Overview
1. metrics: throughput, turnaround, response, resource use, waiting time, consistency
2. 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
The Scheduling Algorithms
1. First Come, First Served (FCFS)
2. Shortest Job Next (SJN), Shortest Job First (SJF), Shortest Process Next (SPN)
3. Shortest Remaining Time (SRT), Preemptive Shortest Process Next (PSPN)
4. Highest Response Ratio Next (HRRN, HRN)
5. Round Robin (RR) with Quantum q
6. Multilevel Feedback Queues (MLF, MLFB) with n different priority levels each of priority T_p
External Priority Methods
1. worst service next
2. response ratio guarantee
3. deadline scheduling
4. 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 rotating basis; continue until service requested, time quantum expires, or pre-empted	scheduling based on strict priority with immediate pre-emption; may time-share processes 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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response 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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response 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 name	arrival time	service time	start time	finish time	turnaround time	waiting time	response 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

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

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

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 1/26/2000