KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services

When I was but a wee computer science student at New Mexico Tech, a graduate student in OS handed me an inch-thick print-out and told me that if I was really interested in operating systems, I had to read this. It was something about a completely lock-free operating system optimized using run-time code generation, written from scratch in assembly running on a homemade two-CPU SMP with a two-word compare-and-swap instruction - you know, nothing fancy. The print-out I was holding was Alexia Massalin's PhD thesis, Synthesis: An Efficient Implementation of Fundamental Operating Systems Services (html version here). Dutifully, I read the entire 158 pages. At the end, I realized that I understood not a word of it, right up to and including the cartoon of a koala saying "QUA!" at the end. Okay, I exaggerate - lock-free algorithms had been a hobby of mine for the previous few months - but the main point I came away with was that there was a lot of cool stuff in operating systems that I had yet to learn.

Every year or two after that, I'd pick up my now bedraggled copy of "Synthesis" and reread it, and every time I would understand a little bit more. First came the lock-free algorithms, then the run-time code generation, then quajects. The individual techniques were not always new in and of themselves, but in Synthesis they were developed, elaborated, and implemented throughout a fully functioning UNIX-style operating system. I still don't understand all of Synthesis, but I understand enough now to realize that my grad student friend was right: anyone really interested in operating systems should read this thesis.

Run-time code generation

The name "Synthesis" comes from run-time code generation - code synthesis - used to optimize and re-optimize kernel routines in response to changing conditions. The concept of optimizing code during run-time is by now familiar to many programmers in part from Transmeta's processor-level code optimization, used to lower power consumption (and many programmers are familiar with Transmeta as the one-time employer of Linus Torvalds.)

Run-time code generation in Synthesis begins with some level of compile-time optimization, optimizations that will be efficient regardless of the run-time environment. The result can thought of as a template for the final code, with "holes" where the run-time data will go. The run-time code generation then takes advantage of data-dependent optimizations. For example, if the code evaluates A * B, and at run-time we discover that B is always 1, then we can generate more efficient code that skips the multiplication step and run that code instead of the original. Fully optimized versions of the code pre-computed for common data values can be simply swapped in without any further run-time computation. Another example from the thesis:

Run-time code generation in Synthesis is a fusion of compile-time and run-time optimizations in which useful code templates are created at compile time that can later be optimized simply and cleanly at run time.

Quajects

Understanding run-time code generation is a prerequisite for understanding quajects, the basic unit out of which the Synthesis kernel is constructed. Quajects are almost but not quite entirely unlike objects. Like objects, quajects come in types - queue quaject, thread quaject, buffer quaject - and encapsulate all the data associated with the quaject. Unlike objects, which contain pointers to functions implementing their methods, quajects contain the code implementing their methods directly. That's right - the actual executable instructions are stored inside the data structure of the quaject, with the code nestled up against the data it will operate on. In cases where the code is too large to fit in the quaject, the code jumps out to the rest of the method located elsewhere in memory. The code implementing the methods is created by filling in pre-compiled templates and can be self-modifying as well.

Quajects interact with other quajects via a direct and simple system of cross-quaject calls: callentries, callouts, and callbacks. The user of quaject invokes callentries in the quaject, which implement that quaject's methods. Usually the callentry returns back to the caller as normal, but in exceptional situations the quaject will invoke a method in the caller's quaject - a callback. Callouts are places where a quaject invokes some other quaject's callentries.

Synthesis implements a basic set of quajects - thread, queue, buffer, clock, etc. - and builds higher-level structures by combining lower-level quajects. For example, a UNIX process is constructed out of a thread quaject, a memory quaject, and some I/O quajects.

As an example, let's look at the queue quaject's interface. A queue has two callentries, queue_put and queue_get. These are invoked by another quaject wanting to add or remove entries to and from the queue. The queue quaject also has four callbacks into the caller's quaject, queue_full, queue_full-1, queue_empty, and queue_empty-1. When a caller invokes the queue_put method and the queue is full, the queue quaject invokes the queue_full callback in the caller's quaject. From the thesis:

The queue_full-1 method is executed when a queue has transitioned from full to not full, queue_empty when the queue doesn't contain anything, and queue_empty-1 when the queue transitions from empty to not empty. With these six callentries and callbacks, a queue is implemented in a generic, extensible, yet incredibly efficient manner.

Pretty cool stuff, huh? But wait, there's more!

Optimistic lock-free synchronization

Most modern operating systems use a combination of interrupt disabling and locks to synchronize access to shared data structures and guarantee single-threaded execution of critical sections in general. The most popular synchronization primitive in Linux is the spinlock, implemented with the nearly universal test-and-set-bit atomic operation. When one thread attempts to acquire the spinlock guarding some critical section, it busy-waits, repeatedly trying to acquire the spinlock until it succeeds.

