CPU Scheduling Algorithms in Operating System
CPU Scheduling:
Scheduling is a fundamental operating system function. Almost all computer resources are scheduled before use. CPU Scheduling is the basis of the Multi-Programmed Operating System. If a process (job) is waiting for an I/o request, then the CPU switches from that job to another job. So, the CPU is always scheduled before use.
Types of CPU Scheduling in OS:
In OS, There are mainly two types of CPU Scheduling Schemes.
i. Non-Preemptive Scheduling: In Non-Preemptive Scheduling, the CPU assigns to a process, and the processor does not release until the completion of that process. The CPU will assign to some other job only after the previous job has finished.
ii. Preemptive Scheduling: In Preemptive Scheduling, the CPU can release the processes even in the middle of execution. Some running tasks interrupt for some time and resume later when the priority task has finished its execution.
Some following schedulers are given below:
1. Short-term scheduler: The function of a Short-term scheduler is that select a job from the ready queue and it gives them control of the CPU to that process with the help of ‘Dispatcher’. That’s why the Short-term scheduler is also say a CPU Scheduler.
2. Long-term scheduler: The function of the Long-term scheduler is that select the job from the pool of jobs and load these jobs into the main memory (ready queue) of the computer. So, the Long-term scheduler is also say a job scheduler.
3. Medium-term scheduler: If a process requests an I/O in the middle of the execution, then the process removes it from the main memory and load into waiting for a queue. When the I/O operation is complete, then the job moves from waiting for the queue to the ready queue that says a Medium-term scheduler.
CPU Scheduling Algorithms:
CPU Scheduling algorithms are the algorithms which uses for assigning the system resources to processes in an operating system. In Operating System, there are mainly five types of CPU Scheduling Algorithms.
First Come First Serve (FCFS) Scheduling:
First Come First Serve Scheduling is the simplest CPU scheduling algorithm. The criteria of the First Come First Serve Scheduling algorithm are the process that requests the CPU first is holds the CPU or which process enters the ready queue first is served first. The operating system maintains a data structure that is a ready queue. If a process requests the CPU then it loads into the ready queue which process is the head of the ready queue, and connects the CPU to that process.
| Process | Burst Time (ms) |
| P1 | 5 |
| P2 | 24 |
| P3 | 16 |
| P4 | 10 |
| P5 | 3 |
Consider the following set of processes that arrive at time o, the length of the CPU burst time in milliseconds (ms).
Burst time:
The burst time is the require-time of the CPU to execute that job. Generally, it’s unit milliseconds (ms). If the processes arrive in the order P!, P2, P3, P4, P5 and it serves in FCFS order.
Now, We have to calculate the average waiting time and average response time.
FCFS Average Turn Around Time:
[no-highlight]Turn Around Time = Finished time – Arrival time
Turn Around Time for:
P1 = 5 – 0 = 5
P2 = 29 – 0 = 29
P3 = 45 – 0 = 45
P4 = 55 – 0 = 55
P5 = 58 – 0 = 58
∴ Average Turn Around Time = (5 + 29 + 45 + 55 + 58) / 5 = 38.4 ms
[/no-highlight]
FCFS Average Waiting Time:
[no-highlight]Waiting Time = Starting time – Arrival time
Waiting Time for:
P1 = 0
P2 = 5 – 0 = 5
P3 = 29 – 0 = 29
P4 = 45 – 0 = 45
P5 = 55 – 0 = 55
∴ Average Waiting Time = (0 + 5 + 29 + 45 + 55) / 5 = 26.8 ms
[/no-highlight]
FCFS Average Response Time:
[no-highlight]Response Time = First response – Arrival time
Response Time for:
P1 = 0
P2 = 5 – 0 = 5
P3 = 29 – 0 = 29
P4 = 45 – 0 = 45
P5 = 55 – 0 = 55
∴ Average Response Time = (0 + 5 + 29 + 45 + 55) / 5 = 26.8 ms
[/no-highlight]
Shortest Job First (SJF) Scheduling:
Shortest Job First Scheduling is non-preemptive scheduling. The criteria of the Shortest Job First Scheduling algorithm is which process has the smallest CPU burst, CPU assigns to that process next. If two processes have the same CPU burst time, FCFS uses to break the tie.
| Process | Burst Time (ms) |
| P1 | 5 |
| P2 | 24 |
| P3 | 16 |
| P4 | 10 |
| P5 | 3 |
Now we have to calculate the average waiting time, average turnaround time, and average response time.
SJF Average Waiting Time:
[no-highlight]Waiting Time = Starting time – Arrival time
Waiting Time for:
P1 = 3 – 0 = 3
P2 = 34 – 0 = 34
P3 = 18 – 0 = 18
P4 = 8 – 0 = 8
P5 = 0
∴ Average Waiting Time = (3 + 34 + 18 + 8 + 0) / 5 = 12.6 ms
[/no-highlight]
SJF Average Turn Around Time:
[no-highlight]Turn Around Time = Finished time – Arrival time
Turn Around Time for:
P1 = 8 – 0 = 8
P2 = 58 – 0 = 58
P3 = 34 – 0 = 34
P4 = 18 – 0 = 18
P5 = 3 – 0 = 3
∴ Average Turn Around Time = (8 + 58 + 34 + 18 + 3) / 5 = 24.2 ms
[/no-highlight]
SJF Average Response Time:
[no-highlight]Response Time = First response – Arrival time
Response Time for:
P1 = 3 – 0 = 3
P2 = 34 – 0 = 34
P3 = 18 – 0 = 18
P4 = 8 – 0 = 8
P5 = 0
∴ Average Response Time = (3 + 34 + 18 + 8 + 0) / 5 = 12.6 ms
[/no-highlight]
Round Robin (RR) Scheduling:
Round Robin Scheduling (RR) is a preemptive scheduling algorithm, it is designed especially for time-sharing systems. In the Round Robin Scheduling algorithm, the CPU switches between the processes. When the time quantum is expired, the CPU switches to another job. If the process may have a CPU burst of less than a one-time quantum then the process releases the CPU voluntarily. The schedule will then proceed to the next process in the ready queue.
| Process | Burst Time |
| P1 | 30 |
| P2 | 6 |
| P3 | 8 |
The first 5 milliseconds assigns to process P1 when the time quantum expires, the CPU switches from process P1 to P2. When the time quantum of P2 expired, the process switches to process P3. Now we have to calculate the average waiting time, average turnaround time, and average response time.
Round Robin Average Waiting Time:
[no-highlight]Waiting Time for:
P1 = 0 + (15 – 5) + (24 – 20) = 14
P2 = 5 + (20 – 10) = 15
P3 = 10 + (21 – 15) = 16
∴ Average Waiting Time = (14 + 15 + 16) / 3 = 15 ms
[/no-highlight]
Round Robin Average Turn Around Time:
[no-highlight]Turn Around Time for:
P1 = 44
P2 = 21
P3 = 24
∴ Average Turn Around Time = (44 + 21 + 24) / 3 = 29.66 ms
[/no-highlight]
Round Robin Average Response Time:
[no-highlight]Response Time for:
P1 = 0
P2 = 5
P3 = 10
∴ Average Response Time = (0 + 5 + 10) / 3 = 5 ms
[/no-highlight]
Priority Scheduling:
Priority Scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue its priority. There are two types of Priorities, these are:
i. Internal Priority: It can define as some measurable quantities or qualities to compute the priority of a process.
- Memory Requirements
- Time Limits
- CPU and I/O Requirements
- File Requirements
ii. External Priority: External priority means that it is external to the operating system, the CPU allocates to the process with the highest priority. It can define as some measurable quantities or qualities to compute the priority of a process.
- The ratio of average I/O burst to average CPU burst
- Importance of process
Consider the below problem for a better understanding of the priority scheduling algorithm:
| Process | Burst Time (ms) | Priority |
| P1 | 6 | 2 |
| P2 | 12 | 4 |
| P3 | 1 | 5 |
| P4 | 3 | 1 |
| P5 | 4 | 3 |
Out of the five processes, P4 has the highest priority, so allocate the CPU to process P4 first. The next priority goes to P1 next. Continue this process until the five processes are completed. Now we have to calculate the average waiting time and average turnaround time.
Priority Average Waiting Time:
[no-highlight]Waiting Time for:
P1 = 3
P2 = 13
P3 = 25
P4 = 0
P5 = 9
∴ Average Waiting Time = (3 + 13 + 25 + 0 + 9) / 5 = 10 ms
[/no-highlight]
Priority Average Turn Around Time:
[no-highlight]Turn Around Time for:
P1 = 9
P2 = 25
P3 = 26
P4 = 3
P5 = 13
∴ Average Turn Around Time = (9 + 25 + 26 + 3 + 13) / 5 = 15.2 ms
[/no-highlight]
Multilevel Queue Scheduling:
In a Multilevel Queue Scheduling, the ready queue partitions into the number of ready queues. Each ready queue has a Multilevel Queue Scheduling algorithm.
Example: The ready queue is partitioned into 4 ready queues.
1. The first ready queue for the system process.
2. The Second ready queue for foreground jobs (iterative process).
3. The third ready queue for background jobs (Batch process)
4. The fourth ready queue for the student process.
The system process queue may follow FCFS, the interactive process may follow SJF, The background jobs queue may follow Round Robin and the student’s process may follow the SRT algorithm. The systems process queue has the highest priority of all, and the student process queue has the lowest priority of all. Each queue has an absolute priority queue.