Introduction:
Multiprogrammed operating systems are based on CPU scheduling. By which the operating system selects a process from the ready queue to be executed by the CPU, this process is done by CPU scheduler.
There are many CPU scheduling algorithms with different properties, so there are many criteria for comparing CPU scheduling algorithms. These criteria include CPU utilization, throughput, turnaround time, waiting time, and response time. Next table the meaning of each one is discussed briefly.
| Criteria | Definition | Desire |
| CPU utilization | It measures to what extent we can keep the CPU as busy as possible | Maximize |
| Throughput | It is a number of completed processes per time unit | Maximize |
| Turnaround time | It is a time from the submission of a process to the time of its completion. | Minimize |
| Waiting time | It is the sum of the waiting periods spent in the ready queue. | Minimize |
| Response time | It is the time from the submission of the process to the first response from the OS. | Minimize |
In this post, I will briefly give an introduction to different CPU scheduling algorithms and list an example with different arrival time for each algorithm and model answers with gantt chart.
First-Come, First-Served (FCFS)
- In this algorithm, the process that requests the CPU first is allocated the CPU first.
- The implementation of the FCFS policy is managed with a FIFO queue.
- The code of the its implementation is easy to write and understand.
- One drawback of this algorithm is that the avarage waiting time is long.
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using FCFS scheduling algorithm .
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time |
| A | 13 | 10 |
| B | 6 | 15 |
| C | 8 | 20 |
| D | 5 | 25 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | 10-10=0 | 13 |
| B | 23-15=8 | 14 |
| C | 29-20=9 | 17 |
| D | 37-25=12 | 17 |
| Average Waiting time= (0+8+9+12)/4=7.25 | Average Turnaround time= (13+14+17+17)/4=15.25 |
Non-preemptive Shortest-Job-First (SJF)
- In this algorithm, the CPU is assigned to the process with the smallest next burst time.
- If the next CPU bursts of two processes are the same, then use FCFS algorithm.
- It gives minimal average waiting time because of bringing the short job before the longest one. This decreases the waiting time of the short process more than it increases the waiting time of the long process
- One drawback of this algorithm that it can't be implemented at the level of short-term CPU scheduling because the CPU burst time of the next process can't be known.
- It has two variant; SJF is a non-preemptive algorithm and Shortest remaining time is a preemptive one
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using Non-preemptive Shortest-Job-First scheduling algorithm .
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time |
| A | 13 | 10 |
| B | 6 | 15 |
| C | 8 | 20 |
| D | 5 | 25 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | 10-10=0 | 13 |
| B | 23-15=8 | 14 |
| C | 34-20=14 | 22 |
| D | 29-25=4 | 9 |
| Average Waiting time= (0+8+14+4)/4=6.5 | Average Turnaround time= (13+14+22+9)/4=14.5 |
Preemptive Shortest-Job-First (SJF)
- It is known also as Shortest Remaining Time First algorithm.
- Same as non preemptive SJF except if a new process arrives with CPU burst length less than remaining time of current running process, the new process preempts the running one.
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using Preemptive Shortest-Job-First scheduling algorithm .
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time |
| A | 13 | 10 |
| B | 6 | 15 |
| C | 8 | 20 |
| D | 5 | 25 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | (10-10)+(21-15)=6 | 19 |
| B | 15-15=0 | 6 |
| C | 34-20=14 | 22 |
| D | 29-25=4 | 9 |
| Average Waiting time= (6+0+14+4)/4=6 | Average Turnaround time= (19+6+22+9)/4=14 |
Non-Preemptive Priority Scheduling
- In this approach, the CPU is assigned to the process with the highest priority.
- If a two processes have the same priority, then they are scheduled by FCFS algorithm.
- Some operating systems use low numbers as a low priority, others use low numbers as a high priority.
- It has two variant; non-preemptive approach and a preemptive approach.
- When a process enters the ready queue, its priority is compared with the priority of the currently running process, then it is put in the head of ready queue.
- It can lead to process starvation, the processes with a low priority will wait indefinitely.
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using Non-preemptive priority scheduling algorithm, suposse that each process will run the listed amount of time and lower priority numbers corresponding to higher CPU priority (1 is the highest) .
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time | Priority |
| A | 13 | 10 | 4 |
| B | 6 | 15 | 2 |
| C | 8 | 20 | 1 (Highest) |
| D | 5 | 25 | 3 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | (10-10)=0 | 13 |
| B | 31-15=16 | 22 |
| C | 23-20=3 | 11 |
| D | 35-25=12 | 17 |
| Average Waiting time= (0+16+3+12)/4=7.75 | Average Turnaround time= (13+22+11+17)/4=15.75 |
Preemptive Priority Scheduling
- Same as non preemptive priority except When a process enters the ready queue, its priority is compared with the priority of the currently running process, then if the priority of the new process is higher than the running one, then preemption is done.
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using Preemptive priority scheduling algorithm, suposse that each process will run the listed amount of time and lower priority numbers corresponding to higher CPU priority (1 is the highest) .
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time | Priority |
| A | 13 | 10 | 4 |
| B | 6 | 15 | 2 |
| C | 8 | 20 | 1 (Highest) |
| D | 5 | 25 | 3 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | (10-10)+(34-15)=19 | 32 |
| B | (15-15)+(28-20)=8 | 14 |
| C | 20-20=0 | 8 |
| D | 29-25=4 | 9 |
| Average Waiting time= (19+8+0+4)/4=7.75 | Average Turnaround time= (32+14+8+9)/4=15.75 |
Round robin Scheduling
- It is a preemptive algorithm designed for time sharing operating systems.
- It solves starvation problem.
- It likes FCFS but preemption is done to switch between processes.
- Ready queue is considered a circular queue and scheduler gives each process CPU resources for 1 time quantum.
- New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
Example :
For the given set of processes:
- Draw the Gantt chart that illustrates the execution of these processes using Round Robin scheduling algorithm with ( quantum=4).
- Calculate the average waiting time and turnaround time for these processes.
| Process ID | CPU burst time | Arrival time |
| A | 13 | 10 |
| B | 6 | 15 |
| C | 8 | 20 |
| D | 5 | 25 |
Gantt chart:
| Process ID | Waiting time= Service Time - Arrival Time | Turnaround |
| A | 10-10+(22-18)+(36-26)=14 | 27 |
| B | (18-15)+(30-22)=11 | 17 |
| C | (26-20)+(37-30)=13 | 21 |
| D | (32-25)+(41-36)=12 | 17 |
| Average Waiting time= (14+11+13+12)/4 =12.5 | Average Turnaround time= (27+17+21+17)/4=20.5 |
