/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Scheduling algorithms
Shortest-Job-First Scheduling
This algorithm associates with ach process the length of the latter’s next CPU burst.
When the CPU is available, it is assigned to the process that has the smallest next CPU
burst. If two processes have the same length next CPU burst, FCFS scheduling is used to
break the tie. The real difficulty with the SJF algorithm is in knowing the length of the
next CPU request. For long term scheduling in a batch system, we can use as the length
the process time limit that a user specifies when he submits the job.
For short-term CPU scheduling, there is no way to length of the next CPU burst. One
approach is to try to approximate SJF scheduling, by assuming that the next CPU burst
will be similar in length to the previous ones, for instance.
The next CPU burst is generally predicted as an exponential average of the measured
lengths of previous CPU bursts. Let tn be the length of the nth CPU burst and 
our predicted value for the next CPU burst. We define
where, 0 ≤ α ≤ 1. We discuss this equation in detail in a subsequent lecture.
The SJF algorithm may either be preemptive or non-preemptive. The choice arises
when a new process arrives at the ready queue while a previous process is executing. The
new process may have a shorter next CPU burst than what is left of the currently
executing process. A preemptive SJF algorithm preempts the currently executing process,
whereas a non-preemptive SJF algorithm will allow the currently running process to
finish its CPU burst. Preemptive SJF scheduling is sometimes called shortestremaining-
time-first scheduling.
We illustrate the working of the SJF algorithm by using the following system state.
The Gantt chart for the execution of the four processes using SJF is shown in Figure 15.1.
Figure 15.1 Gantt chart showing execution of processes using SJF
Here is the average waiting time per process.
- Average waiting time = (0 + 6 + 3 + 7)/4 = 4 time units
We illustrate the working of the SRTF algorithm by using the system state shown above. The Gantt chart for the execution of the four processes using SRTF is shown in Figure 15.2.
Figure 15.2 Gantt chart showing execution of processes using SRTF
Here is the average waiting time per process.
- Average waiting time = (9 + 1 + 0 +2)/4 = 3 time units
Priority Scheduling
SJF is a special case of the general priority-scheduling algorithm. A priority is
associated with each process, and the CPU is allocated to the process with the highest
priority (smallest integer ≡ highest priority). Equal priority processes are scheduled in
FCFS order. The SJF algorithm is simply a priority algorithm where the priority (p) is the
inverse of the (predicted) next CPU burst. The larger the CPU burst of a process, the
lower its priority, and vice versa.
Priority scheduling can either be preemptive or non-preemptive. When a process
arrives at the ready queue, its priority is compared with the priority of the currently
running process. 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 ready queue.
A major problem with priority- scheduling algorithms is indefinite blocking (or
starvation). A process that is ready to run but lacking the CPU can be considered
blocked-waiting for the CPU. A priority-scheduling algorithm can leave some low
priority processes waiting indefinitely for the CPU. Legend has it that when they were
phasing out IBM 7094 at MIT in 1973, they found a process stuck in the ready queue
since 1967!
Aging is solution to the problem of indefinite blockage of low-priority processes. It involves gradually increasing the priority of processes that wait in the system for a long time. For example, if priority numbers range from 0 (high priority) to 127 (high priority), we could decrement priority of every process periodically (say every 10 minutes). This would result in every process in the system eventually getting the highest priority in a reasonably short amount of time and scheduled to use the CPU.
Google +