OS Scheduling

 When/under what  Two categories:

circumstances is the  Nonpreemptive
selection function is  Preemptive
exercised?
Nonpreemptive Preemptive
– currently running
– once a process is in process may be
the running state, it interrupted and moved
will continue until it to ready state by the OS
terminates or blocks – preemption may occur
itself for I/O when a new process
arrives, on an interrupt,
or periodically
Types of CPU schedulers
n The CPU scheduler (sometimes called the dispatcher or
short-term scheduler): selects a process from the ready
queue and lets it run on the CPU
n Types of schedulers:
u Non-preemptive
F Executes only when:
• Process is terminated
• Process switches from running to blocked
F simple to implement but unsuitable for time-sharing systems
u Preemptive
F Executes at times above, also when:
• Process is created
• Blocked process becomes ready
• A timer interrupt occurs
F More overhead, but keeps long processes from monopolizing CPU
F Must not preempt OS kernel while it’s servicing a system call (e.g.,
reading a file) or otherwise OS may end up in an inconsistent state
scheduling algorithms
u First Come First Served (FCFS)
u Round Robin (RR)
u Shortest Job First (SJF)
u Shortest Remainder First (SRF)
u priority
u multilevel queue
u multilevel feedback queue
First Come First Served (FCFS)
u Choose process from ready queue in the order of its
arrival, and run that process non-preemptively
F FCFS schedulers were overly non-preemptive:
the process did not relinquish the CPU until it was
finished, even when it was doing I/O
F Now, non-preemptive means the scheduler chooses
another process when the first one terminates or
blocks
n Implement using FIFO queue (add to tail, take from
head)
n Used in Nachos (as distributed)
Example
FCFS evaluation
n Non-preemptive
n Response time — slow if there is a large variance in
process execution times
u If one long process is followed by
many short processes, short processes have to wait a
long time
u If one CPU-bound process is followed by many I/O-bound
processes, there’s a “convoy effect”
F Low CPU and I/O device utilization
n Throughput — not emphasized
n Fairness —penalizes short processes and I/O bound
processes
n Overhead —minimal
Algorithm for FCFS scheduling:
• Step 1: Start the process
• Step 2: Accept the number of processes in the ready Queue
• Step 3: For each process in the ready Q, assign the process id and accept the CPU
burst time
• Step 4: Set the waiting of the first process as ‘0’ and its burst time as its turn around
time
• Step 5: for each process in the Ready Q calculate
(a) Waiting time for process(n)= waiting time of process (n-1) + Burst time of
process(n-1)
(b) Turn around time for Process(n)= waiting time of Process(n)+ Burst time for
process(n)
• Step 6: Calculate
(a) Average waiting time = Total waiting Time / Number of process
(b) Average Turnaround time = Total Turnaround Time / Number of process
• Step 7: Stop the process
Round-robin scheduling (RR)
n Preemptive version of FCFS
n Policy:
u Define a fixed time slice (also called a time quantum)
u Choose process from head of ready queue
u Run that process for at most one time slice, and if it
hasn’t completed by then, add it to the tail of the ready
queue
u If that process terminates or blocks before its time slice
is up, choose another process from the head of the
ready queue, and run that process for at most one time
slice…
n Implement using:
u Hardware timer that interrupts at periodic intervals
u FIFO ready queue (add to tail, take from head)
Round Robin Example
RR evaluation
n Preemptive (at end of time slice)
n Response time —good for short processes
u Long processes may have to wait n*q time units for
another time slice
F n = number of other processes,
q = length of time slice
n Throughput —depends on time slice
u Too small — too many context switches
u Too large — approximates FCFS
n Fairness —penalizes I/O-bound processes (may not
use full time slice)
n Overhead —low
Algorithm for RR
• Step 1: Start the process
• Step 2: Accept the number of processes in the ready Queue and time
quantum (or) time slice
• Step 3: For each process in the ready Q, assign the process id and accept
the CPU burst time
• Step 4: Calculate the no. of time slices for each process where
• No. of time slice for process(n) = burst time process(n)/time slice
• Step 5: If the burst time is less than the time slice then the no. of time
slices =1.
• Step 6: Consider the ready queue is a circular Q, calculate
• Waiting time for process(n) = waiting time of process(n-1)+ burst time of
process(n-1 ) + the time difference in getting the CPU from process(n-1)
• Turn around time for process(n) = waiting time of process(n) + burst time
of process(n)+ the time difference in getting CPU from process(n).
• Step 7: Calculate
• Average waiting time = Total waiting Time / Number of process
• Average Turnaround time = Total Turnaround Time / Number of process
• Step 8: Stop the process
Shortest Job First (SJF)
• n Other names:
• u Shortest-Process-Next (SPN)
• n Policy:
• u Choose the process that has the smallest next
• CPU burst, and run that process nonpreemptively
• (until termination or blocking)
• u In case of a tie, FCFS is used to break the tie
• n Difficulty: determining length of next CPU burst
• u Approximation —predict length, based on past
• performance of the process, and on past
• predictions
SJF Example
SJF evaluation
n Non-preemptive
n Response time —good for short processes
u Long processes may have to wait until a large
number of short processes finish
u Provably optimal —minimizes average waiting
time for a given set of processes (if preemption
is not considered)
n Throughput — high
n Fairness —penalizes long processes
n Starvation — possible for long processes
n Overhead — can be high (recording and estimating
CPU burst times)
Algorithm for SJF
• Step 1: Start the process
• Step 2: Accept the number of processes in the ready Queue
• Step 3: For each process in the ready Q, assign the process id and accept
the CPU burst time
• Step 4: Start the Ready Q according the shortest Burst time by sorting
according to lowest to
• highest burst time.
• Step 5: Set the waiting time of the first process as ‘0’ and its turnaround
time as its burst time.
• Step 6: For each process in the ready queue, calculate
• Waiting time for process(n)= waiting time of process (n-1) + Burst time of
process(n-1)
• Turn around time for Process(n)= waiting time of Process(n)+ Burst time
for process(n)
• Step 6: Calculate
• Average waiting time = Total waiting Time / Number of process
• Average Turnaround time = Total Turnaround Time / Number of process
• Step 7: Stop the process
Shortest Remaining Time (SRT)

