Criteria of CPU Scheduling
There are several criteria that the CPU scheduler considers when selecting the next process to be executed. These criteria help in evaluating the performance of different scheduling algorithms & determining which one is best suited for a particular situation. The main criteria of CPU scheduling are:
1. CPU Utilization: It refers to the percentage of time the CPU is busy executing processes. The goal is to maximize CPU utilization & minimize idle time.
2. Throughput: It is the number of processes completed per unit time. A higher throughput indicates that the system is able to execute more processes in a given time period.
3. Turnaround Time: It is the total time taken by a process from its submission to its completion, including waiting time & execution time. The aim is to minimize the average turnaround time.
4. Waiting Time: It is the amount of time a process spends waiting in the ready queue before it gets executed. The objective is to minimize the average waiting time.
5. Response Time: It is the time between the submission of a request & the first response from the system. The goal is to minimize the average response time.
Note: A good CPU scheduling algorithm should try to optimize these criteria based on the specific requirements of the system & the nature of the processes being executed.
Importance of Selecting the Right CPU Scheduling Algorithm for Specific Situations
Selecting the right CPU scheduling algorithm is crucial for optimizing system performance & ensuring the efficient utilization of resources. Different scheduling algorithms have different strengths & weaknesses, & they are suited for different types of workloads & system requirements.
For example, in a system with a mix of CPU-bound & I/O-bound processes, a scheduling algorithm that prioritizes I/O-bound processes, such as the Shortest Job Next (SJN) algorithm, can help reduce the average waiting time & improve overall system performance. On the other hand, in a system with mostly CPU-bound processes, a scheduling algorithm that focuses on maximizing CPU utilization, such as the Round Robin (RR) algorithm, may be more appropriate.
Moreover, the choice of scheduling algorithm can also impact the user experience. In an interactive system, such as a desktop computer, a scheduling algorithm that provides good response times, such as the Priority Scheduling algorithm, is important for ensuring a smooth user experience. In contrast, in a batch processing system, such as a scientific computing cluster, a scheduling algorithm that optimizes throughput, such as the First-Come, First-Served (FCFS) algorithm, may be more suitable.
Therefore, it is essential to carefully consider the specific requirements & characteristics of the system & the workload when selecting a CPU scheduling algorithm. Choosing the right algorithm can significantly impact system performance, resource utilization, & user satisfaction.
Factors Influencing CPU Scheduling Algorithms
Several factors influence the choice & performance of CPU scheduling algorithms. These factors are:
1. Process Priority: Some processes may have higher priority than others based on their importance or urgency. Priority-based scheduling algorithms, such as Priority Scheduling, take process priority into account when making scheduling decisions.
2. Process Type: Processes can be classified as CPU-bound or I/O-bound. CPU-bound processes spend most of their time performing computations, while I/O-bound processes spend most of their time waiting for I/O operations to complete. Scheduling algorithms may treat these process types differently to optimize system performance.
3. System Load: The number & characteristics of processes in the ready queue can affect the performance of scheduling algorithms. Some algorithms may perform better under heavy load, while others may be more suitable for light load conditions.
4. Context Switching: Context switching occurs when the CPU switches from one process to another. It involves saving the state of the current process & loading the state of the next process. Frequent context switching can overhead & impact system performance. Scheduling algorithms that minimize context switching, such as the Shortest Remaining Time First (SRTF) algorithm, can help reduce this overhead.
5. Preemption: Preemptive scheduling algorithms allow the CPU to be taken away from a running process & allocated to another process based on certain criteria, such as priority or shortest remaining time. Non-preemptive algorithms, on the other hand, allow a process to run until it voluntarily releases the CPU or terminates. The choice between preemptive & non-preemptive scheduling depends on the specific requirements of the system.
6. Fairness: Scheduling algorithms should ensure fair allocation of CPU time among processes. Fairness can be achieved through techniques such as time-slicing, where each process is given a fixed amount of CPU time in a cyclic manner, as in the Round Robin algorithm.
CPU Scheduling Algorithms
There are several CPU scheduling algorithms, each with its own characteristics & use cases.
Some of the commonly used CPU scheduling algorithms are:
1. First-Come, First-Served (FCFS)
In this algorithm, processes are executed in the order they arrive in the ready queue. The process that arrives first gets the CPU first. FCFS is a non-preemptive algorithm & is simple to implement, but it can lead to long waiting times for processes that arrive later.
2. Shortest Job Next (SJN)
Also known as Shortest Job First (SJF), this algorithm selects the process with the shortest expected execution time to be executed next. SJN can be either preemptive or non-preemptive. It aims to minimize the average waiting time, but it requires knowledge of the execution time of each process, which may not always be available.
3. Priority Scheduling
In this algorithm, each process is assigned a priority, & the process with the highest priority gets the CPU first. Priority can be based on various factors, such as the importance of the process, the amount of time it has been waiting, or the resource requirements. Priority Scheduling can be either preemptive or non-preemptive.
4. Round Robin (RR)
This algorithm assigns a fixed time slice (quantum) to each process in a cyclic manner. Each process gets the CPU for a specific time quantum, & if it is not completed within that time, it is preempted & moved to the end of the ready queue. RR is a preemptive algorithm that ensures fair allocation of CPU time among processes, but it can lead to higher context switching overhead.
5. Multilevel Queue Scheduling
This algorithm partitions the ready queue into multiple separate queues, each with its own scheduling algorithm. Processes are assigned to different queues based on their characteristics, such as priority or process type. For example, the foreground queue may use RR scheduling, while the background queue may use FCFS scheduling.
6. Multilevel Feedback Queue Scheduling
This algorithm is an extension of the Multilevel Queue Scheduling algorithm. It allows processes to move between different queues based on their behavior & CPU burst time. If a process uses too much CPU time, it may be moved to a lower-priority queue, while a process that waits for too long in a lower-priority queue may be moved to a higher-priority queue.
Note: These are just a few examples of CPU scheduling algorithms. The choice of algorithm depends on the specific requirements & characteristics of the system, such as the types of processes, the desired performance metrics, & the available resources.
Frequently Asked Questions
What happens if a process uses up its allocated time slice in the Round Robin scheduling algorithm?
If a process does not complete within its allocated time slice, it is preempted & moved to the end of the ready queue, allowing other processes to execute.
Can a lower-priority process ever get the CPU if there are always higher-priority processes in the ready queue?
In a preemptive priority scheduling algorithm, a lower-priority process may get the CPU if all higher-priority processes are blocked or waiting for I/O operations.
How does the Shortest Job Next (SJN) algorithm handle processes with unknown execution times?
The SJN algorithm requires knowledge of the execution time of each process. If the execution time is unknown, the algorithm may use estimates or heuristics to make scheduling decisions.
Conclusion
In this article, we have learned about CPU scheduling, its importance in operating systems, & the various criteria & factors that influence the choice of scheduling algorithms. We discussed several common CPU scheduling algorithms, including FCFS, SJN, Priority Scheduling, Round Robin, & Multilevel Queue/Feedback Queue Scheduling. Each algorithm has its strengths & weaknesses, & the selection of the most appropriate algorithm depends on the specific requirements & characteristics of the system.
You can also practice coding questions commonly asked in interviews on Coding Ninjas Code360.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
24+ registered 
