ECE344 Fall 2026 (Sec 1) Lec 21 - Advanced Scheduling
Overview
Jon Eyolfson explains how advanced CPU scheduling balances fairness, responsiveness, throughput, and processor efficiency, moving from priority and feedback scheduling to multicore strategies and Linux’s policies. He details priority inversion and inheritance, processor affinity and work stealing, then traces Linux’s fair scheduling from virtual runtime and red-black trees to EEVDF, introduced in Linux 6.6.
Key takeaways
- Priority inheritance prevents medium-priority work from indirectly blocking a high-priority thread: a low-priority mutex holder temporarily inherits the highest priority of threads waiting on its lock.
- Per-CPU queues improve scheduling scalability and cache locality, but work stealing is needed to address load imbalance when one core runs out of work.
- Linux normal-task niceness ranges from -20 to 19, while real-time tasks use SCHED_FIFO or SCHED_RR with static priorities from 0 to 99.
- The Completely Fair Scheduler approximates equal CPU sharing by selecting the runnable task with the lowest weighted virtual runtime, stored in a red-black tree.
- Linux 6.6 introduced EEVDF, which combines fair-share eligibility with virtual deadlines to limit oversized runs and improve responsiveness.
Chapters
- First come, first served is simple, while shortest job first minimizes average waiting time when jobs are non-preemptive.
- Shortest remaining time first can starve long jobs when short processes keep arriving.
- Round robin trades some waiting-time efficiency for fairness and better response time.
- Priority schedulers can preempt lower-priority processes, round-robin equal-priority tasks, or assign different time shares.
- Linux niceness ranges from -20, the highest normal-process priority, to 19, the lowest.
- Feedback scheduling updates priorities at fixed intervals using old priority divided by two plus CPU time used, then resets CPU-time counters.
- In the example, I/O-bound P1 and P2 block for five time units after one unit of CPU, while CPU-bound P3 and P4 continue running.
- Priority inversion occurs when low-priority L holds a mutex needed by high-priority H, while medium-priority M prevents L from running.
- The Mars Pathfinder experienced a serious scheduling problem involving priority inversion.
- POSIX mutex attribute PTHREAD_PRIO_INHERIT temporarily raises a lock holder to the priority of the highest-priority thread waiting for that lock.
- A terminal’s Ctrl+C signal targets its foreground process group, while background groups are not assumed to interact with the user.
- Foreground work benefits from round robin and quick response; background work may favor first come, first served and throughput.
- Schedulers can use separate queues and then choose between them through priorities or round robin.
- Symmetric multiprocessing assumes CPU cores share physical memory, although each core has private caches such as L1.
- A global scheduler keeps CPUs busy when runnable work exists, but shared scheduling locks limit parallel decisions and migrating tasks can hurt cache locality.
- Per-CPU schedulers improve scalability and cache locality, but fixed task assignment can leave one core idle while another remains busy.
- The Linux 2.4-era global scheduler suited systems where most computers had one CPU.
- Work stealing lets an idle CPU take a runnable process from another CPU’s queue to rebalance load.
- Processor affinity records a process’s preference to stay on the same core; Linux taskset can restrict a command to a CPU, and Windows Task Manager exposes affinity settings.
- Gang scheduling, also called co-scheduling, runs related threads together, which can prevent wasted spinning when a thread holding a spin lock is not scheduled.
- The kernel schedules kernel threads; user-level threading libraries must schedule their own user threads.
- Hard real-time systems must guarantee deadlines, while general-purpose Linux offers soft real-time behavior without such guarantees.
- Linux real-time policies include SCHED_FIFO and SCHED_RR, with 100 static priority levels from 0 to 99; 99 is highest.
- Normal tasks use SCHED_OTHER or SCHED_NORMAL and niceness from -20 to 19, with 0 as the default.
- The nice and sched_setscheduler system calls can change scheduling settings; increasing niceness is generally permitted, but lowering it may require root.
- Linux combines priority conventions in an internal priority value: normal-task niceness is offset by 20, while real-time priorities map to negative values.
- In htop, PRI displays the internal priority and NI displays niceness; audio processes such as PipeWire may receive higher priority to reduce crackling.
- Linux moved from a global queue to the per-CPU O(1) scheduler with work stealing, then to the Completely Fair Scheduler and, in Linux 6.6, EEVDF.
- The O(1) scheduler used heuristics to identify interactive tasks, which could be ad hoc and unfair for modern graphical workloads.
- Ideal fair scheduling gives each of n runnable processes 1/n of the CPU, but implementing it literally would require impractically frequent context switches.
- The Completely Fair Scheduler tracks virtual runtime, increasing it by actual CPU time divided by a process weight.
- Higher-weight tasks, including higher-priority tasks, accumulate virtual runtime more slowly; the scheduler selects the runnable task with the lowest virtual runtime.
- Linux stores runnable tasks in a red-black tree keyed by virtual runtime, supporting operations such as finding the minimum in O(log n).
- Linux’s Earliest Eligible Virtual Deadline First scheduler retains CFS-style virtual runtimes and weights but changes how it selects the next task.
- EEVDF considers tasks eligible only when they have not received more than their fair share, then favors the eligible task with the earliest virtual deadline.
- The change helps prevent I/O-heavy tasks from accumulating a large CPU share that could later produce an unexpectedly long run.
- A task can request a shorter slice to become eligible to run sooner, trading duration for responsiveness.
- Interactive workloads prioritize response time, batch jobs prioritize throughput, and real-time workloads prioritize deadlines, so one scheduling policy is always a compromise.
- Modern schedulers must account for performance and efficiency cores, differing memory latencies, and process groups managed with Linux cgroups.
- Disks, GPUs, and AI accelerators also schedule shared requests, extending scheduling tradeoffs beyond the CPU.
Transcript excerpt
2:02 Mhm. >> Mhm.
4:37 >> Alrighty, welcome back to operating system. So, hopefully your midterm hell is over ish. No? That sucks. Well, thankfully we have fairly chill lectures now. So, we even skipped advanced scheduling so that on test two, which hopefully wasn't too bad, uh Worse than test one? It was shorter at least. I counted the number of words. It was like 70%. The answer Okay. Uh okay. I guess I have to redo my
5:41 timing cuz I did like 15 minutes. >> [laughter] >> Yikes. Yeah. Maybe I have to multiply by four instead of three. All right. Well, anyways, well, you'll be good to know that also question five on that was worded poorly enough that uh I accepted A and B. That was the multiple choice on like what happens with the new thread, blah blah blah. Yeah, it wasn't clear what was returning, so I accepted A and B. Basically, I graded that one like everyone got 100% on it. So, yay, free marks. So, hopefully that helps with the uh the subsequent questions. So, anyways, let's get into advanced scheduling. So, recall we talked about basic scheduling with a trade-off. So, we had
6:30 some algorithms, if you can generally call them that. First come, first serve is the simplest. Then there was shortest job first that had no preemptions, aka as soon as I started a process, it would not stop until it finished. So, to minimize the average waiting time, which was one of our things or one of our metrics, we could do shortest job first, always take the one that takes the least amount of time first. If we add preemptions, we could do shortest remaining time first. Again, that would cut the average waiting time, but we would have some
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jon Eyolfson.