OS 09 05 Cpu Scheduling

Operating Systems
Session 4
CPU Scheduling
CPU Scheduling
CPU Scheduling
• 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 distribution

CPU Bursts and I/O Bursts
Histogram of CPU-burst Times
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
Scheduling Criteria
• 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
• 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)
Preemptive vs. Nonpreemptive
Scheduling
• Preemptive processes
– can be removed from their current processor
– can lead to improved response times
– important for interactive environments
– preempted processes remain in memory
• Nonpreemptive processes
– run until completion or until they yield control of a
processor
– unimportant processes can block important ones
indefinitely
First-come First-served (FCFS)
Scheduling
• FCFS scheduling
– simplest scheme
– dispatched according to arrival time
– nonpreemptible
– rarely used as primary scheduling algorithm
First-Come First-Served (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
First-Come First-Served (FCFS)
Scheduling
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
• Convoy effect short process behind long process

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 given to the process it cannot be
preempted until completes its CPU burst
– preemptive
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)
• SJF is optimal – gives minimum average waiting time

for a given set of processes
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
Example of Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (Preemptive)
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16
• Average waiting time = (9 + 1 + 0 +2)/4 = 3

Approximate SJF
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 length of n th CPU burst

2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :
Prediction of the Length of the Next
CPU Burst
 = ½ and 0 = 10
Exponential Averaging
•  =0
– n+1 = n
– Recent history does not count
•  =1
– n+1 =  tn
– Only the actual last CPU burst counts
• If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(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
Priority Scheduling
• 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
– nonpreemptive
• SJF is a priority scheduling where priority is the
predicted next CPU burst time
• Problem  Starvation – low priority processes may never
execute
• Solution  Aging – as time progresses, increase the
priority of the process
Round Robin (RR)
• Each process gets a small unit of CPU time (time
quantum), 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 most q time units at once. No
process waits more than (n-1)q time units.
• Performance
– q large  FIFO
– q small  q must be large with respect to context
switch, otherwise overhead is too high
Time Quantum
• Time slice too large

– FIFO behavior
– Poor response time
• Time slice too small
– Too many context switches (overheads)
– Inefficient CPU utilization
• Heuristic:
– 70-80% of jobs block within time-slice
• Typical time-slice
– 10 to 100 ms
• Time spent in system depends on size of job.
Example of RR with Time Quantum = 20
Process Burst Time

P1 53
P2 17
P3 68
P4 24
• The Gantt chart is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
• Typically, higher average turnaround than SJF, but better

response
Time Quantum and Context Switch Time
Turnaround Time varies with the
Time Quantum
Multilevel Queue
• Ready queue is partitioned into separate queues:
foreground (interactive)
background (batch)
• Each queue has its own scheduling algorithm
– foreground – RR
– background – FCFS
• 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
Multilevel Feedback Queue
• A process can move between the various queues;
aging can be implemented this way
• Multilevel-feedback-queue scheduler defined by the

following parameters:
– number of queues
– scheduling algorithms for each 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
Example of Multilevel Feedback Queue
• Three queues:
– Q0 – RR with time quantum 8 milliseconds
– Q1 – RR time quantum 16 milliseconds
– Q2 – FCFS
• Scheduling
– A new job enters queue Q0 which is served FCFS.
When it gains CPU, job receives 8 milliseconds. 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.
Example of Multilevel Feedback Queue
Multilevel Feedback Queue
• Discussions:
– Favors I/O bound processes to achieve good device
utilization
– Separates processes into categories based on their CPU
need
– Each time a process leaves the queue it is stamped with the
identity of the lowest level queue in which it last resided.
– When the process reenters the fray for CPU, it is sent
directly to the queue where it last completed its execution.
– (the past behavior is a good indicator of the future behavior)
– If the process changes its characteristics from CPU bound
to I/O bound,
1) the process is stamped with the time spent last time on
the CPU.
2) if a process voluntarily relinquishes the CPU, it may be
moved up to the next level queue.
Selfish Round Robin (SRR)
• Objective :
– To give better service to processes that have been
executing for a while than to newcomers.
• Implementation :
– Processes in the ready list are partitioned into two
lists: new and accepted.
– new processes wait.
– accepted processes are serviced by RR.
– priority of a new process increases at rate a.
– priority of an accepted process increases at rate b .
– a and b are parameters to tune the method.
– When the priority of a new process
reaches the priority of an accepted
process, that new process becomes
accepted.
– If all accepted processes finish, the
highest priority new process is accepted.
– Assume that there are no ready processes, when the
first one, A, arrives. It has priority 0 to begin with.
Since there are no other accepted processes, A is
accepted immediately.
– After a while another process, B, arrives. As long as b
/ a < 1, B’s priority will eventually catch up to A’s, so it
is accepted; now both A and B have the same
priority.
– All accepted processes share a common priority
(which rises at rate b ); that makes this policy easy to
implement.
– Even if b / a > 1, A will eventually finish, and then B
can be accepted.
• Adjusting the parameters a and b :
– If b / a >= 1, a new process is not accepted
until all the accepted processes have finished,
so SRR becomes FCFS.
– If b / a = 0, all processes are accepted
immediately, so SRR becomes RR.
– If 0 < b / a < 1, accepted processes are
selfish, but not completely.
• Demonstration a = 2 and b=1
• Demonstration a = 2 and b=1
Lottery Scheduling: Flexible Proportional-Share
Resource Management
Carl A. Waldspurger 􀀀 William E. Weihl

􀀀
MIT Laboratory for Computer Science, 1994
• Novelty :
– Lottery scheduling provides efficient, responsive
control over the relative execution rates of
computations.
– Such control is beyond the capabilities of
conventional schedulers.
– Desirable in systems that service requests of varying
importance, such as databases, media-based
applications, and networks.
Resource Management
• Lottery Scheduling:
– Lottery scheduling is a randomized resource
allocation mechanism.
– Resource rights are represented by lottery tickets.
– Each allocation is determined by holding a lottery;
the resource is granted to the client with the winning
ticket.
– This effectively allocates resources to competing
clients in proportion to the number of tickets that
they hold.
Resource Management
• Demonstration:
Resource Management
• Resource Rights:
– Lottery tickets encapsulate resource rights that are abstract,
relative, and uniform.
abstract:
– They quantify resource rights independently of machine details.
relative:
– since the fraction of a resource that they represent varies
dynamically in proportion to the contention for that resource.
Thus, a client will obtain more of a lightly contended resource
than one that is highly contended.
uniform:
– because rights for heterogeneous resources can be
homogeneously represented as tickets.
Resource Management
• Lotteries:
– Scheduling by lottery is probabilistically fair. The
expected allocation of resources to clients is
proportional to the number of tickets that they hold.
– Since the scheduling algorithm is randomized, the

actual allocated proportions are not guaranteed to
match the expected proportions exactly.
– However, the disparity between them decreases as

the number of allocations increases.
Resource Management
• Lotteries:
– The number of lotteries won by a client has a
binomial distribution.
– Probability p that a client holding t tickets will
win a given lottery with total T tickets is given
by: p = t / T.
– After n identical lotteries, the expected
number of wins w is given by: E[w] = np with
variance σw2 = n.p.(1-p).
Resource Management
• Lotteries:
– The coefficient of variation for the observed
proportion of wins is
σw / E[w] =
– Thus, a client’s throughput is proportional to its ticket
allocation, with accuracy that improves with √n.
Resource Management
• Lotteries:
– The number of lotteries required for a client’s first
win has a geometric distribution.
– The expected number of lotteries n that a client must
wait before its first win is given by:
E[n] = 1/p
with variance σn2 = (1-p) / p2 .
– So, a clients average response time is inversely
proportional to ticket allocation.
Resource Management
• Lotteries:
– Since any client with a non-zero number of tickets
will eventually win a lottery, the conventional
problem of starvation does not exist.
– The lottery mechanism also operates fairly when the
number of clients or tickets varies dynamically.
– For each allocation, every client is given a fair
chance of winning proportional to its share of the
total number of tickets. Since any changes to
relative ticket allocations are immediately reflected in
the next allocation decision, lottery scheduling is
extremely responsive.
Resource Management
• Resource Management Policies:

Ticket Transfer:
– Ticket transfers are explicit transfers of tickets from
one client to another.
– Ticket transfers can be used in any situation where a
client blocks due to some dependency.
– For example, when a client needs to block pending a
reply from an RPC, it can temporarily transfer its
tickets to the server on which it is waiting.
– Clients also have the ability to divide ticket transfers
across multiple servers on which they may be
waiting.
Resource Management

Ticket Inflation:
– Ticket inflation is an alternative to explicit ticket
transfers in which a client can escalate its resource
rights by creating more lottery tickets.
– In general, such inflation should be disallowed, since
it violates desirable modularity and load insulation
properties.
– For example, a single client could easily monopolize
a resource by creating a large number of lottery
tickets. However, ticket inflation can be very useful
among mutually trusting clients; inflation and
deflation can be used to adjust resource allocations
without explicit communications.
Resource Management

Compensation tickets:
– A client which consumes only a fraction f of its
allocated resource quantum can be granted a
compensation ticket that inflates its value by 1/f until
the client starts its next quantum.
– This ensures that each client’s resource
consumption, equal to f times its per-lottery win
probability p , is adjusted by 1/f to match its
allocated share p .
– Without compensation tickets, a client that does not
consume its entire allocated quantum would receive
less than its entitled share of the processor.
Case study: Solaris 2
• Solaris uses priority based scheduling

