CPU Scheduling

Ahmad Yoosofan

https://yoosofan.github.io

University of Kashan

https://github.com/yoosofan/slide/blob/main/os/cpu.rst

CPU Burst / Service Time

cpu utilization by multiprogramming
cpu - I/O cycle of a process
cpu : burst time, service time
I/O : or other blocking events like memory request

CPU Schedular

Short Term Schedular

ready queue
Dispatcher

Time Unit Concept

Millisecond
Nanosecond
?

Scheduling type

nonpreemptive
preemptive

Processes Table

process	service(Burst) time
$P_0$	3
$P_1$	2
$P_2$	1
$P_3$	2

process	service time	arrival time
$P_0$	3	0
$P_1$	2	0
$P_2$	1	3
$P_3$	2	5

prs	st
$P_0$	3
$P_1$	2
$P_2$	1
$P_3$	2

pcs	st	at
$P_0$	3	0
$P_1$	2	0
$P_2$	1	3
$P_3$	2	5

First-Come, First-Served (FCFS)

process	service time	arrival time
$P_0$	2	0
$P_1$	1	0
$P_2$	2	3
$P_3$	1	4

P0		P1		P2		P3
0		2		3		5		6

Gantt Chart
t = 0: ready queue(q) = [$P_0$, $P_1$]
t = 2: q = [$P_1$]
t = 3: q = [$P_2$]
t = 5: q = [$P_3$]

Average Waiting Time

process	service time	arrival time
$P_0$	2	0
$P_1$	1	0
$P_2$	2	3
$P_3$	1	4

P0		P1		P2		P3
0		2		3		5		6

$P_0$ waiting time: 0
$P_1$ waiting time: 2
$P_2$ waiting time: (3-3) = 0
$P_3$ waiting time: (5-4) = 1

Average Waiting Time
$\frac{0 + 2 + 0 + 1}{4} = \frac{3}{4} = 0.75$

FCFS - Convoy effect

process	service time	arrival time
$P_0$	4	0
$P_1$	6	0
$P_2$	1	3
$P_3$	3	4

P0		P1		P2		P3
0		4		10		11		14

Average Waiting Time
$\frac{0 + (4-0) + (10-3) + (11-4)}{4} = \frac{18}{4} = 4\frac{2}{4} = 4.5$

Rearange

P0		P2		P3		P1
0		4		5		8		14

Average Waiting Time
$\frac{0 + (4-3) + (5-4) + 8}{4} = \frac{10}{4} = 2\frac{2}{4} = 2.5$

Average Waiting Time 1: 4.5
Average Waiting Time 2: 2.5

SJF or SPN $\frac{1}{s}$

process	service time	arrival time
$P_0$	6	0
$P_1$	4	0
$P_2$	1	3
$P_3$	3	4

Shortest Job First (SJF)
Shortest Process Next (SPN)

P1		P2		P3		P0
0		4		5		8		14

Average Waiting Time
$\frac{0 + (4-3) + (5-4) + 8}{4} = \frac{10}{4} = 2\frac{2}{4} = 2.5$

Starvation
Nonpreemptive
formula : 1 / (service time)

Shortest Remaining Time(SRT), preemptive SJF

process	service time	arrival time
$P_0$	4	0
$P_1$	6	0
$P_2$	1	1
$P_3$	3	2

P0		P1		P2		P3
0		4		10		11		14

Average Waiting Time
$\frac{0 + (4-0) + (10-1) + (11-2)}{4} = \frac{22}{4} = 5\frac{2}{4} = 5.5$

P0		P2		P0		P3		P1
0		1		2		5		8		14

Average Waiting Time
$\frac{(0+(2-1)) + (8-0) + (1-1) + (5-2)}{4} = \frac{12}{4} = 3$

Hieghest Response Ratio Rate Next (HRRN) $\frac{w + s}{s}$

process	service time	arrival time
$p_0$	5	0
$p_1$	3	1
$p_2$	4	2
$p_3$	2	6

t = 0

$P_0$
0		5

queue : P1, P2, P3

t = 5

$P_0$		$P_1$
0		5		8

queue : P2 P3

P2: $\frac{( 8 - 2 ) + 4}{4} = \frac{6+4}{4} = \frac{10}{4}$
P3: $\frac{( 8 - 6 ) + 2}{2} = \frac{2+2}{2} = \frac{4}{2} = \frac{8}{4}$

t = 8

$P_0$		$P_1$		$P_2$
0		5		8		12

queue : P3

HRRN

$P_0$		$P_1$		$P_2$		$P_3$
0		5		8		12		14

SJF

$P_0$		$P_1$		$P_3$		$P_2$
0		5		8		10		14

Average Waiting Time

HRRN: $\frac{0+(5-1)+(8-2)+(12-6)}{4}=\frac{16}{4}=4$

SJF: $\frac{0+(5-1)+(8-6)+(10-2)}{4}=\frac{14}{4}=\frac{7}{2}=3.5$

