Transcript Chapter 5

Chapter 6: CPU Scheduling
 Overview:

Basic Concepts

Scheduling Criteria

Scheduling Algorithms

Multiple-Processor Scheduling

Real-Time Scheduling

Algorithm Evaluation

Operating Systems Examples
Operating System Concepts
5.1
Silberschatz, Galvin and Gagne ©2005
Basic Concepts
 To Maximize CPU utilization, multiprogramming is used
 CPU–I/O Burst Cycle – Process execution consists of an
alternating sequence of CPU executions and I/O waits
 CPU burst distribution
Operating System Concepts
5.2
Silberschatz, Galvin and Gagne ©2005
Alternating Sequence of CPU And I/O Bursts
of a Process
Operating System Concepts
5.3
Silberschatz, Galvin and Gagne ©2005
Histogram of CPU-burst Times
Operating System Concepts
5.4
Silberschatz, Galvin and Gagne ©2005
CPU 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 non-preemptive
 All other scheduling is preemptive
Operating System Concepts
5.5
Silberschatz, Galvin and Gagne ©2005
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
Operating System Concepts
5.6
Silberschatz, Galvin and Gagne ©2005
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 taken 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)
Operating System Concepts
5.7
Silberschatz, Galvin and Gagne ©2005
Optimization Criteria
 A CPU scheduling algorithm should strive for

Maximizing CPU utilization

Maximizing throughput

Minimizing turnaround time

Minimizing waiting time

Minimizing response time

Making the users happy
Operating System Concepts
5.8
Silberschatz, Galvin and Gagne ©2005
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
0
24
P3
27
30
 Waiting time for P1 = 0; P2 = 24; P3 = 27
 Average waiting time: (0 + 24 + 27)/3 = 17
Operating System Concepts
5.9
Silberschatz, Galvin and Gagne ©2005
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order
P2 , P3 , P1
 The Gantt chart for the schedule is:
P2
0
P3
3
P1
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
Operating System Concepts
5.10
Silberschatz, Galvin and Gagne ©2005
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
CPU burst time.
 Two schemes:
nonpreemptive – once CPU is 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 known as the
Shortest-Remaining-Time-First (SRTF).

 SJF is optimal – gives minimum average waiting time for a given
set of processes.
 It is not possible to implement this algorithm even though it is
optimal because there is no way of knowing the next CPU burst.
Operating System Concepts
5.11
Silberschatz, Galvin and Gagne ©2005
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
0
3
P3
7
P2
8
P4
12
16
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Operating System Concepts
5.12
Silberschatz, Galvin and Gagne ©2005
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
0
P2
2
P3
4
P2
5
P4
P1
11
7
16
 Average waiting time = (9 + 1 + 0 +2)/4 = 3
Operating System Concepts
5.13
Silberschatz, Galvin and Gagne ©2005
Determining Length of Next CPU Burst
 Can only estimate the length of the next CPU burst
 Can be done by using the length of previous CPU bursts, using
exponential averaging
1. t n  actuallength of nth CPU burst
2.  n 1  predictedvalue for thenext CPU burst
3.  , 0    1
4. Define:
 n1   tn  1    n .
Operating System Concepts
5.14
Silberschatz, Galvin and Gagne ©2005
Prediction of the Length of the Next CPU Burst
(α =1/2)
Operating System Concepts
5.15
Silberschatz, Galvin and Gagne ©2005
Examples of 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 t0
 Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor
Operating System Concepts
5.16
Silberschatz, Galvin and Gagne ©2005
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). Under Linux, users can set
priority to processes using the nice command.

Preemptive

Nonpreemptive
 SJF is a priority scheduling algorithm where priority is the predicted
next CPU burst time
 Problem with priority scheduling: Starvation – low priority
processes may never execute

A Solution to this problem: Aging – as time progresses,
increase the priority of the process
Operating System Concepts
5.17
Silberschatz, Galvin and Gagne ©2005
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

How large q should be: q must be large with respect to
context switch, otherwise overhead is too high
Operating System Concepts
5.18
Silberschatz, Galvin and Gagne ©2005
Example of RR with Time Quantum = 20
Process
P1
P2
P3
P4
 The Gantt chart is:
