Various CPU Scheduling Algorithms in Operating Systems

Various CPU Scheduling Algorithms in Operating Systems

CPU Scheduling algorithms decide which of the processes in the ready queue is to be allocated to the CPU. There are many different CPU scheduling algorithms, and out of those algorithms, which algorithm maximizes CPU utilization and throughput and minimizes turnaround time, waiting time, and response time, those algorithms are the best of all algorithms.

  1. First-Come, First-Served Scheduling (FCFS)
  2. Shortest Job First Scheduling (SJF)
  3. Round Robin Scheduling Algorithm (RR)
  4. Priority Scheduling

CPU Scheduling algorithms decide which of the processes in the ready queue is to be allocated to the CPU. The algorithms which maximize CPU Utilization and throughput and minimize turnaround time, waiting time, and response time, those algorithms are the best of all algorithms.

First-Come, First-Served Scheduling [FCFS]

  • It is the simplest CPU algorithm.
  • The criteria are ‘the process that requests the CPU first holds the CPU first’ or which ‘process enters the ready queue first served first‘.
  • Consider the following set of processes that arrive at time 0, the CPU burst time given in milliseconds.
  • Burst time is the time, that requires the CPU to execute that job, generally, it is in milliseconds.
ProcessBurst time (in milliseconds)Arrival Time
P150
P2240
P3160
P4100
P530

If the processes in the orders P1, P2, P3, P4, and P5 are served in FCFS order, we get the results in the following Gantt chart.

P1P2P3P4P5
0529455558

Now we have to calculate the average waiting time, average response time, and average turnaround time.

Average turnaround time:

Turn around time = Finished time – Arrival time
Turnaround time for P1= 5 – 0= 5
Turnaround time for P2= 29 – 0= 29
Turnaround time for P3= 45 – 0= 45
Turnaround time for P4= 55 – 0= 55
Turnaround time for P5= 58 – 0= 58
Average turn around time = (5 + 29 + 45 + 55 + 58) / 5
                         = 192 / 5
                         = 38.4 milliseconds

Average waiting time:

Waiting time = Starting time – Arrival time
Waiting time for P1= 0= 0
Waiting time for P2= 5 – 0= 5
Waiting time for P3= 29 – 0= 29
Waiting time for P4= 45 – 0= 45
Waiting time for P5= 55 – 0= 55
Average waiting time = (0 + 5 + 29 + 45 + 55) / 5
                     = 134 / 5
                     = 26.8 milliseconds

Average Response time:

Response time = First response – Arrival time
Response time for P1= 0= 0
Response time for P2= 5 – 0= 5
Response time for P3= 29 – 0= 29
Response time for P4= 45 – 0= 45
Response time for P5= 55 – 0= 55
Average Response time = (0 + 5 + 29 + 45 + 55) / 5
                      = 134 / 5
                      = 26.8 milliseconds

In this algorithm, the average waiting time and average response time both are the same because it is a non-preemptive scheduling algorithm.

Advantage of FCFS

  • It is easy to implement.
  • It is a very simple algorithm.

Disadvantage of FCFS

  • It is troublesome for time-sharing systems
  • The average waiting time is very high, this may impact the performance of the CPU.

Shortest Job First Scheduling [SJF]

The criteria of this algorithm are which process has the smallest CPU burst, the CPU is assigned to that process next. If the process has the same CPU burst time FCFS is used to break the tie.

ProcessBurst time (in milliseconds)Arrival Time
P150
P2240
P3160
P4100
P530
P1P2P3P4P5
038183458

Average waiting time:

Waiting time = Starting time – Arrival time
Waiting time for P1= 3 – 0= 3
Waiting time for P2= 34 – 0= 34
Waiting time for P3= 18 – 0= 18
Waiting time for P4= 8 – 0= 8
Waiting time for P5= 0 – 0= 0
Average waiting time = (3 + 34 + 18 + 8 + 0) / 5
                     = 63/ 5
                     = 12.6 milliseconds

Average turnaround time:

Turn around time = Finished time – Arrival time
Turnaround time for P1= 8 – 0= 8
Turnaround time for P2= 58 – 0= 58
Turnaround time for P3= 34 – 0= 34
Turnaround time for P4= 18 – 0= 18
Turnaround time for P5= 3 – 0= 3
Average turn around time = (8 + 58 + 34 + 18 + 3) / 5
                         = 121 / 5
                         = 24.2 milliseconds

Average Response time:

 Response time = First response – Arrival time
Response time for P1= 3 – 0= 3
Response time for P2= 34 – 0= 34
Response time for P3= 18 – 0= 18
Response time for P4= 8 – 0= 8
Response time for P5= 0 – 0= 0
Average Response time = (3 + 34 + 18 + 8 + 0) / 5
                      = 63 / 5
                      = 12.6 milliseconds

Advantage of SJF

  • It is having least Average waiting time, Average turnaround time, and Average response time.

Disadvantage of SJF

  • Knowing the length of the next CPU burst time, is difficult.
  • It is an optimal algorithm. It can not be implemented at the level of short-term CPU scheduling.
  • Aging is another problem. Big jobs are waiting so much time for CPU.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top