CPU Scheduling

CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast and fair.

A scheduling system allows one process to use the CPU while another is waiting for I/O, thereby making full use of otherwise lost CPU cycles.

1. CPU-I/O Burst Cycle

Almost all processes alternate between two states in a continuing cycle,

• A CPU burst of performing calculations, and
• An I/O burst, waiting for data transfer in or out of the system.

An I/O bound program typically has many short CPU bursts. A CPU bound program might have a few long CPU bursts. This distribution can be important in the selection of an appropriate CPU scheduling algorithm.

2. CPU Scheduler

• Whenever the CPU becomes idle, it is the job of the CPU Scheduler ( the short-term scheduler ) to select another process from the ready queue to run next.
• The storage structure for the ready queue and the algorithm used to select the next process are not necessarily a FIFO queue. There are several alternatives to choose from, as well as numerous adjustable parameters for each algorithm.

3. Preemptive Scheduling

CPU scheduling decisions take place under one of four conditions:

1. When a process switches from the running state to the waiting state, such as for an I/O request or invocation of the wait( ) system call.
2. When a process switches from the running state to the ready state, for example in response to an interrupt.
3. When a process switches from the waiting state to the ready state, say at completion of I/O or a return from wait( ).
4. When a process terminates.

For conditions 1 and 4 there is no choice - A new process must be selected.

For conditions 2 and 3 there is a choice - To either continue running the current process, or select a different one.

If scheduling takes place only under conditions 1 and 4, the system is said to be non-preemptive, or cooperative. Under these conditions, once a process starts running it keeps running, until it either voluntarily blocks or until it finishes. Otherwise the system is said to be preemptive.

4. Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the scheduler. This function involves:

• Switching context.
• Switching to user mode.
• Jumping to the proper location in the newly loaded program.

The dispatcher needs to be as fast as possible, as it is run on every context switch. The time consumed by the dispatcher is known as dispatch latency.