Estimating Service Time(I)

$\begin{align} \tau_n = \frac{t_0 + t_1 + t_2 + ... + t_{n - 1}}{n}\end{align}$
$\begin{align} n * \tau_n = t_0 + t_1 + t_2 + ... + t_{n - 1}\end{align}$
$\begin{align} \tau_{n+1} = \frac{t_0 + t_1 + t_2 + ... + t_{n - 1} + t_n}{n+1}\end{align}$
$\begin{align} = \frac{t_0 + t_1 + t_2 + ... + t_{n - 1} }{n+1} + \frac{t_n}{n+1}\end{align}$
$\begin{align}\tau_{n+1} = \frac{n * \tau_n}{n + 1} + \frac{t_n}{n+1}\end{align}$
$\begin{align}\tau_{n+1} = \frac{n}{n + 1} * \tau_n + \frac{1}{n+1} * t_n\end{align}$

Estimating Service Time(II)

$\begin{align}\tau_{n+1} = \frac{n}{n + 1} * \tau_n + \frac{1}{n+1} * t_n\end{align}$
$\begin{align}\tau_{n+1} = \frac{n + 1 - 1}{n + 1} * \tau_n + \frac{1}{n+1} * t_n\end{align}$
$\begin{align}\tau_{n+1} = ( \frac{n + 1}{n + 1} - \frac{1}{n + 1} ) * \tau_n + \frac{1}{n+1} * t_n\end{align}$
$\begin{align}\tau_{n+1} = ( 1 - \frac{1}{n + 1} ) * \tau_n + \frac{1}{n+1} * t_n\end{align}$
$\begin{align}\alpha = \frac{1}{n+1}\end{align}$ $\begin{align}\tau_{n+1} = ( 1 - \alpha ) * \tau_n + \alpha * t_n\end{align}$

Estimating Service Time(III)

$\begin{align}\alpha = \frac{1}{n+1}\ , \ \tau_{n+1} = ( 1 - \alpha ) * \tau_n + \alpha * t_n\end{align}$
$\begin{align}t_n = actual\ length\ of\ n^{th}\ service\ time\end{align}$
$\begin{align}\tau_{n+1} = predicted\ value\ for\ the\ next\ service\ time\end{align}$
$\begin{align}0 ≼ \alpha ≼ 1 \ , \ \tau_{n+1} = ( 1 - \alpha ) * \tau_n + \alpha * t_n\end{align}$
$\begin{align}\alpha → 0\end{align}$

Round Robin (RR , quantum) I

process	service time	arrival time
$p_0$	5	0
$p_1$	3	1
$p_2$	4	2
$p_3$	2	6

time quantum or q = 2 ,

Queue (Q): Empty

t = 0 , Q: P0

$P_0$
0		2

t=2, Q: P1(3), P2(4), P0(3)

$P_0$		$P_1$
0		2		4

t=4, Q:P2(4), P0(3), P1(1)

$P_0$		$P_1$		$P_2$
0		2		4		6

t=6, Q: P0(3), P1(1), P3(2), P2(2)

$P_0$		$P_1$		$P_2$		$P_0$
0		2		4		6		8

t=8, Q: P1(1), P3(2), P2(2), P0(1)

$P_0$		$P_1$		$P_2$		$P_0$		$P_1$
0		2		4		6		8		9

t=9, Q: P3(2), P2(2), P0(1)

$P_0$		$P_1$		$P_2$		$P_0$		$P_1$		$P_3$
0		2		4		6		8		9		11

t=11, Q: P2(2), P0(1)

$P_0$		$P_1$		$P_2$		$P_0$		$P_1$		$p_3$		$p_2$
0		2		4		6		8		9		11		13

t=13, Q: P0(1)

$P_0$		$P_1$		$P_2$		$P_0$		$P_1$		$p_3$		$p_2$		$p_0$
0		2		4		6		8		9		11		13		14

Round Robin (RR) II

process	service time	arrival time
$p_0$	5	0
$p_1$	3	1
$p_2$	4	2
$p_3$	2	6

t=11, Q: P2(2), P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
0
2
4
6
8
9
11
13

t=13, Q: P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
$p_0$
0
2
4
6
8
9
11
13
14

Average Waiting Time

$\frac{[0+(6-2)+(13-8)]+[(2-1)+(8-4)]+[(4-2)+(11-6)]+[9-6]}{4}$

= $\frac{9+5+7+3}{4} = \frac{24}{4} = 6$

Priority

Internal
External

smallest integer ≡ highest priority
largest integer ≡ highest priority

preemptive (absolute)
non-preemptive (relative)

Starvation
- Aging

nice [-20 , 19]

root@computer-name:~# nice --5 geany
root@computer-name:~# ps -l
root@computer-name:~# top
user@computer-name:~# nice -n 8 geany

renice

user@computer-name:~# renice 10 -p 19862
user@computer-name:~# renice -n 15 -p 19862