Synchronization based on locks works well enough but it has several problems: contention, deadlock, and priority inversion. Each of these problems can be (and is) worked around by following strict rules: keep the critical section short, always acquire locks in the same order, and implement various more-or-less complex methods of priority inheritance. Defining, implementing, and following these rules is non-trivial and a source of a lot of the pain involved in writing code for modern operating systems.

To address these problems, Maurice Herlihy proposed a system of lock-free synchronization using an atomic compare-and-swap instruction. Compare-and-swap takes the address of a word, the previous value of the word, and the desired new value of the word. It swaps the previous and new values of the word if and only if the previous value is the same as the current value. The bare compare-and-swap instruction allows atomic updates of single pointers. To atomically switch between larger data structures, a new copy of the data structure is created, updated with the changes, and the addresses of the two data structures swapped. If the compare-and-swap fails because some other thread has updated the value, the operation is retried until it succeeds.

Lock-free synchronization eliminates deadlocks, the need for strict lock ordering rules, and priority inversion (contention on the compare-and-swap instruction itself is still a concern, but rarely observed in the wild). The main drawback of Herlihy's algorithms is that they require a lot of data copying for anything more complex than swapping two addresses, making the total cost of the operation greater than the cost of locking algorithms in many cases. Massalin took advantage of the two-word compare-and-swap instruction available in the Motorola 68030 and expanded on Herlihy's work to implement lock-free and copy-free synchronization of queues, stacks, and linked lists. She then took a novel approach: Rather than choose a general synchronization technique (like spinlocks) and apply it to arbitrary data structures and operations, instead build the operating system out of data structures simple enough to be updated in an efficient lock-free manner.

Synthesis is actually even cooler than lock-free: Given the system of quajects, code synthesis, and callbacks, operations on data structures can be completely synchronization-free in common situations. For example, a single-producer, single-consumer queue can be updated concurrently without any kind of synchronization as long as the queue is non-empty, since each thread operates on only one end of the queue. When the callback for queue empty happens, the code to operate on the queue is switched to use the lock-free synchronization code. When the quaject's queue-not-empty callback is invoked, the quajects switch back to the synchronization-free code. (This specific algorithm is not, to my knowledge, described in detail in the thesis, but was imparted to me some months ago by Dr. Massalin herself at one of those wild late-night kernel programmer parties, so take my description with a grain of salt.)

The approach to synchronization in Synthesis is summarized in the following quote:

The last two points will sound familiar if you're aware of Paul McKenney's read-copy-update (RCU) algorithm. In Synthesis, thread structures to be deleted or removed from the run queue are marked as such, and then actually deleted or removed by the scheduler thread during normal traversal of the run queue. In RCU, the reference to a list entry is removed from the linked list while holding the list lock, but the removed list entry is not actually freed until it can be guaranteed that no reader is accessing that entry. In both cases, reads are synchronization-free, but deletes are separated into two phases, one that begins the operation in an efficient low-contention manner, and a second, deferred, synchronization-free phase to complete the operation. The two techniques are by no means the same, but share a similar philosophy.

Synthesis: Operating system of the future?

The design principles of Synthesis, while powerful and generic, still have some major drawbacks. The algorithms are difficult to understand and implement for regular human beings (or kernel programmers, for that matter). As Linux has demonstrated, making kernel development simple enough that a wide variety of people can contribute has some significant payoffs. Another drawback is that two-word compare-and-swap is, shall we say, not a common feature of modern processors. Lock-free synchronization can be achieved without this instruction, but it is far less efficient. In my opinion, reading this paper is valuable more for retraining the way your brain thinks about synchronization than for copying the exact algorithms. This thesis is especially valuable reading for people interested in low-latency or real-time response, since one of the explicit goals of Synthesis is support for real-time sound processing.

Finally, I want to note that Synthesis contains many more elegant ideas that I couldn't cover in even the most superficial detail - quaject-based user/kernel interface, per-process exception tables, scheduling based on I/O rates, etc., etc. And while the exact implementation details are fascinating, the thesis is also peppered with delightful koan-like statements about design patterns for operating systems. Any time you're feeling bored with operating systems, sit down and read a chapter of this thesis.

[ Valerie Henson is a Linux file systems consultant and proud recipient of a piggy-back ride from Dr. Alexia Massalin. ]

Ow, my brain hurts.  I'll stick to the occasional kernel recompile.

But I like those quaject callbacks I think it's more beautiful than doing exception throwing
and signal passing. But again maybe that's just my ignorance showing.. ;-)

