CS201: Elementary Data Structures

A queue is natural data structure for a system serving incoming requests. Most of the process scheduling or disk scheduling algorithms in operating systems use queues.

We can implement a round-robin scheduler using a queue, Q, by repeatedly performing the following steps:

1.  dequeue()e = Q.
2.  Service element e
3.  Q.enqueue(e)

A Round-Robin Scheduler

Job Scheduling

Operating systems access many jobs regularly. These jobs are added into a queue known as the job queue. One by one, jobs are retrieved from the job queue and added to the ready queue, which assigns them to the processor. Then, an algorithm partitions the ready queue into several separate queues. The nature of jobs in this multilevel queue is different. Each job is given a different priority based on its nature. These jobs are in the form of processes. There can be many types of processes queues, like the system queue, which contains all system processes. Processes are permanently assigned to a specific queue based on their properties. Each queue has its own specific scheduling algorithm. Consider the following illustration of multilevel priority queue scheduling:

Multilevel Priority Queue Scheduling

Each queue has absolute priority over lower priority queues. No processes in batch queues will be able to run until the queues above them are empty. Another possibility is to time slice between the queues by allotting each process with a certain portion of CPU time.

Multilevel Feedback Queue Scheduling

Here, processes are not permanently assigned to a queue on entry to the system. Instead, they are allowed to move between queues. The idea is to separate processes with different CPU burst characteristics. If a process uses too much CPU time, it will be moved to a lower priority queue. Similarly, a process that waits too long in a low priority queue will be moved to a higher priority queue. This form of aging prevents starvation.

Multilevel Feedback Queue Scheduling

Source: University of Delhi, http://vle.du.ac.in/mod/book/view.php?id=5697&chapterid=2483
 This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 IN License.