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.