--- title: Scheduling Algorithms description: Scheduling algorithms determine how an operating system allocates CPU execution time to competing processes. Learners will understand different policies, such as Round Robin and First-Come First-Served, and how to evaluate their impact on system throughput and latency. category: programming-tech subcategory: operating-systems difficulty: beginner, intermediate, advanced url: /subject/scheduling-algorithms --- # Scheduling Algorithms Scheduling algorithms determine how an operating system allocates CPU execution time to competing processes. Learners will understand different policies, such as Round Robin and First-Come First-Served, and how to evaluate their impact on system throughput and latency. ## Available Resources 3 Courses • 4 Websites • 2 Papers ## Courses ### 1. CS162: Operating Systems and Systems Programming UC Berkeley's upper-division operating systems course, with lectures, projects and exams covering processes and threads, synchronization, CPU scheduling, virtual memory, file systems, I/O and networking. Students build kernel features in the Pintos teaching OS and understand how operating systems work internally. **Difficulty:** Advanced | **Price:** Free **Link:** https://cs162.org/ **Tags:** operating-systems, concurrency, virtual-memory, file-systems, systems-programming ### 2. Operating Systems: Three Easy Pieces Learn concurrency in operating systems with this course from Remzi & Andrea Arpaci-Dusseau, based on "Operating Systems: Three Easy Pieces." **Difficulty:** Advanced | **Price:** Free **Link:** https://pages.cs.wisc.edu/~remzi/OSTEP/ **Tags:** operating-systems, concurrency, virtual-memory, file-systems, textbook ### 3. CS-537 Introduction to Operating Systems: Lecture Videos **Author:** Remzi H. Arpaci-Dusseau Lecture recordings and notes from Remzi Arpaci-Dusseau's Wisconsin CS-537 course, the class OSTEP was written for. Lecture 2 covers scheduling policies and metrics; lecture 3 works through the multi-level feedback queue on the whiteboard. **Difficulty:** Beginner | **Language:** English | **Price:** Free **Link:** https://pages.cs.wisc.edu/~remzi/Classes/537/Spring2018/Discussion/videos.html **Tags:** operating-systems, cpu-scheduling, lecture-videos, mlfq, ostep ## Papers ### 1. The Linux Scheduler: a Decade of Wasted Cores **Author:** Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, Alexandra Fedorova EuroSys 2016 study that found four bugs in Linux's load balancer leaving cores idle while threads waited, costing up to 13-23% on real workloads. Shows how scheduler invariants break at scale and how to detect it. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://hal.science/hal-01295194/document **Tags:** linux-kernel, cpu-scheduling, load-balancing, multicore, performance-analysis ### 2. Lottery Scheduling: Flexible Proportional-Share Resource Management **Author:** Carl A. Waldspurger, William E. Weihl The 1994 OSDI paper introducing lottery scheduling, a randomized proportional-share mechanism using tickets and currencies. It shows how relative execution rates can be controlled directly, with prototype results on Mach, and grounds every later fair-share scheduler. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://www.waldspurger.org/carl/papers/lottery-osdi94.pdf **Tags:** proportional-share-scheduling, randomized-algorithms, operating-systems, resource-allocation, cpu-scheduling ## Websites ### 1. An EEVDF CPU Scheduler for Linux **Author:** Jonathan Corbet Jonathan Corbet's explanation of why Linux replaced the Completely Fair Scheduler with EEVDF, covering lag, eligibility, virtual deadlines and per-task latency requirements. Clarifies the design reasoning that the kernel's own documentation states only tersely. Practitioner writing with verifiable skin in the game that supplies the 'why' the terse kernel docs omit: what fairness failed to capture and how lag plus virtual deadlines fix latency. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://lwn.net/Articles/925371/ **Tags:** linux-kernel, cpu-scheduling, eevdf, cfs, latency ### 2. OSTEP Chapter 8: Scheduling: The Multi-Level Feedback Queue **Author:** Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau Chapter 8 of OSTEP derives the multi-level feedback queue: how a scheduler infers job behavior at runtime, adjusts priorities with rule changes, and prevents starvation and gaming through periodic priority boosts. Explains the design behind Solaris, BSD and Windows schedulers. MLFQ is where scheduling stops being a quiz topic and becomes design under uncertainty. The chapter builds it rule by rule, breaks each rule with an attack (gaming the quantum, changing behavior), and repairs it, which is exactly the structural reasoning the tutorial pages omit. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf **Tags:** mlfq, cpu-scheduling, operating-systems, priority-scheduling, starvation ### 3. OSTEP Chapter 7: Scheduling: Introduction **Author:** Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau Chapter 7 of Operating Systems: Three Easy Pieces. It builds FIFO, SJF, STCF and Round Robin from first principles, showing how turnaround time and response time trade off against each other and why I/O overlap changes the answer. It develops the policies as a sequence of workload assumptions being relaxed, so the learner acquires the mental model (metrics drive policy) rather than a table of algorithm names. **Difficulty:** Beginner | **Language:** English | **Price:** Free **Link:** https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf **Tags:** cpu-scheduling, operating-systems, round-robin, shortest-job-first, turnaround-time ### 4. osdev.org OSDev.org is a community-driven resource and wiki for operating system development. It offers tutorials, articles, and sample code on topics like kernels, bootloaders, memory management, drivers, and other low-level OS concepts, plus forums for discussion. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://osdev.org **Tags:** websites, technology-computer-science, computer-sciences --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/scheduling-algorithms