The scheduler is a part of the ⚙️ Operating System kernel that decides which process to run. It makes a decision whenever a process starts (arrives but not executing), finishes, blocks (waiting on something), or has run for a certain amount of time.
Scheduling is crucial to maintain the illusion of multiprocessing, and scheduling algorithms must consider many factors:
- Fairness: every program needs to run.
- Liveness: “something” will eventually happen.
- Throughput: amount of work completed over time.
- Wait time: average time a task is “alive” but not running.
- Turnaround time: time between task ready and completing.
- Response time: time between task ready and taking user input.
The goal of the scheduler is to minimize wait time and latency while maximizing throughput and fairness.
Scheduling Algorithms
Scheduling algorithms can either be non-preemptive (continue running thread until completion) or preemptive (interrupt thread after some condition).
Non-Preemptive
- First come first serve: maintain queue of ready threads, run in order of arrival.
- Shortest job first: run task with smallest runtime.
Preemptive
- Round robin: run job for a fixed amount of time (quantum), then run the next.
- Priority round robin: multiple round robin queues for different priorities, finish higher priority queue before moving onto a lower priority one.
- Multi-level feedback round robin: builds on priority round robin by assigning priorities automatically; threads start at highest priority and decrease priority whenever it’s interrupted by scheduler (instead of voluntarily giving up control).