Let’s say you don’t have unlimited resources. Be it RAM, access to files, CPU slots, whatever you can think of. And then you have multiple workloads that will need said resources.

That’s where scheduling comes in. Scheduling comes in MANY shapes and sizes including ones you haven’t even suspected of.

Scheduler types

Here we explore the various scheduler algorithms that deal with scheduling tasks. Keep in mind I also tried to unify the terminology used so a task forms a unit of work that scheduler schedules. This doesn’t always align directly so please take note.

Name Overhead Real time Starvation RT BC RT WC Introduced Read more
Round Robin 😐 🙁 🙂 🙂 🙂 1950s here
First come, first served 🙂 🙁 🙂 🙂 🙁 1950s here
Manual scheduling 🙂 🙂 😐 😐 😐 ∞ here
Priority earliest deadline first 😐 🙂 🙂 😐 😐 1950s here
Shortest remaining time first 😐 🙁 😐 🙂 🙁 1960s here
Fixed priority pre-emptive 🙂 🙂 😐 🙂 🙁 1980s here
Multilevel queue 🙂 🙁 😐 😐 😐 1950s here
Work-conserving 🙂 🙁 😐 🙂 🙁 1960s here

Legend:

  • Overhead - how much time we waste running the scheduling algorithm itself, switching tasks, etc.
  • Real time - is the algorithm suitable for real time systems
  • Starvation - is the algorithm prone to starving tasks in certain conditions
  • RT BC - response time to schedule a task (best case)
  • RT WC - response time to schedule a task (worst case)
  • Introduced - year it was first introduced
  • Introduced by - author/organization that introduced it
  • Type - scheduling algorithm type
  • 🙂 - good; does well in all or almost all situations.
  • 😐 - neutral/average; is generally ok, but might do poorly in certain scenarios.
  • 🙁 - bad; does poorly, probable huge delays, etc.

Implementations

Some of the more prominent and well documented example implementations of scheduler algorithms.

Name Type Introduced Introduced by Read more
Completely Fair Scheduler weighted fair queuing 2000s Ingo Molnár/Linux here
Brain Fuck Scheduler weighted round-robin 2000s Con Kolivas/Linux here
React scheduler N/A 2010s Facebook here
Google maps scheduler N/A 2000s Google here
Windows XP/etc. multilevel feedback queue 2000s Microsoft here
MS-DOS no scheduler 1980s Microsoft here

Closing notes

As you can see schedulers are used all over the place in the software world and knowing something about them helps in solving multi-workload problems quicker and with much less hassle.

And remember evaluating schedulers is a context dependent task so take all this info with a grain of salt and do your homework.