n SRT is a preemptive version of SJF

n Policy:
u Choose the process that has the smallest next
CPU burst, and run that process preemptively…
F (until termination or blocking, or
F until a process enters the ready queue (either a
new process or a previously blocked process))
u At that point, choose another process to run if one
has a smaller expected CPU burst than what is left
of the current process’ CPU burst
SJF Example
SRT evaluation
n Preemptive (at arrival of process into ready queue)
n Response time —good
u Provably optimal wait time— minimizes
average waiting time for a given set of
processes
n Throughput — high
n Fairness —penalizes long processes
u Note that long processes eventually become
short processes
n Starvation — possible for long processes
n Overhead — can be high (recording and
estimating CPU burst times
Priority Scheduling
u Associate a priority with each process
F Externally defined, based on importance, money, politics, etc.
F Internally defined, based on memory requirements, file
requirements, CPU requirements vs. I/O requirements, etc.
F SJF is priority scheduling, where priority is inversely
proportional to length of next CPU burst
u Choose the process that has the highest priority, and run that
process either:
F preemptively, or
F non-preemptively
n Evaluation
u Starvation — possible for low-priority processes
F Can avoid by aging processes: increase priority as they spend
time in the system
Algorithm for Priority Scheduling:
• Step 1: Start the process
• Step 2: Accept the number of processes in the ready Queue
• Step 3: For each process in the ready Q, assign the process id and
accept the CPU burst time
• Step 4: Sort the ready queue according to the priority number.
• Step 5: Set the waiting of the first process as ‘0’ and its burst time
as its turn around time
• Step 6: For each process in the Ready Q calculate
• Waiting time for process(n)= waiting time of process (n-1) + Burst
time of process(n-1)
• Turn around time for Process(n)= waiting time of Process(n)+ Burst
time for process(n)
• Step 7: Calculate
• Average waiting time = Total waiting Time / Number of process
• Average Turnaround time = Total Turnaround Time / Number of
process
• Step 8: Stop the process
Alternative Scheduling Policies
Table 9.4
Process Scheduling
Example
Table 9.5

Comparison
of
Scheduling
Policies
(Assumes no process
blocks itself, for I/O or
other event wait.)
Multilevel queue scheduling
u Use several ready queues, and associate a different priority with
each queue
u Choose the process from the occupied queue that has the highest
priority, and run that process either:
F preemptively, or
F non-preemptively
u Assign new processes permanently to a particular queue
F Foreground, background
F System, interactive, editing, computing
u Each queue can have a different scheduling policy
F Example: preemptive, using timer
• 80% of CPU time to foreground, using RR
• 20% of CPU time to background, using FCFS
n Problem: processes at low level queues may starve
Multilevel feedback queue
u Use several ready queues, and associate a different priority with
each queue
u Choose the process from the occupied queue with the highest
priority, and run that process either:
F preemptively, or
F non-preemptively
u Each queue can have a different scheduling policy
u Allow scheduler to move processes between queues
F Start each process in a high-priority queue; as it finishes each
CPU burst, move it to a lower-priority queue
F Aging —move older processes to higher-priority queues
F Feedback = use the past to predict the future — favor jobs that
haven’t used the CPU much in the past close to SRT!
Unix CPU Scheduling
u Multiple queues (32), each with a priority value - 0-127 (low value
= high priority):
F Kernel processes (or user processes in kernel mode) the lower
values (0-49) - kernel processes are not preemptible!
F User processes have higher value (50-127)
u Choose the process from the occupied queue with the highest
priority, and run that process preemptively, using a timer (time
slice typically around 100ms)
F Round-robin scheduling in each queue
u Move processes between queues
F Keep track of clock ticks (60/second)
F Once per second, add clock ticks to priority value
F Also change priority based on whether or not process has
used more than it’s “fair share” of CPU time (compared to
others)
u users can decrease priority