Categories
UoPeople

Fast-food, Single-Queue versus Multi-Queue Scheduling

This text is an adaptation from a post in the Operating Systems 1 course discussion forum.

Let’s think about a simple fast-food restaurant with one counter attendant and one employee in the kitchen responsible for preparing the orders that arrive. The counter attendant is the scheduler, and the system is First-In, First-Out. The customer arrives, makes a request, pays for it, and waits for the food. If the orders are small, everything is prepared quickly, and the line runs smoothly. But sometimes there are big families that make huge orders. It is definitely not efficient to make the whole line wait in these situations.

The owner might decide to use a Shortest Job (or Order) First method, but I suspect that the customers (especially large families) would not be pleased with this option. Another option is to run a Round Robin process in the kitchen, where the cooker prepares each meal for a short time, rotating around all the orders and delivering as they are ready. I suspect that following this method can make everyone wait a long time, and the food will probably arrive cold.

It is obvious that a successful fast-food restaurant will need more employees at the counter and the kitchen (like more CPUs) and better schedulers, which mean more queues and/or solutions to take people’s orders and process them. For example, to visualize the single-queue versus multi-queue scheduling, picture a fast-food place with many workers in the kitchen, but only one counter. The speed is improved if compared against the “one counter and one kitchen” scenario, but if the place is crowded, we still have a huge line. This is not scalable.

As I am writing my fast-food analogy I can see that it is possible to even to think about caches. This, in fact, is a good advantage of fast-food restaurants. The options are predictable, and a smart manager knows which options are ordered often at certain times of the day (temporal locality). They can be prepared in advance to be heated at the right time, for example. If we talk about combos, such as a hamburguer with french fries, there is even a parallel with the spatial locality concept. Things that are ordered together can be prepared together.

Multi-queue scheduling is the obvious choice, and that is the reason why most fast-food chains have multiple counters. People tend to naturally follow an internal algorithm to avoid load imbalance between queues, changing from the crowded one to the empty one to order as fast as possible. Some restaurants also have special queues for small orders or just desserts. This is an example of Multilevel Feedback Queue (MLFQ) together with Multi-Queue scheduling, where different queues run different scheduling algorithms inside it.

I hope that this fast-food analogy is helpful to better understand this challenging Operating Systems topic. If not, at least it probably made you hungry.

Reference:

Arpaci-Dusseau, R. & Arpaci-Dusseau, A. (2012). Operating Systems: Three Easy Pieces. Madison, WI: University of Wisconsin-Madison. Available at http://pages.cs.wisc.edu/~remzi/OSTEP//

Categories
Tóin UoPeople

Family Scheduler

Unfortunately, this week the contribution is coming late. My personal scheduler (my brain) was unable to switch efficiently between processes during this week. The task of traveling on the weekend to meet my family took priority and starved all other processes on the queue. There was no First In, First Out algorithm applied, as I began to study last Thursday. Then this also got interrupted by work related tasks by the end of the week, together with the previously mentioned travel.

A smart personal scheduler would have allocated resources to the assignments appropriately, even under a long and time-consuming process such as going to another city. It could have used a Multi-level Feedback Queue (MLFQ) to clearly organize the competing processes and, eventually, run a Round-Robin algorithm to rotate the week assignments in the morning or late at night, when the CPU usage was reduced. This was not fully optimized, as I was only able to cover the reading assignments during the weekend. The result was that the discussion forum assignment went to the end of the queue and no priority boost was applied to level everything from time to time. Such a pity.

Despite the rush at the end, I was glad that no Shortest Job First (SJF) or Shortest Time to Completion First (STCF) was used instead. This could have made me lose the train, or even the dinner with my family. It is not a good idea to simplify too much and lose the context of the processes at hand. There are things that are priority no matter what, and for me family is one of them.

References

Arpaci-Dusseau, R. & Arpaci-Dusseau, A. (2012). Operating Systems: Three Easy Pieces. Madison, WI: University of Wisconsin-Madison. Available at http://pages.cs.wisc.edu/~remzi/OSTEP//