Chapter Four

SCHEDULING

1
 Scheduling
• Multiprogrammed 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
• The part of the operating system that makes the
choice is called the scheduler.
• The algorithm used by the scheduler to decide
which process next is called the scheduling
algorithm
• Dispatcher gives control of CPU’s core to the
process selected by scheduler
2
 Scheduling
Process behavior:
• compute-bound (CPU-bound)
– spend most of their time computing
– have long CPU bursts
– infrequent I/O waits
• I/O-bound
– have short CPU bursts
– frequent I/O waits
• The key factor in identifying CPU-bound and
I/O-bound processes is the length of the CPU
burst, not the length of the I/O burst
• As CPUs get faster, processes tend to get more
I/O-bound
3
 Scheduling

Process goes to
blocked/waiting
state. CPU not Interrupt: back from I/O operation,
needed. ready to use the CPU.

a) compute-bound b) I/O-bound 4
 Scheduling
When to Schedule?
• A new 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
– If no process is ready, a system-supplied idle process is normally
run
• 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 info
• I/O interrupt
– Scheduler decides to run the newly ready process, continue the
5
interrupted process or run another process in the ready queue
 Scheduling
Types of scheduling:
• Non-preemptive
– Scheduling algorithm picks a process to run and then
just lets it run until it blocks (either on I/O or waiting
for another process) or until it voluntarily releases the
CPU
– Even if it runs for hours, it will not be forcibly
suspended
• Preemptive
– Picks a process and lets it run for a maximum of
some fixed time
– Requires availability of clock
6
 Scheduling
Types of Scheduling
• Long-term scheduling
– the decision to add to pool of processes to be
executed
• Mid-term scheduling
– the decision to add to the number of processes
that are partially or fully in memory
• Short-term scheduling
– decision as to which available process will be
executed
• I/O scheduling
– decision as to which process’s pending request
shall be handled by an available I/O device
7
Scheduling

8
Scheduling

9
 Scheduling
Scheduling policies in different environments
• Batch systems:
– there are no users impatiently waiting at their terminals
for a quick response
– non-preemptive algorithms, or preemptive algorithms
with long time periods for each process are often
acceptable
– This approach reduces process switches and thus
improves performance
• First Come First Served
• Shortest Job First
• Shortest Remaining Time Next

10
 Scheduling
Scheduling policies in different environments
• Interactive systems:
– preemption is essential to keep one process from
hogging the CPU and denying service to the others
• Round Robin
• Priority Scheduling
• Multiple Queues
• Shortest Process Next
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-share Scheduling
• Real-time systems:
– Static vs. dynamic

11
 Criteria & Objectives
• CPU utilization – keep the CPU as busy as possible
(40% – lightly loaded, 90% – heavily loaded)
• Throughput – number of processes that complete
their execution per unit time
• Turnaround time – amount of time to execute a
particular process (total time spent on the system)
• 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)
12
 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
• Batch systems
– Throughput - maximize jobs per hour
– Turnaround time - minimize time between submission and
termination
– CPU utilization - keep the CPU busy all the time
• Interactive systems
– Response time - respond to requests quickly
– Proportionality - meet users’ expectations
• Real-time systems
– Meeting deadlines - avoid losing data
– Predictability - avoid quality degradation in multimedia
systems
13
 First-Come First-Served
