1. Home
  2. Comparison between various CPU Scheduling algorithms

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

Exercise:

  1. 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?  
  2. 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.  
  3. 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
  1. 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.  
  2. 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
  1. 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
  1. Turn Around Time = Completion Time – Arrival Time Avg Turn Around Time  =  (12 + 3 + 6+  1)/4 = 5.50  
  2. 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
  1. 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

Related articles:



CPU Scheduling in Operating Systems

Scheduling of processes/work is done to finish the work on time. CPU Scheduling is a process that allows one process to use the CPU while another process is delayed (in standby) due to unavailability of any resources such as I / O etc, thus making full use of the CPU. The purpose of CPU Scheduling is to make the system more efficient, faster, and fairer.

Tutorial on CPU Scheduling Algorithms in Operating System

Whenever the CPU becomes idle, the operating system must select one of the processes in the line ready for launch. The selection process is done by a temporary (CPU) scheduler. The Scheduler selects between memory processes ready to launch and assigns the CPU to one of them.

Table of Contents

  • What is a Process?
  • How is Process Memory used for efficient operation?
  • What is Process Scheduling?
  • Why do we need to schedule processes?
  • What is the need for CPU Scheduling Algorithm?
    • Objectives of Process Scheduling Algorithm
  • What are the different terminologies?
  • Things to take care while designing CPU Scheduling Algorithm
  • What are different types of CPU Scheduling Algorithms?
    • 1) First Come First Serve (FCFS)
      • Characteristics of FCFS
      • Advantages of FCFS
      • Disadvantages of FCFS
    • 2) Shortest Job First (SJF)
      • Characteristics of SJF
      • Advantages of SJF
      • Disadvantages of SJF
    • 3) Longest Job First (LJF)
      • Characteristics of LJF
      • Advantages of LJF
      • Disadvantages of LJF
    • 4) Priority Scheduling
      • Characteristics of Priority Scheduling
      • Advantages of Priority Scheduling
      • Disadvantages of Priority Scheduling
    • 5) Round Robin
      • Characteristics of Round Robin
      • Advantages of Round Robin
    • 6) Shortest Remaining Time First (SRTF)
      • Characteristics of SRTF
      • Advantages of SRTF
      • Disadvantages of SRTF
    • 7) Longest Remaining Time First (LRTF)
      • Characteristics of LRTF
      • Advanatges of LRTF
      • Disadvantages of LRTF
    • 8) Highest Response Ratio Next (HRRN)
      • Characteristics of HRRN
      • Advantages of HRRN
      • Disadvantages of HRRN
    • 9) Multiple Queue Scheduling
      • Advantages of multilevel queue scheduling
      • Disadvantages of multilevel queue scheduling
    • 10) Multilevel Feedback Queue Scheduling (MLFQ)
      • Characteristics of MLFQ
      • Advantages of MLFQ
      • Disadvantages of MLFQ
  • Comparison between various CPU Scheduling Algorithms
    • Exercise

Similar Reads

What is a process?

In computing, a process is the instance of a computer program that is being executed by one or many threads. It contains the program code and its activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently....

How is process memory used for efficient operation?

The process memory is divided into four sections for efficient operation:...

What is Process Scheduling?

Process Scheduling is the process of the process manager handling the removal of an active process from the CPU and selecting another process based on a specific strategy....

Why do we need to schedule processes?

Scheduling is important in many different computer environments. One of the most important areas is scheduling which programs will work on the CPU. This task is handled by the Operating System (OS) of the computer and there are many different ways in which we can choose to configure programs. Process Scheduling allows the OS to allocate CPU time for each process. Another important reason to use a process scheduling system is that it keeps the CPU busy at all times. This allows you to get less response time for programs.  Considering that there may be hundreds of programs that need to work, the OS must launch the program, stop it, switch to another program, etc. The way the OS configures the system to run another in the CPU is called “context switching”. If the OS keeps context-switching programs in and out of the provided CPUs, it can give the user a tricky idea that he or she can run any programs he or she wants to run, all at once. So now that we know we can run 1 program at a given CPU, and we know we can change the operating system and remove another one using the context switch, how do we choose which programs we need. run, and with what program? That’s where scheduling comes in! First, you determine the metrics, saying something like “the amount of time until the end”. We will define this metric as “the time interval between which a function enters the system until it is completed”. Second, you decide on a metrics that reduces metrics. We want our tasks to end as soon as possible....

What is the need for CPU scheduling algorithm?

CPU scheduling is the process of deciding which process will own the CPU to use while another process is suspended. The main function of the CPU scheduling is to ensure that whenever the CPU remains idle, the OS has at least selected one of the processes available in the ready-to-use line....

What are the different terminologies to take care of in any CPU Scheduling algorithm?

Arrival Time: Time at which the process arrives in the ready queue. Completion Time: Time at which process completes its execution. Burst Time: Time required by a process for CPU execution. Turn Around Time: Time Difference between completion time and arrival time....

Things to take care while designing a CPU Scheduling algorithm?

Different CPU Scheduling algorithms have different structures and the choice of a particular algorithm depends on a variety of factors. Many conditions have been raised to compare CPU scheduling algorithms....

What are the different types of CPU Scheduling Algorithms?

There are mainly two types of scheduling methods:...

Comparison between various CPU Scheduling algorithms

Here is a brief comparison between different CPU scheduling algorithms:...

Categories

HTML CSS3 Bootstrap Foundation Sass JavaScript TypeScript JQuery AngularJS React NodeJS Highcharts PHP Python Python3 Django Linux Docker Ruby Java C C ++ Perl Servlet JSP Lua Scala Go ASP C # SQL MySQL SQLite MongoDB Redis Android Swift ionic Kotlin XML tutorial

Contact US