#operating system design

Linux in recent years has fixed some of the biggest annoyances I had with the UNIX model, and I'm feeling rather happy about this. One example of this is with how you can refer to processes.

With traditional UNIX APIs, you can never signal a process without a PID reuse race condition. The problem is somewhat inherent to the model: a PID is just an integer reference to a kernel-level Thing, but crucially, that Thing is not being passed around between processes. If I tell you the PID 42, that's not qualitatively different from you randomly picking the number 42 - either way, you can try to signal whichever process currently has PID 42. You might not have permissions to signal the current resident of that PID for other reasons, but you don't need a prior relationship to signal it - you don't need to receive any capability object from anyone. I haven't given you something tied to any process, I just gave you a number, and in the traditional UNIX model there's nothing better (more intrinsically tied to a single process) to pass around.

Compare file descriptors. An FD is also "just" an integer, but having that integer is worthless unless you also have the kernel-level Thing shared with your process. Even if I give you the number 2, you can't write to my stderr - I have to share my stderr, for example by inheritance or by passing it through a UNIX domain socket.

This difference is subtle but technically crucial for eliminating race conditions: since an FD has to be shared from one process to another through the kernel, and the underlying "file" descriptor/description is managed and owned by the kernel, when you later use the FD in a system call, the kernel can always know a fully unambiguous identity of which Thing you were referring to. If you just told it 42 in some global ID space, well do you mean the thing currently at index 42? Or did you really think you were referring to a thing which existed some time ago at index 42? That information has been lost, or at least isn't being conveyed. But if you told it 42 in your file descriptor table, now that can hold more information, so it can remember precisely which thing your 42 was referring to when you last received or changed it.

So how did Linux fix this?

We now have "PID FDs", which are magic FDs referring to processes. Processes "as a file", in a more true and complete way than the older procfs stuff.

