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.
