Transcript Operating Systems I: Chapter 5

Chapter 5: CPU Scheduling
•
•
•
Efficiency Goal: Some (useful) process running at all times if such a
process exists
– Maximum of one process running (uniprocessor)
– CPU–I/O Burst Cycle
 Process execution consists of a cycle of CPU execution and
I/O wait
 CPU burst distribution is not uniform
Approaches:
– Batch: Reduce I/O / setup cost
– Multiprogramming: Context switch on I/O
– Time-sharing (multi-tasking): Context switch on I/O or expiration
of quantum
Maximum CPU utilization obtained with multiprogramming
– Why?
CEG 433/633 - Operating Systems I
5.1
Dr. T. Doom
Histogram of CPU-burst Times
CEG 433/633 - Operating Systems I
5.2
Dr. T. Doom
Context Switch
•
•
•
•
Assumption of Finite Progress: Processes move forward in execution
in a sequential fashion, a temporal halt does not effect the correctness of
the execution and thus allowed. Execution rate is positive, but unknown
A context switch (and thus a CPU scheduling decision) takes place on:
1. Process state changes from running to waiting
2. Process state changes from running to terminated
3. Process state changes from waiting to ready
4. Process state changes from running to ready
Non-preemptive: a process keeps the CPU until it releases it through its
own actions (initiate I/O or termination) (1 and 2, above)
– MS-Windows is non-preemptive
Preemptive: “outside” events may cause context switch (3 and 4)
– subject to race-conditions
CEG 433/633 - Operating Systems I
5.3
Dr. T. Doom
Scheduler and Dispatcher
•
•
•
•
•
Almost all computer resources are allocated (scheduled) before
use. The CPU is one of the primary resources.
CPU Scheduler: selects from among the processes in memory
that are ready to execute, and allocates the CPU to one of them
The Dispatcher carries out the scheduler decision
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
CEG 433/633 - Operating Systems I
5.4
Dr. T. Doom
Scheduling Criteria
•
•
•
CPU utilization – keep the CPU as busy as possible (0-100%)
•
Waiting time – amount of time a process waits in the ready queue
– Note: This is the metric the scheduling algorithm really affects - it
can not directly reduce wait time (I/O) or execution time (on CPU)
•
Response time – amount of time it takes from when a request was
submitted until the first I/O is produced. Very useful for interactive
processes (such as a shell) where I/O speed is not relevant
•
Throughput – # of processes that complete their execution per time unit
Turnaround time – amount of time to execute a particular process (from
entering the system to leaving the system)
Optimize for overall (average) performance - but to be fair we want to
minimize additional metrics (such as maximum turnaround time, etc.)
CEG 433/633 - Operating Systems I
5.5
Dr. T. Doom
First-Come, First-Served (FCFS) Scheduling
•
•
Example:
Process
Burst Time (ms)
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
Average turn-around time (24+27+30)/3 = 27
CEG 433/633 - Operating Systems I
5.6
Dr. T. Doom
FCFS Scheduling (Cont.)
•
Suppose that the processes arrive in the order, P2 , P3 , P.
The Gantt chart for the schedule is
P2
0
–
–
–
–
•
•
P3
P1
3
6
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Average turn-around time: (30+ 3+ 6)/3 = 13
Much better than previous case
30
FCFS is non-preemptive, no “decisions”, performance is poor
(average turn-around time tends to be large)
Convoy effect: All of the short process (I/O-bound) are slowed
behind the long processes (CPU-bound). I/O sits idle when, for
the small price of a preemption and short CPU-burst, it could be
doing useful work
CEG 433/633 - Operating Systems I
5.7
Dr. T. Doom
Shortest-Job-First (SJR) Scheduling
•
•
Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest time.
– Provably optimal (gives minimum average waiting time for a
given set of processes) but requires historic
knowledge/hints (req. time) or an oracle (req. magic)
 Example: predict next CPU burst length as an
exponential average of its history
Two schemes:
– nonpreemptive – once CPU 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 know as the
Shortest-Remaining-Time-First (SRTF).
CEG 433/633 - Operating Systems I
5.8
Dr. T. Doom
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
Average turn-around time = ((7-0)+(8-4)+(12-2)+(16-5))/4 = 8
CEG 433/633 - Operating Systems I
5.9
Dr. T. Doom
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): Assume no effective overhead for switch
P1
0
•
•
P2
2
P3
4
P2
5
P4
7
P1
11
16
Average waiting time = (9 + 1 + 0 +2)/4 = 3
Average turn-around time = (16 + 5 + 1 + 6)/4 = 7
CEG 433/633 - Operating Systems I
5.10
Dr. T. Doom
Determining Length of Next CPU Burst
•
•
Can only estimate the length.
Can be done by using the length of previous CPU bursts, using
exponential averaging.
1. tn  actual lenght of nthCPU burst
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :
 n1   tn  1    n .
