Scheduling Queues

• As processes enter the system, they are put into a job queue, which consists of all processes in the system.
• The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue.
• This queue is generally stored as a linked list. A ready-queue header contains pointers to the first and final PCBs in the list. Each PCB includes a pointer field that points to the next PCB in the ready queue.
• Suppose the process makes an I/O request to a shared device, such as a disk. Since there are many processes in the system, the disk may be busy with the I/O request of some other process.
• The process therefore may have to wait for the disk. The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue (see Fig. 3.8).

  Figure 3.8: The ready queue and various I/O device queues.

  
• A common representation for a discussion of process scheduling is a queuing diagram, such as that in Fig. 3.9.

  Figure 3.9: Queueing-diagram representation of process scheduling.

  
  • Each rectangular box represents a queue. Two types of queues are present: the ready queue and a set of device queues.
  • The circles represent the resources that serve the queues, and the arrows indicate the flow of processes in the system.
• A new process is initially put in the ready queue. It waits there until it is selected for execution, or is dispatched.
• Once the process is allocated the CPU and is executing, one of several events could occur:
  • The process could issue an I/O request and then be placed in an I/O queue.
  • The process could create a new subprocess and wait for the subprocess's termination.
  • The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue.
• A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated.