Schedulers

• A process migrates among the various scheduling queues throughout its lifetime.
• The OS must select, for scheduling purposes, processes from these queues in some fashion. The selection process is carried out by the appropriate scheduler.
• Often, in a batch system, more processes are submitted than can be executed immediately. These processes are spooled to a mass-storage device (typically a disk), where they are kept for later execution.
• The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution.
• The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them.
• The long-term scheduler controls the degree of multiprogramming (the number of processes in memory). If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
• Thus, the long-term scheduler may need to be invoked only when a process leaves the system. Because of the longer interval between executions, the long-term scheduler can afford to take more time to decide which process should be selected for execution.
• It is important that the long-term scheduler make a careful selection. In general, most processes can be described as either I/O bound or CPU bound.
  • An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations.
  • A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations.
• It is important that the long-term scheduler select a good process mix of I/O-bound and CPU-bound processes.
• On some systems, the long-term scheduler may be absent or minimal. For example, time-sharing systems such as UNIX and Microsoft Windows systems often have no long-term scheduler but simply put every new process in memory for the short-term scheduler.
• The stability of these systems depends either on a physical limitation (such as the number of available terminals) or on the self-adjusting nature of human users.
• Some OSs, such as time-sharing systems, may introduce an additional, intermediate level of scheduling. This medium-term scheduler is diagrammed in Fig. 10.

  Figure 10: Addition of medium-term scheduling to the queuing diagram.

  
• The key idea behind a medium-term scheduler is that sometimes it can be advantageous to remove processes from memory (and from active contention for the CPU) and thus reduce the degree of multiprogramming.
• Later, the process can be reintroduced into memory, and its execution can be continued where it left off. This scheme is called swapping.