|
Snapshot of the Word file:"Module 6: CPU Scheduling_Module 6: CPU SchedulingBasic ConceptsScheduling Criteria Scheduling AlgorithmsM".doc
Module 6:
CPU Scheduling
Basic Concepts
Scheduling Criteria
Scheduling Algorithms
Multiple-Processor Scheduling
Real-Time Scheduling
Algorithm Evaluation
Basic Concepts
Maximum CPU utilization
obtained with multiprogramming
CPU–I/O Burst Cycle
– Process execution consists of a cycle of CPU execution and
I/O wait.
CPU burst distribution
Alternating Sequence
of CPU And I/O Bursts
Histogram of CPU-burst
Times
CPU 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:
1.Switches from running to waiting
state.
2.Switches from running to ready
state.
3.Switches from waiting to ready.
4.Terminates.
Scheduling under 1 and
4 is nonpreemptive.
All other scheduling
is preemptive.
Dispatcher
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.
Scheduling Criteria
CPU utilization – keep
the CPU as busy as possible
Throughput – # of processes
that complete their execution per time unit
Turnaround time – amount
of time to execute a particular process
Waiting time – amount
of time a process has been wiating in the ready queue
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)
Optimization Criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
First-Come, First-Served
(FCFS) Scheduling
Example:Process
Burst Time
P1
24
P2
3
P3
3
P1
P2
P3
24
27
30
0
Suppose that the processes
arrive in the order: P1 , P2
, P3
The Gantt Chart for the schedule is:
Waiting time for P1
= 0; P2 = 24; P3
= 27
Average waiting time:
(0 + 24 + 27)/3 = 17
FCFS Scheduling
(Cont.)
Suppose that the processes arrive
in the order
P2 , P3
, P1 .
P1
P3
P2
6
3
30
0
The Gantt chart 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
(SJR) 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:
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).
SJF is optimal – gives
minimum average waiting time for a given set of processes.
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
P3
P2
7
3
16
0
P4
8
12
Average waiting time
= (0 + 6 + 3 + 7)/4 - 4
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)
P1
P3
P2
4
2
11
0
P4
5
7
P2
P1
16
Average waiting time
= (9 + 1 + 0 +2)/4 - 3
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.
Examples of Exponential
Averaging
|