LWN: Comments on "Deadline scheduling part 1 — overview and theory"

Deadline scheduling part 1 — overview and theory

bristot-memorial — Fri, 19 Jan 2018 15:17:03 +0000

Hi!

There is one mechanism on the Linux implementation of the deadline scheduler that prevents the domino effect. This mechanism is the CBS. It will be explained in the next article of the series ;).

Deadline scheduling part 1 — overview and theory

iabervon — Thu, 18 Jan 2018 17:39:44 +0000

I'm surprised that the deadline scheduler doesn't preempt tasks that run over their declared run time, either immediately or at the point where they would interfere with other tasks making their deadlines. Preempting them immediately seems like it would be technically easy, since that's normal scheduler functionality, and like it would be necessary to meet the goal of having the fewest possible misses if the requested schedule is impossible, as well as penalizing the task that makes the schedule impossible.

Deadline scheduling part 1 — overview and theory

Cyberax — Tue, 16 Jan 2018 21:33:45 +0000

Back when I was doing schedulers for distributed computing, we converged on a bin-packing algorithm with some heuristics to handle its pathological cases.

It worked wonders and was simple to implement.

Deadline scheduling part 1 — overview and theory

bristot-memorial — Tue, 16 Jan 2018 20:27:12 +0000

There are some nice results with semi-partitioned scheduling in the academic world, like this:

http://drops.dagstuhl.de/opus/volltexte/2017/7165/pdf/LIP...

Actually, we are already working on it, but still, it is not optimal.

Deadline scheduling part 1 — overview and theory

jreiser — Tue, 16 Jan 2018 19:30:59 +0000

The bin-packing strategy First Fit Decreasing has a tight bound of 11/9 optimal, plus 2/3.

Deadline scheduling part 1 — overview and theory

Cyberax — Tue, 16 Jan 2018 19:09:34 +0000

> Distribution of tasks to processors turns out to be an NP-hard problem (a bin-packing problem, essentially) and, due to other anomalies, there is no dominance of one scheduling algorithm over any others.
Fortunately, the most naive bin-packing algorithm produces results that are at most 2 times worse than the optimal packing.