IT Blogs

Round Robin Scheduling

• In round robin scheduling processes are dispatched FIFO but are given a limited amount of CPU time called a time-slice or a quantum. If a process does not complete before its CPU time expires, the CPU is preempted and given to the next waiting process. The preempted process is then placed at the back of the ready list.
• Round Robin is effective in timesharing environments in which the system needs to guarantee reasonable response times for interactive users.
• The preemption overhead is kept low by efficient context switching mechanisms and by providing adequate memory for the processes to reside in main storage.

• The only interesting issue with round robin is the length of the quantum.
• Switching from one process to another requires a certain amount of time for doing the administration – saving and loading registers, updating various tables etc.
• The conclusion can be formulated as follows: setting the quantum too short causes too many process switches and lowers the CPU efficiency, but setting it too long may cause poor response to short interactive requests. A quantum around 100 msec is often a reasonable compromise.

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 (interactive) processes and background (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 (externally defined) over background processes.
• A multilevel queue-scheduling algorithm partitions the ready queue into several separate queues (Figure). The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority or process type.
• Each queue has its own scheduling algorithm. For example, separate queues might be used for foreground and background processes.
• The foreground queue might be scheduled by an RR algorithm, while the background queue is scheduled by an FCFS algorithm.
• In addition, there must be scheduling between the queues, which is commonly implemented as a fixed-priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue.

Let us look at an example of a multilevel queue scheduling algorithm with five queues:

1. System processes
2. Interactive processes
3. Interactive editing processes
4. Batch processes
5. Student processes

• Each queue has absolute priority over lower-priority queues. No process in the batch queue, for example, could run unless the queues for system processes, interactive processes, and interactive editing processes were all empty.
• If an interactive editing process entered the ready queue while a batch process was running, the batch process would be preempted.
• Another possibility is to time slice between the queues. Each queue gets a certain portion of the CPU time, which it can then schedule among the various processes in its queue.
• For instance, in the foreground-background queue example, the foreground queue can be given 80 percent of the CPU time for RR scheduling among its processes, whereas the background queue receives 20 percent of the CPU to give to its processes in a FCFS manner.