P1
0
P2
20
37
P3
Burst Time
53
17
68
24
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
 Typically, higher average turnaround than SJF, but better response
time
Operating System Concepts
5.19
Silberschatz, Galvin and Gagne ©2005
Time Quantum and Context Switch Time
Operating System Concepts
5.20
Silberschatz, Galvin and Gagne ©2005
Turnaround Time Varies With The Time Quantum
Operating System Concepts
5.21
Silberschatz, Galvin and Gagne ©2005
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; e.g., 80% to
foreground in RR; 20% to background in FCFS
Operating System Concepts
5.22
Silberschatz, Galvin and Gagne ©2005
Multilevel Queue Scheduling
Operating System Concepts
5.23
Silberschatz, Galvin and Gagne ©2005
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
Operating System Concepts
5.24
Silberschatz, Galvin and Gagne ©2005
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.
Operating System Concepts
5.25
Silberschatz, Galvin and Gagne ©2005
Multilevel Feedback Queues
Operating System Concepts
5.26
Silberschatz, Galvin and Gagne ©2005
Multiple-Processor Scheduling
 CPU scheduling is more complex when multiple CPUs are available
 Some approaches for multiprocessor scheduling

Asymmetric multiprocessing: only one processor accesses the
system data structures, reducing the need for data sharing; scheduling
decisions are handled by this processor.

Symmetric multiprocessing (SMP): Each processor is self
scheduling. All processes may be in a common ready queue or each
processor may have its own ready queue

Each processor has its own scheduler.

Since multiple processors are trying to access and modify common
data structures (such as ready queue, etc), schedulers must be
carefully programmed.

Virtually all operating systems including Windows, Linux, and Mac
OS X support SMP.
Operating System Concepts
5.27
Silberschatz, Galvin and Gagne ©2005
Some issues related to SMP
 Processor affinity:

When a process running on a processor is migrated to another processor, the
contents of the cache memory for that processor must be invalidated and
repopulated to the cache of the processor to which the process is migrated.
This involves large overhead. To prevent this overhead, most SMP systems
try to avoid migration of processes from one processor to another processor
and instead keep a process running on the same processor. This is called
processor affinity.

Soft affinity: Operating system has a policy of attempting to keep a process
running on the same processor without guaranteeing to do so. Linux
implements soft affinity.

Hard affinity: Some operating systems allow a process to specify the set of
processors on which it may run. Linux provides support for hard affinity
through the system call sched_setaffinity().
Operating System Concepts
5.28
Silberschatz, Galvin and Gagne ©2005
Some issues related to SMP …
 Load balancing: This attempts to keep workload evenly distributed
across all processors. This is especially needed in systems where
each processor has its own queue which is the case in most
contemporary Operating systems.

Note that load balancing counteracts the benefits of
processor affinity. So, this is not an easy problem to solve.
 Two approaches for load balancing:

Push migration: a specific task periodically checks the load on
each processor and balances the load by moving (or pushing)
processes from overloaded processors to lightly loaded
processors.

Pull migration: Idle processor pulls a waiting task from a busy
processor.
 Linux scheduler implements both Push and Pull migration.
Operating System Concepts
5.29
Silberschatz, Galvin and Gagne ©2005
Some issues related to SMP …
 Multicore processors: Multiple processor cores are placed on a single physical
chip.

Each Core appears to the OS as a separate processor.

SMP systems that use multicore processors are faster and consume less power
than systems in which each processor is on a separate physical chip.
 Scheduling multicore processors: When a processor accesses memory, it waits
for the data to become available for reasons such as cache miss – called memory
stall.

To solve the memory stall problem, many recent hardware designs have
implemented multithreaded processor cores, in which two or more hardware
threads are assigned to each core.

This way the hardware can switch to another thread when a currently executing
thread is waiting for memory.

Coarse-grained multithreading: The usual way of switching threads

Fine-grained (or interleaved) multithreading: Thread switching occurs a
the boundary of an instruction cycle. The architectural design includes logic
for thread switching which results in further lowering switching overhead.
Operating System Concepts
5.30
Silberschatz, Galvin and Gagne ©2005
Some issues related to SMP …
 Scheduling Multicore processors (contd.): So, multithreaded
