4 Scheduling
Week 5: September 26 - 30, 2022
- LOVE Chapter 4, pgs 41-50 up to Implementation
- DINOS 5.1, 5.2, 5.3, 5.7.1
- DINOS 5.5
- Simple and easy introduction to Lottery, Stride and Linux’s CFS Scheduling
Scheduling in an integral function of the kernel. As it manages processes and threads, the kernel needs to share the computational resources (i.e. processors and cores) across the many tasks that wish to run under the illusion that they have the entire processor to themselves.
There are lot of tensions at play here:
- CPU-bound vs. IO-bound processes
- Low priority vs. high priority and does priority mean more time on the CPU or preference for scheduling even if once scheduled the task runs for a short time slice
- Time-slice and context-switch time and why there is limit on how small time-slices can be
- Why we are constrained in the run-time complexity of the scheduler? It should make decisions very quickly to not add to the context-switch overhead
As we gain a deeper understanding of different scheduling algorithms and expand from single-queue to multiple-queues, single-processor to multiple-processors, we will also start to examine how other factors such as maintaining hot caches, maximizing CPU/IO-utilization, etc. interact with our scheduling algorihtm.
4.1 A video summary
4.1.1 Overview: policies, metrics & simple algorithms
Errata: I say in the lecture that when the time slice in Linux is 10ms, the overhead of context-switching is 3%. When the time slice is 1ms, then the overhead can be as high as 3%.
4.1.2 Priority Scheduling
Learning Objectives
- How can we assess if our scheduling algorithm is doing well?
- Define the different scheduling performance metrics: throughput, response time, wait time
- Demonstrate with examples schedules that lead to poor performance (using any metric: throughput, response time, wait time) with round-robin or first-come first-served scheduling.
- What purpose does Belady’s Shortest Job First Scheduling algorithm serve?
- What is a good time slice value? Why does the time of a context switch matter?
- What is perfect multitasking? Why can we never achieve it? How can we get close to it?
- How does Linux’s Completely Fair Scheduler work?
- How does Lottery Scheduling work?