Different types of CPU Scheduling Algorithms
Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to ready state. The resources (mainly CPU cycles) are allocated to the process for a limited amount of time and then taken away, and the process is again placed back in the ready queue if that process still has CPU burst time remaining. That process stays in the ready queue till it gets its next chance to execute.
Algorithms based on preemptive scheduling are: Round Robin (RR),Shortest Remaining Time First (SRTF), Priority (preemptive version), etc.
2. Non-Preemptive Scheduling:
Non-preemptive Scheduling is used when a process terminates, or a process switches from running to the waiting state. In this scheduling, once the resources (CPU cycles) are allocated to a process, the process holds the CPU till it gets terminated or reaches a waiting state. In the case of non-preemptive scheduling does not interrupt a process running CPU in the middle of the execution. Instead, it waits till the process completes its CPU burst time, and then it can allocate the CPU to another process.
Algorithms based on non-preemptive scheduling are: Shortest Job First (SJF basically non preemptive) and Priority (non preemptive version), etc.
- from running state to waiting state.
Different types of CPU Scheduling Algorithms
Let us now learn about these CPU scheduling algorithms in operating systems one by one:
1. First Come First Serve:
FCFS considered to be the simplest of all operating system scheduling algorithms. First come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first and is implemented by using FIFO queue.
- FCFS supports non-preemptive and preemptive CPU scheduling algorithms.
- Tasks are always executed on a First-come, First-serve concept.
- FCFS is easy to implement and use.
- This algorithm is not much efficient in performance, and the wait time is quite high.
- Easy to implement
- First come, first serve method
- FCFS suffers from Convoy effect.
- The average waiting time is much higher than the other algorithms.
- FCFS is very simple and easy to implement and hence not much efficient.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on First come, First serve Scheduling.
2. Shortest Job First(SJF):
Shortest job first (SJF) is a scheduling process that selects the waiting process with the smallest execution time to execute next. This scheduling method may or may not be preemptive. Significantly reduces the average waiting time for other processes waiting to be executed. The full form of SJF is Shortest Job First.
- Shortest Job first has the advantage of having a minimum average waiting time among all operating system scheduling algorithms.
- It is associated with each task as a unit of time to complete.
- It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of ageing.
Advantages of Shortest Job first:
- As SJF reduces the average waiting time thus, it is better than the first come first serve scheduling algorithm.
- SJF is generally used for long term scheduling
- One of the demerit SJF has is starvation.
- Many times it becomes complicated to predict the length of the upcoming CPU request
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on Shortest Job First.
3. Longest Job First(LJF):
Longest Job First(LJF) scheduling process is just opposite of shortest job first (SJF), as the name suggests this algorithm is based upon the fact that the process with the largest burst time is processed first. Longest Job First is non-preemptive in nature.
- Among all the processes waiting in a waiting queue, CPU is always assigned to the process having largest burst time.
- If two processes have the same burst time then the tie is broken using FCFS i.e. the process that arrived first is processed first.
- LJF CPU Scheduling can be of both preemptive and non-preemptive types.
- No other task can schedule until the longest job or process executes completely.
- All the jobs or processes finish at the same time approximately.
- Generally, the LJF algorithm gives a very high average waiting time and average turn-around time for a given set of processes.
- This may lead to convoy effect.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on the Longest job first scheduling.
4. Priority Scheduling:
Preemptive Priority CPU Scheduling Algorithm is a pre-emptive method of CPU scheduling algorithm that works based on the priority of a process. In this algorithm, the editor sets the functions to be as important, meaning that the most important process must be done first. In the case of any conflict, that is, where there are more than one processor with equal value, then the most important CPU planning algorithm works on the basis of the FCFS (First Come First Serve) algorithm.
Characteristics of Priority Scheduling:
- Schedules tasks based on priority.
- When the higher priority work arrives while a task with less priority is executed, the higher priority work takes the place of the less priority one and
- The latter is suspended until the execution is complete.
- Lower is the number assigned, higher is the priority level of a process.
Advantages of Priority Scheduling:
- The average waiting time is less than FCFS
- Less complex
Disadvantages of Priority Scheduling:
- One of the most common demerits of the Preemptive priority CPU scheduling algorithm is the Starvation Problem. This is the problem in which a process has to wait for a longer amount of time to get scheduled into the CPU. This condition is called the starvation problem.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on Priority Preemptive Scheduling algorithm.
5. Round robin:
Round Robin is a CPU scheduling algorithm where each process is cyclically assigned a fixed time slot. It is the preemptive version of First come First Serve CPU Scheduling algorithm. Round Robin CPU Algorithm generally focuses on Time Sharing technique.
Characteristics of Round robin:
- It’s simple, easy to use, and starvation-free as all processes get the balanced CPU allocation.
- One of the most widely used methods in CPU scheduling as a core.
- It is considered preemptive as the processes are given to the CPU for a very limited time.
- Round robin seems to be fair as every process gets an equal share of CPU.
- The newly created process is added to the end of the ready queue.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on the Round robin Scheduling algorithm.
6. Shortest Remaining Time First:
Shortest remaining time first is the preemptive version of the Shortest job first which we have discussed earlier where the processor is allocated to the job closest to completion. In SRTF the process with the smallest amount of time remaining until completion is selected to execute.
Characteristics of Shortest remaining time first:
- SRTF algorithm makes the processing of the jobs faster than SJF algorithm, given it’s overhead charges are not counted.
- The context switch is done a lot more times in SRTF than in SJF and consumes the CPU’s valuable time for processing. This adds up to its processing time and diminishes its advantage of fast processing.
- In SRTF the short processes are handled very fast.
- The system also requires very little overhead since it only makes a decision when a process completes or a new process is added.
- Like the shortest job first, it also has the potential for process starvation.
- Long processes may be held off indefinitely if short processes are continually added.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on the shortest remaining time first.
7. Longest Remaining Time First:
The longest remaining time first is a preemptive version of the longest job first scheduling algorithm. This scheduling algorithm is used by the operating system to program incoming processes for use in a systematic way. This algorithm schedules those processes first which have the longest processing time remaining for completion.
Characteristics of longest remaining time first:
- Among all the processes waiting in a waiting queue, the CPU is always assigned to the process having the largest burst time.
- If two processes have the same burst time then the tie is broken using FCFS i.e. the process that arrived first is processed first.
- LJF CPU Scheduling can be of both preemptive and non-preemptive types.
- No other process can execute until the longest task executes completely.
- All the jobs or processes finish at the same time approximately.
- This algorithm gives a very high average waiting time and average turn-around time for a given set of processes.
- This may lead to a convoy effect.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on the longest remaining time first.
8. Highest Response Ratio Next:
Highest Response Ratio Next is a non-preemptive CPU Scheduling algorithm and it is considered as one of the most optimal scheduling algorithms. The name itself states that we need to find the response ratio of all available processes and select the one with the highest Response Ratio. A process once selected will run till completion.
Characteristics of Highest Response Ratio Next:
- The criteria for HRRN is Response Ratio, and the mode is Non-Preemptive.
- HRRN is considered as the modification of Shortest Job First to reduce the problem of starvation.
- In comparison with SJF, during the HRRN scheduling algorithm, the CPU is allotted to the next process which has the highest response ratio and not to the process having less burst time.
Response Ratio = (W + S)/S
Here, W is the waiting time of the process so far and S is the Burst time of the process.
- HRRN Scheduling algorithm generally gives better performance than the shortest job first Scheduling.
- There is a reduction in waiting time for longer jobs and also it encourages shorter jobs.
- The implementation of HRRN scheduling is not possible as it is not possible to know the burst time of every job in advance.
- In this scheduling, there may occur an overload on the CPU.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on Highest Response Ratio Next.
9. Multiple Queue Scheduling:
Processes in the ready queue can be divided into different classes where each class has its own scheduling needs. For example, a common division is a foreground (interactive) process and a background (batch) process. These two classes have different scheduling needs. For this kind of situation Multilevel Queue Scheduling is used.
The description of the processes in the above diagram is as follows:
- System Processes: The CPU itself has its process to run, generally termed as System Process.
- Interactive Processes: An Interactive Process is a type of process in which there should be the same type of interaction.
- Batch Processes: Batch processing is generally a technique in the Operating system that collects the programs and data together in the form of a batch before the processing starts.
Advantages of multilevel queue scheduling:
- The main merit of the multilevel queue is that it has a low scheduling overhead.
Disadvantages of multilevel queue scheduling:
- Starvation problem
- It is inflexible in nature
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on Multilevel Queue Scheduling.
10. Multilevel Feedback Queue Scheduling::
Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is like Multilevel Queue Scheduling but in this process can move between the queues. And thus, much more efficient than multilevel queue scheduling.
Characteristics of Multilevel Feedback Queue Scheduling:
- In a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system, and processes are not allowed to move between queues.
- As the processes are permanently assigned to the queue, this setup has the advantage of low scheduling overhead,
- But on the other hand disadvantage of being inflexible.
Advantages of Multilevel feedback queue scheduling:
- It is more flexible
- It allows different processes to move between different queues
Disadvantages of Multilevel feedback queue scheduling:
- It also produces CPU overheads
- It is the most complex algorithm.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article on Multilevel Feedback Queue Scheduling.
Comparison between various CPU Scheduling algorithms
Here is a brief comparison between different CPU scheduling algorithms:
| Algorithm | Allocation is | Complexity | Average waiting time (AWT) | Preemption | Starvation | Performance |
|---|---|---|---|---|---|---|
| FCFS | According to the arrival time of the processes, the CPU is allocated. | Simple and easy to implement | Large. | No | No | Slow performance |
| SJF | Based on the lowest CPU burst time (BT). | More complex than FCFS | Smaller than FCFS | No | Yes | Minimum Average Waiting Time |
| LJFS | Based on the highest CPU burst time (BT) | More complex than FCFS | Depending on some measures e.g., arrival time, process size, etc. | No | Yes | Big turn-around time |
| LRTF | Same as LJFS the allocation of the CPU is based on the highest CPU burst time (BT). But it is preemptive | More complex than FCFS | Depending on some measures e.g., arrival time, process size, etc. | Yes | Yes | The preference is given to the longer jobs |
| SRTF | Same as SJF the allocation of the CPU is based on the lowest CPU burst time (BT). But it is preemptive. | More complex than FCFS | Depending on some measures e.g., arrival time, process size, etc | Yes | Yes | The preference is given to the short jobs |
| RR | According to the order of the process arrives with fixed time quantum (TQ) | The complexity depends on Time Quantum size | Large as compared to SJF and Priority scheduling. | Yes | No | Each process has given a fairly fixed time |
| Priority Pre-emptive | According to the priority. The bigger priority task executes first | This type is less complex | Smaller than FCFS | Yes | Yes | Well performance but contain a starvation problem |
| Priority non-preemptive | According to the priority with monitoring the new incoming higher priority jobs | This type is less complex than Priority preemptive | Preemptive Smaller than FCFS | No | Yes | Most beneficial with batch systems |
| MLQ | According to the process that resides in the bigger queue priority | More complex than the priority scheduling algorithms | Smaller than FCFS | No | Yes | Good performance but contain a starvation problem |
| MFLQ | According to the process of a bigger priority queue. | It is the most Complex but its complexity rate depends on the TQ size | Smaller than all scheduling types in many cases | No | No | Good performance |
- Consider a system which requires 40-time units of burst time. The Multilevel feedback queue scheduling is used and time quantum is 2 unit for the top queue and is incremented by 5 unit at each level, then in what queue the process will terminate the execution?
- Which of the following is false about SJF? S1: It causes minimum average waiting time S2: It can cause starvation (A) Only S1 (B) Only S2 (C) Both S1 and S2 (D) Neither S1 nor S2 Answer (D) S1 is true SJF will always give minimum average waiting time. S2 is true SJF can cause starvation.
- Consider the following table of arrival time and burst time for three processes P0, P1 and P2. (GATE-CS-2011)
| Process | Arrival time | Burst Time |
| P0 | 0 ms | 9 ms |
| P1 | 1 ms | 4 ms |
| P2 | 2 ms | 9 ms |
- The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes? (A) 5.0 ms (B) 4.33 ms (C) 6.33 (D) 7.33 Solution : Answer: – (A) Process P0 is allocated processor at 0 ms as there is no other process in the ready queue. P0 is preempted after 1 ms as P1 arrives at 1 ms and burst time for P1 is less than remaining time of P0. P1 runs for 4ms. P2 arrived at 2 ms but P1 continued as burst time of P2 is longer than P1. After P1 completes, P0 is scheduled again as the remaining time for P0 is less than the burst time of P2. P0 waits for 4 ms, P1 waits for 0 ms and P2 waits for 11 ms. So average waiting time is (0+4+11)/3 = 5.
- Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds (GATE-CS-2004)
| Process | Arrival time | Burst Time |
| P1 | 0 ms | 5 ms |
| P2 | 1 ms | 3 ms |
| P3 | 2 ms | 3 ms |
| P4 | 4 ms | 1 ms |
- What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm ? (A) 5.50 (B) 5.75 (C) 6.00 (D) 6.25 Answer (A) Solution: The following is Gantt Chart of execution
| P1 | P2 | P4 | P3 | P1 |
| 1 | 4 | 5 | 8 | 12 |
- Turn Around Time = Completion Time – Arrival Time Avg Turn Around Time = (12 + 3 + 6+ 1)/4 = 5.50
- An operating system uses the Shortest Remaining Time First (SRTF) process scheduling algorithm. Consider the arrival times and execution times for the following processes:
| Process | Arrival time | Burst Time |
| P1 | 20 ms | 0 ms |
| P2 | 25 ms | 15 ms |
| P3 | 10 ms | 30 ms |
| P4 | 15 ms | 45 ms |
- What is the total waiting time for process P2? (A) 5 (B) 15 (C) 40 (D) 55 Answer (B) At time 0, P1 is the only process, P1 runs for 15 time units. At time 15, P2 arrives, but P1 has the shortest remaining time. So P1 continues for 5 more time units. At time 20, P2 is the only process. So it runs for 10 time units At time 30, P3 is the shortest remaining time process. So it runs for 10 time units At time 40, P2 runs as it is the only process. P2 runs for 5 time units. At time 45, P3 arrives, but P2 has the shortest remaining time. So P2 continues for 10 more time units. P2 completes its execution at time 55
Total waiting time for P2
= Completion time – (Arrival time + Execution time)
= 55 – (15 + 25)
= 15