11. A Scheduling Story Flashcards

1
Q

How do oracular schedulers predict the future?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Describe the process of implementing a multi-level feedback queue.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What happens to CPU-bound threads using multi-level feedback queues?

A

They descent to lower levels

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What happens to I/O-bound threads using multi-level feedback queues?

A

They rise up to higher levels

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What problem can arrive if CPU-bound threads are reprioritized and I/O bound threads are promoted?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Describe the kind of abstraction that priorities are.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How can priorities relate to thread quantum?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Broadly describe the O(1) Linux scheduler implemented in Linux 2.6

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What was the main problem with the O(1) scheduler in Linux 2.6?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What was Con Kolivas’ definition of “responsiveness” of an application?

A

The rate at which your workloads can proceed under different load conditions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What was Con Kolivas’ definition of “interactivity” of an application?

A

The scheduling latency and jitter present in tasks where the user would not notice a palpable deterioration under different load conditions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Summarize the difference between responsiveness and interactivity, as Con Kolivas saw it.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Who was Con Kolivas?

A

An Australian anesthetist who became interested in scheduling and designed a revolving staircase scheduler for Linux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How does the Rotating Staircase Deadline Scheduler (RSDL) work?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is “round-robin” scheduling?

A

When the scheduler moves sequentially through a queue of threads. This approach enforces fairness among threads of equal priority.

17
Q

Walk through the steps of setting up and running a RSDL.

A

To begin a scheduling epoch, first put all threads in a queue determined by their priority.

Run threads from highest non-empty queue round-robin.

If a thread blocks or yields, leave it at that level with reduced quota.

If thread runs out of quota, move it to next level down and give it quota associated with that level

If the level runs out of its quota, all remaining threads move down to next level

Continue until all quotas are exhausted or no threads are runnable, then restart another epoch (reset)

18
Q

What positives did the RSDL achieve?

A

Scheduling can still be done in O(1) while prioritizing interactivity.

The implementation is very simple and can easily calculate how long it will be before a thread at a certain priority level runs (given the # of runnable tasks in the system and their priorities.). This makes it very easy to model the algorithm.

19
Q

What was Con Kolivas’ chief complaint against “most” fair scheduling designs?

A

He said that most fair scheduling designs end up penalizing interactive threads because they sleep often.

He complained that these designs have to go about the complicated and unnecessary process of “bonusing” the priority of interactive threads to offset the deprioritization that happens when interactive threads sleep.

20
Q

Who is Ingo Molnar?

A

The head of all things scheduling in the Linux development community.

21
Q

What is the Brain Fuck Scheduler (BFS) at the top level?

A

It is a desktop-oriented scheduler with extremely low latencies for excellent interactivity by design.

It does not calculate anything to achieve low latencies using the rigid fairness philosophy of other schedulers.