5 ms·

Making scheduling decisions requires information that only the kernel has (for starts, what processes are even running). Since userspace programs can't read ker

Making scheduling decisions requires information that only the kernel has (for starts, what processes are even running). Since userspace programs can't read kernel memory, you have to copy this information into their process before they can work.

cloudwalk9 3y ago
Would be interesting to see how minimal they could make the overhead, since that's one of their goals. I wonder what the lower limit might be. That would have broad implications for basically everything else in userspace.
- vacuity 3y ago
  Ah, the dream of fully-featured, performant M:N threading. Spawn tasks left and right, optimize with a small declarative config, and sit back and relax. I'm very interested to see how close we can get.
PaulDavisThe1st 3y ago
Making scheduling decisions optimally requires information only held on each side of the kernel/user space divide. An application knows things about its own operation that the kernel cannot. The kernel knows things about the state of the system that user space cannot. Hence the "scheduler activations" concept from the early 1990s, in which the kernel calls into user space with sufficient information for a user space scheduler to make the best possible decision (in theory).
- vacuity 3y ago
  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.

cloudwalk9 3y ago

Would be interesting to see how minimal they could make the overhead, since that's one of their goals. I wonder what the lower limit might be. That would have broad implications for basically everything else in userspace.

vacuity 3y ago
Ah, the dream of fully-featured, performant M:N threading. Spawn tasks left and right, optimize with a small declarative config, and sit back and relax. I'm very interested to see how close we can get.

PaulDavisThe1st 3y ago

Making scheduling decisions optimally requires information only held on each side of the kernel/user space divide. An application knows things about its own operation that the kernel cannot. The kernel knows things about the state of the system that user space cannot. Hence the "scheduler activations" concept from the early 1990s, in which the kernel calls into user space with sufficient information for a user space scheduler to make the best possible decision (in theory).

vacuity 3y ago
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.