CPU Scheduling

Chapter 6
  Basic Concepts
Scope  Scheduling Criteria
 Scheduling Algorithms
  To introduce CPU scheduling, which is the basis for
multiprogrammed operating systems
Objectives  To describe various CPU-scheduling algorithms
 To discuss evaluation criteria for selecting a CPU-scheduling
algorithm for a particular system
Basic Concepts
 Maximum CPU utilization obtained with
multiprogramming
 CPU–I/O Burst Cycle – Process execution
consists of a cycle of CPU execution and I/O
wait
 CPU burst followed by I/O burst
 CPU burst distribution is of main concern
  Short-term scheduler selects from among the processes in ready
queue, and allocates the CPU to one of them
 Queue may be ordered in various ways

 CPU scheduling decisions may take place when a process:

 1. Switches from running to waiting state
 2. Switches from running to ready state

CPU Scheduler 

3. Switches from waiting to ready
4. Terminates

 Scheduling under 1 and 4 is nonpreemptive

 All other scheduling is preemptive
 Consider access to shared data
 Consider preemption while in kernel mode
 Consider interrupts occurring during crucial OS activities
  Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this involves:
 switching context
 switching to user mode
Dispatcher  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
  CPU utilization – keep the CPU as busy as possible
 Throughput – # of processes that complete their execution per
time unit
 Turnaround time – amount of time to execute a particular process
 TAT = CT - AT

 Waiting time – amount of time a process has been waiting in the

Scheduling ready queue
 WT = CT - AT - BT
Criteria  WT = TAT - BT

 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)
 RT = (The first time to be executed by CPU) - AT
Completion Time (CT): This is the time when the process completes its execution.
Arrival Time (AT): This is the time when the process has arrived in the ready state.
Burst Time (BT): This is the time required by the process for its execution.
  Max CPU utilization
Scheduling
 Max throughput
Algorithm  Min turnaround time
Optimization  Min waiting time
Criteria  Min response time
 Process Burst Time
P1 24
P2 3
P3 3
First- Come,  Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
First-Served P1 P2 P3
(FCFS) 0 24 27 30

Scheduling  Waiting time for P1 = 0; P2 = 24; P3 = 27

 Average waiting time: (0 + 24 + 27)/3 = 17
 Suppose that the processes arrive in the order:
P2 , P3 , P1
 The Gantt chart for the schedule is:

P2 P3 P1

FCFS
0 3 6 30

 Waiting time:
Scheduling  P1 = 6;
 P2 = 0;
(Cont.)  P3 = 3
 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case
 Convoy effect - short process behind long process
 Consider one CPU-bound and many I/O-bound
processes
  Associate with each process the length of its next
CPU burst
 Use these lengths to schedule the process with the
Shortest-Job- shortest time
First (SJF)  SJF is optimal – gives minimum average waiting time
for a given set of processes
Scheduling  The difficulty is knowing the length of the next CPU
request
 Could ask the user
 Process Arrival Time Burst Time
P1 0.0 6
P2 0.0 8
P3 0.0 7
P4 0.0 3
Example of  SJF scheduling chart
SJF  Average waiting time = (3 + 16 + 9 + 0) / 4 = 7
 What is the average waiting time using FCFS scheduling ?

P4 P1 P3 P2
0 3 9 16 24
 Process Arrival Time Burst Time
P1 0.0 6
P2 2.0 8
P3 4.0 7
P4 5.0 3
Example of
SJF  SJF scheduling
 Execution order:
 Average waiting time:

 What is the average waiting time using FCFS scheduling ?

  Can only estimate the length – should be similar to the previous
one
 Then pick process with shortest predicted next CPU burst

 Can be done by using the length of previous CPU bursts, using

exponential averaging
Determining 1. t n = actual length of n th CPU burst
2.  n +1 = predicted value for the next CPU burst
Length of Next 3.  , 0    1
CPU Burst 4. Define :
 n =1 =  t n + (1 −  ) n .
 Commonly, α set to ½
 Preemptive version called shortest-remaining-time-first