CEG 433/633 - Operating Systems I
5.11
Dr. T. Doom
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 -1 + …
+(1 -  )n=1 tn 0
Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor.
CEG 433/633 - Operating Systems I
5.12
Dr. T. Doom
Priority Scheduling
•
•
•
•
•
•
•
A priority number (integer) is associated with each process
(smallest integer  highest priority).
The CPU is allocated to the process with the highest priority
– Ties are usually handled FCFS
Preemptive or Non-preemptive
SJF is a priority scheduling algorithm
– priority is the predicted next CPU burst time
Problem: Starvation – low priority processes may never execute
Solution: Aging – as time progresses increase the priority of the
process
Note: Priority is often based on process-type. Interactive or I/Obound processes have a higher priority that CPU-bound processes
CEG 433/633 - Operating Systems I
5.13
Dr. T. Doom
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.
FCFS but with a switch every quantum
– “Circular” Queue
Performance depend on quantum
– Turnaround time and overhead Vary with Time Quantum
– q
 FCFS
– q0
 context switch overhead 100% of CPU time
Non optimal (SJF is better) but response time is less/better
CEG 433/633 - Operating Systems I
5.14
Dr. T. Doom
Example: RR with Time Quantum = 20
•
Process
Burst Time
P1
53
P2
17
P3
68
P4
24
The Gantt chart is:
P1
0
P2
20
CEG 433/633 - Operating Systems I
37
P3
P4
57
P1
77
P3
97 117
5.15
P4
P1
P3
P3
121 134 154 162
Dr. T. Doom
Multilevel Queue
•
•
Ready queue is partitioned into separately scheduled queues:
foreground (interactive) - RR
background (batch)
- FCFS (or priority, or preemptive SJF)
Scheduling must be done between the queues.
– Fixed priority scheduling; i.e., serve all from high priority queue
before considering next priority. Possibility of starvation.
– Time slice – each queue gets a certain amount of CPU time which
it can schedule amongst its processes; i.e., 80% interactive, 20%
batch
CEG 433/633 - Operating Systems I
5.16
Dr. T. Doom
Multilevel Feedback Queue
•
•
•
The standard multilevel queue algorithm does not allow a
process to change queues
Using feedback/history, a process can be moved 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
CEG 433/633 - Operating Systems I
5.17
Dr. T. Doom
Example of Multilevel Feedback Queue
•
•
•
Three queues:
– Q0 – time quantum 8 milliseconds
– Q1 – 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.
Most general scheduling algorithm
CEG 433/633 - Operating Systems I
5.18
Dr. T. Doom
CPU Scheduling in UNIX
•
•
•
•
•
•
Three classes of processes: Time Sharing, Interactive, Real Time
Processes are given small CPU time slices that reduce to roundrobin for CPU-bound jobs
– Designed to benefit interactive processes
Each process has a scheduling priority (large # is low priority)
– Set locally, check with priocntl -l (-60 to 60 is common)
Processes with priority < 0 are doing I/O or OS tasks
– such processes can not be killed by signals!
Ordinary user processes have priority > 0
– “nice” can be used to set priority
The more CPU time a process accumulates the more positive its
number (negative feedback)
– Gives short-term scheduler some control over “job mix”
– Aging prevents starvation
CEG 433/633 - Operating Systems I
5.19
Dr. T. Doom
Multiple-Processor Scheduling
•
•
•
•
CPU scheduling more complex when multiple CPUs are available
– If processors are identical (homogeneous), then we can simply
focus on load-sharing
Use a common ready queue
Asymmetric multiprocessing – only one processor accesses the
system data structures, alleviating the need for data sharing
Symmetric multiprocessing - any CPU can access system data
structures (such as the ready queue)
– More efficient
– More reliable if race conditions are avoided
CEG 433/633 - Operating Systems I
5.20
Dr. T. Doom
Algorithm Evaluation
•
•
•
•
•
Deterministic modeling –
– Define performance for a synthetic workload
Queuing models - Queuing Network Analysis (Theoretic)
Simulation - Random interarrival, burst length, etc.
Implementation - Experimentation in real conditions
Look for major problems and solutions...
– Livelock (starvation)
 Solution: Aging
– Priority Inversion - What if a high priority process needs to access
resources held by a low priority process? Does the high priority
process must wait on the low-priority process?
 Solution: Priority Inheritance - Upgrade the lower priority
process until required resource is released
 Is this a good solution?
CEG 433/633 - Operating Systems I
5.21
Dr. T. Doom