OS - Scheduling algorithms

We'll discuss four major scheduling algorithms here which are following

• First Come First Serve (FCFS) Scheduling 
• Shortest-Job-First (SJF) Scheduling 
• Priority Scheduling 
• Round Robin(RR) Scheduling 
• Multilevel Queue Scheduling

First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis. 
• Easy to understand and implement. 
• Poor in performance as average wait time is high.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.55

Shortest Job First (SJF)

• Best approach to minimize waiting time. 
• Impossible to implement 
• Processer should know in advance how much time process will take.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	3 - 0 = 3
P1	0 - 0 = 0
P2	16 - 2 = 14
P3	8 - 3 = 5

Average Wait Time: (3+0+14+5) / 4 = 5.50

Priority Based Scheduling

• Each process is assigned a priority. Process with highest priority is to be executed first and so on. 
• Processes with same priority are executed on first come first serve basis. 
• Priority can be decided based on memory requirements, time requirements or any other resource requirement.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	9 - 0 = 9
P1	6 - 1 = 5
P2	14 - 2 = 12
P3	0 - 0 = 0

Average Wait Time: (9+5+12+0) / 4 = 6.5

Round Robin Scheduling

• Each process is provided a fix time to execute called quantum. 
• Once a process is executed for given time period. Process is preempted and other process executes for given time period. 
• Context switching is used to save states of preempted processes.

Wait time of each process is following

Process	Wait Time : Service Time - Arrival Time
P0	(0-0) + (12-3) = 9
P1	(3-1) = 2
P2	(6-2) + (14-9) + (20-17) = 12
P3	(9-3) + (17-12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5

Multi Queue Scheduling

• Multiple queues are maintained for processes. 
• Each queue can have its own scheduling algorithms. 
• Priorities are assigned to each queue.