Protsessi plaanimise algorütmid

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 RobinRR 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.