3 ms·

We've been here before, (way) back in the 90s: "Scheduler activations: effective kernel support for the user-level management of parallelism" https://dl.acm.or

We've been here before, (way) back in the 90s: "Scheduler activations: effective kernel support for the user-level management of parallelism" https://dl.acm.org/doi/10.1145/121132.121151 https://dl.acm.org/doi/10.1145/121132.121151 and also: "Adding Scheduler Activations to Mach 3.0" https://dada.cs.washington.edu/research/tr/1992/08/UW-CSE-92-08-03.pdf https://dada.cs.washington.edu/research/tr/1992/08/UW-CSE-92... People put a lot of time into thinking and researching this sort of thing. It even made it into Solaris. For one reason or another (possibly a lack of sufficient hardware parallelism) it never really gained much traction. Another critical issue to solve is that to do this "properly" (at least based on our model of this from the 90s), you have to have a re-entrant context switch routine, which is an interesting challenge.

convolvatron 3y ago
my understanding was that schedule activations are really an upcall mechanism thats allows a userspace scheduler to manage its own threads (green) more effectively and provide more robust support for asynchrony across the user/kernel boundary. isn't this is more of a extreme micro/exo thing where the monolithic scheduler is herniated out into userspace?
- PaulDavisThe1st 3y ago
  Not "green" threads. Full kernel threads (otherwise it doesn't make much sense). And yes, this is a more extreme thing, but what's the point unless there's some capability in user space that can't exist in the kernel? And what would that thing be? Application-specific knowledge allowing better scheduling decisions to be made.
  - vacuity 3y ago
    Can you elaborate on what it means for them to be kernel threads as opposed to green threads (no userspace control over when it blocks and yields?) and reentrant context switch routines? I read the original paper but I fear I don't have enough background to fully appreciate it.
    - PaulDavisThe1st 3y ago
      Scheduler activations is a design that involves calling back up into the user space scheduler whenever the kernel decides to: 1. block a thread AND 2. allow the task that owns the thread to retain use of the CPU so when a thread (in user space) calls write, it ends up in the kernel, and the kernel in a traditional design would put the thread to sleep waiting on the write, invoke the scheduler to decide what should run next. With SA, the kernel first assesses whether the task can continue to use the CPU, and if so, calls the task's user-space scheduler so that it can decide which thread to run (since the user-space scheduler has better information about this). Green threads are unknown to the kernel, they play no role in such a design. Reentrant context switching is required because you can be in the middle of a context switch invoked from the user space scheduler when a h/w interrupt (incl. timers) causes the kernel to rethink what is going and rip the CPU away from the task.
      - vacuity 3y ago
        Reentrancy is a nuisance. seL4 allows for the kernel to be preempted only at specific points of long running operations, which massively reduces concurrent spaghetti but also sacrifices some latency. Would the userspace program have some way of knowing about global resource contention to avoid choosing a thread suboptimally? As I understand it, SA by itself only allows userspace programs to manage their own resources efficiently.
        PaulDavisThe1st 3y ago
        No, the kernel gets to do it's job: decide which task ("process" in classical Unix speak) should get the core based on kernel-side scheduling policies, then the task itself gets to decide which thread should run on the core. The amount of information required to correctly decide which task should get the core is too large to sensibly move across the kernel boundary, and providing read-access to it in a safe way from user space is problematic.
        vacuity 3y ago
xoranth 3y ago
I believe something like the mechanism you are describing has been in production at Google for at least a decade. See this talk [1]. The kernel interface that the article uses (called sched_ext) is the result of the attempts to mainstream the Google thing. [1]: https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
- PaulDavisThe1st 3y ago
  Yeah, I'm loosely familiar with sched_ext already. However, it is actually the opposite of scheduler activations. SA means upcalling to user-space when thread scheduling is required. sched_ext means loading a scheduler (coded in BPF) into the kernel. Not dissimilar goals/purposes but wildly different systems.
  - xoranth 3y ago
    Thanks for the clarification!

convolvatron 3y ago

my understanding was that schedule activations are really an upcall mechanism thats allows a userspace scheduler to manage its own threads (green) more effectively and provide more robust support for asynchrony across the user/kernel boundary. isn't this is more of a extreme micro/exo thing where the monolithic scheduler is herniated out into userspace?

PaulDavisThe1st 3y ago
Not "green" threads. Full kernel threads (otherwise it doesn't make much sense). And yes, this is a more extreme thing, but what's the point unless there's some capability in user space that can't exist in the kernel? And what would that thing be? Application-specific knowledge allowing better scheduling decisions to be made.
- vacuity 3y ago
  Can you elaborate on what it means for them to be kernel threads as opposed to green threads (no userspace control over when it blocks and yields?) and reentrant context switch routines? I read the original paper but I fear I don't have enough background to fully appreciate it.
  - PaulDavisThe1st 3y ago
    Scheduler activations is a design that involves calling back up into the user space scheduler whenever the kernel decides to: 1. block a thread AND 2. allow the task that owns the thread to retain use of the CPU so when a thread (in user space) calls write, it ends up in the kernel, and the kernel in a traditional design would put the thread to sleep waiting on the write, invoke the scheduler to decide what should run next. With SA, the kernel first assesses whether the task can continue to use the CPU, and if so, calls the task's user-space scheduler so that it can decide which thread to run (since the user-space scheduler has better information about this). Green threads are unknown to the kernel, they play no role in such a design. Reentrant context switching is required because you can be in the middle of a context switch invoked from the user space scheduler when a h/w interrupt (incl. timers) causes the kernel to rethink what is going and rip the CPU away from the task.
    - vacuity 3y ago
      Reentrancy is a nuisance. seL4 allows for the kernel to be preempted only at specific points of long running operations, which massively reduces concurrent spaghetti but also sacrifices some latency. Would the userspace program have some way of knowing about global resource contention to avoid choosing a thread suboptimally? As I understand it, SA by itself only allows userspace programs to manage their own resources efficiently.
      - PaulDavisThe1st 3y ago
        No, the kernel gets to do it's job: decide which task ("process" in classical Unix speak) should get the core based on kernel-side scheduling policies, then the task itself gets to decide which thread should run on the core. The amount of information required to correctly decide which task should get the core is too large to sensibly move across the kernel boundary, and providing read-access to it in a safe way from user space is problematic.
        vacuity 3y ago

xoranth 3y ago

I believe something like the mechanism you are describing has been in production at Google for at least a decade. See this talk [1]. The kernel interface that the article uses (called sched_ext) is the result of the attempts to mainstream the Google thing. [1]: https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw

PaulDavisThe1st 3y ago
Yeah, I'm loosely familiar with sched_ext already. However, it is actually the opposite of scheduler activations. SA means upcalling to user-space when thread scheduling is required. sched_ext means loading a scheduler (coded in BPF) into the kernel. Not dissimilar goals/purposes but wildly different systems.
- xoranth 3y ago
  Thanks for the clarification!