Chapter 3: CPU Scheduling

Compiled by: Kassawmar M. December, 1

2023
 Outline
 Introduction to scheduling

 When to schedule

 Scheduling Criteria

 Types of scheduling

 Schedulers and its type

 Categories of scheduling algorithms

 Scheduling algorithm Goals

 Scheduling policies in different environments

 Thread Scheduling
2
 Introduction to CPU scheduling
• To make your day more logical and efficient, you work on a
schedule.
• An OS operates in a similar manner by scheduling tasks, improving
efficiency, reducing delays and wait times, and managing CPU
resources better.
• This activity is called process scheduling.
• CPU scheduling is the basis of multi-programmed OS.
• Multi-programmed computer
– Multiple processes running concurrently.
– Processes compete for the CPU.
– If there is a single CPU, a choice has to be made which process to
run next.

3
 Cont..
 The aim of process scheduling is to assign processes to
be executed by the processor or processors over time in
a way that meets the system objectives.
 Fundamentally, scheduling is a matter of managing
queues to minimize delays and to optimize
performance.
 Scheduling in batch systems was simple.
 But in time sharing- algorithms are becoming more and
more complex.

4
 When to schedule
When to Schedule?
 A new process is created
– Since the parent and child processes are in ready state, decision needs
to be made whether to run the parent process or the child process.
 A process exits
– That process can no longer run (since it no longer exists), so some other
process must be chosen from the set of ready processes.
 A process blocks
– when a process blocks on I/O, on a semaphore, or for some other
reason, another process has to be selected to run.
– The reason for blocking may play a role in the selection of the next
process, but the scheduler doesn’t have enough information.
 I/O interrupt
– Scheduler decides to run the newly ready process, continue the
interrupted process or run another process in the ready queue.
5
 Scheduling Criteria
• CPU utilization – keep the CPU as busy as possible.
• Throughput – the 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).

6
 Types of scheduling
1. Non-preemptive Scheduling
• A scheduling algorithm picks a process to run and then just lets it
run until it terminates or voluntary releases the CPU.

• Even if it runs for hours, it will not be forcibly suspended.

• Once the processor starts its execution, it must finish it before
executing the other. It can’t be paused in the middle.
• CPU utilization is less efficient compared to preemptive
Scheduling.
• Waiting and response time of the non-preemptive Scheduling
method is higher.
Examples: First Come First Serve
Shortest job first
7
Priority Scheduling
 Cont…
2. Preemptive Scheduling
• A CPU allocated to the process for limited time.

• Picks a process and lets it run for a maximum of some fixed

time.
• A processor can be preempted to execute the different
processes in the middle of any current process execution.
• CPU utilization is more efficient compared to Non-
Preemptive Scheduling.
• Waiting and response time of preemptive Scheduling is less.

Examples: – Round Robin

– Shortest Remaining Time Next
8
– Priority Scheduling (preemptive)
Cont..

9
 Schedulers
 Scheduler
• Part of operating system which selects the process
• Uses scheduling algorithm.
 Their main task is to select the jobs to be submitted into
the system and to decide which process to run.

 Schedulers are three types

1. Long Term Scheduler

2. Short Term Scheduler

3. Medium Term Scheduler

10
 Long Term Scheduler
 It is also called job scheduler.
 Long term scheduler determines which programs are
admitted to the system for processing.
 It selects processes from the pool of jobs and loads them
into main memory for execution.
• Occurs infrequently, typically when a new process is
created or when a process in the ready queue exits.
• Process loads into the main memory for CPU
scheduling.
• [ Job Pool/new] ---> [ Long-Term Scheduler ] ---> [ Ready
Queue ]
11
 Short Term Scheduler
 It is also called CPU scheduler.
 CPU scheduler selects processes from the ready queue and
allocates CPU time to them for execution.
 The method of selecting a process from ready queue is depending
on the CPU scheduling algorithm.
 Main objective is increasing system performance in accordance
with the chosen set of criteria.
 A dispatcher, is module, it connect the CPU to the process selected
by the short term scheduler.
 The main function of the dispatcher is switching the CPU from
one process to another process.
• Runs frequently, making decisions on which process to execute
next on the CPU.
• [ Ready Queue ] ---> [ Short-Term Scheduler ] ---> [ CPU ] 12
 Medium Term Scheduler
 If a process request an I/O in the middle of the execution,
then the process removed from the main memory and loaded
into waiting queue.

 When the I/O operation completed the job moved from

waiting queue to ready queue.

 This two operation performed by the medium term scheduler.

 Medium term scheduling is part of the swapping.

• [ Main Memory ] <--> [ Medium-Term Scheduler ] <--> [
Secondary Storage ]
13
 Categories of Scheduling Algorithm

 Batch- there is no user waiting for output , it is

mostly non-preemptive.

 Interactive – preemption is needed

 Real time – may or may not need preemptive

14
 Scheduling Algorithm Goals
All systems
• Fairness - giving each process a fair share of the CPU
• Policy enforcement - seeing that stated policy is carried out
• Balance - keeping all parts of the system busy. (avoid
overload in 1 part)

Batch systems
• Throughput - maximize jobs per hour
• Turnaround time - minimize time between submission and
termination
• CPU utilization - keep the CPU busy all the time

15
 Cont.…
Interactive systems
• Response time - respond to requests quickly
• Waiting Time (wt): for each process time spent in ready
queue.
• Proportionality - meet users’ expectations.
Real-time systems
– Meeting deadlines - avoid losing data
– Predictability - avoid quality degradation in multimedia
systems

16
 Cont…
 Scheduling of processes is done to finish the work on time.
Below are different time with respect to a process.
• Arrival Time: Time at which the process arrives in the ready
queue.
• Completion Time: Time at which process completes its
execution.
• Burst Time: Time required by a process for CPU execution.
• TurnAround Time: Time Difference between completion time
and arrival time.
Turn Around Time = Completion Time - ArrivalTime
• Waiting Time(W.T): Time Difference between turn around time
and burst time.
Waiting Time = Turn Around Time - Burst Time

17
Scheduling policies in different environments

 Scheduling in Batch Systems:

 Scheduling in Interactive System

 Scheduling in Real Time System

18
Scheduling in Batch Systems
• Batch systems are designed for processing large amounts of
data without user interaction.
• Jobs are submitted in advance, and the system processes them
in a batch mode without requiring user intervention during
execution.
• Long-term scheduling is more relevant in batch systems, and
throughput is a key performance metric.
• It commonly uses Non-preemptive algorithms with long time
periods for each process are often acceptable.
• Ex. of batch system scheduling algorithms:-
• First Come First Served
• Shortest Job first
• Priority scheduling 19
 Scheduling in Interactive System
• Interactive systems involve direct user interaction.
• They are designed to respond quickly to user inputs
• Short-term scheduling is crucial in interactive systems to
ensure responsiveness.
• Round Robin or Priority Scheduling algorithms are commonly
used.
• The focus is on minimizing response time and providing a fair
share of the CPU to interactive tasks.
• Ex. Interactive system scheduling algorithms:-
• Round-robin scheduling
• Priority Scheduling
• Multiple Queues
• Lottery Scheduling
• Fair-share Scheduling 20
 Cont…
1. First Come First Served
• It’s the simplest of all algorithms.

• It is non preemptive and use linked list to keep track the jobs

• Works in FIFO and it is not optimal.

• When the running process blocks or exits, the first process on the
queue is run next.

• When a blocked process becomes ready, like a newly arrived job,

it is put on the end of the queue.

21
 Cont.…
Example
EXAMPLE DATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5

The Gantt chart for the schedule is:

0 P1 8 P2 12 P3 21 P4 26

Average Turnaround time = Completion time- arrival time

= ( (8-0) + (12-1) + (21-2) + (26-3) )/4
= (8+11+19+23)/4=61/4
Average wait time = Turn Around Time - Burst Time
= (8-8) + (11-4) + (19-9) + (23-5) )/4= 40/4 22
 Cont…
2. Short Job First
• The scheduler selects the shortest job first
• Shortest job first is only optimal when all the jobs are
available simultaneously.
• Two schemes:
– Non-preemptive – once CPU given to the process it cannot
be preempted until completes its CPU burst.
– Pre-emptive – if a new process arrives with CPU burst
length less than remaining time of current executing
process, preempt.
• This scheme is know as the Shortest-Remaining-Time-
First (SRTF).

23
Cont…
Example

24
 Preemptive SJF – (Shortest Remaining Time First)

• Preemptive version of SJF.

• If a new process arrives with CPU burst length less than remaining
time of current executing process, preempt the currently executing
process and allocate the CPU to the new process.

• It minimizes average waiting times.

25
 Cont…
Example #2: Preemptive SJF (Shortest-remaining-time-first)
Process Arrival Burst
Time Time
1 0 7
2 2 4
3 4 1
4 5 4

The Gantt chart for the schedule is:

P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16

Completion time for p1,p2,p3,p4 is 16,7,5,11 respectively

Turnaround time = CT-AT=((16-0) + (7-2) + (5-4) + (11-5) )/4=7
Average waiting time = TAT-BT=((16-7)+(5-4)+(1-1)+(6-5))/4 = 26
 Cont..
