‫‪CPU Scheduling‬‬

‫تقسيم وقت المعالج على العمليات‬

‫النشطة فى الـ )‪(Ready Queue‬‬
Q: Explain what is meant by CPU scheduling, and then
discuss the difference between loader and dispatcher?
Sol:
Difference between loader and dispatcher:

Ready Queue

Process need to
be executed
CPU scheduling
• The method to select a process from the ready queue to
be executed by CPU whenever the CPU becomes idle.

• Some Examples:
– First Come First Serviced (FCFS) scheduling.
– Shortest Job First (SJF) scheduling.
– Priority scheduling. FCFS
SJF
CPU Scheduling Priority
Algorithm

Process 1
Ready
Process 2
Queue CPU
Process 3 ? Dispatcher

Memory
Q: Explain the main differences between
preemptive and non preemptive scheduling?

Sol:

Preemptive scheduling:
 Allows releasing current executing process from CPU 
when another higher priority process comes and need
execution.

Non-preemptive scheduling:
 Once the CPU has been allocated to a process  The
process keeps the CPU until it release the CPU .
 Preemptive
Scheduling

CPU

Non- Preemptive
Scheduling

CPU
Q: discuss in details, what is meant by the
following parameters:

 CPU utilization.
 System throughput.
 Turnaround time.
 Waiting time.
 Response time.

Then discuss which parameter to maximize and which

one to minimize?
Sol:
CPU Utilization:
 The percentage of times while CPU is busy to the total time
( times CPU busy + times it is idle).

 Measures the benefits from CPU.

Times CPU Busy

CPU Utilization  *100
Total Time

 To maximize utilization, keep CPU as busy as possible.

 CPU utilization range from 40% (for lightly loaded systems) to

90% (for heavily loaded) (Explain why? CPU utilization can not
reach 100%, because of the context switch between active
processes).
System Throughput:
 The number of process that are completed per time unit (hour)

Turnaround time:
 The total time needed for process execution (from the time of
submission to the time of completion).

 It is the sum of process execution time and its waiting times

(to get memory, perform I/O, ….).

Waiting time:
 The sum of all periods the process spends waiting in the ready
queue.

Response time.
 It is the time from the submission of a process until the first
response is produced (the time the process takes to start
responding).
It is desirable to:

• Maximize:
– CPU utilization.
– System throughput.

• Minimize:
– Turnaround time.
– Waiting time.
– Response time.
First Come First Serviced (FCFS)

 The process that comes first will be executed first.

 Not preemptive.

Ready queue

FCFS Scheduling

CPU
Consider the following set of processes, with the length of the CPU
burst (Execution) time given in milliseconds:
Process Burst Time
The processes arrive in the order 1 P1 24
P1, P2, P3. All at time 0. 2 P2 3
3 P3 3

• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3
Waiting Time (WT) 0 24 27
Turnaround Time (TAT) 24 27 30
+
Execution
• Hence, average waiting time= (0+24+27)/3=17 milliseconds Time
Repeat the previous example, assuming that the processes arrive in
the order P2, P3, P1. All at time 0.

Process Burst Time

3 P1 24
1 P2 3
2 P3 3
• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3
Waiting Time (WT) 6 0 3
Turnaround Time (TAT) 30 3 6

• Hence, average waiting time= (6+0+3)/3=3 milliseconds

Q: Explain why? FCFS CPU scheduling algorithm
introduces a long average waiting time?

Sol:

Because:

it suffers from Convoy effect, (all other processes must wait

for the big process to execute if this big process comes first).

This results in a long waiting time for small processes, and

accordingly increases the average waiting time.
 Shortest-Job-First (SJF) scheduling

• When CPU is available, it will be assigned to the process

with the smallest CPU burst (non preemptive).
• If two processes have the same next CPU burst, FCFS is
used.

SJF Scheduling

10 5 18 7
X
18 10 7 5

CPU
Note: numbers indicates the process execution time
Consider the following set of processes, with the length of the
CPU burst time given in milliseconds:
Process Burst Time
The processes arrive in the order P1 6

P1, P2, P3, P4. All at time 0. P2 8

P3 7
P4 3

1. Using FCFS
• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3 P4
Waiting Time (WT) 0 6 14 21
Turnaround Time (TAT) 6 14 21 24

• Hence, average waiting time= (0+6+14+21)/4=10.25 milliseconds

2. Using SJF Process Burst Time
P1 6
P2 8
• Gant chart: P3 7
P4 3

• waiting times and turnaround times for each process are:

Process P1 P2 P3 P4
Waiting Time (WT) 3 16 9 0
Turnaround Time (TAT) 9 24 16 3

• Hence, average waiting time= (3+16+9+0)/4=7 milliseconds

Q: Explain why? SJF CPU scheduling algorithm introduces the minimum
average waiting time for a set of processes? Give an example.

Sol:
Because: by moving a short process before a long one, the waiting time of the
short process decreases more than it increases the waiting time of the long
process. Hence, the average waiting time decreases.

Example: assuming two processes P1 and P2

Process Burst Time

P1 30
P2 2

Using FCFS Using SJF

P1 P2 P2 P1
0 30 32 0 2 32
Waiting time(P1)=0 Waiting time(P1)=2
Waiting time(P2)=30 Waiting time(P2)=0
Average waiting time=(0+30)/2=15 Average waiting time=(0+2)/2=1
Shortest-Remaining-Time-First (SRTF)

– It is a preemptive version of the Shortest Job First .

– It allows a new process to gain the processor if its
execution time less than the remaining time of the
currently processing one.

SRTF Scheduling

2 10 7 5 3
4

CPU
Consider the following set of processes, with the length of the CPU
burst time given in milliseconds:
Process Burst Time Arrival Time
The processes arrive in the order P1 7 0
P1, P2, P3, P4. as shown in table. P2 4 2
P3 1 4
P4 4 5
1. Using SJF
• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3 P4
Waiting Time (WT) 0 6 3 7
Turnaround Time (TAT) 7 10 4 11

• Hence, average waiting time= (0+6+3+7)/4=4 milliseconds

2. Using SRTF Process Burst Time Arrival Time
P1 7 0
P2 4 2
• Gant chart: P3 1 4
P4 4 5

• waiting times and turnaround times for each process are:

Process P1 P2 P3 P4
Waiting Time (WT) 9 1 0 2
Turnaround Time (TAT) 16 5 1 6

• Hence, average waiting time= (9+1+0+2)/4=3 milliseconds

 Priority scheduling
• A priority number (integer) is associated with each
process
• The CPU is allocated to the process with the highest
priority (smallest integer). There are two types:
– Preemptive
– nonpreemptive

Priority Scheduling

10 5 18 7
X
18 10 7 5

CPU
Note: numbers indicates the process priority
Problems with Priority scheduling

• Problem  Starvation (infinite blocking)– low priority

processes may never execute
• Solution  Aging – as time progresses increase the
priority of the process

Very lowVery
priority
low process
priority process

8 28
26 30
8 5 4 2

Starvation
Aging
 Consider the following set of processes, with the length of the CPU
burst time given in milliseconds:
Process Burst Time priority

The processes arrive in the order P1 10 3

P1, P2, P3, P4, P5. All at time 0. P2 1 1

P3 2 4
P4 1 5

1. Using priority scheduling P5 5 2

• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3 P4 P5
Waiting Time (WT) 6 0 16 18 1
Turnaround Time (TAT) 16 1 18 19 6

• Hence, average waiting time= (6+0+16+18+1)/5=8.2 milliseconds

Note: preemptive scheduling ≡ non-preemptive as all processes arrives at time 0

 Ex: Consider the following set of processes, with the length
of the CPU burst time and arrival times given in milliseconds:

Process Burst Time priority Arrival Time

P1 5 3 0

P2 9 4 2

P3 4 1 3

P4 2 2 5

P5 1 5 6
P6 8 2 8

Show how to schedule those processes using:

– Preemptive priority.

– Non-preemptive priority.
 Round Robin scheduling
• Allocate the CPU for one Quantum time (also called
time slice) Q to each process in the ready queue.
• This scheme is repeated until all processes are
finished.
• A new process is added to the end of the ready
queue.

Q Q
Q Q

CPU
Consider the following set of processes, with the length of the CPU burst
time given in milliseconds:
Process Burst Time
The processes arrive in the order P1 24
P1, P2, P3. All at time 0. P2 3
use RR scheduling with Q=2 and Q=4
P3 3

RR with Q=4

• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3
Waiting Time (WT) 6 4 7
Turnaround Time (TAT) 30 7 10

• Hence, average waiting time= (6+4+7)/3=5.66 milliseconds

RR with Q=2 Process Burst Time
P1 24
P2 3
P3 3

• Gant chart:

• waiting times and turnaround times for each process are:

Process P1 P2 P3
Waiting Time (WT) 6 6 7
Turnaround Time (TAT) 30 9 10

• Hence, average waiting time= (6+6+7)/3=6.33 milliseconds

Explain why? If the quantum time decrease, this will
slow down the execution of the processes.

Sol:

• Because decreasing the quantum time will increase the

context switch (the time needed by the processor to
switch between the processes in the ready queue) .

• This will increase the time needed to finish the

execution of the active processes, hence, this slow
down the system.
Multi-level queuing scheduling
• There are two types:
– Without feedback: processes can not move between queues.
– With feedback: processes can move between queues.

1. Multi-level queuing without feedback:

• Divide ready queue into several queues.
• Each queue has specific priority and its own scheduling algorithm (FCFS, …).

High priority Queue

CPU

Low priority Queue

In multi-level Queuing Scheduling with feedback, using 3 queues with
the corresponding quantum times shown in the following figure. Show
how to execute the following processes;

Process Burst Time Arrival Time

P1 10 0
P2 26 5
P3 7 12

Queue 0

Queue 1

Queue 2
 Solution
Time Available Processes Allocated Process
0 P1(10) at Q1 P1
8 P2(26) at Q1 P2
P1(2) at Q2
16 P3(7) at Q1 P3
P1(2) at Q2
P2(18) at Q2
23 P1(2) at Q2 P1
P2(18) at Q2
25 P2(18) at Q2 P2

41 P2(2) at Q3 P2

43 Finished

Execution Sequence: P1, P2, P3, P1, P2, P2

 P1 P2 P3 P1 P2 P2
0 8 16 23 25 41 43

P1 P2 P3
WT 15 12 4
TAT 25 38 11

Average waiting time= (15+12+4)/3=10.33

Repeat the previous example assuming P3 arrives at time 22.

Process Burst Time Arrival Time

P1 10 0
P2 26 5
P3 7 22

Queue 0

Queue 1

Queue 2
In multi-level Queuing Scheduling with feedback, using 3 queues Q1,
Q2, and Q3 with the corresponding quantum times 10, 20, FCFS
respectively. Show how to execute the following processes;

Process Burst Time Arrival Time

P1 12 0
P2 25 8
P3 33 21

P4 2 30
P5 8 37
P6 40 41
Any Questions?