5 ms·
Writing a scheduler for Linux in Rust that runs in user-space
- BigParm 3y agoIf we schedule in user space does that make it possible to share compute workloads between arbitrary computers on a network? Because kernel scheduling has context and different architectures must be considered etc.
- MuffinFlavored 3y ago> the communication between kernel and user-space is going to add some overhead, What does this look like specifically? Is it that the kernel operation needs to copy memory that is in "kernel space" to/from "user space" for security reasons? Is that all?
- Analemma_ 3y agoMaking 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 agoWould 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 agoAh, 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 agoMaking 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 agoI 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 agoMy 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 agoHow so?
- PaulDavisThe1st 3y agoIn 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".
- vlovich123 3y agoIf I’m reading the page correctly, at the end is this: > while the communication of tasks happen using the bpf() syscall, accessing the queued and dispatched maps. > NOTE: we could make this part more efficient by using eBPF ring buffers, this would allow direct access to the maps without using a syscall (there’s an ongoing work on this - patches are welcome if you want to contribute). The kernel piece needs to produce information that the user space consumes and it doesn’t use a 0-copy ring buffer yet.
- cgh 3y agoHe’s referring to the syscalls necessary to share data back and forth with eBPF. These are wrapped in userspace libraries, eg libbpf.c. Data is shared with the kernel in buffers which in eBPF parlance are referred to as “maps”, which are basically key/value pairs accessed via a file descriptor. There’s a lot of docs on eBPF if you are curious: https://www.kernel.org/doc/html/latest/bpf/index.html https://www.kernel.org/doc/html/latest/bpf/index.html
- jandrese 3y agoOf all the things a you can run in userspace, the scheduler is the one that I never thought would happen. I guess the scheduler has to give itself time to run in userspace? It seems like there would be a chicken and egg problem at boot time before userspace is brought up. Would be pretty embarrassing if your scheduler got killed by a OOM or something.
- anthk 3y agoWell, GNU Hurd would survive to that right?
- deleted 3y ago[deleted]
- kccqzy 3y agoYou could make the kernel treat the scheduler specially (just like today it already treats PID 1 specially) by always making the scheduler run whenever the kernel doesn't know what to run next.
- wyldfire 3y ago> Would be pretty embarrassing if your scheduler got killed by a OOM or something. Or if you starved your scheduler process because it wasn't high enough priority :/
- thewakalix 3y ago> in case of bugs the user-space scheduler will just crash and sched-ext will transparently restore the default Linux scheduler.
- lstodd 3y agoHappens all the time with the userspace async stuff, swapcontext(3), freebsd n:m threads, greenthreads, stackless py, it's all ancient, and they're all userspace schedulers. I think SA takes it a bit too far though. Even if it looks like a 'logical progression of them older ideas.'
- jandrese 3y ago
- PaulDavisThe1st 3y agoWe'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 agomy 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 agoNot "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 agoCan 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.
- sppfly 3y agoI'm wondering if this scheduler is for something like user-space threads. And What is the relationship between such scheduler and go runtime for goroutine and JVM for Java virtual thread?
- matthews2 3y agoIn this example, the kernel is doing the task switching. They are "real" threads. The userspace component is informing the kernel which tasks should be run. goroutines and Java virtual threads are a separate idea. The application saves its state and then yields back to a scheduler in the application.
- legulere 3y agoWhy not compile directly to ebpf and run your code without context switches?
- NegativeK 3y agoEBPF has strict limitations, like 512-byte stack and 1M instructions, that would make it inapplicable to a lot of programs. It's intentionally not Turing complete. Also, because context switches are good?
- aminepa8 3y agoWhile eBPF aims to minimize context switches and provide efficient in-kernel execution, there might still be scenarios where context switches are unavoidable. For example, interactions with user-space applications or handling specific events may require transitioning between user and kernel space. However, the goal is to keep such transitions to a minimum and leverage the advantages of eBPF's in-kernel execution model
- alexchamberlain 3y agoAre we getting to the point where parts of the kernel could benefit from running on a low power, cheap, less featureful CPU/co-processor, so that the beefy, suped up, SIMD, floating point instructioned super cores can be dedicated to rendering cat videos and sending IMs?