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//

Leave a Reply

Your email address will not be published. Required fields are marked *