The process scheduler overview

Explaining how your computer decides on what to do next from a very high level.

Vincenzo Marcella
5 min readJul 4, 2019

--

Imagine walking into Starbucks one day to get your regular order of a Bagel and Coffee to go. However, when you show up there is no line, a barrage of customers walking up to the cashier and telling them their order, and an absolute mess in the kitchen with tons of orders being attempted to be made. That would be a nightmare. Thankfully, when you show up to Starbucks to place an actual order this is not the case. Instead, they have a line of customers that approach the cashier when they’re ready. This type of system has a name, and it is known as a queue. According to Merriam Webster, a queue can non technically be defined as “a waiting line especially of persons or vehicles”.

But what do queues have to do with our computers and operating system? No matter what kind of device you’re using, the operating system that powers the device is constantly allocating time and resources towards the software running on it. This is an important process because it ensures that your operating system will run smoothly and that the most important processes are getting enough time and resources allocated to them when requested. The way that your operating system handles this is the same way that Starbucks chose to handle the lengthy lines of customers, by implementing a queue.

People standing in line from: https://solink.com/resources/reduce-wait-times-at-queue-lines-and-keep-customers-happy-during-service-delays

Let’s go back to Starbucks for a second, Except in this Starbucks they have a processor working as the cashier and in line are a bunch of your favorite apps like Spotify, Instagram, and Facebook trying to obtain some of that delicious CPU time your processor has. While you’re not all that interested in eating a a slice of CPU time, you decide to stay in line anyways. As you’re standing in line, someone walks into Starbucks and is recognized by the cashier. The cashier calls on the person to come up to the front of the line to get served and skips to the front of the line, passing by everyone else including yourself. Angered that you’ll now have to wait slightly longer, you yell at the cashier asking them what that was all about. The cashier responds, “I’m sorry, they have a higher priority than you”.

Whoa, what? Since when did Starbucks have priorities for which customers they should serve first? Well, thankfully every corporately owned Starbucks doesn’t have this policy. However, it doesn’t explain why this one specifically does. While customers at every corporate Starbucks should be prioritized the same way, it turns out that it’s best for this weird Starbucks to not do the same.

You see, the person that walked in wasn’t just any person. It was actually a wifi utility driver that needed to have a slice of CPU time asap. Not only was it starving, but it also had a much higher priority than yourself and the other applications in line. The cashier acknowledged the priority that the wifi utility driver had, and decided to move it up in line to service it as fast as possible.

Wifi from: https://en.wikipedia.org/wiki/Wi-Fi

So let’s reiterate over how each process would happen in a normal Starbucks and in our version of Starbucks:

Normal Starbucks

  1. Enter the store.
  2. Enter the line. (enqueue)
  3. Wait on line as cashier processes orders.
  4. Other people come behind you and leave in front of you.
  5. When it’s your turn, order.
  6. Get your delicious food! (dequeue)

Weird technical Starbucks

  1. Enter the store.
  2. Enter the line. (enqueue)
  3. Wait on line as cashier processes orders.
  4. Other applications come into the line behind you and leave from in front of you, but other applications also jump to the front if they have a higher priority.
  5. When it’s your turn, order.
  6. Get your delicious CPU time slice! (dequeue)
Queue from https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

The line you enqueue into when you walk into a Starbucks will always treat you as a normal customer and same goes for anyone else who may get on line with you. You get in line, wait for all the people in front of you to order, and then you finally get the opportunity to order that coffee and bagel you have been waiting for! This is pretty simple and a good standard as Starbucks shouldn’t prioritize it’s customers in any way, shape, or form. Let’s look at an extremely light code sample to examine how Starbucks would represent their in store line:

How Starbucks would implement a queue

As you can tell, this is fairly straight forward representation of what Starbucks does for customers entering their store. They insert customers to the end of the line (Beginning of our list, named line), and then serve those at the front (End of our list named line).

Our computers on the other hand are different. Applications get in line, wait for all the applications within the queue ahead of them to get processed, but if someone that is more important than them enters the queue, the more important application will get served first. This would sound absurd in any other scenario, but for computers it makes a lot of sense. While you may have Facebook as a high priority for yourself, it wouldn’t make sense to your computer to give it a higher priority than your computers wireless drivers, which are in turn allowing your Facebook application to work in the first place.

While this is a very high level overview of how they work, I hope that this helps unravel the mystery behind how processes on your computer are picked and chosen for when they get a good ol’ slice of CPU time. If you’d like to learn more about the technical aspects to how your operating system and more specifically kernel are powering your computer, please check out some of the resources that I used to help write this article. Thank you!

Resources

--

--