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, the CPU is always scheduled before use.
Types of CPU Scheduling in OS:
In OS, There are mainly two types of CPU Scheduling Scheme.
Some following schedulers are given below:
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, 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 in milliseconds (ms).
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, average response time.
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 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)|
Now we have to calculate the average waiting time, average turnaround time, average response time.
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 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 scheduled will then proceed to the next process in the ready queue.
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, average response time.
Priority Scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue its priority. There are basically two types of Priorities, these are:
Consider the below problem for a 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 turnaround time.
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.
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.