Priority Queues1.1. Job Scheduler and Dynamic Task Management

So, supposing we would have a job scheduler running on an operating system. So, when we run multiple tasks on an operating system each of them runs for a little bit of time, and then is opted out. So, job scheduler maintains a list of all jobs which are pending along with their priorities. Whenever the processor is free, the scheduler picks out a job with a maximum priority in the list and schedules it. Now what happens? Of course, is this dynamic. So, while some jobs are running, other new jobs may arrive. So, each time when new jobs arrive they will come with different priorities, and this is the job of the scheduler to make sure that the new jobs with higher priority come ahead of older jobs with lower priority.

In a computer system, a job scheduler is responsible for managing the execution of multiple tasks or jobs. These jobs take a certain amount of time to complete. The scheduler keeps track of which jobs are pending and their respective priorities. When the CPU is available, the scheduler selects the job with the highest priority to execute. This is important as new jobs may arrive while others are running, and the scheduler must ensure that high-priority tasks are executed before lower-priority ones.

Think of a restaurant where customers place orders at different times. The kitchen staff needs to manage these orders efficiently. If a customer who ordered a gourmet meal arrives after someone who ordered a simple sandwich, the staff would prioritize the gourmet meal because it is more complex and requires more preparation time. This is similar to how a job scheduler ensures high-priority tasks are managed first.

From a data structure point of view, our question is what is the best way for the scheduler to maintain the list of pending jobs with their priorities? So, this is what we call a priority queue? So, we have two basic operations in a priority queue; the first is to extract the next job which in this case means take the job with the highest priority, and remove it from the queue. Now of course, we have the situation where you have multiple jobs in the same priority. So, we do not assume the priorities are unique, but if they are not unique then we can assume either there is some type writing rule or we do not care which one of the highest priority jobs we get right.

To manage jobs effectively, the scheduler uses a data structure known as a priority queue. This structure allows the scheduler to maintain an organized list of jobs based on their priorities. The two primary operations of a priority queue are 'extract' (or 'delete max'), which removes the job with the highest priority from the queue, and 'insert', which adds a new job along with its priority. If two or more jobs have the same priority, the scheduler must have a method to decide which one to process next.

Consider a queue at a grocery store where customers with priority passes (like VIP members) can skip the line. The priority queue works like this: when a VIP customer arrives, they go to the front of the line (extract max), while others can still join the queue (insert). If two VIPs arrive simultaneously, the service staff might follow a rule like 'first in line' to decide who gets served first.

So, the first solution that one could think of to keep such data is to maintain a list, some kind of a linear structure, an array or a list, since it is growing dynamically a list is your obvious choice. Now if we keep an unsorted list, then it is easy to add a job, which is up to appended to the list. So, insertion is a constant time operation takes time O(1), but as we have seen many times if we have an unsorted list, then we have to scan the entire list to find the minimum or the maximum. So, in this case if we want to do a delete max from an unsorted list, this operation is going to take as linear time proportional to the size of the list or the number of jobs in a pending at the moment.

When considering data structures for managing the priority queue, one might start with a simple list or array. Inserting a new job into an unsorted list is quick and can be done in constant time O(1). However, finding and removing the job with the highest priority from this unsorted list is slow, requiring a scan of the entire list, which takes time proportional to the number of jobs (linear time). Thus, while insertion is fast with an unsorted list, deletion is not efficient.

Think about students registering for a class. If they can just add their names to a list without worrying about order, it’s quick (like adding new jobs in an unsorted list). But when the list needs to announce the student who registered first, the staff must check every name, which takes a lot longer – this reflects the inefficiency of deletion in an unsorted list.

So, between an unsorted list or in a sorted list, we have a trade-off in an unsorted list delete max takes linear time, in a sorted list insert takes linear time. So, whether we use an unsorted list or a sorted list over a sequence of N jobs, supposing N jobs arrive in the system, we will process them. Then we will be inserting them N times and deleting max N times. So, whichever solution we use among these two, we will end up spending order N squared time.

Using a sorted list instead of an unsorted one may seem like an improvement since deletion can then be done in constant time when the list is maintained in order. However, the insert operation will take longer as it requires finding the correct position, which takes linear time. As a result, both methods can lead to inefficiencies, particularly when many jobs need to be processed since we will end up with an overall time complexity of O(N^2) for processing N jobs.

Consider a scenario where students are lining up for a lecture. If they randomly join a line, counting how many are in line takes time (unsorted). If instead, they join according to their student ID in sorted order, adding to the line takes time as they look for their correct spot (sorted). Whichever way they choose will slow down the process of getting through the line!

So, we have to go from a one dimensional structure to a two dimensional structure. So, let us start with a very naive two dimensional structure, just to show how we can get drastic improvements, just by moving from one dimension to two dimensions. So, here we assume that we know in advance the number of total jobs we can have. So, we have assumed in this case say that N is 25. So, now what we do is instead of maintaining a one-dimensional list of length 25-maximum length 25, we reorganize this list as a square array of 5 by 5.

To improve the efficiency of the priority queue further, we can transition from a one-dimensional array to a two-dimensional array. For example, if we anticipate having 25 jobs, we can organize them in a 5x5 grid. This allows us to maintain a list where each row can be sorted independently. When looking for a position to insert a job, we check each row for available space, potentially speeding up operations because they are contained within smaller groupings.

Think of a library where books are organized not just on one long shelf (like a one-dimensional list) but across multiple shelves, with each shelf holding a specific genre. When you want to find a book, you can first decide which shelf to search, making your search quicker and more efficient.

Having deleted 43 then we remove it, and then of course we have to also reduce the size back from 4 to 3. So, we can keep track of the size as in when we manipulate in the previous example as we had increased 11, we make this 3 into 4. So, again it is an order root N operation. So, we have now achieved a data structure, which keeps track of elements in a priority queue where insert takes order root N time, delete max takes order root N time, and therefore, now processing a sequence of N jobs takes N root N time.

By utilizing the two-dimensional structure, we significantly improved our operations, allowing both insertion and deletion to take approximately O(√N) time. This means that if we process N jobs, the total time becomes N√N, a substantial improvement over the O(N^2) from previous methods. This efficiency is key to handling larger numbers of jobs in a timely manner.

It’s like a skilled chef working in a modern kitchen. Instead of searching through a huge pile of ingredients spread out everywhere (leading to chaos and time wasted), they organize everything neatly in sections (like rows in a two-dimensional array). This organization allows the chef to find and use what they need quickly, significantly reducing the time to complete meals or orders.

--