Introduction

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. Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.

Following are some sheduling algorithms:

First Come First Serve (FCFS)

The simplest of all scheduling algorithms. The process that requested the CPU first is allocated the CPU first.

• Unfortunately, however, FCFS can yield some very long average wait times, particularly if the first process to get there takes a long time.
• FCFS can also block the system in a busy dynamic system in another way, known as the convoy effect. When one CPU intensive process blocks the CPU, a number of I/O intensive processes can get backed up behind it, leaving the I/O devices idle. When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leavinwhile everyone queues up for I/O, and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.

Shortest Job First (SJF)

The scheduling criteria under this policy depends on which process has the shortest-next-CPU-burst. It is an optimal way of CPU scheduling, i.e it gives the minimum average waiting time for a set of processes. If two process have the same burst time left, FCFS is used to resolve the tie.

• SJF can be proven to be the fastest scheduling algorithm, but it suffers from one important problem: How do you know how long the next CPU burst is going to be?
• The next CPU burst length is thereby approximated using statistical techniques like exponential average.

Shortest Remaining Time First (SRTF)

This is the preemptive version of Shortest Job First scheduling. A newly arrived process in the ready queue may have a burst time lesser than that of the current process getting executed. In such a case, the current process is preempted and the newly arrived process is scheduled to execute. Similar to SJF, FCFS is used to resolve the tie here.

Non-preemptive priority

A more general case of the SJF scheduling where the priority was based on burst time. Each process is associated with a priority and CPU is allocated to the process with highest priority. Equal priority processes are scheduled in FCFS order. A newly arrived process is simply put in the ready queue based on its priority and does not interrupt the currently executing process.

• In a heavily loaded computer system, a steady stream of high priority processes can leave some low priority processes waiting for a long time. This is called as indefinite blocking or starvation.

Preemptive priority

It is a preemptive version of the priority scheduling algorithm. The priority of newly arrived processes are compared with the currently executing process. If the priority is higher, then the currently executing process is preempted and the newly arrived process executes

Round-Robin

The ready queue is treated as a circular queue. The CPU scheduler goes around the queue, allocating the CPU to each of the processes a time period of 1 quantum. If the burst time left for a process is less than the time quantum, then the process will itself release the CPU voluntarily. If the burst time left is more than 1 time quantum, the timer for that process will go off and a context switch is forced. This algorithm is preemptive.

• Performance depends heavily on the time quantum. A very large time quantum will it make it effectively an FCFS algorithms and a very short time quantum will force a very large number of context switches.
• A rule of thumb is that 80% of the CPU bursts must be shorter than the time quantum.