3. Priority scheduling
• Each process is assigned in a priority.
• Schedule highest priority first. All processes within same priority
are in FCFS.
• Priority may be determined by user or by some default
mechanism.
• The system may determine the priority based on memory
requirements, time limits, or other resource usage.
• Priority scheduling can be either preemptive or non-
preemptive
– A preemptive approach will preempt the CPU if the priority of the
newly-arrived process is higher than the priority of the currently
running process
– A non-preemptive approach will simply put the new process (with
the highest priority) at the head of the ready queue
27
 Cont…
Example #1: Priority scheduling (Non-preemptive)
AT Priority BT
Lesser the number ,higher
P1 0 3 8 the priority
P2 1 4 2
P3 3 4 4 By default will be higher for
lesser number
P4 4 5(L) 1
P5 5 2 (H) 12

The Gantt chart for the schedule is:

P5 P1 P2 P3 P4
0 12 20 22 26 27
Completion time for p1,p2,p3,p4 and p5 is 20,22,26,27 and 12 respectively
Turnaround time = CT-AT=((20-0) + (22-1) + (26-3) + (27-4) + (12-5) )/5=
Average waiting time = TAT-BT=((20-8)+(21-2)+(23-4)+(23-1)+(7-12))/5 =
28
 Cont…
• Draw Gantt chart for Priority preemptive
scheduling and also calculate average waiting
time, Average turn-around time of the above
usin.

29
 Cont.…
4. Round- Robin scheduling
• Processes will be given equal priority
• Each process is assigned a time interval called quantum
• Therefore each process will be given an interval of time
(quanta of time).
1 quantum, 2 quanta…..
• Setting the quantum should have to be done carefully
• The two main things in setting quantum
– Setting the quantum too short causes to many process
switches that will result in performance degradation.
– But setting it too long may cause poor response to short
interactive commands.

30
 Cont…
Example
EXAMPLE DATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5

Round Robin, quantum = 4, the Gantt chart is

P1 P2 P3 P4 P1 P3 P4 P3
0 4 8 12 16 20 24 25 26

TAT = ( (20-0) + (8-1) + (26-2) + (25-3) )/4 =

WT = ( (20-8) + (7-4) + (24-9) + (22-5) )/4 =
31
 Cont…
5. Multiple queues
• It is independent scheduling algorithm
• It groups jobs of similar characteristic together
• Each queue can have its own schedule algorithm
• Priority can be assigned to each queue.

32
 Scheduling in Real Time System
• A real-time system is a computing system that must meet specific timing
constraints or deadlines associated with the tasks it performs.
• Real-time systems are classified into two main categories(hard real-time
systems and soft real-time systems) based on the strictness of the timing
requirements and the consequences of missing deadlines.
1. Hard real-time systems – required to complete a critical task within a
guaranteed amount of time.
– A Real time system in which, the violation of time constraints will cause critical
failure and loss of life or property damage
– Ex: Deadline in a missile control embedded system, in RADAR system
2. Soft real-time computing – requires that critical processes receive
priority over less fortunate ones.
– The violation of time constraints will cause only the degraded quality, but the
system can continue to operate is known as a Soft real time system.
– Ex: washing machine, and TV remote etc.
33
 Cont..
Algorithms under real time system

 Rate monotonic scheduling

 Earliest deadline First scheduling

Reading more about the two real time system

scheduling algorithm.

34
 Cont…
Rate monotonic Scheduling
Assumptions:
 Each periodic process must complete within its period
 No process is dependent on any other process
 Each process needs the same amount of CPU time on
each burst
 Any non-periodic process have no deadline
 preemption has no overhead

35
 Cont…
Earliest Job First
 Dynamic scheduling
 Do not need process to be periodic
 Process can use different amount of CPU time
 Scheduler keeps list of runnable process based on their deadline
order
 if the process at ready state ,the system checks at deadline and pick
the nearest deadline.

36
 Thread Scheduling
1. User-level threads:
• Since the kernel is not aware of the existence of threads, it operates
as it always does, picking a process.
• The runtime system of the process decides which thread to run
next.
• Since there are no clock interrupts to threads, this thread may
continue running as long as it wants to.
• Round-robin scheduling and priority scheduling are most common.
2. Kernel-level threads
• Here the kernel picks a particular thread to run.
• The executions of thread in the process is scheduled by the kernel
rather than runtime system.

37
 Cont.…

(a) Possible scheduling of user-level threads with quantum.

(b) Possible scheduling of kernel-level threads
38
.

39