- Basic Concepts
- Scheduling Criteria
- Scheduling Algorithms
- Multiple-Processor Scheduling
- Real-Time Scheduling
- Algorithm Evaluation
- Maximum CPU utilization obtained with multi programming.
- CPU-I/O Burst Cycle - Process execution consists of a cycle of CPU
execution and I/O wait.
- CPU burst distribution
- Short-term 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:
- switches from running to waiting state.
- switches from running to ready state.
- switches from waiting to ready.
- Scheduling under 1 and 4 is non-preemptive (cooperative).
- All other scheduling is preemptive.
- 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
- Dispatch latency - time it takes for the dispatcher to stop one process
and start another running.
- CPU utilization - keep the CPU as busy as possible
- Throughput - # of processes that complete their execution per time
- Turnaround time - amount of time to execute a particular process
- Waiting time - amount of time a process has been waiting in the ready
- 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)
- Max CPU utilization
- Max throughput
- Minimum turnaround time
- Minimum waiting time
- Minimum response time
First-Come, First-Served (FCFS) Scheduling
Process Burst time
Suppose that the processes arrive in the order:
P1, P2, P3.
A diagram to show this schedule is:
Waiting time for:
P1 = 0
P2 = 24
P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
Suppose that the processes arrive in the order:
P2 , P3 , P1.
The diagram for the schedule is:
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
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 time.
- Two schemes:
a) non-preemptive - once CPU given to the process it cannot be preempted
until it completes its CPU burst.
b) 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
Example of SJF
Process Arrival time CPU time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Average waiting time = (9 + 1 + 0 + 2)/4 = 3
How do we know the length of the next CPU burst?
- Can only estimate the length.
- Can be done by using the length of previous CPU bursts, using exponential
- Tn = actual length of n'th CPU burst
- Pn = predicted value of n'th CPU burst
- 0 <= W <= 1
Pn+1 = W * Tn + (1-W) Pn
- W = 0
Pn+1 = Pn
Recent history does not count.
- W = 1
Pn+1 = Tn
Only the actual last CPU burst counts.
- If we expand the formula, we get:
Pn+1 = W Tn+ (1-W ) W Tn-1+ (1-W)2
W Tn-2+ ... + (1 - W )q W Tn-q
So if W = 1/2 - each successive term has less and less weight.
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.
q large -> FIFO
q small -> q must be large with respect to context
switch, otherwise overhead is too high.
Example of RR with time quantum = 20
Process CPU times
- Typically, higher average turnaround than SRTF, but better response.
- Ready queue is partitioned into separate queues.
- Each queue has its own scheduling algorithm.
- Scheduling must be done between the queues.
- Fixed priority scheduling
- Time slice - each queue gets a certain amount of CPU time which it
can schedule amongst its processes.
Multilevel Feedback Queue
- A process can move between the various queues; aging can be implemented
- Multilevel-feedback-queue scheduler defined by the following parameters:
- number of queues
- scheduling algorithm 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
Example of multilevel feedback queue
- Three queues:
- Q0 - time quantum 8 milliseconds
- Q1 - time quantum 16 milliseconds
- Q2 - FCFS
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 .
- CPU scheduling more complex when multiple CPUs are available.
- Homogeneous processors within a multiprocessor (CPUs must be the same).
- Load sharing - use a common ready queue.
- Each processor schedules itself, or one processor is used for scheduling.
- Hard real-time systems - required to complete a critical task within
a guaranteed amount of time.
- Soft real-time computing - requires that critical processes receive
priority over less fortunate ones.
- Deterministic modeling - takes a particular predetermined workload
and defines the performance of each algorithm for that workload.
- Queuing models - make a mathematical model based on the distributions
of job start times and burst times.
- Simulation - write a program to schedule imaginary tasks using various
- Implementation - code the algorithms into the OS.
- 2 queues - ready and I/O request.
- FCFS simple but causes short jobs to wait for long jobs.
- SJF is optimal giving shortest waiting time but need to know length
of next burst.
- SJF is a type of priority scheduling - may suffer from starvation -
prevent using aging
- RR is gives good response time, it is preemptive. FCFS is non-preemptive
priority algorithms can be both. Problem selecting the quantum.
- Multiple queue Algorithms use the best of each algorithm by having
more than one queue. Feedback queues allow jobs to move from queue to queue.
- Algorithms may be evaluated by deterministic methods, mathematical
models and implementation.