The multiprogramming 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 multiprogramming, 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.
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.
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.
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.
short-term scheduler, or CPU scheduler, selects processes from memory that are ready for execution and allocate CPU to one of the processes.
short-term scheduler switches between processes within milliseconds, therefore, it must be fast enough and not waste time in context switching.
long term scheduler executes slowly and several minutes before a new process is created. It controls the degree of multiprogramming. The degree of multiprogramming 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
scheduler and directly load the processes in memory . Example. UNIX and Microsoft Windows.
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.
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.