Operating System

CS205

Lecture 9
CPU Scheduling
1st April 2019

By: Dr. Rana Asif Rehman

1 CS-205 Operating System

 What’s in today’s lecture
 Basic Concepts
 Scheduling Criteria
 Scheduling Algorithms
 Multiple-Processor Scheduling
 Real-Time Scheduling
 Algorithm Evaluation

2 CS-205 Operating System

 Basic Concepts
 In multiprogramming systems, where there is more than
one process runnable (ready), the OS must decide which
one to run next
 We already talked about the dispatcher, whose job is to
allow the next process to run
 It’s intimately associated with a scheduler whose job is to
decide (using a scheduling algorithm) which process to
have the dispatcher dispatch
 We will focus on the scheduling, understand the
problems associated with it, and look at some scheduling
algorithms

3 CS-205 Operating System

 Alternating Sequence of CPU And
I/O Bursts

4 CS-205 Operating System

 Nature of Process
 Not all processes have an even mix of CPU and I/O
usage
 A number crunching program may do a lot of
computation and minimal I/O
 This is an example of a CPU-BOUND process
 A data processing job may do little computation and a lot
of I/O
 This is an example of an I/O-BOUND process

5 CS-205 Operating System

 Types of Schedulers
 We have to decide which ready process to execute next –
this is Short-Term Scheduling or CPU Scheduler and
occurs frequently
 Short-term scheduling only deals with jobs that are currently
resident in memory
 Jobs are constantly arriving, and Long-Term Scheduling
or Job Scheduler must decide which to let into memory
and in what order
 Medium-Term Scheduling involves suspending or
resuming processes by swapping (rolling) them out of or into
memory (from disk)

6 CS-205 Operating System

 Scheduling
 Short term scheduler (CPU Scheduler)
 Whenever the CPU becomes idle, a process must be selected
for execution
 The Process is selected from the Ready queue
 Ready queue is not necessarily a FIFO queue
 It can be
 Priority based
 A Tree
 Unordered linked list etc

7 CS-205 Operating System

 Short term Scheduler
 Selects from among the processes in memory that are
ready to execute, and allocates the CPU to one of them
 CPU scheduling decisions may take place when a
process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
 Scheduling under 1 and 4 is nonpreemptive
 All other scheduling is preemptive

8 CS-205 Operating System

 When to select a new process to Run
2. Interrupt occurs,
 Four circumstances move from Running to
Ready

Dispatch
Admit Release

New Ready Running Exit

Time-out
1. Wait for I/O/
waitpid()/
3. Event I/O
Event occurs
P()/ Acquire()
Completion/ exit(0) Event wait
etc
/ V() /
Release()

Blocked

4. A Process
terminates
9 CS-205 Operating System
 Non Preemptive Scheduling
 Once the CPU has been allocated to a process
 The process keeps it until
 It Terminates
 Or has to wait for:
 I/O
 Mutex
 Child process
 Semaphore
 Conditional Variables etc
 There is no way, to get the CPU back, FORCEFULLY

10 CS-205 Operating System

 Non Preemptive Scheduling
 Only the case 1 and 4
 Must select a new process, if any, from the Ready Queue

Dispatch
Admit Release

New Ready Running Exit

Time-out
1. Wait for I/O/
Event occurs
waitpid()/
Event wait
P()/ Acquire()
etc

Blocked
4. A Process
terminates
11 CS-205 Operating System
 Preemptive Scheduling
 Possible to get the CPU back from a process, even if the
process has not completed its execution.

12 CS-205 Operating System

 Preemptive Scheduling 2. Interrupt occurs,
move from Running to
Ready

Dispatch
Admit Release

New Ready Running Exit

Time-out

In case of 2 and 3, there is a

3. Event I/O
Event occurs choice
Completion/ exit(0) Whether to continue, with the
Event wait

/ V() / same process

Release() or select a new one from the
ready queue
Blocked

13 CS-205 Operating System

 Dispatcher
 Dispatcher module gives control of the CPU to the
process selected by the short-term scheduler; this
involves:
 Switching context
 Switching to user mode
 Jumping to the proper location in the user program to restart
that program
 Dispatch latency – time it takes for the dispatcher to
stop one process and start another running

14 CS-205 Operating System

 Scheduling Criteria
 CPU Utilization
 Keep the CPU as busy as is possible
 May range from 0% to 100%
 Throughput
 Number of processes completed per unit time
 E.g. long processes
 1 process / hr
 Short processes
 10 processes / hr

15 CS-205 Operating System

 Scheduling Criteria

 Turnaround Time
 How long it take to execute a Process

Turnaround = Completion_Time
– Submission_Time

Turnaround = Wait_TimeGetIntoMemory
+ Wait_TimeReadyQueue
+ Wait_TimeBlockQueue
+ CPU_Execution_Time

16 CS-205 Operating System

 Scheduling Criteria
 Scheduling Algorithm does not effect the waiting time in
Block Queue
 It only effect the Waiting Time in the Ready Queue
 Waiting Time
 Sum of the periods spent waiting in the Ready Queue

17 CS-205 Operating System

 Scheduling Criteria

 Turnaround Time is not a good criteria for Interactive

Systems
 A process may
 Produce “Some” output
 Computes new results, while previous results are output to the
user
 Response Time
 Response_Time =
First_Response_Start_Time
– Submission_Time

18 CS-205 Operating System

 Additional Scheduling Criteria
 There are also other elements to consider:
 Priority/Importance of work – hopefully more important
