Types of Schedulers

The multi-programming technique wants high CPU utilization by executing some process all the time. The time-sharing computer keeps switching among processes so that all users can interact with their running programs.

A process scheduler does the selection of processes for execution on CPU. But there are challenges in multi-programming, if a process has to wait for an event, all other processes must wait for it to finish. The bigger the process, longer the wait time and idle time for CPU.

Scheduling Queues

The process that enters the system is put into a job queue. The process already in memory and waiting to execute are put in a list called ready queue. The process executes and quits, or wait for an event such as I/O request. Since many processes do requests for I/O, the processes, therefore, have to wait in the device queue.

Scheduler Queues
Scheduler Queues

Each device has a device queue.
e.g disk, printer, display, network and so on.

The new process waits in the ready queue until selected for execution or dispatched. Once CPU time is allocated to a process:

  • The process can do an I/O request.
  • The process creates a new child process and waits for its termination.
  • The process can be put back in ready queue forcibly due to an interrupt.

When a process terminates, it is removed from all queues and its resources are deallocated.

Schedulers

A process migrates through various scheduling queues during its lifetime. The selection of processes from queues is performed by the scheduler on behalf of OS.

In batch system, jobs are spooled to a disk for later execution. The job scheduler or long-term scheduler loads processes from this pool to memory.

The short-term scheduler, or CPU scheduler, selects processes from memory that are ready for execution and allocate CPU to one of the processes.

The short-term scheduler switches between processes within milliseconds, therefore, it must be fast enough and not waste time in context switching.

The long term scheduler executes slowly and several minutes before a new process is created. It controls the degree of multi-programming. The degree of multi-programming must be stable – the rate of process creation must equal to rate at which process departs.

When a process departs, the long-term scheduler makes a careful selection of processes to be loaded into memory. The selection is a mix of I/O bound process and CPU bound. If selection is all I/O bound processes, then CPU queue will be empty and it remains idle. If all selection is CPU bound, then I/O queue will be empty leave it idle.

Sometimes operating systems does not have long termscheduler and directly load the processes in memory . Example. UNIX and Microsoft Windows.

Medium-Term Scheduler
Medium-Term Scheduler

But operating system uses a swapping technique, called the medium-term scheduler. The waiting or blocked processes can be swapped out or swapped into a disk to free memory for other active processes.

References

  • Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
  • Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
Skip to content