Introduction to Scheduling:
In an Operating system (OS) multiple processes are running at a time. One process may have multiple threads in it also. For example, the MS Word program has multiple threads in it, one thread for checking grammar, one thread for counting words etc. All the processes and threads in OS are managed by the OS. The OS have to assign time for running these processes and thread. The management of processes and threads is known as CPU scheduling.
In OS multiprogramming is used to switch the CPU among different processes. The goal of multiprogramming is that at least one process keeps running on the CPU at a given time. If there is one processor then one process has to run at a given time and if there are multiple processors then there will be multiple processes running at a given time by the CPU.
There is a mechanism by which the CPU has to decide which process has to run next. For this purpose, the ready queue is created by OS. The process which has to run next is kept ready state. The process is moved from the ready state to the running state. If a process needs any input/output request then that process is moved from the running state to the waiting state. After the process completes the input/output operation then that process is again placed in a ready state to be run by the OS.
Objectives of Scheduling:
There are some goals or objectives of scheduling that makes the OS perform well. Some goals of scheduling are:-
- Maximize throughput. Throughput is the number of jobs completed per unit of time.
- The CPU time has to be divided in fairness way i.e. all jobs should be treated equally.
- As CPU is costly so the purpose of scheduling is to maximize CPU utilization.
- Minimize response time. Response time is the time a process stays in a ready state and gets CPU for the first time.
- Maximize utilization of other resources such as printers and disks.
- Minimize waiting time. Waiting time is the total time a process is kept in a ready state.
- Minimize turnaround time. Turnaround Time = Waiting Time + I/O Time + Computation Time.
Preemptive and Non-Preemptive Scheduling:
In Preemptive scheduling, if a process is running then if any high-priority process comes then the previous process has to be stopped. The previous process is moved from the running state to the ready state.
In non-preemptive scheduling, the process continues to run until it needs input/output resources. That process is given CPU time again after completing the input/output request.
Scheduling Criteria:
There are some criteria for scheduling that judge the performance of the CPU. They are:-
Turnaround Time: The amount of time that is needed to execute a process is called turnaround time. It is the actual job time plus the waiting time.
Waiting Time: The amount of time the process has to wait for execution is called waiting time. It is the turnaround time minus actual job time.
Throughput: The number of processes executed at a specified period is called throughput. Throughput decreases if the size of processes is huge. It increases for short processes.
CPU utilization: The CPU has to be active all the time for the best performance. CPU utilization is considered important in real-time applications and multi-programmed systems.
Response Time: The amount of time between a request being submitted and the first response being produced is called response time.
Scheduling Algorithms:
The CPU scheduling algorithm tries to minimize waiting time, turnaround time and response time. Also, it is used to maximize throughput and CPI utilization.
Below is a list of scheduling algorithms that we will discuss:-
- First Come First Served Scheduling
- Shortest Job First Scheduling
- Priority Scheduling
- Round Robin Scheduling
- Multi-Level Queue Scheduling
- Multi-Level Feedback Queue Scheduling
First Come First Served Scheduling:
In this type of scheduling the process which enters first will be executed first and then the second process which comes next will be executed next and so on.
If the first process has the longest burst time then other processes will have to wait longer. If the first process burst time is shorter then the remaining processes will be executed more quickly.
Shortest Job First Scheduling:
In this type of scheduling, the average waiting time is reduced. The process/job that has less completion time will be run first. Then the next job with the shortest completion time than the first job will be run.
The shortest job first scheduling (SJF) will run the process with a lower burst time and assigns it to the CPU.
Priority Scheduling:
In this type of scheduling all the processes are assigned a priority id. The priority id is in integer form and has a value from 0 to 10. The lower the value of the priority id the higher the priority value.
In priority scheduling the process with higher priority will be executed first then the second process with higher priority will be executed.
Round Robin Scheduling:
In Round Robin scheduling each process is given a quantum of time to run by the CPU. It is the same as FCFS but the process is switched to another process after a quantum of time.
All the processes are first placed in the ready queue then the first process that has come will be executed for some fixed time. Then the next process is ready queue will be executed for a fixed amount of time and so on.
Multi-Level Queue Scheduling:
In this type of scheduling two categories are made, one is interactive processes (foreground processes) and one is non-interactive (background processes). The interactive processes are executed first and have high priority and non-interactive processes have lower priority and are executed after interactive processes.
In this scheduling ready queue is divided into 5 sub-queues i.e.
- System processes
- Interactive processes
- Interactive editing processes
- Batch processes
- Student processes
Note that the process which is assigned to one sub-queue will remain in that sub-queue and it cannot be moved to other sub-queues until it completes its lifetime.
In a multi-level queue, each sub-queue has a priority assigned to it that range from 0 to 4. 0 is considered high priority and 4 is considered low priority. The processes that are placed in a higher sub-queue will be executed first then all the processes which are in low priority sub-queue will be executed and so on.
All the sub-queues are assigned a quantum of time and then the CPU shift to another sub-queue and execute processes in that sub-queue.
Multi-Level Feedback Queue Scheduling:
In this queue, processes are placed in different sub-queues as we see in multi-level queue scheduling. But in this scheduling, the processes can be moved to a higher priority queue if they are waiting longer.
This type of scheduling follows the first come first serve (FCFS) rule.
