6.3. CPU Scheduling RR Priority Scheduling.pptx
Download
Report
Transcript 6.3. CPU Scheduling RR Priority Scheduling.pptx
Priority Scheduling Example
Fixed (strict) priority scheduling
Process
Burst Time
P1
10
P2
1
P3
2
P4
1
P5
5
Priority scheduling Gantt Chart
0
P1
P5
P2
1
6
Average waiting time = 8.2 msec
P3
16
Priority
3
1
4
5
2
P4
18
19
Priority Scheduling
A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest priority (usually
smallest integer highest priority)
Preemptive
Nonpreemptive
SJF is priority scheduling where priority is the inverse of predicted
next CPU burst time
Equal-priority processes are scheduled in FCFS order
Problem Starvation (indefinite blocking) – low priority processes
may never execute
Solution Aging – as time progresses increase the priority of the
process
Internal / External Priorities
Priorities can be defined either internally to OS or externally
Internally defined priorities use some measurable quantity or
quantities to compute the priority of a process. For example,
time limits
memory requirements
the number of open files
the ratio of average I/O burst to average CPU burst have been used in
computing priorities
External priorities are set by criteria that are external to the
operating system such as the
Importance of the process
Urgency
…
Round Robin (RR)
• The round-robin (RR) scheduling algorithm is designed especially for
timesharing systems.
• It is similar to FCFS scheduling, but preemption is added to switch between
processes.
• A small unit of time, called a time quantum (or time slice), is defined.
• Adv:The RR provides acceptable response time for the processes.
• DAdv:The average waiting time under the RR policy is often quite long.
• Performance depends on time quantum length.
Example of RR with Time Quantum = 4 ms
Process
P1
P2
P3
Burst Time
24
3
3
The Gantt chart is:
P1
0
P2
4
P3
7
P1
10
P1
14
P1
18
22
P1
P1
26
30
Typically, higher average turnaround than SJF, but better response
q should be large compared to context switch time
q usually 10ms to 100ms, context switch < 10 usec
Time Quantum and Context Switch Time
If the time quantum is 1 time unit, then 9 context switches will occur, slowing the
execution of the process accordingly.
Turnaround Time Varies With The Time Quantum
Empiric Conclusion
80% of CPU bursts
should be shorter
than q
The average turnaround time of a set of processes does not necessarily
improve as the time-quantum size increases.
In general, the average turnaround time can be improved if most processes finish
their next CPU burst in a single time quantum.