Writing an OS in Rust: Async/Await
os.phil-opp.com
os.phil-opp.com
It's a viable option for user-space programs because you can far more tightly characterize them and program them from top to bottom to work with that paradigm nice. Embedding islands of cooperative multitasking in a sea of pre-emptive multitasking seems to make a lot more sense than the other way around.
However, this post is a question, not a statement. If, for example, a Linux kernel developer posts "nah, it's no biggie, the Linux kernel is effectively structured the same", for instance, I would not quibble.
Interacting with hardware, dealing with interrupts, memory mapping/managing, task isolation, etc are all other aspects of an OS that are apart from task scheduling but still needed.
Cooperative multitasking works fine as long as the users/developers understand the limitation.
The problem is, we basically already know that is not the case. We've got years of experience with what "cooperatively multitasked" OS looks like, and it was not a "works fine" situation. You can't understand the limitations at scale as they interact with each other far, far beyond the human mind's capacity to understand.
Symbian also had it, both called them active objects.
The issue OP is discussing is cooperative vs. preemptive, not async vs. sync.
Pretty much my opinion. I think a preemptive threaded environment where some threads might run multiple async tasks (in order to boost efficiency) can make a lot of sense.
Pure cooperative environments seem too error-prone for bigger systems, because they lack the necessary isolation between tasks. Any bad task can degenerate the performance of all others tasks by blocking the execution thread.
Async/await is a programming paradigm that moves the state management of an asynchronous program into the compiler rather than being explicitly managed by the user. The paradigm is almost universally a win: if you don't want to write asynchronous code, just don't use it; it doesn't impact your code at all.
A second question is how the language actually drives the execution of asynchronous tasks. Most of the languages that have added async/await have incorporated it into their execution model, so you are forced to use the particular semantics of the language. There are subtle, but very important, differences here: for example, when you actually provide the answer that resolves the await, do you execute the waiting code immediately, or schedule it for a future iteration? This is what can cause the most problems with async/await, but Rust does not define any executors [1], so it's not an issue here.
The final question is if asynchronous code at all makes sense for an OS kernel. I'd argue that the answer is very much yes: communication with devices are almost invariably asynchronous (you set some memory lines to tell the device to do something, and get an interrupt telling you it's arrived). Particularly for the filesystem, where there are both synchronous and asynchronous system calls for the same code, a good executor for asynchronous code could well be beneficial for simplifying code paths. (Note that filesystems also generally have some degree of task dependency requirements--you need to ensure that the various requests happen in a particular partial order).
Now do note that this requires a far more complex executor model than most async/await toolkits (including this tutorial) provide.
[1] Logically, it would make sense to provide a utility function that synchronously runs an async function, but this isn't implemented yet.
I'm assuming the async/await language support in Rust is intrinsically tied to a cooperative approach, which is the part I'm questioning. Obviously a kernel needs to be able to generically work in an asynchronous fashion... the question is, is this asynchronous fashion appropriate?
If the Rust async/await support is indeed so flexible that with some work you could tie it together with a pre-emptive runtime of your own custom creation (as would make sense for an OS kernel), or some intermediate support that may not be "pre-emptive" but would be fully immune by-construction to the sort of issues I'm worried about, then, yes, by all means use it.
But a fundamentally cooperative kernel would really worry me. You'd be looking at freezing the whole kernel, and likely the whole machine, if anything, anywhere, goes wrong with the cooperation. It won't take a lot of scale before that's a problem.
And that's the worst case. Kernels strike me as very likely to also have to deal with the starvation situations that cooperative multitasking can have, where one "task" never gives up control. Even if this doesn't freeze the machine, this can cause significant, human-visible latency issues to emerge.
I think that's exactly what it is. AIUI it's basically an API for async/await (and maybe a default runtime?) that different back-ends can be plugged into. At least that's what I've come away with over the months of reading random bits about it here.
I mean, you don't actually use preemption in the kernel right? Don't you have to handle all that yourself, since there's nothing higher level than you to handle it for you? In that respect, doesn't plugging in a Futures runtime that looks for device flags and stuff as appropriate and flags tasks to wake up/finish accomplish the same thing? (those are actual questions, not leading statements)
[1] as in: http://journal.stuffwithstuff.com/2015/02/01/what-color-is-y...
* Magic keywords (i.e., async and await) to manage the state machine aspect of the function for you.
* A standard interface for describing an asynchronous task (core::future::Future). The magic keywords create an implementation of this interface.
* An interface for saying that task progress can be made (core::task::Waker).
That's it. There is no runtime provided, not even optionally, in the standard library (let alone core). A fair amount of this post is giving instructions for how to build the runtime to execute asynchronous tasks.
One important thing to note is that Rust uses a polling-based approach to implement tasks. That is, the core interface to a task is to run it and have it return the result or indicate that is waiting on something else. In the case of the latter, there is a callback mechanism (the Waker object) that the task is responsible for calling when it has more information to make progress--and the caller is responsible for calling the task again when that happens. Many (most?) other implementations instead use a resolution model, where the caller provides a function that is called with the result, and when the function gets called (particularly in the case of tasks that can execute quickly) differs from implementation to implementation. Rust's model definitely maps much more easily to a kernel, since the dominant pattern will be to drain a buffer, poke a device, and then wait for an interrupt to happen (the interrupt handler calling the wake function).
What is nice about Rusts model is that it prevents the continuation from running inline the event handler which signaled the completion. That avoids a ton of reentrancy issues and questions around "where does my code actually run"? That indeed makes it also interesting to use for interrupt handlers, since it is guaranteed that the code which waits for the interrupt to happen runs purely in the executors thread and will not accidentally take over the interrupt handler.
The article isn't discussing schedulers, but async-await within the OS codebase in general. Forgetting the scheduler, for example, Interrupt handling and driver code is generally async in nature, and at a base level needs to be cooperative.
while let Some(byte) = keyboard.interrupt().await() {
...
}
This is already the case, isn’t it? If you do a ‘while(!operation_complete) {}’ anywhere in the kernel and it never happens then I’d expect it’s pretty much done.
Whereas with async/await it’d be more likely that the coroutine would simply never resume. It might wind up being a memory leak, yeah, but not freeze your system.
That assumption is incorrect. The blog post explains this in detail better than anyone could here - and if that does not suffice, the Rust book and the async book, as well as the Fuchsia kernel documentation, also all go into this.
> If the Rust async/await support is indeed so flexible
It is indeed even more flexible than that. You don't even need a run-time to drive progress. You can manually drive progress of async tasks by polling them throughout your code at specific points if you wanted - essentially interleaving the async processing of tasks with your main thread's task (and well, you can build any sort of executor you want, with different priority levels or whatever you feel like doing). I have an HPC app that does this to drive MPI non-blocking communication.
The blog post explains all of this. It's pointless for you to invest a lot of your and others time into speculations built on top of incorrect assumptions, when the first 2 minutes of actually reading the blog post clarify this for you.
> Embedding islands of cooperative multitasking in a sea of pre-emptive multitasking seems to make a lot more sense than the other way around.
In my reading of the post, the proposal is to do cooperative multitasking within the kernel, and preemptive multitasking between the kernel and the userspace. I think this is tenable, within the kernel, you pretty much need to play nice with the rest of the kernel anyway. Most kernels don't have effective protection for one part of the kernel causing problems with the rest; although, some do have limited protection against drivers that crash or loop.
[1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
Linux has a lot of cruft and isn't as async as some would like, but NT is pretty async underneath it all (although they still allow you to do syncronous work as well).
One way to address you concern would be to guarantee that task always terminate in a bounded amount of instructions.
One way to solve that would be offer a limited buffer in which the program instructions for the task might be expressed, and a language to express them in that is strongly normalizing (think something like Morte)
Atomic tasks are generally expected to do a finite amount of work that can be finished in a short time without waiting for anything else (except maybe a spinlock, which should be held by some other similarly-atomic task that will finish in a short time).
You might want to look at Joe Duffy's posts about Microsoft's Midori OS. In particular the post "Asynchronous Everything":
http://joeduffyblog.com/2015/11/03/blogging-about-midori/
Their findings sound pretty compelling to me. Personally I'm convinced that eventually we'll see much more system-level use of async/await style mechanisms. Perhaps with Rust, perhaps with C++ once coroutines land in C++20.
That's completely wrong. Either cooperative multitasking works or it doesn't. There is no probability involved. What often happens is that foreign code that is not under your control is not yielding. It only takes a single non cooperating task to block an entire core. If you have properly written code the probability of a malfunction is 0% and this probability doesn't grow with the number of threads.
> The only requirement is that we use at least nightly 2020-03-25 of Rust because async/await was not no_std compatible before.
There's some fun stuff here that's omitted (which makes sense, of course). It was always a design constraint of async/await in Rust that you could use it without the standard library. However, the initial implementation required thread local storage. The future trait's poll method took a &mut Context, and generators didn't support passing context in to them when resuming. This meant that the context would be placed in TLS, and would pull it back out when needed. Generators are unstable, partially for this reason. However, this was fixed, and that means TLS is no longer a requirement here! See https://github.com/rust-lang/rust/pull/68524 for more details.
I was trying to figure out if QNX does this with `MsgSend`, as QNX is renowned for being a fast microkernel, but it wasn't clear to me. According to Animats, "There's no scheduling delay; the control transfer happens immediately, almost like a coroutine. There's no CPU switch, so the data that's being sent is in the cache the service process will need." [1] According to wikipedia, "If the receiving process is waiting for the message, control of the CPU is transferred at the same time, without a pass through the CPU scheduler." [2]
It seems like `MsgSend` circumvents the scheduler, but does it circumvent context switching to the kernel entirely too?
Context-switching on most current platforms with virtual memory requires fiddling with things like page mappings, and that simply must be done from supervisor mode.
The ability to switch tasks in hardware has existed on some historical machines. For example the GEC 4000 series basically implemented a microkernel, including the scheduler, in hardware. Switching to another process was done with a single hardware instruction.
I don't think anything current has such features besides the long-obsolete and unused taskswitching feature on x86 processors.
So my feeling about it is that it may turn out to be an evolutionary dead end, or anti-pattern at the least. My gut feeling is that async/await is functionally equivalent to the the synchronous/blocking/coroutine/channel system of other languages like Go. Could we write a thin wrapper that converts async/await to that or vice versa?
This is the primary reason why I've stuck to synchronous/blocking PHP with all of its flaws instead of Node.js. I think this is a fundamental thing that shouldn't be glossed over and accepted so readily into other languages.
> Come to think of it, all of the times I've encountered it, there was no way to analyze the codepaths and prove that every exceptional situation and failure mode was handled.
There is nothing special about async/await with regards to this in Rust, at least if I'm understanding you correctly. Async functions can return Results like any other function for recoverable errors, and can panic like any other function for un-recoverable errors.
> My gut feeling is that async/await is functionally equivalent to the the synchronous/blocking/coroutine/channel system of other languages like Go.
It depends on what level of abstraction you're talking about. For Rust, which cares a lot about details, they're not. I gave a talk comparing and contrasting all this stuff here: https://www.infoq.com/presentations/rust-2019/
Then if something does fail (wifi blips out without a retry, who knows) the page just hangs with no indication of what went wrong.
Contrast this with Unix-style synchronous blocking code piping data between threads with no shared state. Since every step of execution happens in a single thread, blocking until a pipe returns data, it's trivial to step through the code.
Async/await really becomes a problem in Javascript though because they made it a language keyword in Node.js. So you never know if you are dealing with a sync function or async function. Eventually the entire program has async in front of everything and ends up being written just exactly like sync blocking (but with superfluous syntactic sugar everywhere). So I question what was really gained there. IMHO it just doubles the workload in the mind since now we have to juggle both types of functions and explore those permutations. That's the last thing we need when we're trying to brainstorm a solution from a large possible search space.
I'm also looking at this from a one-shot functional programming perspective. I realize that sync blocking code blocks the main thread, which is usually the GUI rendering loop. There are ways around that though. The best solution I've seen so far is Apple's Grand Central Dispatch:
https://en.wikipedia.org/wiki/Grand_Central_Dispatch
https://www.raywenderlich.com/5370-grand-central-dispatch-tu...
https://www.swiftbysundell.com/articles/a-deep-dive-into-gra...
Basically it works by being sync blocking and providing simple ways to run closures on other threads. I find it much easier to debug than async/await though. Rust probably already has all of that functionality, so I don't understand the advantage of copying Javascript model with all of its caveats. I think what's happening is that people just want to run with the context they're already familiar with.
> I don't understand the advantage of copying Javascript model with all of its caveats. I think what's happening is that people just want to run with the context they're already familiar with.
With respect, I think it's because you don't understand it in Rust yet. It was not directly copied from JS, and was certainly not due to familiarity. Read the post! It's very good :)
Channels are just queues and passing methods. Rust style futures are closer to continuations. Both are powerful and can accomplish neat taska, but not ABI compatible or even used the same way.
My understanding is channels in `go` are 0 sized by default- and thus turn into "rendezvous channels" that can be used to synchronize progress between threads.
This article compares Go and Rust threads and includes an example of how go uses channel's to synchronize. [0]
[0] - https://medium.com/@deckarep/paradigms-of-rust-for-the-go-de...
The programming model of async/await is essentially syntactic sugar for a state machine, where each of the states are determined implicitly by the site of the call to await, and the ancillary storage of the state machine is managed implicitly by the compiler. It's basically no different from a generator pattern (and is usually implemented on top of the same infrastructure) [1].
Since the result of calling an async function is a task object that doesn't do anything until you call methods on it (including implicitly via await), most languages integrate these task objects with their event model. This model is completely orthogonal to the feature, and often exists (at least in the library, if not the language) before async/await is added to the language. JS has a built-in event loop that predates async/await by several years, whether programming in client-side browsers or using something like Node.js. Rust is unusual in that it prescribes absolutely nothing for the executor model; all it defines in its standard library is the interface to drive the tasks manually.
I doubt async/await is an evolutionary dead end. It's the third kind of coroutine to hit it big in mainstream languages, the first two being the zero-cost exception handling mechanism (i.e., try/catch) and the generator (i.e. yield). The biggest criticism of zero-cost exceptions essentially amounts to their types not being made explicit, but the design of async/await makes their effects on the type of coroutine quite apparent, so it's not going to run into the same problems.
[1] There is a difference in the pattern, which is that you're probably going to get back different kinds of objects implementing different interfaces, which is a bigger deal if you manually drive the interfaces. Structurally--that is, in terms of the actual machine code running--there is likely to be no difference.
Edit: I forgot to mention that I came to your same conclusion a few years ago about async/await being equivalent to a state machine. It happened a different way for me, when I realized that a coroutine performs the same computation as a state machine, but is much easier to trace. I was working on a game, and made a rather large state machine with perhaps 20-50 states and some side effects where those states interacted with game state. But it simplified down to just a few lines of ordinary flow control code when I tried it as coroutines with message passing. So to me, async/await carries the burden of state machine complexity but loses the simplicity of coroutine (and sync/blocking obviously) traceability. So I just don't see a compelling reason to use it.
I couldn't find a post about it, sadly, but I know the information is out there somewhere.
> The Control thread is designed to be entirely deterministic when its inputs and scheduling decisions are fixed. We use this property to fuzz it with pseudorandom simulation testing. With a seed for our random number generator, we can generate random initial filesystem state, schedules, and system perturbations and let the engine run to completion. Then, if we fail any of our sync correctness checks, we can always reproduce the bug from the original seed. We run millions of scenarios every day in our testing infrastructure.
Certainly as a human reader, Future-based code (which async/await is sugar for) is the easiest form of concurrency/parallelism to reason about: yes you have small tasks that might execute in parallel, but all your functions still return values, function composition still works the way you'd expect, there's no way for parallel tasks to silently interfere with each other in some hidden way. The control flow is still what it looks like (unlike with general coroutines). Of course if you can afford to avoid parallelism entirely you probably should, but async/await is the least intrusive/most understandable way to manage it if you do need it.
> Will it come back to this state in the future?
If there's a path from the current state back to itself and it gets the correct inputs, yes. Otherwise no.
> Is there a route from state Y to state Z?
A simple glance at the graph will suffice to answer this.
Of course poorly written code, regardless of the constructs, will be hard to reason about.
But programming by editing graphs never caught on. So the graph is always going to be a secondary representation of your program; it won't be the natural view in your debugger or profiler (if it's even visible at all).
And more importantly, no-one's found a really compositional approach to programming with graphs yet. In conventional programming you can define an interface that exposes one function, and maybe you have an incredibly complex implementation behind that interface, but you can reason about the rest of your program without having to look inside that black box, even as the implementation changes drastically. I've never seen the same approach applied to state machines: maybe you know that this cluster of states is independent now, but anyone can add a new state transition that changes the global control flow willy-nilly.
>Has it already been through state X?
Like everything else, logging
>Will it come back to this state in the future?
Mentioned in the comment before, there is a transition graph that you can do static analysis on, note that you might run into a halting problem
>Is there a route from state Y to state Z?
There is a transition graph
>State machines are effectively goto writ large...
quoting Prof Carl Hewitt of Actor Model, "goto is harmless"[2], function/procedure call is a goto, much like sending an named event while in particular state with/out parameters
[1] https://en.wikipedia.org/wiki/UML_state_machine
[2] https://www.youtube.com/watch?v=7erJ1DV_Tlo&t=34m54s
note: edited for formatting
Would need to see what the implementation actually looked like and how it was worked on. The graphs may look nice, but I've never seen people program effectively by editing graphs.
> Mentioned in the comment before, there is a transition graph that you can do static analysis on, note that you might run into a halting problem
Sure, but the graph seems to be very much secondary. You don't step through the graph in a debugger, for example.
> quoting Prof Carl Hewitt of Actor Model, "goto is harmless"[2]
Not at all convinced, and he fails to make any real case for it. I've worked on actor systems, and they're bad in the same way that unstructured code is bad.
> function/procedure call is a goto,
It's not, because you still have the call stack. You know where you came from and why (and can see it in the debugger), and you know you're going back there. You can reason compositionally, because in g(f(x)) f is a black box and always will be even if it gets refactored, whereas there's no equivalent "locality" in a state machine.
> much like sending an named event while in particular state with/out parameters
That also sounds like a bad way of doing things.
> Would need to see what the implementation actually looked like and how it was worked on
Examples are but not limited to Simulink, Rhapsody, Unreal Blueprint, QT SCXML
>The graphs may look nice, but I've never seen people program effectively by editing graphs
graph mentioned is a state transition graph, not necessarily a visual graph, although its a nice eventuality
> You don't step through the graph in a debugger, for example.
Yes you do, if using the mentioned example
Combining a state machine with actor model has been a work wonder for me. I have to agree with you on locality in pure state machine, but if a state machine is defined as an Actor you get locality by definition. Its more of a deterministic abstract modelling, testing and execution
Not really. You have a kind of binary version of locality - whether something is in the same actor or not - but you can't reason about any region that's smaller or larger than that. Incoming messages might arrive from anywhere, and emitted messages might cause any kind of effect anywhere (including other messages back to the sending actor). So you can't really understand any region larger than an actor without having to understand the whole system - and that's before we even get to passing actor addresses around.
What ends up happening is that exceptional situations happen and the state machine becomes muddled with special cases. So for example, say you're writing a networked game of Tetris or Pacman, something with a relatively small state machine. You get all done but realize that you forgot to handle people joining or leaving the game, or the game closing or jumping ahead when a remote player beats the level and the game needs to go back to the title screen. The state machine starts getting all of these checks interspersed with the game logic.
Typically this doesn't happen with sync/blocking code though. You write an ordinary main loop, adding checks for these exceptional situations just like any other event you watch for. In my experience, the sync/blocking code is roughly an order of magnitude smaller and easier to reason about than a state machine. But more importantly, it can be scaled infinitely, because you can always add tracing or step through it in a debugger as you normally would. But a large state machine is just exactly what you described: a large switch command of gotos. You can't just look at it and know where the code came from or what conditions got it there. You have to derive that history by hand in your head.
And since async/await is more conceptually equivalent to a state machine than a coroutine or sync/blocking code, that severely limits how well we can reason about large promise chains. See my comment to jcranmer on this thread for a bit more insight about the internals of this:
I have to disagree with that. You can implement async/await using state machines, just as you can implement a loop using goto, but it's a more constrained model that's much easier to reason about than a fully general state machine or a fully general coroutine. The control flow still proceeds the way you expect - you still execute code from top to bottom, you still return once from every function call - you just yield at some points in it. You're not interleaving your control flow with some other function that you communicate with (like a generator), and you're certainly not treating suspended control flow as something to be copied or passed around (like a coroutine). It's a much simpler concept.
What's old is new again ...
> Using async/wait, we now have basic support for cooperative multitasking in our kernel. While cooperative multitasking is very efficient, it leads to latency problems when individual tasks keep running for too long and thus prevent other tasks to run. For this reason, it makes sense to also add support for preemptive multitasking to our kernel.
> In the next post, we will introduce threads as the most common form of preemptive multitasking. In addition to resolving the problem of long running tasks, threads will also prepare us for utilizing multiple CPU cores and running untrusted user programs in the future.
It seems the plan here is to use this for internal work, and still give a preemptive multitasking API to userspace.
And yes, the GP is not wrong that if this were the only mechanism provided, it would be similar. It does not seem like the plan is to expose this externally whatsoever, though.
Again, this is based on my admittedly limited understanding, but I haven't yet seen good reasoning why pre-emptive is still preferred.
The laptop I'm writing this on has four cores, and the Chrome instance has 17 threads running...
You would probably still want to preempt, because you're not going to rewrite all the widely used software to actually yield.
Because that's the thing about cooperative multithreading, the participating parties need to cooperate.
And if you look at the amount of threads that some software open it's just crazy. Looking on my machine the top5 are:
1. 260 threads System (ok, that's basically the OS that could be changed).
2. 145 threads Dropbox.exe (that's enough to lock all cores on any single consumer CPU).
3. 87 threads SearchIndexer.exe (also OS, could be rectified).
4. 74 threads EpicGamesLauncher (looks like an i9 is no longer enough)
5. 70 threads MemoryCompression (also OS)
I know not all of those threads are active at all time an I guess all the blocking threads could be said to be cooperating but even Dropbox alone regularly has 3-5 threads running.
There's still so many 2 and 4 core consumer machines out there that cooperative multi-tasking with the current software ecosystem would be a disaster.
Not only would applications keep each other from making regular steady progress but even single applications would regularly hang themselves from all the threads they themselves created if there was no pre-emptive yielding beyond using any OS-call as a yield-point
On N-core, 2-way SMT hardware (which describes pretty much all consumer hardware), the maximum amount of threads that can be usefully doing work in parallel is between N and 2 * N. Any more threads than that, and it must be the case that you expect those threads to spend a lot of time doing nothing to justify the cost of their creation.
There's two main categories that can justify that. The first is threads that are spending a lot of time stuck in blocking I/O--i.e., they're calling things that exist as yield-points in practical kernels anyways. The second thing is some sort of event processing loop, which looks like kind of like this:
while (!shutdown) {
event_t *e = get_next_event(queue);
if (!e) { sleep_until_work(queue); }
else { execute(e); }
}
With cooperative multitasking, launching something like a parallel compilation would make your machine unusable.
It might not lock-up your OS but it would lock up all of the userland and the kernel couldn't do anything about it, because it can't pre-empt. All it could do under that model is let the user kill the browser or just kill the browser itself automatically.
I think most people would prefer being able to use their PC for other things while transcoding a video or compiling a program at near the PCs full capability. Instead of sacrificing a whole core to the OS and then also having to wait longer for those tasks to finish, plus not being able to do anything else.
A model with less pre-emption is certainly possible, but current end-user software makes an approach without any pre-emption very in-advisable.
Anyway, this SO answer[0] explains why early Linux, much like the hobby kernel in this article, used cooperative scheduling inside the kernel, and only preempted user-space stuff.
I don't understand why this would be different for a Rust based OS..
The difference between preemptive and cooperative multitasking is not whether you do full context switches, but whether there is a way to do context switch at a point where the process does not expect it (ie. by handling some kind of timer interrupt as scheduling opportunity).
Computation can also be viewed as a blocking operation.
For this to work, perhaps Rust should cooperate too, inserting .await points at strategic places in the code, to keep cost low but still guaranteeing a certain responsiveness of the overall system.
And you would need to avoid having any kind of call to external code (or yield before and after every such call, and pray for the best).
i've been going through http://craftinginterpreters.com/ in rust (in order to learn rust) and it's a fantastic learning experience. the language is straightforward after you understand the basics (smart pointers and generics) and if you have a good ide with completion (CLion). lifetimes/borrow checker aren't as painful as people would have you believe if you use heap allocation (i.e. Box, Rc<RefCell>). now obviously heap allocation isn't optimal but for getting started it enables a smooth progression.