CPU Scheduling in Operating System

The goal of the multi-programming system is to keep the CPU busy at all times. In a uni-processor system whenever the CPU becomes idle it is allocated to a new process. Which process will be allocated the CPU is decided by the short-term scheduler. CPU scheduling means to select the next process to be allocated to the CPU whenever the CPU becomes idle. Other common names of CPU scheduling are process scheduling or thread scheduling. The question is – When to call the short-term scheduler? In other words when is CPU scheduling in the operating system required? There are four circumstances:

1. A Process switches from running state to waiting state.
2. Process switches from running state to ready state.
3. Process switches from waiting state to ready state.
4. A Process terminates.

Refer the process state diagram for details on these four transitions.

Preemptive and Non-preemptive scheduling

If you analyse points (1) and (4) closely, in both these situations the process voluntarily releases the CPU. In (1) the process needs an I/O output devices so it releases the CPU. While in (4) the process finishes and hence it releases the CPU. It is called non-preemptive scheduling. For example, Microsoft Windows 3.x used such scheduling policy.

Under (2) and (3) the system forcefully takes back the CPU from the currently running process to allocate it a new process. This is called preemptive scheduling. This may be due to the arrival of a higher priority process or due to time-slice expiry. For example, Microsoft Windows 95 and above follow this scheduling

Dispatcher

A Dispatcher is that module of the operating system which gives control of the CPU to the process. Short term scheduler only decides which process to allocate to CPU. Whereas the dispatcher actually allocates the CPU to that process.

It involves three steps:

• First, it performs Context switching
• Second, Switching to user mode
• Finally, Jumping to the proper location in the user program to restart that process.

Which is the best CPU scheduling algorithm?

This is a common question that comes to our mind. An Operating System uses different algorithms for CPU scheduling. Every algorithm can perform better depending upon the situation. There are five points to decide which algorithm performs better than others.

1. CPU utilization – It means how much the CPU is busy. That is, for a given duration of time how long was the CPU doing the processing. The CPU utilization should be high (40-90%)
2. Throughput – Throughput is the number of processes that complete execution in a given time.
3. Turnaround time – is the interval from the time of submission of the process to the time of its completion
4. Waiting time – is the time spent by the process in the ready queue (waiting for the CPU)
5. Response time – is the time from the submission of the process until it gives the first response.

An algorithm is effective if it has high CPU utilization and throughput, whereas low turnaround, waiting and response time.

CPU Scheduling Algorithms

Some of the most commonly use CPU scheduling algorithms are:

• First Come First Serve(FCFS)
• Shortest Job First (SJF)
• Priority Scheduling
• Round Robin (RR)

PPT on CPU Scheduling in Operating System

Note: Clicking on the “next” slide button will not display any animation. Click within the slide area for animations.

Previous                                 Next
Operations on Process         CPU Scheduling Algorithms