Transcript CPU Scheduling

Module 2.2: 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
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
5
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
6
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
7
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
8
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
9
Operating Systems
SJF - Shortest Job First
SJF is Optimal:
Let t1, t2, t3,…, tn be the time taken for p1, p2, p3, …,pn
Also t1< t2<… < tn-1< tn then the average turn around times for pi
are:
Tp1= t1 ; Tp2= t1 + t2; Tp3= t1 + t2 + t1 ; … Tpn= t1 + t2 + …+ tn-1+tn ;
average turnaround time = TA = (Tp1+ Tp2 +…+ Tpn) / n
= t1+(t1+ t2 )+(t1+ t2 + t3 )+…+tn = nt1 + (n-1) t2 + (n-2) t3 + …+ tn ) / n
Now, if any of the tn is/are interchanged with tn-1 in the above
equation TA’ > TA , because (n-k) tj > (n-k) tk, where tj > tk
Assumptions ? – Can pi(s) arrival times be different ?
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…1]
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 = small value favor past history, larger value favors recent
Why is keeping the history small good enough ? – Do the weight of
the successive terms in the equation get smaller (why?)
t n+1 = a tn + (1 - a)a tn-1 + (1 - a)2a tn-2 +..+(1 - a)ja tn-j + +(1 - a)jt 0
K. Salah
11
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
12
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
13
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
14
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).
K. Salah
15
Operating Systems