CPU Scheduling (Important)

There are two types of scheduling algorithms.

Non-Preemptive Scheduling

For Example: In this image above, we can see that all the processes were
executed in the order of which they appeared, and none of the processes were
interrupted by another, making this a non-preemptive, FCFS (First Come, First
Served) CPU scheduling algorithm. P2was the first process to arrive(arrived
at time = 0), and was hence executed first. Let's ignore the third column for a
moment, we'll get to that soon. Process P3arrived next(at time = 1)` and was
executed after the previous process - P2 was done executing, and so on.
Preemptive Scheduling

Preemptive scheduling includes Round Robin, Shortest Remaining Time First

(SRTF), Priority (preemptive version) etc.
For example, the CPU executing the process p1, in the middle of the execution
the CPU received a request signal from process p2. Then the OS compare the
priorities of p1 and p2, if the priority of p1 is higher than p2 then the CPU
continues the execution process p1, otherwise [priority (p1<p2)] the CPU
preempt the process p1 and assigned to process p2.

In preemptive scheduling, the CPU resource are allocated to a process for only a
limited period of time and then those resources are taken back and assigned to
another process (the next in execution). If the process was yet to complete its
execution, it is placed back in the ready state, where it will remain till it gets a
chance to execute once again.
Important CPU Scheduling Terminologies

 Arrival Time: When a process enters in the ready queue.

 Completion Time: As the name suggests, completion time is the
time at which a process completes its execution. It is not to be confused
with burst time
 Burst Time/Execution Time: It is a time required by the process to
complete execution. It is also called running time.
 Turn-Around Time: Time difference between completion time and
arrival time (Turn Around Time = Completion Time - Arrival Time).
 Waiting Time: Time difference between turnaround time and burst
time. (Waiting Time = Turn Around Time – Burst Time).
 Response Time: It is the amount of time to start responding. Time
between user’s request for the output and the start of the actual output

CPU Scheduling Criteria

Many criteria have been suggested for comparing CPU scheduling. A CPU
scheduling algorithm tries to maximize and minimize the following:
Maximize
CPU utilization: We have to keep the CPU as busy as possible. CPU utilization
is the main task in which the operating system needs to make sure that CPU
remains as busy as possible. It can range from 0 to 100 percent.

Throughput: Number of processes completed per unit time. It may range from
10 second to 1 hour depending on the specific processes.

Minimize
Waiting time: Waiting time is an amount that specific process needs to wait in
the ready queue.Time difference between turnaround time and burst time.
(Waiting Time = Turn Around Time – Burst Time).

Response time: It is the amount of time to start responding. Time between

user’s request for the output and the start of the actual output

Turnaround Time: How long it takes to execute a process. It is the amount of

time taken to execute a particular process, i.e. Time difference between
completion time and arrival time (Turn Around Time = Completion Time -
Arrival Time).

CPU Scheduler and Dispatcher

A scheduler is basically a system of software. Whenever the CPU becomes idle,

the OS must select one of the processes in the ready queue to be executed. The
selection process is carried out by the CPU scheduler. The scheduler selects
from among the processes in memory that are ready to execute and allocates the
CPU one of them

The dispatcher is the module that gives control of the CPU to the process
selected by the CPU scheduler.

.
Example – There are 4 processes in the ready queue, P1, P2, P3, P4; Their
arrival times are t0, t1, t2, t3 respectively. A First in First out (FIFO) scheduling
algorithm is used. Because P1 arrived first, the scheduler will decide it is the first
process that should be executed, and the dispatcher will remove P1 from the
ready queue and give it to the CPU. The scheduler will then determine P2 to be
the next process that should be executed, so when the dispatcher returns to the
queue for a new process, it will take P2 and give it to the CPU. This continues in
the same way for P3, and then P4.

Scheduling Algorithms
CPU scheduling deals with the problem of deciding which of the process in the
ready queue is to be allocated the CPU. The purpose of a scheduling algorithm:

 Maximum CPU utilization

 Fare allocation of CPU
 Maximum throughput
 Minimum turnaround time
 Minimum waiting time
 Minimum response time
 Avoid indefinite
postponement
 Enforce Priorities.
There are several CPU scheduling algorithms such as:

First-Come First-Serve Scheduling (FCFS)

Shortest-Job-First Scheduling (SJF)
Priority-Based Scheduling
Round-Robin Scheduling
Multilevel Queue Scheduling (MLQ)
Multilevel Feedback Queue Scheduling

First-Come First-Serve Scheduling (FCFS)

It is the simplest of all scheduling algorithms. In the "First come first serve"
scheduling algorithm, as the name suggests, the process which arrives first, gets
executed first, or we can say that the process which requests the CPU first, gets
the CPU allocated first.

In FCFS scheduling:

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

  The process which arrives first in the ready queue is firstly assigned the
CPU
 In case of a tie, process with smaller process id is executed first
 Jobs are executed on first come, first serve basis
 Easy to understand and implement
 Its implementation is based on FIFO queue
 Poor in performance as average wait time is high

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Numerical 1 :

Consider the set of processes p1, p2, p3 given in the below table, arrives for
execution in the same order, with Arrival Time 0, and given Burst Time.

Process Arrival Time Burst Time

P1 0 24
P2 0 3
P3 0 3

Calculate – Total Wait Time, Average Waiting Time, Total Turn Around
Time, Average Turn Around Time and Throughput.

Solution

Gantt chart

Process Wait Time Turn Around Time

P1 0 24
P2 24 27
P3 27 30

Total Wait Time = 0 + 24 + 27 = 51 ms

Average Waiting Time = (Total Wait Time) / (Total Number of Process)

= 51/3 =17 ms

Total Turn Around Time = 24+27+30 = 81 ms

Average Turn Around Time = (Total Turn Around Time) / (Total No.of
Process)

= 81/3 = 27 ms

Throughput = 3 jobs / 30 sec = 0.1 jobs / sec

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

  Arrival Time: When a process enters in the ready queue.
 Completion Time: As the name suggests, completion time is the
time at which a process completes its execution. It is not to be confused
with burst time
 Burst Time/Execution Time: It is a time required by the process to
complete execution. It is also called running time.
 Turn-Around Time: Time difference between completion time and
arrival time (Turn Around Time = Completion Time - Arrival Time).
 Waiting Time: Time difference between turnaround time and burst
time. (Waiting Time = Turn Around Time – Burst Time).
 Response Time: It is the amount of time to start responding. Time
between user’s request for the output and the start of the actual output

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Numerical 2 :

Consider the following set of processes that arrive at time 0, the length of
the CPU burst time given in millisecond.

Process Burst Time in

millisecond
P1 5
P2 24
P3 16
P4 10
P5 3

If the processes arrive in order p1, p2 , p3, p4 , p5 and are served in FCFS order.
Calculate average waiting time and average turn around time.

Solution

P1 P2 P3 P4 P5
0 5 29 45 55 58

Turn Around Time = Finished Time – Arrival Time

Turn Around Time for p1 = 5-0 =5

Turn Around Time for p2 = 29-0 = 29

Turn Around Time for p3 = 45-0 = 45

Turn Around Time for p4 = 55-0 = 55

Turn Around Time for p5 = 58-0 = 58

Average Turnaround Time = (5+29+45+55+58) / 5

= 187 / 5 = 37.4 ms

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Average Waiting Time

Waiting Time = Starting Time – Arrival Time

Waiting Time for p1 = 0

Waiting Time for p2 = 5 – 0 =5

Waiting Time for p3 = 29 - 0 =29

Waiting Time for p4 = 45 –0 =45

Waiting Time for p5 = 55 – 0 =55

Average Waiting Time = (0+5+29+45+55)/5

= 125/5 = 25 ms

Numerical 3 :

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Shortest Job First (SJF)

Shortest Job First scheduling is a different approach to CPU scheduling. When

the CPU is available, it is assigned to the process that has the smallest next CPU
burst. If the two processes have the same length of CPU burst then FCFS
scheduling algorithm is followed.

 Processes which have the shortest burst time are scheduled first.
 If two processes have the same bust time, then FCFS is used to break the
tie.
 Best approach to minimize waiting time.
 Easy to implement in Batch systems where required CPU time is known
in advance.
 Impossible to implement in interactive systems where required CPU time
