CPU Scheduling Algorithms in Operating System
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, CPU is always scheduled before use.
Types of CPU Scheduling:
There are mainly two types of CPU Scheduling Scheme.
In the Non-Preemptive Scheduling, the CPU assigned to a process, the processor does not release until the completion of that process. The CPU will be assigned to some other job only after the previous job has finished.
In the Preemptive Scheduling, the CPU can release the processes even in the middle of executing. Some running task is interrupted for some time and resumed it later when the priority task has finished its execution.
Some following schedulers are given :
1. Short-term scheduler
2. Long-term scheduler
3. Medium-term scheduler
The function of Short-term scheduler is that select a job from the ready queue and it gives them control of CPU to that process with the help of ‘Dispatcher’. That’s why the Short-term scheduler is also called CPU Scheduler.
The function of the Long-term scheduler is that selects the job from the pool of jobs and loaded these jobs into main memory (ready queue) of the computer. So, the Long-term scheduler is also called job scheduler.
If a process requests an I/O in the middle of the execution, then the process removed from the main memory and loaded into waiting for a queue. When the I/O operation completed, then the job moved from waiting for the queue to ready queue that is called Medium-term scheduler.
Types of CPU Scheduling Algorithms:
1. First Come First Serve Scheduling Algorithm
2. Shortest Job First Scheduling Algorithm
3. Round Robin Scheduling Algorithm
4. Priority Scheduling Algorithm
5. Multilevel Queue Scheduling Algorithm
First Come First Serve (FCFS) Scheduling:
First Come First Serve Scheduling is the simplest CPU scheduling algorithm. The criteria of 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 request the CPU then it is loaded into the ready queue which process is the head of the ready queue, connect the CPU to that process.
|Process||Burst Time (ms)|
Consider the following set of processes that arrive at time o, the length of the CPU burst time is given in milliseconds (ms).
The burst time is the time required 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 served in FCFS order.
Now, We have to calculate the average waiting time, average response time.
Turn Around Time = Finished time - Arrival time Turn Around Time for P1 = 5 - 0 = 5 Turn Around Time for P2 = 29 - 0 = 29 Turn Around Time for P3 = 45 - 0 = 45 Turn Around Time for P4 = 55 - 0 = 55 Turn Around Time for P5 = 58 - 0 = 58
Average Turn Around Time =(5+29+45+55+58)/5 = 38.4 ms
Waiting Time = Starting time - Arrival time Waiting Time for P1 = 0 Waiting Time for P2 = 5 - 0 Waiting Time for P3 = 29 - 0 Waiting Time for P4 = 45 - 0 Waiting Time for P5 = 55 - 0
Average Turn Waiting Time =(0+5+29+45+55)/5 = 26.8 ms
Response Time = First response - Arrival time Response Time for P1 = 0 Response Time for P2 = 5 - 0 Response Time for P3 = 29 - 0 Response Time for P4 = 45 - 0 Response Time for P5 = 55 - 0
Average Response Time =(0+5+29+45+55)/5 = 26.8 ms
Shortest Job First (SJF) Scheduling:
Shortest Job First Scheduling is non-preemptive scheduling. The criteria of Shortest Job First Scheduling algorithm is that which process having the smallest CPU burst, CPU is assigned to that process next. If two process having the same CPU burst time, FCFS is used to break the tie.
|Process||Burst Time (ms)|
Now we have to calculate the average waiting time, average turn around time, average response time.
Waiting time = Starting time - Arrival time Waiting time for P1 = 3 - 0 = 3 Waiting time for P2 = 34 - 0 = 34 Waiting time for P3 = 18 - 0 = 18 Waiting time for P4 = 8 - 0 = 8 Waiting time for P5 = 0
Average Waiting Time = (3+34+18+8+0)/5 = 12.6 ms
Turn around time = Finish time - Arrival time Turn around time for P1 = 8 - 0 = 8 Turn around time for P2 = 58 - 0 = 58 Turn around time for P3 = 34 - 0 = 34 Turn around time for P4 = 18 - 0 = 18 Turn around time for P5 = 3 - 0 = 3
Average Turn Around Time = (8+58+34+18+3)/5 = 24.2 ms
Response time = First response time - Arrival time Response time for P1 = 3 - 0 = 3 Response time for P2 = 34 - 0 = 34 Response time for P3 = 18 - 0 = 18 Response time for P4 = 8 - 0 = 8 Response time for P5 = 0
Average Response Time = (3+34+18+8+0)/5 = 12.6 ms
Round Robin (RR) Scheduling:
Round Robin Scheduling (RR) is a preemptive scheduling algorithm, it is designed especially for time-sharing systems. In 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 one-time quantum then the process releases the CPU voluntarily. The scheduled will then proceed to the next process in the ready queue.
The first 5 milliseconds are assigned to process P1 when time quantum is expired, 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 turn around time, average response time.
Waiting time for P1 = 0+(15-5)+(24-20) = 14 Waiting time for P2 = 5+(20-10) = 15 Waiting time for P3 = 10+(21-15) = 16
Average Waiting Time = (14+15+16)/3 = 15 ms
Turn around time for P1 = 44 Turn around time for P2 = 21 Turn around time for P3 = 24
Average Turn Around Time = (44+21+24)/3 = 29.66 ms
Response time for P1 = 0 Response time for P2 = 5 Response time for P3 = 10
Average Response Time = (0+5+10)/3 = 5 ms
Priority Scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue its priority.
Generally, Priorities are two types.
It can be defined as some measurable quantities or qualities to compute the priority of a process.
It means that it is external to the operating system, the CPU is allocated to the process with the highest priority. External priority can be defined as some measurable quantities or qualities to compute the priority of a process.
Consider the below problem for better understanding of the priority scheduling algorithm:
|Process||Burst Time (ms)||Priority|
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, average turn around time.
Waiting time for P1 = 3 Waiting time for P2 = 13 Waiting time for P3 = 25 Waiting time for P4 = 0 Waiting time for P5 = 9
Average Turn Waiting Time = (3+13+25+0+9)/5 = 10 ms
Turn Waiting Time for P1 = 9 Turn Waiting Time for P2 = 25 Turn Waiting Time for P3 = 26 Turn Waiting Time for P4 = 3 Turn Waiting Time for P5 = 13
Average Turn Waiting Time = (9+25+26+3+13)/5 = 15.2 ms
Multilevel Queue Scheduling:
In a Multilevel Queue Scheduling, the ready queue is partitioned into the number of ready queues. Each ready queue has Multilevel Queue Scheduling algorithm.
Example: The ready queue is partitioned into 4 ready queues.
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 having the highest priority of all, and student process queue having the lowest priority of all. Each queue has an absolute priority queue.