Transcript P 1

CS444/CS544
Operating Systems
Scheduling
1/31/2007
Prof. Searleman
[email protected]
CS444/CS544

Spring 2007
CPU Scheduling
Reading assignment:

Chapter 5
HW#3: done in lab 2-2-2007
HW#4 posted, due: 2-7-2007
Help for Lab1, 6-7 pm tonight in ITL/COSI
Benefits of Concurrency

Hide latency of blocking I/O without additional
complexity




Without concurrency
 Block whole process
 Manage complexity of asynchronous I/O (periodically
checking to see if it is done so can finish processing)
Ability to use multiple processors to accomplish the
task
Servers often use concurrency to work on multiple
requests in parallel
User Interfaces often designed to allow interface to
be responsive to user input while servicing long
operations
Scheduling





CPU or “short term” scheduler selects process
from ready queue (every 10 msec or so)
“dispatcher” does the process switching
“long-term” scheduler controls “degree of
multiprogramming” (number of processes in
memory); selects a good “job mix”
“job mix” – I/O-bound, CPU-bound, interactive,
batch, high priority, background vs. foreground,
real-time
“non-preemptive” (cooperative) vs. “preemptive”
Performance Measures




Throughput: #processes/time unit
Turnaround time: time completed – time submitted
Waiting time: sum of times spent in ready queue
Response time: time from submission of a request
until the first response is produced



Variation of response time (predictability)
CPU utilization
Disk (or other I/O device) utilization
I/O-bound & CPU-bound
Device1
P1
CPU
time quantum
Device2
P2
CPU
I/O-bound & CPU-bound
P1: CPU-bound
Device1 idle
Device1 idle
CPU idle
Device1 idle
CPU idle
Turnaround time for P1
I/O-bound & CPU-bound
P2: I/O-bound
Device2 idle
Device2 idle
CPU idle
CPU idle
Turnaround time for P2
I/O-bound & CPU-bound
Schedule1: non-preemptive, P1 selected first
Turnaround time for P1
Turnaround time for P2
Without P1
I/O-bound & CPU-bound
Schedule2: non-preemptive, P2 selected first
Turnaround time for P1
Turnaround time for P2
I/O-bound & CPU-bound
How does the OS know whether a process is
I/O-bound or CPU-bound?
- can monitor the behavior of a process & save the
info in the PCB
- example: how much CPU time did the process use
in its recent time quanta? (a small fraction => I/O
intensive; all of the quantum => CPU intensive)
The nature of a typical process changes from I/Obound to CPU-bound and back as it works through
its Input/Process/Output Cycle
Preemptive vs. Non-Preemptive
t0
ready:
P1, P2
t2
t1
ready: P2
blocked: P1
Preemptive vs. Non-Preemptive
Non-Preemptive: must continue to run P1 at t3
Preemptive: can choose between P1 & P2 at t3
t2
ready: P1
blocked: P2
t3
ready: P2
running: P1
New
admit
dispatch
Ready
(2)
interrupt
(3)
I/O completed
or event occurs
(4)
exit,
abort
Terminated
Running
(1)
block for I/O
or wait for event
Waiting
• nonpreemptive (cooperative): (1) and (4) only
• preemptive: otherwise
First Come First Serve (FCFS)



Also called First In First Out (FIFO)
Jobs scheduled in the order they arrive
When used, tends to be non-preemptive



If you get there first, you get all the resource until
you are done
“Done” can mean end of CPU burst or completion
of job
Sounds fair


All jobs treated equally
No starvation (except for infinite loops that
prevent completion of a job)
Process CPU
burst
P1
18
FCFS
Gantt chart
P2
2
P3
4
P1
0
P3
P2
18
20
P1, P2, P3
ready

average waiting time = (0 + 18 + 20)/3 = 12.6
24
Problems with FCFS/FIFO

Can lead to poor overlap of I/O and CPU



If let first in line run till they are done or block for
I/O then can get convoy effect
While job with long CPU burst executes, other
jobs complete their I/O and the I/O devices sit idle
even though they are the “bottleneck” resource
and should be kept as busy as possible
Also, small jobs wait behind long running jobs
(even grocery stores know that)

Results in high average turn-around time
Shortest Job First (SJF)

So if we don’t want short running jobs waiting
behind long running jobs, why don’t we let the
job with the shortest CPU burst go next


Can prove that this results in the minimum
(optimal) average waiting time
Can be preemptive or non-preemptive

Preemptive version called shortest-remaining-time
first (SRTF)
Process CPU
burst
P1
18
SJF
Gantt chart
0
2
2
P3
4
P1
P3
P2
P2
6
P1, P2, P3
ready

average waiting time = (0 + 2 + 6)/3 = 2.6
24
SJF
nonpreemptive
Process Arrival
time
CPU
burst
P1
P2
P3
P4
7
4
1
4
P1
0
2
P1
ready
0
2
4
5
P3
4
5
7
P1 running
P2 , P3 ready
P2
8
P4
12
P1 running
P2 , P3 , P4 ready
P1 running
P2 ready

average waiting time = (0 + 6 + 3 + 7)/4 = 4
16
SRTF
preemptive
P2
P1
0
2
P1
ready
P1 running
P2 ready

CPU
burst
P1
P2
P3
P4
7
4
1
4
0
2
4
5
P2
P3
4
Process Arrival
time
5
P2 running
P1 , P3 ready
P4
7
P1
11
16
P1 , P4 ready
P3 completes
P1 , P2 , P4 ready
average waiting time = (9 + 1 + 0 + 2)/4 = 3
P1 ready
Process turnaround
Time
SRTF
preemptive
0


2
16 – 0 = 16
7–2=5
5–4=1
11 – 5 = 6
P1
P2
P3
P4
P2
P1
P2
P3
4
5
waiting
Time
P4
7
9
1
0
2
P1
11
average waiting time = (9 + 1 + 0 + 2)/4 = 3
average turnaround time = (16 + 5 + 1 + 6)/4
16
Problems with SJF

First, how do you know which job will have
the shortest CPU burst or shortest running
time?


Can guess based on history but not guaranteed
Bigger problem is that it can lead to
starvation for long-running jobs

If you never got to the head of the grocery queue
because someone with a few items was always
cutting in front of you