• Four classes of scheduling in order of priority
1) real time 2) system 3) time sharing 4) interactive
• Each class has different priority and different
scheduling algorithms.
• A process starts as a LWP and can create more
LWPs.
• Default scheduling class for a process is time
sharing.
• Scheduling policy for time sharing dynamically
adjusts priorities and assigns time slices of
different lengths using multilevel feedback queue.
• The higher the priority the smaller the time slice
• Interactive processes have a higher priority
• CPU bound processes have a lower priority
• Gives
– Good response time for interactive processes
– Good throughput for CPU bound processes
• Interactive class uses same scheduling policy as

the time sharing class but gives more priority for
windowing applications.
• System class designates the kernel processes

(scheduling and paging daemon for example)
• Priority of a system process does not change
• User processes running in kernel mode are not in

the system class
• A system class thread runs until it either blocks or

is preempted by a higher priority thread.
• Real time threads are given the highest

priority amongst all classes
• A real time process will run before a

process in any other class
• Each scheduling class has a priority and the

scheduler converts class-specific priorities into
global priorities
• Thread with the highest global priority is selected

for CPU.
• A thread runs until:

– it blocks
– uses the time slice ( if not a system thread)
– it is preempted by a higher priority thread
• If there are multiple threads with same priority,

round robin is used.
Case study: Windows 2000
• Priority based preemptive scheduling
• A thread selected by the dispatcher will run

until
• preempted by a higher priority thread or
• it terminates, or
• its time quantum ends, or
• it calls a blocking system call (for I/O etc.)
• If a higher real time thread is ready, the

lower priority thread will be preempted
• Windows dispatcher uses 32-level priority to determine the

order of thread execution
• Priorities are divided into two classes:

– Variable class – threads with priorities from 1 to 15
– Real-time class – with priorities from 16 to 31
• A thread running at priority 0 used for memory management
• Dispatcher uses a queue for each scheduling priority, and

traverses the set of queues from highest to lowest priority
until finds a thread ready to run.
• If no ready thread is found, it runs a special thread called idle

thread
A process may belong to several Within each of these priority

priority classes: classes there is a relative priority:
1. REALTIME_PRIORITY_CLASS 1. TIME_CRITICAL
2. HIGH_PRIORITY_CLASS 2. HIGHEST
3. ABOVE_NORMAL_PRIORITY_CLASS 3. ABOVE_NORMAL
4. NORMAL_PRIORITY_CLASS 4. NORMAL
5. BELOW_NORMAL_PRIORITY_CLASS 5. BELOW_NORMAL
6. IDLE_PRIORITY_CLASS 6. LOWEST
7. IDLE
All priority classes except
REALTIME_PRIORITY_CLASS are The priority of each thread is
variable class properties. based upon the priority class
it belongs to and the relative
priority within the class.
PRIORITY CLASSES
Real- High Above Normal Below Idle

RELATIVE PRIORITY
time Normal normal priority

Time- 31 15 15 15 15 15
critical
Highest 26 15 12 10 8 6
Above 25 14 11 9 7 5
normal
Normal 24 13 10 8 6 4 BASE
PRIORITY
Below 23 12 9 7 5 3
normal
Lowest 22 11 8 6 4 2
Idle 16 1 1 1 1 1
• Processes are typically members of the

NORMAL_PRIORITY_CLASS unless the parent was
of IDLE_PRIORITY_CLASS or another class was
specified when the process was created.
• Initial priority of the thread is typically the base

priority of the process the thread belongs to.
• If thread’s time quantum runs out, the thread is

interrupted and if the thread is in variable priority
class (not in real_time_priority_class), the priority
is lowered.
• Aim is to limit CPU consumption of compute-bound

jobs
• When a variable priority thread is released from a

wait operation, the dispatcher boosts priority:
– large boost for threads which had been waiting
for key-board input
– moderate – for disk operation
• Aim is to give good response time to interactive

threads using key-board, mouse and windows, to
keep the I/O devices busy.
• Compute bound threads use the spare CPU cycles.
• The current window gets a priority boost to

enhance response time.
• Windows 2000 selects the foreground

process (the window which is currently
selected) and gives it typically thrice the
time quantum for better results.
Case study: Linux
• Linux uses two separate scheduling algorithms:
– time sharing algorithm for fair preemptive scheduling

among multiple processes
– for real-time tasks with absolute priorities where

priorities are more important than fairness
Case study: Linux
• Linux allows only the processes running in

user mode to be preempted.
• A process may not be preempted while

running in kernel mode even if a real time
process with higher priority is available to
run.
Case study: Linux
• Time sharing scheduling class:

– uses a prioritized, credit-based algorithm
• Each process has a certain number of

scheduling credits, the process with the
most credits is selected by the dispatcher
• Every time a timer interrupt occurs, the

process loses one scheduling credit, if the
credit reaches zero, it is suspended.
Case study: Linux
• If no runnable process have any credits,

then recrediting is done.
• Adds credits to all the processes (not only

the runnable ones) in the system as per the
following rule:
credit = credits / 2 + priority
• Mixes the process’ history and its priority.
• Half of the credits still held by the process

is counted.
Case study: Linux
• Processes running all the time, tend to

exhaust their credits while the interactive
processes accumulate credits over multiple
recrediting operations, finally getting higher
priority leading to rapid response.
• Including the process priority while

recrediting, Linux forces the background
batch jobs (having lower priority) to get less
scheduling credits than the interactive jobs
(with higher priority), eventually forcing
them spend less time on CPU.
Case study: Linux
• Linux real time scheduling:

– The scheduler always runs the process with the highest
priority
– If priorities are equal, it selects the one which has been
waiting longest.
• The above principles are implemented in two

different paradigms:
1) FCFS 2) RR
• This is soft real time scheduling
• Scheduler maintains strict relative priority
• Linux kernel code is never preempted
• If kernel executes on behalf of another process, the
“waken up” real time process may have to wait for
the system call to complete or block.
Case study: Linux
SCHED_FIFO Scheduling
• Any SCHED_FIFO task on a system will preempt any
other tasks and run for as long as it wants to.
• SCHED_FIFO tasks do not have timeslices.
• Multiple SCHED_FIFO tasks are scheduled by priority
- higher priority SCHED_FIFO tasks will preempt
lower priority SCHED_FIFO tasks.
SCHED_RR Scheduling
• SCHED_RR tasks have timeslices and are always
preempted by SCHED_FIFO tasks.
• SCHED_RR tasks are scheduled by priority, and within
a certain priority they are scheduled in a round-robin
fashion.
• Each SCHED_RR task within a certain priority runs for
its allotted timeslice, and then returns to the bottom of
the list in its priority array queue.
End of Session 4

OS 09 05 Cpu Scheduling

Uploaded by

Copyright:

Available Formats

OS 09 05 Cpu Scheduling

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

OS 09 05 Cpu Scheduling

Uploaded by

Copyright:

Available Formats

Operating Systems

• Maximum CPU utilization obtained with

• CPU–I/O Burst Cycle – Process execution consists of a

• CPU burst distribution

• Dispatcher module gives control of the CPU to the

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

• Average waiting time: (6 + 0 + 3)/3 = 3

• Much better than previous case

• Convoy effect short process behind long process

• SJF is optimal – gives minimum average waiting time

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

Determining Length of Next CPU Burst:

• can only estimate the length

1. t n  actual length of n th CPU burst

• Since both  and (1 - ) are less than or equal to 1,

• Time slice too large

Process Burst Time

• The Gantt chart is:

0 20 37 57 77 97 117 121 134 154 162

• Typically, higher average turnaround than SJF, but better

• Multilevel-feedback-queue scheduler defined by the

Carl A. Waldspurger 􀀀 William E. Weihl

– Since the scheduling algorithm is randomized, the

– However, the disparity between them decreases as

• Resource Management Policies:

• Resource Management Policies:

• Resource Management Policies:

• Solaris uses priority based scheduling

• The higher the priority the smaller the time slice

• Interactive processes have a higher priority

• CPU bound processes have a lower priority

• Interactive class uses same scheduling policy as

• System class designates the kernel processes

• Priority of a system process does not change

• User processes running in kernel mode are not in

• A system class thread runs until it either blocks or

• Real time threads are given the highest

• A real time process will run before a

• Each scheduling class has a priority and the

• Thread with the highest global priority is selected

• A thread runs until:

• If there are multiple threads with same priority,

• Priority based preemptive scheduling

• A thread selected by the dispatcher will run

• If a higher real time thread is ready, the

• Windows dispatcher uses 32-level priority to determine the

• Priorities are divided into two classes:

• A thread running at priority 0 used for memory management

• Dispatcher uses a queue for each scheduling priority, and

• If no ready thread is found, it runs a special thread called idle

A process may belong to several Within each of these priority

Real- High Above Normal Below Idle

time Normal normal priority

• Processes are typically members of the

• Initial priority of the thread is typically the base

• If thread’s time quantum runs out, the thread is

• Aim is to limit CPU consumption of compute-bound

• When a variable priority thread is released from a

• Aim is to give good response time to interactive