It's definitely more elegant. It's more like the Emacs hooks-everywhere scheme than exception
handling, though.

(I've seen one program that approaches things in the same way as this does with its quaject
callbacks, and that's the ERC IRC client, which has a fairly conventional server core, but all
the actual processing is done by invoking hooks with names constructed from the type of the
server response; said hooks can then send messages back again, or whatever. Of course ERC
doesn't have all the *other* nifty stuff in Synthesis.)

(btw, isn't the cartoon at the end a picture of a quala, not a koala? --- sorry.)

I think you would need to come up with some new programming language syntax that encapsulates
the special conventions of quajects and the locking primitives (sort of how Occam encapsulates
the CSP-style synchronization primitives of the Transputer), doing all the bookkeeping and
self-modifying code invisibly for you. Without a higher-level language to write programs in
you presumably are left with hand-edited and fragile assembly-language code...

Ah, but with Synthesis, the kernel can recompile iself! :)

I'm not sure whether to thank you or curse you for posting this fascinating article (and
linking to the thesis). I've been infected now. I'm not going to be able to write hardly
anything in future without borrowing ideas from this.

I shall have to spread the pain by telling everyone I have ever met about it. :)

The approaches described here seem to completely ignore the fact that the increased amount of
code would result in increased cache misses, possibly penalizing the program more than
benefiting it. Instead of using the special-case function f(p) for p == 1, it might be faster
to just call the generic one, just because it's in the cache already. Cache is everything
nowadays, so the algorithms should be tailored for cache efficiency. Having more code hardly
helps here.

Furthermore, it seems to be unclear when to optimize and for what data — the time spent
creating new code, the memory consumed to hold it, and, once again, the cache penalties
resulting from having it executed once in a while should all be worth it. The whole approach
feels like it can be simplified to the idea of 'having a compiler inside of the running
program used to recompile its parts in runtime', but somehow I fail to see too many benefits
in that. To my understanding, if one wants to optimize, the better way to do is to think more
about caches/cpus interactions. The "network channels" apporach is one nice example of that.

More code does not imply slower.  Think bubble sort vs. quicksort.

Besides, it sounds like the recompilations only happen at exceptional times.  I highly doubt
that they result in the sort of cache thrashing that you imply.

The bubble sort vs. quicksort would be an incorrect analogy. The idea here is to inject
several optimized versions of the same code. My arguing was that one generic version might
perform better than a multitude of specialized copies of the same code.

Yes. Especially as today's CPUs move towards annotating cache lines and doing certain
optimizations of the generic functions by observing their usage and annotating specific
instructions. Creating _more_ code goes into the opposite direction.

I played around with lock-free algorithms a year ago and came away with a rather dim view of
them.  It's easy to write a provably correct lock-free queue when you assume infinite memory
(something that most papers seem to do).  It's a lot messier when you need to ensure the safe
disposal of list items when you're done with them.

You mention he's using an atomic CAS.  Does he explicitly solve CAS's ABBA problem?  It's
easily solved if you assume infinite memory of course.  If you're on a real-world system, if
you're not careful, you can easily open yourself up to situations where CAS assures you that a
value is unchanged when in reality you lost out a long time ago and the ring has just wrapped.
(yes, it's not hard to solve if you're watching for it, but always having to worry about this
sort of subtlety is what makes working lock-free such a pain)

After realizing they were anything but maintainable, I chucked lock-free algorithms on my
shelf of stuff that is academically fascinating but unrealistic for the real world.  Should I
take them back down and re-examine them?

> When the callback for queue empty happens, the code to operate on the queue is switched to
use the lock-free synchronization code. When the quaject's queue-not-empty callback is
invoked, the quajects switch back to the synchronization-free code.

Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

> After realizing they were anything but maintainable, I chucked lock-free algorithms on my
> shelf of stuff that is academically fascinating but unrealistic for the real world.  Should
I
> take them back down and re-examine them?

My personal opinion is that lock-free algorithms are not a good generic synchronization
technique, and are definitely very very complex and difficult to understand.  However, in
certain specific cases, lock-free can be simple, elegant, and a huge performance advantage
over traditional approaches.  It's much like RCU - you wouldn't want to use RCU for every
synchronization problem, but when it comes to highly-shared read-mostly data in the hot path
(e.g., the dcache), it's worth the trouble.

It's kind of like my advice on choosing a file system: Use ext3 unless it's not
fast/big/whatever enough for you, in which case use XFS.  My recommendation is use locks
unless they have too much contention/complexity/whatever, in which case look into lock-free.

> > When the callback for queue empty happens, the code to operate on the queue is switched to
> > use the lock-free synchronization code. When the quaject's queue-not-empty callback is
> > invoked, the quajects switch back to the synchronization-free code.
> 
> Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

