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.
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|
|First come, first served||🙂||🙁||🙂||🙂||🙁||1950s||here|
|Priority earliest deadline first||😐||🙂||🙂||😐||😐||1950s||here|
|Shortest remaining time first||😐||🙁||😐||🙂||🙁||1960s||here|
|Fixed priority pre-emptive||🙂||🙂||😐||🙂||🙁||1980s||here|
- 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.
Some of the more prominent and well documented examples 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|
|Google maps scheduler||N/A||2000s||here|
|Windows XP/etc.||multilevel feedback queue||2000s||Microsoft||here|
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.