Page 84 - DCAP403_Operating System

Unit 5: Scheduling

Notes
P 1 P 3 P 2 P 4

0 3 7 8 12 16
Average waiting time = (0 + 6 + 3 + 7)/4 = 4

2. SRT (preemptive SJB)
P P P P P P
1 2 3 2 4 1
0 2 4 5 7 11 16

Average waiting time = (9 + 1 + 0 +2)/4 = 3

5.3.3 Shortest Remaining Time (SRT)

Shortest remaining time is a method of CPU scheduling that is a preemptive version of shortest
job next scheduling. In this scheduling algorithm, the process with the smallest amount of time
remaining until completion is selected to execute. Since the currently executing process is the one
with the shortest amount of time remaining by definition, and since that time should only reduce

as execution progresses, processes will always run until they complete or a new process is added
that requires a smaller amount of time.
Shortest remaining time is advantageous because short processes are handled very quickly.
The system also requires very little overhead since it only makes a decision when a process
completes or a new process is added, and when a new process is added the algorithm only needs
to compare the currently executing process with the new process, ignoring all other processes
currently waiting to execute. However, it has the potential for process starvation for processes
which will require a long time to complete if short processes are continually added, though this
threat can be minimal when process times follow a heavy-tailed distribution.

Like shortest job first scheduling, shortest remaining time scheduling is rarely used outside of
specialized environments because it requires accurate estimations of the runtime of all processes
that are waiting to execute.

5.3.4 Priority Scheduling

A priority is associated with each process, and the CPU is allocated to the process with the highest
priority. Priority can be defined either internally or externally. Internally defined priorities use

some measurable quantities to compute the priority of a process.

Example: Time limits, memory requirements, no. of open files, ratio of average I/O burst
time to average CPU burst time etc. external priorities are set by criteria that are external to the
OS, such as the importance of the process, the type and amount of funds being paid for computer
use, the department sponsoring work and other often political factors.
Priority scheduling can be preemptive or non preemptive. A preemptive priority scheduling
algorithm will preempt the CPU if the priority of the newly arrived process is higher than the
priority of the currently running process. A non preemptive priority scheduling algorithm will
simply put the new process at the head of the ready queue.
A major problem with priority scheduling algorithms is indefinite blocking or starvation. This

can be solved by a technique called aging wherein I gradually increase the priority of a long
waiting process.

LOVELY PROFESSIONAL UNIVERSITY 77