CPU-Scheduling-and-Algorithm - Handouts.pdf
Burst Time
Process Execution Time
Turn Around Time
Completion Time - Arrival Time
Waiting Time
Turn Around Time - Bust Time
Average Waiting Time
Waiting Time / Number of Processes
Priority Numbers
Based on these numbers, the algorithm prioritises processes
The lowest the number the higher the priority
The highest the number the lowest the priority
Types
Non-Preemptive
These algorithms have no control over the preemption of the process, thus the next process can only come when the previous one is done completing its bust time
SJF - Shortest Job First
gantt
title SFJ Gantt Chart
dateFormat X
axisformat %M:%S
section P1
7/7: 0, 7
section P2
4/4: 8, 12
section P3
1/1: 7,8
section P4
4/4: 12, 16
| Processes | Arrival Time | Burst Time | Turn Around Time | Waiting Time |
|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 0 |
| P2 | 2 | 4 | 10 | 6 |
| P3 | 4 | 1 | 4 | 3 |
| P4 | 5 | 4 | 11 | 7 |
FCF - First Come First
gantt
title FCF Gantt Chart
dateFormat X
axisformat %M:%S
section P1
24: 0, 24
section P2
3: 24, 27
section P3
3: 27, 30
section P4
5: 30, 35
| Processes | Burst Time | Turn Around Time | Waiting Time |
|---|---|---|---|
| P1 | 24 | 24 | 0 |
| P2 | 3 | 27 | 24 |
| P3 | 3 | 30 | 27 |
| P4 | 5 | 35 | 30 |
Preemptive
SRTF - Shortest Remaining Time First
- Preemptive version of SJF - Shortest Job First
- Preempt the CPU based on the shortest time required by a process
gantt
title SRTF Gantt Chart
dateFormat X
axisformat %M:%S
section P1
2/7: 0, 2
7/7: 11, 16
section P2
2/4: 2, 4
4/4: 5, 7
section P3
1/1: 4, 5
section P4
4/4: 7, 11
| Processes | Arrival Time | Burst Time | Turn Around Time | Waiting Time |
|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 9 |
| P2 | 2 | 4 | 5 | 1 |
| P3 | 4 | 1 | 1 | 0 |
| P4 | 5 | 4 | 6 | 2 |
RR - Round Robin
-
Provide equal Time Quantum to all processes
-
A queue is maintained where processes waiting are put one after another
- The next processes is picked from the top of the queue
Time Quantum
The CPU time which is to be assigned to each processes
Example Time Quantum = 2
gantt
title RR Gantt Chart
dateFormat X
axisformat %M:%S
section P1
2/5: 0, 2
4/5: 6, 8
5/5: 11, 12
section P2
2/4: 2, 4
4/4: 9, 11
section P3
2/2: 4,6
section P4
1/1: 8,9
| Process | Arrival Time | Burst Time | Turn Around Time | Waiting Time |
|---|---|---|---|---|
| P1 | 0 | 5 | 2 | 7 |
| P2 | 1 | 4 | 10 | 6 |
| P3 | 2 | 2 | 4 | 2 |
| P4 | 3 | 1 | 6 | 5 |
Example Time Quantum = 10
gantt
title RR Gantt Chart
dateFormat X
axisformat %M:%S
section P1
10/20: 0, 10
20/20: 10, 20
section P2
10/25: 25, 35
20/25: 45, 55
25/25: 65, 70
section P3
10/25: 35,45
20/25: 55, 65
25/25: 80, 85
section P4
10/15: 70, 80
15/15: 85, 90
section P5
10/10: 100, 110
section P6
10/10: 110, 120
| Process | Arrival Time | Burst Time | Turn Around Time | Waiting Time |
|---|---|---|---|---|
| P1 | 0 | 20 | 20 | 0 |
| P2 | 25 | 25 | 45 | 20 |
| P3 | 30 | 25 | 55 | 30 |
| P4 | 60 | 15 | 30 | 15 |
| P5 | 100 | 10 | 10 | 0 |
| P6 | 105 | 10 | 15 | 5 |
Multi Level Queue Scheduling
- Multiple Queues are maintained with each Queue having a Priority
- Each Queue may represent a process, such as System Processes, Interactive Processes, Student Processes etc.
- Lower priority queues will only be executed until the higher priority queues are not empty
- If lower priority queue process is executing and within that time a higher priority queue process arrives then the lower priority queue process is preempted and higher priority process is executed first.
gantt
title Two Queues with Q1 (RR Time Quantum 2) & Q2 (FCFS)
dateFormat X
axisformat %M:%S
section P1
2/4: 0, 2
4/4: 4, 6
section P2
2/3: 2, 4
3/3: 6, 7
section P4
2/5: 10, 12
4/5: 12, 14
5/5: 14, 15
section P3
3/8: 7, 10
8/8: 15, 20
| Processes | Arrival Time | Burst Time | Queue Number |
|---|---|---|---|
| P1 | 0 | 4 | 1 |
| P2 | 0 | 3 | 1 |
| P4 | 10 | 5 | 1 |
| P3 | 0 | 8 | 2 |
Multi Level Feedback Queue
- Initially all processes belong to the first queue
- Shift the processes to below queues if they are not bursted within the current queue
- Last queue always have FCFS
| Processes | Burst Time |
|---|---|
| P1 | 30 |
| P2 | 20 |
| P3 | 10 |
gantt
title Multil Level Feedback Queue - RR TQ = 1 (Queue 1) | RR TQ = 2 (Queue) 2 & FCFS
dateFormat X
axisformat %M:%S
section P1
(Queue 1) 1/30: 0, 1
(Queue 2) 3/30: 3, 5
(Queue 3) 30/30: 9, 35
section P2
(Queue 1) 1/20: 1, 2
(Queue 2) 3/20: 5, 7
(Queue 3) 20/20: 35, 51
section P3
(Queue 1) 1/10: 2, 3
(Queue 2) 3/10: 7, 9
(Queue 3) 10/10: 51, 57