# CS604 - Operating Systems - Lecture Handout 15

User Rating:  / 0
PoorBest

## 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.