is not known
 The processer should know in advance how much time process will take.
 Pre-emptive mode of Shortest Job First is called as Shortest Remaining
Time First (SRTF).

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Example 1

Consider the set of 5 processes whose arrival time and burst time are given
below.

Process Arrival time Burst Time

P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3

If the CPU scheduling policy is SJF non-preemptive, calculate the average

waiting time and average turnaround time.

Solution 1
Gantt chart

We know
Turn Around Time = Finished Time – Arrival Time
Waiting Time = Turn Around Time – Burst Time

Process Finished time Turn around time Waiting time

(exit time)
P1 7 7-3=4 4-1=3
P2 16 16-1=15 15-4=11
P3 9 9-4=5 5-2=3
P4 6 6-0=6 6-6=0
P5 12 12-2=10 10-3=7

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Now
Average turnaroundtime = (4+15+5+6+10)/5
= 40/ 5 = 8 unit
Average waiting time = (3+11+3+0+7)/5
= 24/5 = 4.8 unit

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Example 2

Shortest job first algorithm may either be preemptive or non-preemptive .

Consider the following example

Process Arrival Time Burst time

P1 0 8
P2 1 4
P3 2 9
P4 3 5

If the CPU scheduling policy is SJF preemptive, calculate the average waiting
time.

Calculate average waiting time if the .

Solution

0 1 5 10 17 26

P1 P2 P4 P1 P3

At t=0, only one process p1 is in the system whose burst time is 8 ms. After 1
msi.e t=1, new process p2 (burst time =4) arrives in the ready queue. Because its
burst time is less than the remaining burst time of p1 ( 7ms) so p1 is preempted
and execution of p2 is started.

Again after one msi.e a t=2, a new process p3 arrives in ready queue but its
burst time (9 ms) is larger than the remaining burst time of currently executing
process (3 ms).

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Waiting time (start time – arrival time)

Waiting time p1 = (10 - 1) = 9

P1 = (1 – 1 ) = 0
P3 = (17 – 2) = 15
P4 = (5 – 3) = 2

Average waiting time = (9 + 0 + 15 + 2 ) / 2

= 6.5 ms

Also calculate average waiting time with non-preemptive mode.

??

Solution

0 8 12 17 26

P1 P2 P3 P4

Waiting time for p1 = 0

P2 = (8 – 1) = 7
P3 = (17 – 2) = 15
P4 = (12 – 3) = 9

= (0 + 7 + 15 + 9) /4
= 7. 75 ms

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Round Robin Scheduling (RR)

The round-robin (RR) scheduling algorithm is designed especially for time-

sharing system. It is similar to FCFS but preemption is added to switch between
processes. Each process gets a small unit of CPU time (time quantum), usually
10-100 milliseconds. After this quantum has elapsed , the process is preempted
and added to the end of the ready queue. If there are n processes in the ready
queue and time quantum is q, then each process gets 1/n of the CPU time in
chunks of at least q time units at once.
No process waits more than (n-1) q time unit.

Example
Consider the following set of processes that arrive at time 0 ms.

Process Burst Time

P1 20
P2 3
P3 4

Calculate waiting time using R-R scheduling. Use quantum time of 4 ms.
Solution

0 4 7 11 15 19 23 27
P1 P2 P3 P1 P1 P1 P1

According to R-R scheduling processes are executed in FCFS order. So firstly

p1 (burst time = 20 ms) is executed but after 4 ms it is preempted and new
process p2 (burst time =3) starts its execution whose execution is completed
before the time quantum, then next p3 (burst time =4) starts its execution and
finally remaining part of p1 gets executed with time quantum of 4 ms.

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Waiting time for p1 = (11-4) = 7 ms
p2 = 4 ms
p3 = 7 ms

Average Waiting time = 7+4+7/3 = 6 ms

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

EXTRA

Example 2

Consider the set of 5 processes whose arrival time and burst time are given
below.

Process Arrival time Burst Time

P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3

If the CPU scheduling policy is SJF preemptive, calculate the average waiting
time and average turnaround time.

Solution 2
Gantt chart

0 1 3 4 6 8 11 16

P4 P2 P1 P2 P3 P5 P4

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming

Dr. Shafiqul Abidin, CSD, AMU | O S & Shell Programming