I know... The whole damn dissertation is like that.

>> When the callback for queue empty happens, the code to operate on the queue is switched to
use the lock-free synchronization code. When the quaject's queue-not-empty callback is
invoked, the quajects switch back to the synchronization-free code.
>
>Whoa...  that ran shivers down my spine.  What an outrageously cool idea.

Uh? I don't think that it's a particulary original idea..
But implementing this efficiently on the other hand, this seems quite hard to do!
I have some difficulties downloading the PDF, so I cannot read the paper yet..

Thanks for this very insightful writeup, now I have yet another thing to read and become
immersed in instead of doing real work :P

Having this write-up, to say nothing of an online copy of Massalin's dissertation, would have
saved me much time back when I was doing my own dissertation.  ;-)  Good to see both now
available!!!

One of the key strengths of Massalin's work is the focus on determining what techniques work
well in given situations, and then matching up techniques with the corresponding situations.
"Use the right tool for the job!"

Although lock-free techniques can be quite valuable for situations requiring real-time
response, as can other non-blocking-synchronization (NBS) techniques, these techniques are not
a panacea.  NBS algorithms rely heavily on hardware arbitration, which is usually unaware of
process priorities.  This can result in priority-inversion-like effects when the hardware
gives the contended cache line to the low-priority process.

> NBS algorithms rely heavily on hardware arbitration, which is usually
> unaware of process priorities.

There are no priorities and scheduler is I/O rate-based, PLL-managed.
On pdf.page 139 (123) find some ideas for hardware and open yor eyes
(pdf.page 142 (126).

> This can result in priority-inversion-like effects when the hardware
> gives the contended cache line to the low-priority process.

Oh, read whole dissertation, please.
_____

Let's see, page 139:123...

Fully coherent instruction caches do exist on some systems.  Replicated registers for fast
interrupt handling were present in some 8080-based CPUs back in the late 70s and early 80s,
but have fallen out of favor, though one might get the same effect on modern multithreaded
hardware by reserving one thread to process interrupts on behalf of the other, but not sure
that this would be worthwhile.  Double-compare-and-swap is indeed useful, but doesn't exist on
the systems I have access to, despite its appearing in the 68K line quite some time ago.
Large caches, large cacheline sizes, and very high memory bandwidths have reduced the urgency
of partial-register saving, and again, in some cases you could assign processes to hardware
threads -- but perhaps this will become more compelling in the future.  Some CPUs have vector
operations that do some of the multi-byte operations (e.g., SSE, 3DNow, Altivec, ...), and
perhaps compilers will become more aggressive about implementing them.  Some of the fancier
bitwise operations are indeed useful in some contexts, so who knows.

But I do apologize for my extreme bigotry in favor of hardware features that I can use today
across a wide variety of CPU types.  ;-)

The operating systems I work with -do- have priorities, so I don't get to ignore them.
Perhaps more sophisticated scheduling policies will come into vogue.  There are certainly
people working on this.  In any case, stock Linux running on commodity microprocessors does
context switches orders of magnitude faster than the one-millisecond figure called out on page
142:126 -- old-style Moore's law at work.

Hardware cache-coherence protocols coupled with high software memory contention really can
result in priority-inversion-like effects.  I have seen this, logic analyzer and everything.
Would you care to outline your objections in more detail?

Your solution is not as ugly as another I've seen in C++ where the programmer used placement
new to reconstruct the object with a different derived type (but the same base type) in-place.

Now, that was scary.

Insane?

Oh.

So, er, I should be ashamed that I did almost exactly that (via a custom 
allocator layered atop big mmap()ed hunks) in C about a year ago? (Well, 
it was more like a twisted sort of RCU: I'd construct a new instance that 
was a copy of the old one with a zero reference count, then changing 
pointers in the new instance's VMT-analogue, translating the object's data 
into a new representation at the same time. The old instance got 
reference-zapped when nobody was executing methods via those pointers 
anymore.)

(yes, there were pressing reasons. It was a bundle of fun, as well. :) )

As a matter of fact eight-year developer of PowerPC Linux port Cort Dougan has citations of
Massalin's work in his research and application publications.

Bottom line, as far as i can see, can be read here:

Cort Dougan: Good Programmers are not Lazy. unpublished draft.
http://hq.fsmlabs.com/~cort/papers/lazy/lazy.nohead.html

A must read.

Ouch, fsmlabs and software patents? Microsoft has patent on double-click, so what? Now Novel,
RH and others have all that protecting-patents dance. Thus, sw patents in this case are
irrelevant. About sw freedom and money, please read the article.