Transcript module_21

Module 2.1: CPU Scheduling
•
•
•
•
Scheduling Types
Scheduling Criteria
Scheduling Algorithms
Performance Evaluation
K. Salah
1
Operating Systems
CPU SCHEDULING
– The basic problem is as follows: How can OS schedule the
allocation of CPU cycles to processes in system, to achieve
“good performance”?
– Components of CPU scheduling subsystem of OS:
 Dispatcher – gives control of the CPU to the new
process
 Scheduler - selects next process from those in main
memory (short-term scheduler)
 Swapper - manages transfer of processes between
main memory and secondary storage (medium-term
scheduler)
 Long-Term Scheduler - in a batch system, determines
which and how many jobs to admit into system.
K. Salah
2
Operating Systems
Types of Scheduling Algorithms
– Preemptive: process may have CPU taken away before
completion of current CPU burst (e.g. end of CPU
quantum.)
– Non-preemptive: processes always run until CPU burst
completes
– Static Priority
– Dynamic Priority
K. Salah
3
Operating Systems
Performance Criteria for Scheduling
•
•
•
•
•
•
•
•
Scheduling (as an Optimization task):
How to best order the ready queue for efficiency purposes.
CPU utilization: % of time CPU in use
Throughput: # of jobs completed per time unit
Turnaround Time: wall clock time required to complete a job
Waiting Time: amount of time process is ready but waiting to run
Response Time: in interactive systems, time until system responds to a command
Response Ratio: (Turnaround Time)/(Execution Time) -- long jobs should wait longer
The overhead of a scheduling algorithm (e.g., data kept about execution activity,
queue management, context switches) should also be taken into account.
Kleinrock's Conservation Law:
•
•
No matter what scheduling algorithm is used, you cannot help one
class of jobs without hurting the other ones.
Example: A minor improvement for short jobs (say, on waiting time)
causes a disproportionate degradation for long jobs.
K. Salah
4
Operating Systems
Optimization Criteria
•
•
•
•
•
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
K. Salah
5
Operating Systems
Basic Scheduling Algorithm
•
•
•
FCFS - First-Come, First-Served
– Non-preemptive
– Ready queue is a FIFO queue
– Jobs arriving are placed at the end of queue
– first job in queue runs to completion of CPU burst
Advantages: simple, low overhead
Disadvantages: long waiting time, inappropriate for interactive
systems, large fluctuations in average turnaround time are
possible.
K. Salah
6
Operating Systems
FCFS Example
• Pid
Arr CPU Start Finish Turna Wait Ratio
---+---+---+-----+------+-----+----+----A
0
3
0
3
3
0
1.0
B
1
5
3
8
7
2
1.4
C
3
2
8
10
7
5
3.5
D
9
5
10
15
6
1
1.2
E 12
5
15
20
8
3
1.6
---+---+---+-----+------+-----+----+----A
0
1
0
1
1
0
1.00
B
0 100
1
101 101
1
1.01
C
0
1
101
102 102
101 102.00
D
0 100
102
202 202
102
2.02
K. Salah
7
Operating Systems
RR - Round Robin
•
•
Preemptive version FCFS
Treat ready queue as circular
– arriving jobs placed at end
– first job in queue runs until completion of CPU burst, or
until time quantum expires
– if quantum expires, job again placed at end
K. Salah
8
Operating Systems
Properties of RR
Advantages: simple, low overhead, works for interactive
systems
Disadvantages: if quantum too small, too much time wasted in
context switching; if too large, approaches FCFS.
Typical value: 10 - 100 msec
Rule of thumb: choose quantum so that large majority (8090%) of jobs finish CPU burst in one quantum
K. Salah
9
Operating Systems
SJF - Shortest Job First
– non-preemptive
– ready queue treated as a priority queue based on smallest
CPU-time requirement
 arriving jobs inserted at proper position in queue
 shortest job (1st in queue) runs to completion
Advantages: provably optimal w.r.t. average turnaround time
Disadvantages: in general, unimplementable. Also, starvation
possible!
Can do it approximately: use exponential averaging to predict
length of next CPU burst
==> pick shortest predicted burst next!
K. Salah
10
Operating Systems
Exponential Averaging
t n+1 = a tn + (1 - a) t n
tn+1 : predicted length of next CPU burst
tn : actual length of last CPU burst
tn : previous prediction
a = 0 implies make no use of recent history
(t n+1 = t n)
a = 1 implies tn+1 = tn (past prediction not used).
a = 1/2 implies weighted (older bursts get less and less weight).
K. Salah
11
Operating Systems
Prediction of the Length of the Next CPU Burst
K. Salah
12
Operating Systems
SRTF - Shortest Remaining Time First
– Preemptive version of SJF
– Ready queue ordered on length of time till completion
(shortest first)
– Arriving jobs inserted at proper position
– shortest job runs to completion (i.e. CPU burst finishes)
or until a job with a shorter remaining time arrives (i.e.
placed in the ready queue.)
K. Salah
13
Operating Systems
Performance Evaluation
•
Deterministic Modeling (vs. Probabilistic) Look at behavior of algorithm on a
particular workload, and compute various performance criteria
Example:
workload -
•
Job 1: 24 units
Job 2: 3 units
Job 3: 3 units
Gantt chart for FCFS:
| Job 1 | Job 2
0
24
| Job 3
27
|
30
Total waiting time: 0 + 24 + 27 = 51
Average waiting time: 51/3 = 17
Total turnaround time: 24 + 27 + 30 = 81
Average turnaround time: 81/3 = 27
K. Salah
14
Operating Systems
RR and SJF
•
Chart for RR with quantum of 3:
| Job 1 | Job 2 | Job 3 |
0
3
6
9
Job 1
|
30
Total waiting time: 6 + 6 + 3 = 15
Avg. waiting time: 15 / 3 = 5
•
Chart for SJF:
| Job 2 | Job 3 |
0
3
6
Job 1
|
30
Total waiting time: 6 + 0 + 3 = 9
Avg. waiting time: 9 / 3 = 3
•
Can see that SJF gives minimum waiting time. RR is intermediate. (This can
be proved in general.)
K. Salah
15
Operating Systems
HPF - Highest Priority First
– general class of algorithms
– each job assigned a priority which may change dynamically
– may be preemptive or non-preemptive
•
Problem: how to compute priorities?
– SJF is a special case of priority; the longer the CPU burst, the lower
the priority.
– Priority can be internally computed, e.g., CPU burst vs. I/O burst.
Or it can be externally defined depending on the importance of the
process, (e.g. using nice command in Unix).
– Effective Priority = System (Internal) + User defined
 System: type of process + age (dynamically changes)
K. Salah
16
Operating Systems
Windows XP Priorities
6 priority classes (shown with Task Manager)
7 default relative priorities/values (shown with Process
Explorer)
•16-31 (time critical)
•1-16 (others)
K. Salah
17
Operating Systems
Multilevel Queue Scheduling
K. Salah
18
Operating Systems
Multilevel Feedback Queue
•
•
•
•
A process is admitted to one class of queues
Schedule top queue processes first
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
K. Salah
19
Operating Systems
Example of Multilevel Feedback Queue
•
•
•
Attractive scheme for I/O bound jobs
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.
K. Salah
20
Operating Systems
Multilevel Feedback Queues
K. Salah
21
Operating Systems
Further Readings
•
•
When is processor affinity used?
In Windows XP, what is the default base priority for a process
when it gets created?
K. Salah
22
Operating Systems