11. A Scheduling Story Flashcards
How do oracular schedulers predict the future?
They use the past to predict the future. They look to see what the thread did recently and assume that they will keep doing it.
Describe the process of implementing a multi-level feedback queue.
First, choose a scheduling quantum. Second, establish some number of queues, each of which represents a priority level. Threads from the highest-level queues are chosen first.
Third, choose and run a thread from the highest-level non-empty queue.
If the thread blocks or yields, promote it to a higher level queue. If the thread must be preempted at the end of a quantum (ran out of quantum before exiting), demote it to a lower level queue.
What happens to CPU-bound threads using multi-level feedback queues?
They descent to lower levels
What happens to I/O-bound threads using multi-level feedback queues?
They rise up to higher levels
What problem can arrive if CPU-bound threads are reprioritized and I/O bound threads are promoted?
We get starvation on the CPU-bound threads. Threads trapped in the lower queues may never have a chance to run.
One solution is to periodically rebalance the levels by periodically tossing everyone back to the top level
Describe the kind of abstraction that priorities are.
Priorities are a scheduling abstraction that allows the user, or the system itself, to assign relative importance to different tasks on the system.
Priorities are always relative, and so host to a variety of different problems
Strict priorities can lead to starvation when low-priority threads are constantly blocked by high-priority threads with work to do. What is one solution to this problem?
Lottery scheduling. Give each thread a number of tickets proportional to their priority. Choose a ticket at random. The thread holding the ticket gets to run.
How can priorities relate to thread quantum?
Priorities can be used to determine how long threads are allowed to run, i.e. dynamically adjusting their time quantum so that higher priority threads get more quantum.
Broadly describe the O(1) Linux scheduler implemented in Linux 2.6
The scheduler achieved O(1) by combining a static AND dynamic priority.
The static priority was set by the user or system using “nice”
The dynamic priority offered a potential “boost” to the static priority if the thread was interactive
What was the main problem with the O(1) scheduler in Linux 2.6?
The interactivity boost code was very complex and difficult to understand. This made it difficult to test to determine if it was doing what it was intended to do
What was Con Kolivas’ definition of “responsiveness” of an application?
The rate at which your workloads can proceed under different load conditions
What was Con Kolivas’ definition of “interactivity” of an application?
The scheduling latency and jitter present in tasks where the user would not notice a palpable deterioration under different load conditions.
Summarize the difference between responsiveness and interactivity, as Con Kolivas saw it.
Responsiveness would allow you to continue using your machine without too much interruption to your work.
Interactivity would allow you to play audio or video without any dropouts and dragging a GUI window across the screen would be rendered smoothly.
Who was Con Kolivas?
An Australian anesthetist who became interested in scheduling and designed a revolving staircase scheduler for Linux
How does the Rotating Staircase Deadline Scheduler (RSDL) work?
The scheduler takes one parameter, called the round-robin interval. It also takes one input, a thread priority.
A task can run for at most a fixed amount of time (quantum) per level. Note that a level itself has a camp on how long it can run tasks before it must stop and surrender to the next level (this ensures bounded latency).
The task’s priority determines how many levels the task can appear in.
