CPU scheduling is a technique used by operating systems to manage the allocation of the CPU's processing time to the various processes or threads that are competing for it. A CPU scheduling algorithm is a method used by the operating system to determine which process should be given access to the CPU next. The selection process will be carried out by the CPU scheduler. It selects one of the processes in memory that are ready for execution.
| Process ID | Arrival Time | Burst Time |
|---|---|---|
| P1 | CPU | |
In a multi-tasking operating system, multiple processes may be running simultaneously, and the CPU must allocate time to each of these processes. The CPU scheduling algorithm plays a crucial role in determining how efficiently the system uses the CPU and how responsive it is to user requests. CPU scheduling algorithms can be preemptive or non-preemptive. In preemptive algorithms, the currently executing process can be interrupted if a higher-priority process arrives or if the current process exceeds its allotted time slice. In non-preemptive algorithms, a process will continue to execute until it releases the CPU voluntarily. The performance of a CPU scheduling algorithm can be evaluated based on several metrics, such as turnaround time, waiting time, and response time. The goal is to minimize these metrics and ensure that the system is responsive and efficient. Different scheduling algorithms may be more suitable for different types of workloads, and the choice of algorithm may depend on factors such as system utilization, average process run time, and user requirements.
First-Come, First-Served (FCFS) is the simplest CPU scheduling algorithm, where the processes are executed in the order they arrive in the ready queue. The process that enters the queue first gets the CPU first, and the other processes wait in a queue until the currently running process completes its execution. In this type of algorithm, processes which requests the CPU first get the CPU allocation first. This is managed with a FIFO queue.
Shortest Job First is a scheduling policy that selects the waiting process with the smallest execution time to execute next. It is a non-preemptive and Greedy algorithm. Shortest Job first has the advantage of having a minimum average waiting time among all scheduling algorithms. It may cause starvation if shorter processes keep coming.
This Algorithm is the preemptive version of SJF scheduling. In SRTF, the execution of the process can be stopped after certain amount of time. At the arrival of every process, the short term scheduler schedules the process with the least remaining burst time among the list of available processes and the running process.
Prerequisite – CPU Scheduling Given n processes with their Arrival times and Burst times, the task is to find average waiting time and average turn around time using HRRN scheduling algorithm. The name itself states that we need to find the response ratio of all available processes and select the one with the highest Response Ratio. A process once selected will run till completion.
Longest Job First is a non-preemptive scheduling algorithm. This algorithm is based upon the burst time of the processes. The processes are put into the ready queue based on their burst times i.e., in a descending order of the burst times. As the name suggests this algorithm is based upon the fact that the process with the largest burst time is processed first. The burst time of only those processes is considered that have arrived in the system until that time.
Prerequisite – Process Management & CPU Scheduling This is a pre-emptive version of Longest Job First (LJF) scheduling algorithm. In this scheduling algorithm, we find the process with the maximum remaining time and then process it. We check for the maximum remaining time after some interval of time(say 1 unit each) to check if another process having more Burst Time arrived up to that time.
Round Robin is the preemptive process scheduling algorithm. Each process is provided a fix time to execute, it is called a quantum. Once a process is executed for a given time period, it is preempted and other process executes for a given time period. Context switching is used to save states of preempted processes.