Relative Priority

process	service time	arrival time	Priority
P0	2	0	4
P1	3	1	3
P2	1	2	3
P3	2	5	1

t=0, Q: P0(2,4)

P0
0		2

t=2, Q: P1(3,3), P2(1,3)

P0		P1
0		2		5

t=5, Q: P2(1,3), P3(2,1)

P0		P1		P3
0		2		5		7

t=6, Q: P2(1,3)

P0		P1		P3		P2
0		2		5		7		8

Absolute Priority

process	service time	arrival time	Priority
P0	2	0	4
P1	3	1	3
P2	1	2	3
P3	2	5	1

t=0, Q: P0(2,4)

P0
0		2

t=1, Q: P1(3,3), P0(1,4)

P0		P1
0		1		4

t=4, Q: P0(1,4), P2(1,3)

P0		P1		P2
0		1		4		5

t=5, Q: P0(1,4), P3(2,1)

P0		P1		P2		P3
0		1		4		5		7

t=7, Q: P0(1,4)

P0		P1		P2		P3		P0
0		1		4		5		7		8

Priority Round Robin

process	service time	arrival time	Priority
P0	2	0	4
P1	3	1	3
P2	1	2	2
P3	2	5	1

t=0, Q: P0(2)

P0
0		1

t=1, Q: P0(1,4), P1(3,3)

P0		P1
0		1		2

t=2, Q: P0(1,4), P1(2,3), P2(1,2)

P0		P1		P2
0		1		2		3

t=3, Q: P0(1,4), P1(2,3)

P0		P1		P2		P2
0		1		2		3		5

t=5, Q: P0(1,4), P3(2,1)

P0		P1		P2		P2		P3
0		1		2		3		5		7

t=7, Q: P0(1,4)

P0		P1		P2		P2		P3		P0
0		1		2		3		5		7		8

Multilevel Queue

process	service time	arrival time
$p_0$	5	0
$p_1$	3	1
$p_2$	4	2
$p_3$	2	6

t=11, Q: P2(2), P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
0
2
4
6
8
9
11
13

t=13, Q: P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
$p_0$
0
2
4
6
8
9
11
13
14

Average Waiting Time

$\frac{(0+(6-2)+(13-8))+((2-1)+(8-4))+((4-2)+(11-6))+(9-6)}{4}$

= $\frac{9+5+7+3}{4} = \frac{24}{4} = 6$

Multilevel Queue Feedback (MLQF)

process	service time	arrival time
$P_0$	5	0
$P_1$	3	1
$P_2$	4	2
$P_3$	2	6

t=11, Q: P2(2), P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
0
2
4
6
8
9
11
13

t=13, Q: P0(1)

$P_0$
$P_1$
$P_2$
$P_0$
$P_1$
$p_3$
$p_2$
$p_0$
0
2
4
6
8
9
11
13
14

Average Waiting Time

$\frac{(0+(6-2)+(13-8))+((2-1)+(8-4))+((4-2)+(11-6))+(9-6)}{4}$

= $\frac{9+5+7+3}{4} = \frac{24}{4} = 6$

Scheduling Criteria

CPU utilization : keep the CPU as busy as possible
Throughput : number of processes that complete their execution per time unit
Turnaround time : amount of time to execute a particular process
Waiting time : amount of time a process has been waiting in the ready queue
Response time : amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

Optimization Criteria

Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time

END

process	service(Burst) time
\(P_0\)	3
\(P_1\)	2
\(P_2\)	1
\(P_3\)	2

process	service time	arrival time
\(P_0\)	3	0
\(P_1\)	2	0
\(P_2\)	1	3
\(P_3\)	2	5

prs	st
\(P_0\)	3
\(P_1\)	2
\(P_2\)	1
\(P_3\)	2

pcs	st	at
\(P_0\)	3	0
\(P_1\)	2	0
\(P_2\)	1	3
\(P_3\)	2	5

process	service time	arrival time
\(P_0\)	2	0
\(P_1\)	1	0
\(P_2\)	2	3
\(P_3\)	1	4

CPU Scheduling

Ahmad Yoosofan

CPU Burst / Service Time

CPU Schedular

Short Term Schedular

Time Unit Concept

Scheduling type

Processes Table

First-Come, First-Served (FCFS)

Average Waiting Time

FCFS - Convoy effect

SJF or SPN \(\frac{1}{s}\)

Shortest Remaining Time(SRT), preemptive SJF

Hieghest Response Ratio Rate Next (HRRN) \(\frac{w + s}{s}\)

Estimating Service Time(I)

Estimating Service Time(II)

Estimating Service Time(III)

Round Robin (RR , quantum) I

Round Robin (RR) II

Priority

Relative Priority

Absolute Priority

Priority Round Robin

Multilevel Queue

Multilevel Queue Feedback (MLQF)

Scheduling Criteria

Optimization Criteria