>Synthesis: An Efficient Implementation of Fundamental Operating System Services
>This dissertation shows that operating systems can provide fundamental services
an order of magnitude more efficiently than traditional implementations. It describes the
implementation of a new operating system kernel, Synthesis, that achieves this level of
performance.
>The Synthesis kernel combines several new techniques to provide high performance
without sacrificing the expressive power or security of the system. The new ideas include:
>- Run-time code synthesis -- a systematic way of creating executable machine code
at runtime to optimize frequently-used kernel routines | queues, buffers, context
switchers, interrupt handlers, and system call dispatchers | for specific situations,
greatly reducing their execution time.
>- Fine-grain scheduling -- a new process-scheduling technique based on the idea of
feedback that performs frequent scheduling actions and policy adjustments (at submillisecond intervals) resulting in an adaptive, self-tuning system that can support
real-time data streams.
>- Lock-free optimistic synchronization is shown to be a practical, efficient alternative to
lock-based synchronization methods for the implementation of multiprocessor operating system kernels.
>- An extensible kernel design that provides for simple expansion to support new kernel
services and hardware devices while allowing a tight coupling between the kernel and
the applications, blurring the distinction between user and kernel services.
>The result is a significant performance improvement over traditional operating system implementations in addition to providing new services.
>Alexia Massalin’s 1992 PhD thesis has long been one of my favorites. It promotes the view that operating systems can be much more efficient than then-current operating systems via runtime code generation, lock-free synchronization, and fine-grained scheduling. In this piece we’ll only look at runtime code generation, which can be cleanly separated from the other aspects of this work.
Valerie Henson's commentary on the Synthesis kernel (2008) (lwn.net)
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 (formerly Henry) 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.
>Massalin's Synthesis kernel [10] stands out to me as another example that for me crosses the boundaries and is both outstanding engineering and art in challenging the ideas of how systems could be built in ways that make me look at it just as much because of the beauty of it as because of the practical ideas. (The main thing it brought was the idea of making the kernel adapt to its clients by generating custom code for system calls; to me it is art because it turned the idea of a kernel as something static on its head; and conceptually we're still just scraping the very surface of dynamic code generation in kernels that Massalin's thesis started playing with). There are many works like that, where the specific implementations are irrelevant - nobody uses the Synthesis kernel - but where the ideas are as important as any expressed in more overt or "intentional" art.
>ggm: It feels to me like if you can do runtime code call checks, and confirm which actual calls you make, then stripping the bits of libc and associated libraries out, being left with only the strictly required calls, and then by extension the syscalls, and then by extension the kernel elements, is actually possible a lot of the time. So, library -> reduced library -> reduced calls -> reduced syscalls -> reduced kernel state is a sequence or set or something, of applied minimisations which can be done, if you can predict all the call paths in your code and their dependencies.
>NelsonMinar: That sounds a little like the ideas in the Synthesis kernel, the idea of the kernel JIT-compiling itself to optimize your code path.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29....
>Synthesis: An Efficient Implementation of Fundamental Operating System Services
>This dissertation shows that operating systems can provide fundamental services an order of magnitude more efficiently than traditional implementations. It describes the implementation of a new operating system kernel, Synthesis, that achieves this level of performance.
>The Synthesis kernel combines several new techniques to provide high performance without sacrificing the expressive power or security of the system. The new ideas include:
>- Run-time code synthesis -- a systematic way of creating executable machine code at runtime to optimize frequently-used kernel routines | queues, buffers, context switchers, interrupt handlers, and system call dispatchers | for specific situations, greatly reducing their execution time.
>- Fine-grain scheduling -- a new process-scheduling technique based on the idea of feedback that performs frequent scheduling actions and policy adjustments (at submillisecond intervals) resulting in an adaptive, self-tuning system that can support real-time data streams.
>- Lock-free optimistic synchronization is shown to be a practical, efficient alternative to lock-based synchronization methods for the implementation of multiprocessor operating system kernels.
>- An extensible kernel design that provides for simple expansion to support new kernel services and hardware devices while allowing a tight coupling between the kernel and the applications, blurring the distinction between user and kernel services.
>The result is a significant performance improvement over traditional operating system implementations in addition to providing new services.
Previous discussion on HN:
The Synthesis Kernel (1988) [pdf] (usenix.org)
https://news.ycombinator.com/item?id=15076642
https://www.usenix.org/legacy/publications/compsystems/1988/...
It’s Time for a Modern Synthesis Kernel (regehr.org)
https://news.ycombinator.com/item?id=20337231
https://blog.regehr.org/archives/1676
>Alexia Massalin’s 1992 PhD thesis has long been one of my favorites. It promotes the view that operating systems can be much more efficient than then-current operating systems via runtime code generation, lock-free synchronization, and fine-grained scheduling. In this piece we’ll only look at runtime code generation, which can be cleanly separated from the other aspects of this work.
Valerie Henson's commentary on the Synthesis kernel (2008) (lwn.net)
https://news.ycombinator.com/item?id=10441995
https://lwn.net/Articles/270081/
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 (formerly Henry) 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.
Other interesting mentions:
https://news.ycombinator.com/item?id=19598385
>Massalin's Synthesis kernel [10] stands out to me as another example that for me crosses the boundaries and is both outstanding engineering and art in challenging the ideas of how systems could be built in ways that make me look at it just as much because of the beauty of it as because of the practical ideas. (The main thing it brought was the idea of making the kernel adapt to its clients by generating custom code for system calls; to me it is art because it turned the idea of a kernel as something static on its head; and conceptually we're still just scraping the very surface of dynamic code generation in kernels that Massalin's thesis started playing with). There are many works like that, where the specific implementations are irrelevant - nobody uses the Synthesis kernel - but where the ideas are as important as any expressed in more overt or "intentional" art.
https://news.ycombinator.com/item?id=20507155
>ggm: It feels to me like if you can do runtime code call checks, and confirm which actual calls you make, then stripping the bits of libc and associated libraries out, being left with only the strictly required calls, and then by extension the syscalls, and then by extension the kernel elements, is actually possible a lot of the time. So, library -> reduced library -> reduced calls -> reduced syscalls -> reduced kernel state is a sequence or set or something, of applied minimisations which can be done, if you can predict all the call paths in your code and their dependencies.
>NelsonMinar: That sounds a little like the ideas in the Synthesis kernel, the idea of the kernel JIT-compiling itself to optimize your code path.