Prediction of
the Length of
the Next CPU
Burst

Prove that diagram !!!

   =0
 n+1 = n
 Recent history does not count

  =1
 n+1 =  tn
Examples of  Only the actual last CPU burst counts

Exponential  If we expand the formula, we get:

 n+1 =  tn+(1 - ) tn -1 + …
Averaging  +(1 -  )j  tn -j + …
 +(1 -  )n +1 0

 Since both  and (1 - ) are less than or equal to 1, each successive

term has less weight than its predecessor
  Now we add the concepts of varying arrival times and preemption to the
analysis
Process Arrival Time Burst Time
P1 0 8

Example of P2 1 4
P3 2 9
Shortest- P4 3 5
remaining-
time-first  Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

 Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec

  A priority number (integer) is associated with each process
 The CPU is allocated to the process with the highest priority
(smallest integer  highest priority)
 Preemptive
 Non-preemptive
Priority  SJF is priority scheduling where priority is the inverse of
Scheduling predicted next CPU burst time
 Problem :
 Starvation – low priority processes may never execute

 Solution
 Aging – as time progresses increase the priority of the
process
 Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
Example of P5 5 2

Priority  Priority scheduling Gantt Chart

Scheduling

 Average waiting time = 8.2 msec

 What is the average waiting time using FCFS and SJF?
  Each process gets a small unit of CPU time (time quantum q),
 usually 10-100 milliseconds.

 After this time 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 the time quantum
is q, then each process gets 1/n of the CPU time in chunks of at
Round Robin most q time units at once.
(RR)  No process waits more than (n-1)q time units.
 Timer interrupts every quantum to schedule next process
 Performance
 q large  FIFO
 q small  q must be large with respect to context switch, otherwise
overhead is too high
 Process Burst Time
P1 24
P2 3
P3 3
 The Gantt chart
Example of
RR with Time P1 P2 P3 P1 P1 P1 P1 P1
Quantum = 4 0 4 7 10 14 18 22 26 30

 Average turnaround time= (30+ 7+ 10)/3= 15.67 msec

 Typically, higher average turnaround time than SJF, but better response
 q should be large compared to context switch time
 q usually 10ms to 100ms, context switch < 10 usec
Time
Quantum and
Context
Switch Time
  For Q=1
 Average turn around time = 11 msec (prove)
 For Q=5
 Average turn around time = 12.25 msec (prove)
Turnaround and so on.

Time Varies
With The
Time
Quantum
 Scheduling Preemptive/ nonpreemptive
FCFS nonpreemptive

Preemptive / SJF may be either preemptive/ nonpreemptive

Non-preemptive Priority may be either preemptive/ nonpreemptive

Scheduling
RR preemptive
  Ready queue is partitioned into separate queues, e.g.:
 foreground (interactive)
 background (batch)
 Process permanently in a given queue
 Each queue has its own scheduling algorithm:
 foreground – RR
Multilevel  background – FCFS

Queue  Scheduling must be done between the queues:

 Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.
 Time slice – each queue gets a certain amount of CPU time which it
can schedule amongst its processes; i.e., 80% to foreground in RR
 20% to background in FCFS
Multilevel
Queue
Scheduling
  A process can move between the various queues; aging can be
implemented this way
 Multilevel-feedback-queue scheduler defined by the following
Multilevel parameters:
 number of queues
Feedback  scheduling algorithms for each queue
Queue  method used to determine when to upgrade a process
 method used to determine when to demote a process
 method used to determine which queue a process will enter when
that process needs service
  Three queues:
 Q0 – RR with time quantum 8 milliseconds
 Q1 – RR time quantum 16 milliseconds
 Q2 – FCFS

Example of  Scheduling
Multilevel  A new job enters queue Q0 which is served
FCFS
Feedback  When it gains CPU, job receives 8
milliseconds
Queue  If it does not finish in 8 milliseconds,
job is moved to queue Q1
 At Q1 job is again served FCFS and
receives 16 additional milliseconds
 If it still does not complete, it is
preempted and moved to queue Q2
End of  Questions?!
Chapter 6