Synthesis Os

(From FuturistProgramming.) "Synthesis: An Efficient Implementation of Fundamental Operating System Services" is a PhD thesis by Henry Massalin, 1992.

Operating System services provided "an order of magnitude" faster than Unix, by... It generates code at run-time, optimized for the services you happen to be using at the time. When you "open" different services, it generates new code to handle that. LockFree? concurrency management eliminates the many performance, deadlocking, and PriorityInversion problems caused by LockBasedSynchronization.

The best URL I can find is ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz although it does not accept connections from hosts without name servers (like mine). (Please give a better link if you can find one.)

For people having trouble accessing their FTP server, I've copied the file to http://www.sluug.org/~jeff/foreign/cucs-039-92.ps.gz (Unfortunately, our local Unix user group server is not the most reliable thing on the planet. ;-) -- JeffGrigg

It's on CiteSeer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4871
I read the Synthesis Thesis paper; it's excellent. It isn't really a self-modifying program, it's more like a JustInTimeCompiler. As I understand it, it is based around a fairly general PartialEvaluation system similar to the "currying" in functional languages (see CurryingSchonfinkelling).

For example, in a normal OS when you open a file you get a handle which you pass to the Read function. In Synthesis, instead of a handle you get a version of the read function that is specialised for your particular file. It was compiled in full knowledge of, eg, where all the buffers are. You don't need to pass it any further arguments. It doesn't need to do any general checks (for example, to ensure the handle belongs to a readable file) - all those are optimised out. -- DaveHarris
[Before reading the paper I said...] Might be interesting to read the Synthesis Thesis paper. The part about "you get a version of the read function that is specialized for your particular file" sounds remarkably like what Microsoft is doing with COM: You get an object with methods that conform to standard interfaces, but which have an implementation that depends on the particular object. -- JeffGrigg

The point is not so much the FactoryPattern, as that the code is generated at runtime. It makes it faster. For example, a load-immediate instruction will be faster than loading a variable through N levels of indirection. Expressions like A*B are more likely to have A or B (or both) known, allowing simpler code. It's PartialEvaluation, basically; the root of all optimisation. The longer you postpone code generation, the more knowledge you have and the better job you can do. -- DaveHarris

Just finished reading the paper. Most interesting. So it creates instances that are a mix of state (data) and generated code. There's no need to pass the "object pointer" to methods as a parameter, as the current program counter identifies both the method to invoke and the instance it refers to.

I think Henry Massalin hit on something important there: Maintainability is an attribute of the source code, not the executing machine code. By recognizing that program instructions can be manipulated as data (as any optimizing compiler will do), one can break through some serious conceptual barriers. -- JeffGrigg

HigherOrderProgramming? concepts directly into computer operating systems design, marvelous. I do want to add, that machine code may some times need human inspection, at least while developing operating systems. Traditional low level errata [KillerBug?] that are common before a computer is running a (sufficiently) stable operating system.


A related idea is described on RethinkingCompilerDesign. Anyone interested in actually implementing it?? -- JamesCrook
Calton Pu used to work on a related project, Synthetix, at the OregonGraduateInstitute. He is now at Georgia Tech - http://www.cc.gatech.edu/~calton and working on the Infosphere project: http://www.cc.gatech.edu/projects/infosphere/ -- Galen Swint
A nice explanation of Synthesis is

KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services by Valerie Henson (February 20, 2008)

http://lwn.net/Articles/270081/

A must read is the Alexia Henry Massalin's preceding paper,

Superoptimizer -- A Look at the Smallest Program

http://www.cs.utexas.edu/users/lasr/shangri-la/reference/massalin87superoptimizer.pdf

and the Wikipedia Article on Alexia Henry Massalin is worth a peek too: http://en.wikipedia.org/wiki/Henry_Massalin

-- Chris Lent, I watched the Qua's happen, was carried, and have carried. Good memories. :-)


EditText of this page (last edited October 8, 2011) or FindPage with title or text search