/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Scheduling algorithms
Why is SJF optimal?
SJF is an optimal algorithm because it decreases the wait times for short processes much more than it increases the wait times for long processes. Let’s consider the example shown in Figure 16.1, in which the next CPU bursts of P1, P2, and P3 are 5, 3, and 2, respectively. The first Gantt chart shows execution of processes according to the longestjob- first algorithm, resulting in the waiting times for P1, P2, and P3 to be 0, 5, and 8 times units. The second Gantt chart shows execution of processes according to the shortest-job-first algorithm, resulting in the waiting times for P1, P2, and P3 to be 0, 2, and 5. Note that the waiting time for P2 has decreased from 5 to 2 and that of P3 has decreased from 8 to 0. The increase in the wait time for P1 is from 0 to 5, which is much smaller than the decrease in the wait times for P2 and P3.
Figure 16.1 Two execution sequences for P1, P2, and P3: longest-job-first and shortestjob- first
Round-Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for time-sharing
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. The
ready queue is treated as a circular queue. The CPU scheduler goes around the ready
queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
To implement RR scheduling, we keep ready queue as a FIFO queue of processes. New
processes are added to the tail of the ready queue. The CPU scheduler picks the first
process from the ready queue, sets a timer to interrupt after 1 time quantum, and then
dispatches the process. One of the two things will then happen. The process may have a
CPU burst of less than 1 time quantum, in which case the process itself will release the
CPU voluntarily. The scheduler will then proceed to the next process in the ready queue.
Otherwise, if the CPU burst of currently running process is longer than one time quantum, the timer will go off and will cause an interrupt to the operating system. A
context switch will happen, the current process will be put at the tail of the ready queue,
and the newly scheduled process will be given the CPU.
The average waiting time under the RR policy however is often quite long. It is a
preemptive scheduling algorithm. If there are n processes n the ready queue, context
switch time is tcs and the time quantum is q then each process gets 1/n of the CPU time in
chunks of at most q time units. Each process must wait no longer than (n-1)*(q+tcs) time
units until its next time quantum.
The performance of RR algorithm depends heavily on the size of the time quantum. If
the time quantum is very large (infinite), the RR policy remains the same as the FCFS
policy. If the time quantum is very small, the RR approach is called the processor
sharing and appears to the users as though each of n processes has its own processor
running at 1/n the speed of real processor (q must be large with respect to context switch,
otherwise the overhead is too high). The drawback of small quantum is more frequent
context switches. Since context switching is the cost of the algorithm and no useful work
is done for any user process during context switching, the number of context switches
should be minimized and the quantum should be chosen such that the ratio of a quantum
to context switching is not less than 10:1 (i.e., context switching overhead should not be
more than 10% of the time spent on doing useful work for a user process). Figure 16.2
shows increase in the number of context switches with decrease in quantum size.
Figure 16.2 Quantum size versus number of context switches
The turnaround time of a process under round robin is also depends on the size of the
time quantum. In Figure 16.3 we show a workload of four processes P1, P2, P3, and P4
with their next CPU bursts as 6, 3, 1, and 7 time units. The graph in the figure shows that
best (smallest) turnaround time is achieved when quantum size is 6 or greater. Note that
most of the given processes finish their next CPU bursts with quantum of 6 or greater.
We can make a general statement that the round-robin algorithm gives smallest average
turnaround time when quantum value is chosen such that most of the processes finish
their next CPU bursts within the quantum.
Figure 16.3 Turnaround time versus quantum size
We now consider the following system workload to illustrate working of the roundrobin algorithm. Execution of P1 though P4 with quantum 20 is shown in Figure 16.4. In the table, original CPU bursts are shown in bold and remaining CPU bursts (after a process has used the CPU for one quantum) are shown in non-bold font.
Figure 16.4 Gantt chart showing execution of P1, P2, P3, and P4 with quantum 20 time units
Figure 16.5 shows wait and turnaround times for the four processes. The average wait
time for a process comes out to be 73 time units for round robin and 38 for SJF.
Typically, RR has a higher average turnaround than SJF, but better response. In timesharing
systems, shorter response time for a process is more important than shorter
turnaround time for the process. Thus, round-robin scheduler matches the requirements of
time-sharing systems better than the SJF algorithm. SJF scheduler is better suited for
batch systems, in which minimizing the turnaround time is the main criterion.
Figure 16.5 Wait and turnaround times for processes
Multilevel Queue Scheduling
Another class of scheduling algorithms has been created for situations in which processes
are easily classified into different groups. For example, a common division is made
between foreground (or interactive) processes and background (or batch) processes.
These two types of processes have different response time requirements and so might
have different scheduling needs. In addition, foreground processes may have priority over
background processes.
A multilevel queue-scheduling algorithm partitions the ready queue into several
separate queues, as shown in Figure 16.5. Each queue has its own priority and scheduling
algorithm. Processes are permanently assigned to one queue, generally based o some
property of the process, such as memory size, process priority or process type. In
addition, there must be scheduling among the queues, which is commonly implemented
as fixed-priority preemptive scheduling i.e., serve all from foreground then from
background. Another possibility is to time slice between queues. Each queue gets a
certain portion of the CPU time, which it can then schedule among the various processes
in its queue, e.g., 80% to foreground in RR and 20% to background in FCFS. Scheduling
across queues prevents starvation of processes in lower-priority queues.
Figure 16.5 Multilevel queues scheduling
Google +