4 ms·

I believe I saw a presentation on OKL4 describing this sort of abstraction as virtual CPUs capabilities. There is a similar mechanism in Barrelfish and Psyche.

I believe I saw a presentation on OKL4 describing this sort of abstraction as virtual CPUs capabilities. There is a similar mechanism in Barrelfish and Psyche. Last I heard, the seL4 team was pursuing a different approach of scheduling capabilities. I think we still haven't realized the optimal design, but these are probably good local maxima and points for further exploration.

PaulDavisThe1st 3y ago
My own suspicion is that we have realized the optimal design already, but it turns out that it just doesn't matter very much.
- vacuity 3y ago
  How so?
  - PaulDavisThe1st 3y ago
    In the 90s, the cost of choosing the wrong thread to run when another thread blocked was significant in specific kinds of applications. Since then, the cost has (in absolute terms) gone down, the number of applications for which this is true has not really increased. In addition, there has been some expansion in the number of applications for which SCHED_RT and SCHED_FIFO are appropriate for at least some threads (financial services high speed trading, real time audio), which has also reduced the pressure for a user-space scheduler that "gets it right". This is also true for designs which require guaranteed scheduling slots. So, SA might still bring some benefits to large, highly-threaded monolithic apps such as RDBMS, but it doesn't really provide much to the majority of contemporary applications. It certainly doesn't do much for mobile environments, which tend not to run applications where "the application knows best".
    - vacuity 3y ago
      Makes sense. Ideally the OS should provide the capability to do SA (or similar), but I don't know how the overhead would be for programs that opt out of using it.
- topspin 3y ago
  That seems unlikely. The dimensions of the problem space are huge and getting larger. Although the next Linux kernel scheduler I write will be my first, it's not hard to infer the increase in complexity due to the evolution of CPUs that Linux runs on: "efficiency" cores (now on AMD devices as well), multi-chip modules creating cache locality problems, critical power and thermal management requirements on high power/current devices — all changing concurrently.
  - vacuity 3y ago
    There certainly isn't one concrete scheduler that works for all workloads. It probably doesn't matter for server or supercomputer environments; as long as some scheduler works, it doesn't have to change. For other use cases, the scheduler should be flexible with throughput and fairness. Priority, resource usage, realtime, but more cohesive. Tuning the scheduler might be harder in such a design, but it should allow for users to not need to switch to a different base entirely. It'd be more of a scheduler framework that can be used to support various workloads dynamically.
  - PaulDavisThe1st 3y ago
    Implicit in all this is the idea that if you do not get the scheduler behaving optimally that it will make a difference sufficient that we can call it a "failure". That's what I'm questioning. Precisely because the dimensions of the problem space have increased, and the raw performance of everything except register save/restore and TLB invalidation has increased, there's wide latitude for scheduling algorithms that are "not quite right".

PaulDavisThe1st 3y ago

My own suspicion is that we have realized the optimal design already, but it turns out that it just doesn't matter very much.

vacuity 3y ago
How so?
- PaulDavisThe1st 3y ago
  In the 90s, the cost of choosing the wrong thread to run when another thread blocked was significant in specific kinds of applications. Since then, the cost has (in absolute terms) gone down, the number of applications for which this is true has not really increased. In addition, there has been some expansion in the number of applications for which SCHED_RT and SCHED_FIFO are appropriate for at least some threads (financial services high speed trading, real time audio), which has also reduced the pressure for a user-space scheduler that "gets it right". This is also true for designs which require guaranteed scheduling slots. So, SA might still bring some benefits to large, highly-threaded monolithic apps such as RDBMS, but it doesn't really provide much to the majority of contemporary applications. It certainly doesn't do much for mobile environments, which tend not to run applications where "the application knows best".
  - vacuity 3y ago
    Makes sense. Ideally the OS should provide the capability to do SA (or similar), but I don't know how the overhead would be for programs that opt out of using it.
topspin 3y ago
That seems unlikely. The dimensions of the problem space are huge and getting larger. Although the next Linux kernel scheduler I write will be my first, it's not hard to infer the increase in complexity due to the evolution of CPUs that Linux runs on: "efficiency" cores (now on AMD devices as well), multi-chip modules creating cache locality problems, critical power and thermal management requirements on high power/current devices — all changing concurrently.
- vacuity 3y ago
  There certainly isn't one concrete scheduler that works for all workloads. It probably doesn't matter for server or supercomputer environments; as long as some scheduler works, it doesn't have to change. For other use cases, the scheduler should be flexible with throughput and fairness. Priority, resource usage, realtime, but more cohesive. Tuning the scheduler might be harder in such a design, but it should allow for users to not need to switch to a different base entirely. It'd be more of a scheduler framework that can be used to support various workloads dynamically.
- PaulDavisThe1st 3y ago
  Implicit in all this is the idea that if you do not get the scheduler behaving optimally that it will make a difference sufficient that we can call it a "failure". That's what I'm questioning. Precisely because the dimensions of the problem space have increased, and the raw performance of everything except register save/restore and TLB invalidation has increased, there's wide latitude for scheduling algorithms that are "not quite right".