Easy Multiprogramming
The Join object is simple but it was hard to invent and remains hard to understand.
Yet it often provides simple multiprogramming with minimal disruption of code design and yields functionality referred to in Linux as “kernel threads”.
This page uses Keykos jargon and assumes knowledge of domain states.
A program P has come to the point where two bodies of work, W0 and W1, lie ahead and their inputs are at hand.
They will each produce results which are to be combined towards some greater end.
They each take enough time to warrant design care.
They do not unduly compete for the same resource.
We describe the solution to this symmetric problem asymmetrically.
A pre allocated JOIN object j is available and holds no message.
P holds J which is a start key to j.
P calls J with order 0 and gets a return key R to j.
j is now waiting.
P forks another domain written to be called and designed to perform W1.
The message sent by the fork includes the initial data for W1 and includes R as the return key.
P proceeds itself to perform W0.
(It may do this by calling yet another domain; but this is irrelevant.)
When W0 is finished P calls J again with order 1.
There are two cases that P need not distinguish:
- W1 has finished first and j already holds W1’s results which are immediately returned to P leaving j in the available state,
- W0 has finished first and j will be busy.
P will stall until W1 finishes and delivers its results to P via j.
In either case j is back in the available state and P has the results of both W0 and W1.
Q.E.D.
When P calls J with order 0, j calls the return key that was included in the message.
That creates the return key to j and delivers it P.
When W1 returns to R with its results, j grabs hold of the keys and 20 bytes of data and becomes available by returning to DK(0).
When P calls J with order 1, j returns the held keys and the data.
Never have I worked so hard inventing a 10 instruction program.
The limit of 20 characters arose from accepting the string in the registers.
j’s whole program has no stores to memory and j’s state is entirely in registers.
j’s behavior is defined by a program of about 10 commands in a single, shared RO page which comprised j’s entire address space.
This note shows how to get a very similar functionality from Promises in JavaScript.
Promises are somewhat more heavyweight for they give a name to a value that has not yet been produced.
Promises generally operate at a higher level.
The rules for domain interactions were designed to at least do common patterns efficiently while hewing to space accountability and exclusion necessary for servers.
Hacks such as the above were unexpected benefits.