multicore scheduling requires scheduling at two different levels

1. at the Operating system level: For the OS may choose any
scheduling algorithm such as the one we discussed earlier.

2. at the hardware level: this scheduling specifies how each
core decides which hardware thread to run.

The UltraSPARC T3 uses a simple round-robin algorithm to
schedule eight hardware threads to each core.

The Intel Itanium dual-core processor assigns two hardware
threads for each core.
Operating System Concepts
5.31
Silberschatz, Galvin and Gagne ©2005
Real-time CPU scheduling
 Soft Real-time systems: Provides no guarantees as to when a
critical real-time process will be scheduled. It only guarantees that
the process will be given preference over noncritical processes.
Linux, Windows, Solaris, etc. support soft real-time scheduling.
 Hard Real-time systems: Guarantees that a critical task will be
serviced by its deadline. Different scheduling algorithms exist for
such systems. We will not talk about them here.
Operating System Concepts
5.32
Silberschatz, Galvin and Gagne ©2005
Algorithm Evaluation

Analytic evaluation


Queuing models: knowing the job arrival rates and service rates we can
compute CPU utilization, average queue length, average waiting time, etc.



Deterministic modeling – takes a particular predetermined workload
and compares the performance of each algorithm for that workload.
Simple and easy to do; but requires exact numbers for input which is
hard to get for any given system.
This is a separate area of research, called queuing-network analysis
Simulations

Involves programming a model of the system.

Results are of limited accuracy
Implementation

Implement the algorithm and study the performance

It is the best way to study and compare the performance of different
algorithms

It is expensive and time consuming
Operating System Concepts
5.33
Silberschatz, Galvin and Gagne ©2005
5.15
Operating System Concepts
5.34
Silberschatz, Galvin and Gagne ©2005
CPU Scheduling in Solaris 2
 Uses priority-based process scheduling
 It has four classes of scheduling which are in order of priority, real-time, system,
interactive and timesharing
 Each of these classes includes different priorities and scheduling algorithms
 Time sharing and interactive processes use the same scheduling algorithm
 The default scheduling class for a process is time sharing
 The scheduling policy for time sharing dynamically alters priorities and assigns
time slices of different length using multilevel feedback queue
 There is an inverse relationship between priorities and time slices: the higher the
priority, the smaller the time slice and the lower the priority, the larger the time
slice
 Interactive processes typically have a higher priority; CPU bound processes have
a lower priority.
 The scheduling policy is designed to give good response time for interactive
processes and good throughput for CPU bound processes
Operating System Concepts
5.35
Silberschatz, Galvin and Gagne ©2005
CPU Scheduling in Solaris 2…
 Interactive class uses the same scheduling policy as the timesharing class but it
gives windowing applications higher priority for better performance
 It uses the system class to run kernel processes such as scheduler, paging
daemon, etc

Priority of a system process, once established, never changes.

User processes running in system mode do not belong to system class

Scheduling policy for the system class does not time-slice. i.e., a process
belonging to the system class runs until it blocks or is preempted by a higher
priority process
 Processes in real-time class are given the highest priority to run among all
classes
Operating System Concepts
5.36
Silberschatz, Galvin and Gagne ©2005
CPU Scheduling in Solaris 2…
 Each scheduling class includes a set of priorities
 The scheduler converts this class specific priorities into global
priority and selects the process with the highest global priority. The
selected process runs on the CPU until one of the following
occurs:

It blocks

It uses its time-slice (if it is not a system process)

It is preempted by a higher priority process
Operating System Concepts
5.37
Silberschatz, Galvin and Gagne ©2005
Solaris 2 Scheduling
Operating System Concepts
5.38
Silberschatz, Galvin and Gagne ©2005
Scheduling in windows XP
 Windows XP uses a priority-based preemptive scheduling algorithm.
 It ensures that the highest priority process will always run
 A process selected by the scheduler (called dispatcher in windows) to run
will run until

It terminates

Its time quantum ends or

It calls a blocking system call, such as for I/O
 If a higher priority real-time process becomes ready while a lower priority
