Post By: Hanan Mannan
Contact Number: Pak (+92)-321-59-95-634
-------------------------------------------------------

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	0 - 0 = 0
P1	3 - 1 = 2
P2	8 - 2 = 6
P3	16 - 3 = 13

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

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.