A Crash Course on Some Popular OS Scheduling Algorithms
At any given time, the Operating System has a difficult choice to make ~
“What task should be executed on the CPU from a given set of tasks?”
But how does the OS decide which process to run, and for how long? That’s where the magic of scheduling algorithmscomes in. Let’s look at some of the most popular algorithms that the OS uses to orchestrate the execution of processes, ensuring efficient use of resources and optimal performance. Ready to dive in?
Starting with the first algorithm, the First Come — First Serve.
As the name suggests, this scheduling algorithm works by allocating CPU to the tasks that arrived the earliest. It is much like how any queue works! The person at the head of the queue would be the one served first.
There is, however, a major downside to this algorithm. Consider a case where the person at the head of the queue takes a very long time to get his/her job done. In such a situation, everyone in the queue will have to wait. Because of this, the First Come-First Serve algorithm suffers from low throughput and longer average waiting times.
Next up on the list is the Round-Robin algorithm.
To ensure fairness among all arriving tasks, the OS can allocate fixed, equal time slices of CPU time to each task. This is one of the simplest algorithms to implement, ensuring that no tasks face starvation.
Round-robin is a preemptive algorithm, i.e., a task’s execution can be paused mid-way by the scheduler. This leads to some extra overhead of context-switching, where the CPU stops processing a task in hand and picks another task. This also suffers from the problem of low throughput.
Moving on to the Shortest Job Next Algorithm.
The Shortest Job Next (SJN) also known as Shortest Job First (SJF) is a scheduling method where the process with the shortest expected execution time is given priority. This approach aims to minimize the average waiting time for all processes, making it highly efficient when tasks vary in length. By prioritizing shorter tasks, the system can process many jobs quickly, leading to less idle time and improved throughput.
The problem with SJN is that it can lead to starvation, where longer processes may never get a chance to run if shorter tasks keep arriving. This creates unfairness, as some processes are perpetually delayed.
Following up with a similar yet another algorithm which is the Shortest Remaining Time First Algorithm.
The Shortest Time Remaining (STR) algorithm is a preemptive version of the Shortest Job Next (SJN) algorithm, where the process with the least remaining time to execute is given priority. It aims to complete the task that is closest to completion, allowing the CPU to complete tasks as quickly as possible.
STR aims to minimize the total time spent waiting for all processes by always focusing on the process that will finish the soonest.
One of the key advantages of STR is its ability to respond dynamically to new tasks. If a process with a shorter remaining time arrives while another is running, the scheduler preempts the current process to give the new task a chance. This reduces the overall waiting time and improves system responsiveness
However, STR requires constant tracking of the remaining time for each process, which can be difficult in practice. Moreover, like SJN, it suffers from starvation. Longer tasks may never get executed if a constant stream of shorter tasks keeps arriving, leading to unfair delays.
Lastly, let’s discuss the Priority Scheduling algorithm.
Priority Scheduling is an algorithm where each process is assigned a priority, and the CPU is allocated to the process with the highest priority. Think of it like a doctor seeing the most critical patients first, ensuring that urgent tasks are handled before less time-sensitive ones. This approach is widely used in real-time systems where some tasks, like emergency services, need to be prioritized to ensure quick response times.
One of the main advantages of priority scheduling is that it allows the operating system to cater to different types of tasks with varying importance.
However, this system also comes with significant downsides. Starvation is a major issue, where low-priority processes might never get executed if higher-priority processes keep arriving. To mitigate this, some variations of the algorithm implement aging, where the priority of a process gradually increases the longer it waits.
And with that, we come to the end of this article! We’ve explored some of the most popular scheduling algorithms, but there’s much more to discover. If you’d like me to dive into more algorithms in a fun and engaging way, don’t forget to give this story a clap and leave a comment below! I’d love to hear your thoughts and suggestions.