process is running, the lower priority process will be preempted, thus giving
a preferential treatment to real-time processes
 Scheduler uses a 32-level priority scheme to determine the order of process
execution, and also has several classes of process
Operating System Concepts
5.39
Silberschatz, Galvin and Gagne ©2005
Scheduling in windows XP
 The scheduler uses a queue for each scheduling priority (i.e., 32
queues) and traverses the set of queues from highest to lowest until
it finds a process to run. If no process is found, then it executes a
special process called idle thread
 Priorities are divided into two classes


The variable class

Contains processes having priorities from 1 to 15

Priority of processes in this class can change

This is further divided into high priority, above normal,
normal, below normal, and idle priority classes
The real-time class

Contains processes with priorities ranging from 16 to 31

Priorities of processes in this class do not change.
Operating System Concepts
5.40
Silberschatz, Galvin and Gagne ©2005
Windows XP Priorities
Win32 API identifies several priority classes to which a process can
belong. These include : Real-time, high, above normal, normal etc.
A process within a given priority also has a relative priority. The
values for these relative priorities include: time-critical, highest,
above normal, below normal, etc.
Operating System Concepts
5.41
Silberschatz, Galvin and Gagne ©2005
Scheduling in windows XP

Processes are typically members of normal priority class unless the parent process
was of the idle priority class or another class was specified when the process was
created

When a process’s time quantum runs out



The process is interrupted and its priority is lowered if it is in the variable priority
class

Lowering the priority helps in limiting CPU consumption of compute-bound
processes
When a variable-priority process is released from a wait operation, its priority is
boosted

The amount of boost depends on what the process was waiting for. For
example, a process waiting for keyboard I/O will get a large boost whereas a
process that was waiting for disc I/O will get a moderate boost.

This strategy gives good response time for processes that are using windows
and mouse (i.e., interactive processes), while compute-bound processes are
permitted to use the CPU cycles in the background. (this strategy is used by
other OSs as well)
Windows distinguishes between foreground (i.e., processes selected on the
screen) and background processes.

When a process moves to the foreground, it increases the quantum by some
factor – typically by 3.
Operating System Concepts
5.42
Silberschatz, Galvin and Gagne ©2005
Scheduling in Linux
 Linux provides two separate process-scheduling algorithms: one
is designed for time-sharing processes for fair preemptive
scheduling among multiple processes; the other, designed for
real-time tasks

A process may not be preempted while running in kernel
mode even if a real-time process with a higher priority is
ready
 For processes in the time-sharing class, Linux uses a prioritized
credit-based algorithm.

Each process (task) possesses a certain number of credits

When a new process must be chosen, the process with
most credit is selected

Every time a timer interrupt occurs, the currently running
process loses one credit. When the credit reaches 0, that
process is suspended and another process is selected
Operating System Concepts
5.43
Silberschatz, Galvin and Gagne ©2005
Scheduling in Linux…
 If no runnable processes have any credit, then Linux performs a
recrediting operation to every process in the system using the
following rule:

Credits = Credits/2 + priority

Note that I/O bound processes that remain suspended can get
multiple credits and hence will gain high priority; thus
interactive processes will have rapid response time

Using priority in calculating new credits allows the priority of a
process to be fine-tuned. i.e., batch jobs can be given low
priority and hence they will automatically receive fewer credits
than the interactive users’ jobs.
Operating System Concepts
5.44
Silberschatz, Galvin and Gagne ©2005
Scheduling in Linux…
 Real-time scheduling: Linux implements two real-time scheduling
classes, namely FCFS and RR

In both cases each process has a priority in addition to its
scheduling class.

Scheduler always runs the process with highest priority

Linux’s real-time scheduling is soft in the sense that it offers
strict guarantees about priorities but the kernel does not offer
any guarantees about how quickly a real-time process becomes
runnable (Linux kernel code can be never preempted by user –
mode code). For example, if an interrupt that wakes up a realtime process arrives while the kernel is already executing a
system call on behalf of some other process, the real-time
process has to just wait.
Operating System Concepts
5.45
Silberschatz, Galvin and Gagne ©2005