CPU scheduling deals with the issue of deciding which of the processes in the ready queue needs to be allocated to the CPU. There are several different CPU scheduling algorithms used nowadays within an operating system. In this tutorial, you will get to know about some of them.
First-Come, First-Served Scheduling (FCFS) Algorithm
The easiest and simplest CPU scheduling algorithm is the first-come, first-served (FCFS) scheduling technique. With this method, the process that requests the CPU first gets allocated to the CPU first. The execution of the FCFS policy is easily managed with a FIFO queue. As a process enters the ready queue, its Process Control Block is linked with the tail of the queue. When the CPU gets free, it is assigned to the process at the head or start of the queue.
Consider the following set of processes/jobs which arrive at time 0, with the length of the CPU burst that is given in milliseconds:
| Process list | Burst - Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
When the processes arrive in the order - P1, P2, and P3 and are served using the FCFS method, you get the outcome as given in the below-mentioned Gantt chart:
Shortest-Job-First Scheduling Technique
A diverse approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm, which links the length of the process's next CPU burst with each process. The CPU is assigned to the process with the minimum next CPU burst if it is available. If the subsequent CPU bursts of two processes become identical, then FCFS scheduling breaks the tie.
Let us take an example of SJF scheduling with the given set of processes below and the length of the CPU burst in milliseconds:
| Process list | Burst - Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
Priority Scheduling
The SJF algorithm is a unique example of the common priority scheduling technique. A priority is related and assigned to each process, and the CPU gets assigned to the process with the maximum priority. Equal priority processes get scheduled using the FCFS method. An SJF algorithm is a priority algorithm wherein the priority (P) is the opposite of the (predicted) subsequent CPU burst. The better the CPU burst, the lower the priority is, and vice versa.
Round-Robin Scheduling
The round-robin (RR) scheduling technique is intended mainly for time-sharing systems. This algorithm is related to FCFS scheduling, but preemption is included to toggle among processes. A small unit of time termed a time quantum or time slice has to be defined. A 'time quantum' is usually from 10 to 100 milliseconds. The ready queue gets treated with a circular queue. The CPU scheduler goes about the ready queue, allocating the CPU with each process for the time interval, which is at least 1-time quantum.
Multilevel Queue Scheduling
Another scheduling technique has been designed for situations where processes are classified into groups. A multi-level queue scheduling technique partitions or divides the ready queue into many separate queues. The processes get permanently assigned to one queue, usually based on some property of the process, such as the memory size, process priority, and type of process. Each queue has its scheduling algorithm, which works in a multilevel form.
Here is the diagram of how it works:
