CPU Scheduling in Operating Systems | OS Tutorials

In an operating system, CPU processor scheduling aims to assign processes to be executed by the processor in a way that meets system objectives such as response time, throughput, and processor efficiency. As processes enter the system, they are put into a job queue, which consists of all processes in the operating 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.

CPU Scheduling

The list of processes waiting for any particular I/O device is called a device queue. A new process is initially put in the ready queue. It waits there until it is selected for execution, or is dispatched. In many systems, the scheduling activity is broken down into three separate functions:

1. Long Term Scheduling
2. Medium Term Scheduling
3. Short Term Scheduling.

Figure 1 relates the scheduling functions to the process state transition diagram.

• Long-Term Scheduling is performed when a new process is created. This is a decision whether to add a new process to the set of processes that are currently active.
• Medium-Term Scheduling is a part of the swapping function. It moves processes between the memory and the disk to optimize use of the memory.
• Short-Term Scheduling is the actual decision of which ready process to execute next.

Figure 2 recognizes the state transition diagram of Figure 1 to suggest the nesting of scheduling functions.

The table below summarizes the types of scheduling.

Long Term Scheduling (Job Scheduler)

• The long-term scheduler executes much less frequently; minutes may separate the creation of one new process and the next.
• The long-term scheduler determines which programs are admitted to the system for processing. Thus, it controls the degree of multiprogramming.
• 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.
• Since, due to the longer time interval between executions, the long-term scheduler can afford to take more time to decide which process should be selected for execution.
• The decision as to which job/process to admit next can be on a simple first-come-first-served basis. The criteria used may include priority, expected execution time, and I/O requirements.
• 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.

Medium Term Scheduling

• Operating systems such as time – sharing systems may introduce an additional intermediate level of scheduling called medium-term scheduling.
• The medium-term scheduler is shown in Figure 3.

• The medium-term scheduler can sometimes be advantageous to remove processes from memory and thus reduce the degree of multiprogramming.
• After some time, the process can be reintroduced into the memory and continue the execution from where it left off. This process is called swapping.
• Swapping may be necessary to improve the process mix or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up.

Short term Scheduler (CPU Scheduler)

• Short term scheduling is concerned with effective use of the CPU. The main objective of short-term scheduling is to allocate processor time in such a way as to optimize the system behavior.
• It is basically concerned with the effective use of the CPU. It selects one process from a list of ready processes, decides for how long the process should be executed, and arranges to produce a timer interrupt when the time elapses.
• In practice, the short-term scheduler is invoked whenever an event (internal or external) causes the global state of the system to change.

COMPARISON OF LONG, MEDIUM AND SHORT TERM SCHEDULER

In terms of Frequency of Execution:

• The long-term scheduler executes relatively infrequently and makes the coarse-grained decision of whether or not to take on a new process and which one to take.
• The medium-term scheduler is executed somewhat more frequently to make a swapping decision.
• The short-term scheduler, also known as Dispatcher, executes most frequently and makes the fine-grained decision of which process to execute next. The short-term scheduler executes whenever an event occurs. Examples of such events include:

1. Clock Interrupts
2. I/O Interrupts
3. Operating System Calls.
4. Signals