• Simplest of all scheduling algorithms is nonpreemptive
FCFS or FIFO
• As each process becomes ready, it joins the ready
queue
• When the running process blocks or exits, the first
process on the queue (i.e with the longest waiting time in
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
• Advantages:
– Easy to understand and program
– It is fair
• Limitations
– Favors CPU-bound processes over I/O bound processes
– May result in inefficient use of both the processor & I/O devices

14
 First-Come First-Served
• FCFS performs (less normalized turnaround time) much
better for long processes than short ones. Consider the
following example:

15
 First-Come First-Served

Throughput = No jobs/total time

= 4/202
=0.02
16
 First-Come First-Served

Turn around time:

Average Turn Around Time:
TrW = 1-0 = 1 AvgTr = (1+100+100+199) / 4 = 100
TrX = 101-1=100
TrY = 102-2=100
TrZ = 202-3=199
17
 First-Come First-Served

Waiting time: Average Waiting time:

Avg Wt ={Wt(W) + Wt(X) + Wt(Y) + Wt(Z)} / 4
WtW = 0-0=0
WtX = 1-1=0 =(0+0+99+99)/4
WtY = 101-2=99 =49.5
WtZ = 102-3=99
18
 First-Come First-Served

Response Time: Response time is different from

RtW = 0-0=0 waiting time if the process is
RtX = 1-1=0 interrupted or blocks for I/O
RtY = 101-2=99 operations
RtZ = 102-3=99
AvgRt = (99+99)/4 = 49.5 19
 Shortest Job First
• This another nonpreemptive batch algorithm that
assumes the run times are known in advance.
• The scheduler picks the process with the shortest run
time
• Shortest job first is only optimal when all the jobs are
available simultaneously
• Shortest job first is provably optimal.
• Consider the case of four jobs, with run times of a, b, c,
and d, respectively.
– The first job finishes at time a, the second finishes at time a + b,
and so on.
– The mean turnaround time is (4a + 3b + 2c + d)/4
– It is clear that a contributes more to the average than the other
times, so it should be the shortest job, with b next, then c, and
finally d as the longest as it affects only its own turnaround time

20
 Shortest Job First
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 5 15 15 1.5
X 0 100 65 165 165 1.65
Y 0 5 0 5 5 1
Z 0 50 15 65 65 1.35
Mean 62.5 1.38

• Throughput = 4/165 = 0.024

• Avg Turnaround time = 15+165+5+65
= 62.5
21
 Shortest Job First
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 5 15 15 1.5
X 0 100 65 165 165 1.65
Y 0 5 0 5 5 1
Z 0 50 15 65 65 1.35
Mean 62.5 1.38

Waiting time:
WtW = 5-0 = 5
WtX = 65-0 = 65
WtY = 0-0 = 0
WtZ = 15-0 = 15
Avg Wt = (5+65+0+15)/4 = 21.25
22
 Shortest Job First
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 5 15 15 1.5
X 0 100 65 165 165 1.65
Y 0 5 0 5 5 1
Z 0 50 15 65 65 1.35
Mean 62.5 1.38

Response Time:
RtW = 5-0 = 5
RtX = 65-0 = 65
RtY = 0-0 = 0
RtZ = 15-0 = 15
Avg Rt = (5+65+0+15)/4 = 21.25
23
Shortest Remaining Time Next
• It is a preemptive version of shortest job first
• The scheduler always chooses the process
whose remaining run time is the shortest
• When a new job arrives, its total time is
compared to the current process’ remaining time
– If the new job needs less time to finish than the current
process, the current process is suspended and the
new job started
• This scheme allows new short jobs to get good
service

24
 Shortest Remaining Time Next
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 0 16 16 1.6
X 1 5 1 7 6 1.2
Y 2 1 2 3 1 1
Z 3 50 16 66 63 1.26
W

Z
25
0 1 2 34 7 16 66 Time
 Shortest Remaining Time Next
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 0 16 16 1.6
X 1 5 1 7 6 1.2
Y 2 1 2 3 1 1
Z 3 50 16 66 63 1.26
Turnaround Time:
TrW = 16-0 = 16 Throughput = 4/66 = 0.063
TrX = 7-1 = 6
TrY = 3-2 = 1
TrZ = 66-3 = 63
Avg Tr = (16+6+1+63)/4 = 21.5

26
Shortest Remaining Time Next
W

1 2 34 7 16 66 Time
Waiting Time:
WtW = 7-1 = 6
WtX = 3-2 = 1
WtY = 0
WtZ = 16 – 3 = 13
Avg Wt = (6+1+0+13)/4 = 5 27
 Shortest Remaining Time Next
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
W 0 10 0 16 16 1.6
X 1 5 1 7 6 1.2
Y 2 1 2 3 1 1
Z 3 50 16 66 63 1.26
Response Time:
RtW = 0-0 = 0
RtX = 1-1 = 0
RtY = 2-2 = 0
RtZ = 16-3 = 13
Avg Rt = 13/4 = 3.25 28
 Round-Robin Scheduling
• One of the oldest, simplest, fairest, and most widely
used algorithm.
• Each process is assigned a time interval, called its
quantum, which it is allowed to run.
• At the end of the quantum, the CPU is preempted
and given to another process
• Round robin is easy to implement
– scheduler needs to maintain a list of runnable processes
– When the process uses up its quantum, it is put on the
end of the list
• Limitation
– Overhead involved in handling the clock interrupt and
performing the scheduling and dispatching function
– Relative treatment of processor-bound and I/O-bound
processes 29
 Round-Robin Scheduling
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
A 0 3 0 4 4 1.33
B 2 6 2 18 16 2.66
C 4 4 5 17 13 3.25
D 6 5 7 20 14 2.8
E 8 2 10 15 7 3.5

q=1
 Round-Robin Scheduling
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
A 0 3 0 4 4 1.33
B 2 6 2 18 16 2.66
C 4 4 5 17 13 3.25
D 6 5 7 20 14 2.8
E 8 2 10 15 7 3.5

Turnaround time:
TrA = 4-0 = 4
TrB = 18-2 = 16
TrC = 17-4 = 13
TrD = 20-6 = 14
TrE = 15-8 = 7
Avg Tr = (4+16+13+14+7)/5 = 10.8 31
 Round-Robin Scheduling
Process Arrival Service Start Finish Turnaround Tr/Ts
Time Time Time Time Time
A 0 3 0 4 4 1.33
B 2 6 2 18 16 2.66
C 4 4 5 17 13 3.25
D 6 5 7 20 14 2.8
E 8 2 10 15 7 3.5

Response Time:
RtA = 0-0 = 0
RtB = 2-2 = 0
RtC = 5-4 = 1
RtD = 7-6 = 1
RtE = 10-7 = 3
Avg Rt = (0+0+1+1+3)/5 =1 32
Round-Robin Scheduling

Waiting time:
WtA = 1
WtB = 1+1+2+3+3 = 10
WtC = 1+2+3+3 = 9
WtD = 1+3+3+2 = 9
WtE = 2+3 = 5
Avg Wt = (9+9+5)/5 =4.6
33
 Priority Scheduling
• Each process is assigned a priority (int), and the
runnable process with the highest priority is allowed
to run
• High priority process may run indefinitely (starvation
of low priority processes)
– Aging - the scheduler may decrease the priority of the
currently running process at each clock tick
– Alternatively, each process may be assigned a maximum
time quantum that it is allowed to run
• Priorities can be assigned to processes
– Statically
• Predefined before the system starts
– Dynamically
• I/O-bound processes might be given high priority by the system
• Aging
34
 Priority Scheduling
Process Arrival Processing Priority
Time Time

A 0 8 3

B 1 3 1 (lowest)

C 3 5 2

D 5 2 10 (highest)

35
 Multiple Queue Scheduling
• It is often convenient to group processes
into priority classes:
– use priority scheduling among the classes
– round-robin scheduling within each class

36
 Thread Scheduling
• 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
– If it uses up the process’ entire quantum, the
kernel will select another process to run
– Round-robin scheduling and priority scheduling
are most common
– The only constraint is the absence of a clock to
interrupt a thread that has run too long 37
 Thread Scheduling
• Kernel-level threads
– Here the kernel picks a particular thread to run
– The thread is given a quantum and is forceably
suspended if it exceeds the quantum
• With kernel-level threads it requires a full context
switch, changing the memory map, and
invalidating the cache, which is several orders of
magnitude slower => Low performance (for system)
• On the other hand, with kernel-level threads,
having a thread block on I/O does not suspend
the entire process as it does with user-level
threads => Higher Performance (for process) 38
 Thread Scheduling

(a) Possible scheduling of user-level threads with a 50-msec process quantum

and threads that run 5 msec per CPU burst.
(b) Possible scheduling of kernel-level threads with the same characteristics as39(a)
 Multiple-Processor Scheduling
We can classify multiprocessor systems as follows:
• Loosely coupled or distributed multiprocessor, or
cluster:
– Consists of a collection of relatively autonomous systems, each
processor having its own main memory and I/O channels
• Functionally specialized processors:
– there is a master, general-purpose processor; specialized processors
are controlled by the master processor and provide services to it.
• Tightly coupled multiprocessing:
– Consists of a set of processors that share a common main memory
and are under the integrated control of an operating system
• Multicore CPUs: multiple computing cores, each appear
logical CPU to the operating system.
• In multiprocessor systems threads can be used to exploit
true parallelism in an application
• Scheduling algorithms in multiprocessing focuses on thread
scheduling 40
 Multiple-Processor Scheduling
• Four general approaches:
1. Load sharing:
– Processes are not assigned to a particular processor.
– A global queue of ready threads is maintained, and each
processor, when idle, selects a thread from the queue
2. Gang scheduling:
– A set of related threads is scheduled to run on a set of
processors at the same time, on a one-to-one basis
3. Dedicated processor assignment:
– Each program is allocated a number of processors equal to the
number of threads in the program, for the duration of the
program execution.
– When the program terminates, the processors return to the
general pool for possible allocation to another program
4. Dynamic scheduling:
– The number of threads in a process can be altered during the
41
course of execution
 Real-Time Scheduling
• A real-time system is one in which time plays an
essential role
• Hard real-time systems
– required to complete a critical task within a guaranteed amount
of time
• Soft real-time computing
– requires that critical processes receive priority over less
fortunate ones
• Aperiodic events
– Events which occur unpredictably that a real-time system may
have to respond
• Periodic events
– occurring at regular intervals
• Real-time systems which responds to periodic events
are schedulable
42
 Scheduling Examples
• Linux
– Uses Completely Fair Scheduler (CFS)
– Applies different scheduling algorithms based
on the type of the system and its processes
– Considerations: nice value, targeted latency,
virtual runtime
• Windows
– Uses priority-based, preemptive scheduling
– Has multiple priority-classes: normal, high,
realtime, etc priority classes.

43
THANK YOU.

44