Unlike PIDs, which by design can only travel around like raw numbers divorced from the true identity information they gesture at, a PID FD can never lose track of the process it refers to: if that process dies, its PID FD will forever "know" that its dead even if the PID is reused (because when that process yields to or is preempted by the kernel for the last time, the kernel remembers that there's a PID FD for it which needs to be updated, and even if the kernel recycles the PID it knows not to update that PID FD to point to the new process).

And we now have a system calls which let us

create a new process (or thread!) and have that return a PID FD instead of a PID (or "TID" in the case of threads, but in the Linux kernel those are basically the same thing)

signal a PID FD instead of the traditional PID (or TID), and

wait on a PID FD (in fact, the FDs just plug into the normal poll, select, or epoll system calls, so waiting on process or thread status can just hook into all existing event loops).

The one crucial thing is that we must not forget that these guarantees only start once we've gotten the PID FD: in particular, if you get a PID FD from a PID instead of getting the PID FD directly, you still need to check once if the PID hasn't gotten invalidated between when you got the PID and when you got the PID FD. This is something you can only do as the direct parent or (sub)reaper of the PID in question, because then you can use the traditional "wait" system call on the PID after getting the PID FD - if getting the PID FD succeeded but then the wait reports that the PID exited, that means you could've gotten a PID reuse by the time you got the PID FD from the PID.

So ideally, we just don't deal in PIDs at all anymore. When we create a process, we can get its PID FD atomically with the creation. (If we can't do that, if we're creating the process and then getting the PID FD with a separate system call, we do the wait check described in the last paragraph after getting the PID.) Then we pass the PID FD around - this might superficially look like passing an integer around, for example if you need to use the FD number in a shell redirection or communicate it to a child process, but underneath that the actual FD would be getting passed around either by inheritance, UNIX domain sockets, or whatever other means are available.

I've been wanting this for years. I've spent a lot of mental cycles trying to figure out the most elegantly minimal and composable primitives which could work around various problems in service supervision and automatic restarts in the face of random processes dying or getting killed. Those edge cases are now much more simple to totally cover by using the PID FD stuff, at least so long as we're willing to lose compatibility with the BSDs and other Unix-y systems until they catch up. Which, honestly, is an increasingly appealing proposition as Linux has been adding good stuff like this lately.

Android and iOS are toys on the surface, and below that surface is a thorough and deliberate badness which is nearly impossible to express.

on the one hand, preemptive, implicit, unpredictable multitasking is awful for reasoning about code behavior any time there can be relevant side-effects, but

on the other hand, preemptive, implicit, unpredictable multitasking is fine and a significant benefit to writing code if no side-effects that could slip in matter.

Here's where I'm at now with this:

What we really need is a system which requires cooperative multitasking unless you have written code which is "pure" code. If something in the system running your code can prove or has been told that your code need not care about side-effects, then it is fine for the system to do preemptive multitasking anywhere in your logic. But, code rootwards in the call tree from your code must be able to control if preemptive multitasking happens in your code.

Because preemptive multitasking is an optimization, the dangerous kind which is liable to change behavior or introduce bugs unless properly constrained, and like most optimizations it cannot be done without some sort of dialog between the thing implementing the optimization and the people or code which is aware of the bigger picture of the specific use-case, situation, and relevant caveats.

The simplest version of this seems trivial to do.

What's left is to figure out how to best make it granular, because stop-the-world blocking of all preemptive multitasking is rarely necessary, and would probably cause problems if code regularly relied on it to prevent race conditions.

Okay, so, here's roughly the thought process, although by now I've re-ordered and re-written several chunks of this, because the original thought process was a meandering thinking-out-loud. And this still is that, but I've tried to make it at least a little coherent.

Clearly "not safe to preempt" has to be transitive, from the caller down. Even if some pure code by itself is fit to get preempted, and even if we had a system where that code actively indicated that it is compatible with preemptive multitasking or did some sort of yield-if-needed operation, if that pure code sits in a code path which cares about any side-effects that might happen when it is preempted or something else is scheduled concurrently, then it needs to be able to call into that pure code without that code being preemptible.

Caveat: for some code, timing and latency is a relevant side-effect. This is why mainstream preemptive multitasking operating systems are so terrible for trying to build real-time computing systems - you can't guarantee any upper time bounds if any number of other things can be preemptively scheduled in between all of your operations. So whatever method we use cannot even assume that code paths of entirely pure code without side-effects in the semantics of its language is safe to preempt.

Finally, part of why "coloring" functions with an `async` keyword is good is that when `async` is transitive rootwards on the call tree, we always know when something we call is forcing concurrency problems onto us. Of course, if you can perfectly contain the concurrency within your implementation then there might be a way to split your call stack into a call tree of coroutines which are concurrent with each other but isolated from all other concurrency, wait for all those to finish or get cancelled, and that's fine to not reveal to the caller. But if your use of concurrency can breach containment in any way, you shouldn't even have the ability to express your code in a way that hides that from your caller. So that is the wisdom of function "colors".

But if we have an explicit yield-if-needed operation, should it be colored async? If you're already convinced of how great `async` color which contaminates all callers recursively is, and if you've accepted the wisdom of structured concurrency that concurrency should not be allowed to breach containment or slip in under you without you knowing about it and consenting, you might be tempted to say that the answer is obviously yes. Every instance of yield-if-needed is an opportunity for side-effects, after all.

So here's the key realization: yield-if-needed isn't saying "I use concurrency here (you are using concurrency by calling me)", it's saying "I yield to concurrency (you can use concurrency while calling me)".

So they are actually really different things, that we need to handle differently. Code which uses concurrency in a way that breaches containment is non-optionally forcing you to use concurrency, and it needs to be seen and managed as a place where something else can be scheduled underneath you. But code which merely yields to concurrency without using it is just optionally concurrent.

And so we could have a system where we can tell the scheduler "hey, I'm going to execute some optionally concurrent code now, but concurrency in this case is not safe for my logic, so don't schedule anything else in the meantime (and I accept that the only choice this might leave you with is to give me a cancellation signal or just kill me if it takes too long in total)".

Also, if yield-if-needed is an async-colored operation, then libraries doing pure logic can't just call it without tainting themselves as impure, as async-colored, and compilers or other tooling might need to do smarter and more extensive code transforms to automatically put it in for you if you don't care and just want the computer to do it for you. Because async-coloring in many languages changes the implementation of a function to return something that at a minimum holds the state which must be saved between pausing the now-interruptible function and resuming it.

So if we decide that yield-if-needed is not an async-colored operation, then

only code that introduces concurrency is async-colored, rather than any code which is not harmed by yielding to concurrency, and

yield-if-needed becomes something that actually could be slapped literally between any two operations in pure non-async code.

So finally we get to the breakthrough: we upgrade the yield-if-needed operation to yield-if-needed-and-safe.

The scheduler brings the "needed". The caller brings the "safe".

Of course, the scheduler has final say, so if you try to disallow yielding for too long you get some sort of cancellation signal, and if you don't obey your process gets killed. In fact I think there doesn't even need to be an explicit cancellation signal in the simplest version of this: when code sees that the "do I need to yield?" value is no longer zero, it could consult another "is it safe to yield?" value. If that says no, it quickly bails out and goes back to the caller with a "scheduler said to yield before I could finish" error. Or maybe there is also a good argument in some cases for the code to yield in that situation, and then only upon being resumed go back to the caller with the "scheduler said to yield before I could finish" error. Either way, getting that error from something you called functions as the cancellation signal.

I really like this. I think this elegantly solves the problem:

if you have logic which really doesn't care about being preempted, you can just write code without thinking about it, and it's trivial for your tooling or the system to automatically inject preemptive multitasking,

if you are calling into pure logic you don't need to worry about whether or not it has an yield-if-needed operations, because they're yield-if-needed-and-safe operations, and your code gets to say whether or not it is safe,

yield-if-needed-and-safe no longer needs to be async-colored, because it can only introduce concurrency which the system has proven would be irrelevant if you followed its rules, or which you have told the system is irrelevant - it can no longer force concurrency onto your caller,

we can implement this in a backwards-compatible way which allows incremental migration: add the yield-if-needed-and-safe operation, and let code opt-into this mode where it can say "don't interrupt me until I say it is okay" but it will get killed if it doesn't yield for too long,

in fact we maybe no longer need the yield-if-needed-and-safe operation, because the system can do the same check that yield-if-needed-and-safe would do, and if it knows you don't want to be preempted, it can just not schedule the next preemption until the latest possible moment,

although the yield-if-needed-and-safe might still turn out to be useful, either as an optimization, or because there is a need for it which I'm not yet seeing.

And the cool thing here is that we could generalize this! We could have systems that let you take any arbitrary sequence of operations, and the entire sequence will either succeed without interruption or race conditions, or fail somewhere along the way because there wasn't enough time in the time slot you had from the scheduler. You still have to do the hard work of figuring out how to deal with any inconsistent state from partial completions, but you no longer have to worry about all the problems that can only happen if something else gets to operate on the same state at the same time.

We could even probably figure out how to do this across processes. So even shell scripts could say "hey please don't schedule something between these commands that I'm about to run". And if the shell script or its child processes take too long, the whole process tree starting from that shell script gets whacked. And it seems like it would be fairly trivial to pass information between the operating system's scheduler and any event loop scheduler or lightweight thread scheduler in user-space, so most software developers would only need to make the request once in whatever language or framework they're using, and it could apply across all the relevant nested schedulers that are in play.

The other way this generalizes is that it would be nice and probably necessary to have the capability for branches of the call tree to isolate their concurrency from all other concurrency. To let code say "I am using concurrency as part of my implementation, and I am fine with yielding to other coroutines which I spawned as part of my logic, but I need to be safe against races with other logic".

(Incidentally, the most mature and thought-out structured concurrency implementation I know of (the Python library Trio) lets you shield a branch of the call tree from cancellation by code rootwards on the call tree. And what I'm describing here is shielding a branch of the call tree from concurrency with code which is rootwards on the call tree. I imagine Trio has cancellation shielding and not concurrency shielding because in most async code, you want other stuff scheduled while you wait on I/O, and you can get away with putting off handling cancellation until you're done with something that needs to finish to keep things consistent. Meanwhile, I'm currently more focused in robustness against race conditions and how to get the benefits of cooperative multitasking while still being robust against code which fails to yield for too long, all while making guarantees about completing within some upper bound of time - so desirability of concurrency is no longer taken for granted, and cancellation is more starkly revealed to be something that needs to be a non-optional final warning. Notably though, to the extent that cancellation shielding can be permitted, it seems a lot like a special case of concurrency shielding.)

So this is all cool, but so far this solution is fairly all-or-nothing. The simplest implementation I described is absolute - there is a "need to yield" boolean (which we might consider turning into a "yield deadline" monotonic clock value) and a "safe to yield" boolean. Of course, we can implement more granular concurrency scopes/shielding on top of that mechanism. The trouble is actually coming up with how to make it more granular than "yes I'm fine with stuff preempting me" or "no I'm not fine with stuff preempting me". What we really want is a way to specify which stuff we are fine being preempted by.

And maybe the answer is almost just locks - mutexes, or read-write locks, the usual. In a sense, locks are how you say "please do not schedule anything else which uses this specific thing at the same time". Of course this was very hard for me to see because a lot of systems do not have locks for most things or actions which you might want to avoid concurrency for, and what locks they do have are often advisory. But if

everything which touched or did a thing in a way where races might matter was required to get a lock for precisely that thing, and

all locks were automatically released if the holder did not release them on their own soon enough,

then holding locks basically functions as precise specification to the system and its scheduler of exactly what you care about not having scheduled during your code.

An almost stream-of-consciousness ramble of something I was thinking about today.

By Default, Maybe Even Mandatory

The more I think about writing correct code, the more I feel like preemptive multitasking as the norm was a mistake. That operating systems should have been written from the ground up to assume that all good and correct software yields execution back to the scheduler every once in a while. That computer science education and software development tradecraft should teach and presume that cooperative multitasking is the only multitasking available or acceptable.

Preemption for the Uncooperative

Obviously robust systems must have preemption capability, in order to avoid denial-of-service from code which never yields control. So systems would still need the foundation of preemptive multitasking, and processes which do not cooperatively multitask would need to be preempted. The temptation which many operating systems followed is to just make this the norm - anything can be preempted at any time, thus your guarantees against race conditions are weak at best and every piece of the system has to do more work just to keep things sane in the face of multitasking.

But I'm almost ready to say that programs which don't yield control for too long should probably just get killed, ignored, presumed dead or compromised, timed out, invalidated, be stripped of any resources and locks they hold, and so on. At the operating system level, at higher levels of how you design your multiprocessing and distributed systems, in your business logic, at all levels.

Given enough time, all conceivable execution delays and communication partitions which could cause things to not get back to you soon enough to not be a problem will happen. We can either

write code on systems which force us to deal with it thoroughly and from the ground up, across our entire trade and industry and culture, which is cumulatively easier to get right once everyone knows and follows the patterns, or

we can keep living in a sea of code and systems overwhelmingly saturated with an incomprehensibly inconceivably large number of concurrency and latency problems just waiting to happen.

All You Need (Probably... I Just Make Shit Up On The Internet)

Obviously almost everything is in place already, we're just not using it to build systems which are consistently honest, helpfully explicit, and manageably controlled about where concurrency can happen.

In a typical modern operating system, when you call a system call, or at least certain system calls which tend to inherently entail delays and thus are natural points for scheduling or cancellation, you are yielding execution to the kernel. Now the kernel has an opportunity to go do something else, schedule another program, deliver a signal to your program or kill your program with a signal, and so on. The kernel only preempts your process if you don't call into a system call for long enough. Otherwise you're being cooperative. And in the real world, this is how lots of programs actually play. They don't have to be written to cooperatively multitask to do it, they just have to do operations which are natural scheduling or cancellation points, which most program do often enough on their own, because most programs are interacting with the outside world, not slamming the CPU with raw self-contained computation long enough to use up their time slot.

So what about the program that do want to hog the CPU longer than their time slot?

Well, we have the ability to trivially implement a "yield control if something else is waiting" operation which would have effectively zero overhead if it's not time to yield (at most a handful of machine instructions with one branch, and if you're pipelined and branch prediction matters, that branch can be predicted as taking the "no need to yield" path for hot loops and other pure computing logic, which is the only situation where the overhead of that check and branch prediction is actually a problem).

To me that seems like the only remaining primitive the OS kernel needs to provide to user-space to make this work. And it's trivial! Let's assume we're using a memory location for generality, though this could be optimized all the way to the hardware, with a dedicated CPU flag or register and exposed in the instruction set. Anyway, in the in-memory version, the simplest form is a fixed address on systems with an MMU and virtual memory, or perhaps it is provided by the kernel to the process during initialization, to be compatible with ASLR and hardware without an MMU. When the process starts up, the kernel sets the value at that address to zero. When it's getting close to the time when the scheduler would want to preempt the process, the kernel writes one at that address.

(Internally, on modern hardware with all cores busy, flipping the value at this address from zero to one might have to be implemented as a momentary preemption of user-space by kernel-space code. So you can see where the temptation comes from! A working multitasking kernel which does not depend on cooperative multitasking must have all the building blocks necessary for preemptive multitasking, and it is so natural to just let user-space processes partake in concurrency seemingly "for free" - it took humanity half a century of experience to get to this point where we're starting to realize that this is actually detrimental on the whole.)

Now, whenever the process wants to know if it should yield, it reads the value at this address. Is it still zero? You got enough time left to do some work before checking again. Is it anything else? Time to yield - if you checked reasonably often, you've still got ample time to go directly to yielding execution to the scheduler. Did you overwrite it, or take too long to check? That sounds like a you problem, if you don't yield often enough, your process gets preempted, but then it's just killed.

Notice that you're not being asked to gracefully shut down or pause or clean up anything. This isn't some situation where you gotta scramble to flush buffers, save state to disk, commit transactions, or anything like that. You're just being told its time to yield to the scheduler, and if you obey it is exactly the same situation that in a normal preemptive multitasking system would just happen automatically, without warning, unpredictably, possibly between literally any two machine instructions. But incidentally, in a lot of situations, this would probably make it easier to set up systems where you can have enough time to do those things, and fewer possible ways for those things to be interrupted or delayed or half-finished.

So we all gain the profound benefit of being able to pick or at least see where in our code concurrency can slide in and change the state of the world out from under us or give us an out-of-band signal like a cancellation.

And the price is that those of us who write low-level code which does nothing but raw CPU operations for longer than the time slot our process gets have to add an explicit `yield_to_the_scheduler()` call - and if it really really doesn't matter, then just spam it in enough places to be safe. Which is fine because we just established that it's going to be nearly zero-overhead unless you actually have to yield to the scheduler anyway.

Notably, some operating systems already have everything in place to do this. Linux, for example, writes the current time into an address which the process can read and knows about, so the process doesn't need to pay system call context-switching overhead every time it needs the time. In fact, one possible idea to explore for improving my extremely minimal suggestion is that instead of having the memory location work as a boolean, have it contain a deadline.

Beyond that, the structured concurrency people have basically figured out the big picture of how most of this looks for most code - you have operations which are explicitly points where something else could be scheduled or you could be cancelled. For simplicity and human friendliness you probably combine those two concepts together. When we restrict ourselves to languages and primitives where each operation is either explicitly a place where multitasking can be relevant to or intrude on our logic, or a place where there are definitely no relevant concurrency concerns, we can deal with concurrency better.

Exhausting Nuance

There is only one tricky part here. The reason that preemptive multitasking is so useful is that not all concurrency is equally relevant to whatever you're doing. Most of the time, there are specific changes to the state of the world which matter to our logic, and all other changes which might happen don't matter.

Preemptive multitasking kinda takes the gamble that most systems are heavily concurrent but most parts have no reason to care about what the other parts are doing. They are not obviously harmed by the fact that anything could happen between or during any operation they do, because nothing that could happen matters, and so those programs strictly benefit from magical invasive multitasking permeating them with an infinity of possible preemptions.

For example, a typical `sed` invocation which reads from standard input and writes to standard output doesn't care about anything. In between a bunch of pure CPU operations on memory, it will read and it will write, and either those operations succeed, or one of those operations fails and it tries to call another write to standard error with an error message, and then no matter what happens, it will try to exit. Files on the system can change and it doesn't care. If the file it was reading from is truncated while `sed` was reading it, to `sed` it's no different than as if that file always ended there. It could get frozen with a SIGSTOP and eternities could pass, the file it was reading from could get overwritten, and when resumed it would just read from the offset it left off, no different than as if that file always had those contents back when `sed` started. The file it is writing to could be overwritten many times, and `sed` doesn't care - it just writes, and either it's writing in ”append" mode, or it's writing at whatever offset it is currently pointing at and maybe it wins because it's the last write or maybe it gets overwritten and it doesn't notice. `sed` could be started on Linux, have a debugger attached to it, its entire memory could be dynamically copied into another dummy process frozen with a debugger attached, possibly on another computer running a different OS with a compatibility layer for Linux, and then it can be resumed, and it doesn't care.

Notably, in some of those cases, the program which called `sed` to do a specific job probably does care a lot about some of those possibilities.

I, and to some extent structured concurrency, takes a somewhat reductionistic view that conflates all concurrency together. You do an operation and it's either asynchronous or not. You run an asynchronous operation, and anything else that's asynchronous might happen. And in structured concurrency you are never ever allowed to ignore that something is concurrent. You have no choice but to write code which is aware of all scheduling and cancellation points which it is subject to.

Maybe that's fine. Maybe...

everyone should be forced to be aware when they are doing an operation during which anything could asynchronously change,

all code which does too much should be forced to do an asynchronous yield to the scheduler every once in a while,

because these two requirements together would pressure code to cleanly split its pure logic from it impure logic, and to split its pure logic into small chunks of work which the caller can call individually.

This feels onerous to me, but I also suspect that for most problems, the best solution probably naturally meets these requirements. Possibly for all problems. At least for a sufficiently thorough definition of "best", which includes things like "made up of piece of code which are small, composable, reusable, and easy to test, easy to validate and audit, easy to understand in isolation, easy to combine, and easy to change" and "robust against all sorts of real-world problems, including edge cases".

But,

notably my definition of "best" does not include practical things like "could be created or maybe even fully appreciated or maybe even used correctly by a typical fungible software developer, or maybe even by any minds who can actually reliably get things done instead of getting stuck for entire days thinking about the design of everything", and

Back when #! behavior was first implemented in UNIX, they probably should have done argument pass-through 100% transparently, including the zeroth argument in the list of arguments that the shell script interpreter gets. No, not the resolved file path of that script. I mean the actual zeroth argument, the exact string at index zero of the `argv` argument to the `execve` system call.

It would've been nice if there was some standard way to pass the actual zeroth argument, as specified by the caller of the script, to the interpreter, and then for the interpreter to pass it through to the script.

The second part of that is easy: it's already normal for interpreters to expose a zeroth argument to script code - it's just the resolved script file path instead of the program name as invoked or whatever else the caller put in the zeroth argument. Could've just put that in, and exposed the script name in a separate non-argument way.

The first part is the harder part. If you just require that all script interpreter calls look like

foo script.foo arg0 arg1 arg2 ...

then that's bad for the common case. In many situations a default zeroth argument can be reasonably inferred. Human users typing commands do not normally think of zeroth arguments as a thing at all, let alone as a thing distinct from what it normally contains (the invoked program name). So ideally the system would pass the zeroth argument to the interpreter in some other way. Perhaps with an optional flag like `--arg0`, or in an environment variable like `ARG0`, or maybe someone can think of an even better way.

Meanwhile, compiled executables have the opposite problem: on many systems, they literally cannot know the actual resolved file path to themselves - they can only know their zeroth argument. At best they can hope that the zeroth argument will let them infer their file name. They can pray that the zeroth argument, and maybe an environment variable like PATH, will let them infer their location on disk. But the zeroth argument can "lie", because it can be set to anything.

It would have been nice if there was some standard way for compiled executables to learn the actual file path with which they were invoked - the same and only information that scripts inevitably get in their zeroth argument.