work can be done first
 Fairness – hopefully eventually everybody is served
 Implement policies to increase priority as we wait longer… (this is
known as “priority aging”)
 Deadlines – some processes may have hard or soft deadlines
that must be met
 Consistency and/or predictability may be a factor as well,
especially in interactive systems

19 CS-205 Operating System

 Optimization Criteria
 We would like to Maximize
 CPU Utilization
 Throughput
 And Minimize
 Turnaround Time
 Waiting Time
 Response Time

20 CS-205 Operating System

 Scheduling Algorithms

 First come, First serve (FCFS)

 Shortest Job First (SJF)
 Priority Scheduling
 Round-Robin Scheduling
 Multi-level Queue Scheduling
 Multi-level Feed back queue Scheduling

21 CS-205 Operating System

1. First-Come, First-Served (FCFS) Scheduling
 Simplest scheduling algorithm:
 Run jobs in order that they arrive
 Uni-programming:
 Run until done
 Multi-programming:
 Run until done or Blocks on I/O
 Nonpreemptive
 A Process keeps CPU until done or I/O
 Advantage:
 Simplicity

22 CS-205 Operating System

 FCFS Scheduling
Process Burst Time
P1 24
P2 3
P3 3
 Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3

0 24 27 30
 Waiting time for P1 = 0; P2 = 24; P3 = 27
 Average waiting time: (0 + 24 + 27)/3 = 17

23 CS-205 Operating System

 FCFS Scheduling (Cont.)
 Suppose that the processes arrive in the order P2 , P3 , P1
 The Gantt chart for the schedule is:

P2 P3 P1

0 3 6 30

 Waiting time for P1 = 6;P2 = 0; P3 = 3

 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case

24 CS-205 Operating System

 Convoy Effect process service turnaround waiting
time ts time tt time tw
A 10 10 0
B 1 11 10
C 3 14 11
process D 4 18 14

AVERAGE 13.25 8.75

A long CPU-bound job may hog
A 10 the CPU and force shorter (or
I/O-bound) jobs to wait for
B 1
prolonged periods. This in turn
C 3 may lead to a lengthy queue of
ready jobs, and hence to the
D 4
'convoy effect'

time
5 10 15 20 25

25 CS-205 Operating System

 FCFS Scheduling (Cont.)
 FCFS is:
 Non-preemptive
 Ready queue is a FIFO queue
 Jobs arriving are placed at the end of ready queue
 First job in ready queue runs to completion of CPU burst
 Advantages: simple, low overhead
 Disadvantages: long waiting time, inappropriate for
interactive systems, large fluctuations in average
turnaround time are possible

26 CS-205 Operating System

2. Shortest-Job-First (SJF) Scheduling
 Associate with each process the length of its next CPU
burst. Use these lengths to schedule the process with the
shortest time
 Two schemes:
 Nonpreemptive – once CPU is given to the process it cannot be
preempted until the process completes its CPU burst
 Preemptive – if a new process arrives with CPU burst length
less than the remaining time of current executing process,
preempt. This scheme is know as the Shortest-Remaining-
Time-First (SRTF)
 SJF is optimal – gives minimum average waiting time for
a given set of processes

27 CS-205 Operating System

 Example of Non-Preemptive SJF
Process
Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 SJF (non-preemptive)

P1 P3 P2 P4

0 3 7 8 12 16

 Average waiting time = (0 + 6 + 3 + 7)/4 = 4

28 CS-205 Operating System
 SRTF - Shortest Remaining Time
First
 Preemptive version of SJF
 Ready queue ordered on length of time till completion
(shortest first)
 Arriving jobs inserted at proper position
 shortest job
 Runs to completion (i.e. CPU burst finishes) or
 Runs until a job with a shorter remaining time arrives (i.e.
placed in the ready queue)

29 CS-205 Operating System

 Example of Preemptive SJF (i.e.,
SRTF)
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 Preemptive SJF (i.e., SRTF)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

 Average waiting time = (9 + 1 + 0 +2)/4 = 3

30 CS-205 Operating System
 Shortest-Job-First (SJF) Scheduling
 Ready queue treated as a priority queue based on smallest CPU-
time requirement
 Arriving jobs inserted at proper position in queue
 Shortest job (1st in queue) runs to completion
 In general, SJF is often used in long-term scheduling
 Advantages: provably optimal w.r.t. average waiting time
 Disadvantages: Unimplementable at the level of short-term CPU
scheduling. Also, starvation is possible!
 Can do it approximately: use exponential averaging to predict
length of next CPU burst
==> pick shortest predicted burst next!

31 CS-205 Operating System

 Determining Length of Next CPU
Burst
 Can only estimate the length
 Can be done by using the length of previous CPU bursts,
using exponential averaging
1. t n  actual lenght of n th CPU burst
2.  n 1  predicted value for the next (i.e., n th  1) CPU burst
3.  n  predicted value for the n th CPU burst
4.  , 0    1
5. Define :  n1   tn  (1   ) n .
 = 0 implies making no use of recent history ( n+1   n)
 = 1 implies n+1 = tn (past prediction not used)
 = 1/2 implies weighted (older bursts get less and less weight)
32 CS-205 Operating System
 Prediction of the Length of the Next
CPU Burst
This figure is for   0.5 and  0  10

33 CS-205 Operating System

 References
 Operating System Concepts (Silberschatz, 9th edition)
Chapter 5

34 CS-205 Operating System