Linda Meets Unix

Notes on "Linda Meets Unix",  Wm Leler, IEEE Computer, February 1990

This article is behind a paywall. I have a copy but cannot share it publicly. I'll provide some notes here and link to open access articles that fill in some of the details. I can dig in deeper if you leave a note in the comments.

Some people may know Wm from his PhD research on implementing constraints in the Bertrand programming language. (Published as "Constraint Programming Languages: Their Specification and Generation", Addison-Wesley, 1988) Wm later worked a couple miles down the street from me at Tektronix. More recently he worked on Flutter and Dart at Google. Now he's somewhere between Portland and the Puget Sound area. https://leler.com/wm/

When Wm authored this article he was at a Portland startup called Cogent Research. The product was a Transputer-based network of workstations. See more about the hardware. The article "Linda Meets Unix" describes the operating system, especially the use of "Kernel Linda" which is a pared-down implementation of Linda and tuple spaces. The aim of Kernel Linda is to be applicable to systems programming.

The article describes shared-memory multiprocessing, message-passing multiprocessing, and the Linda coordination model which is considered "generative" and can be used to approximate either shared-memory or message-passing, as well as a range of coordination patterns.

The operating system described in this article is QIX ("quicks").

To the user, QIX appears almost identical to Unix but, below the surface, it is considerably different. In terms of existing versions of Unix, QIX is most like Mach, except that Mach is based on a message-passing model, while QIX uses Kernel Linda. Like Mach, QIX has a small operating system kernel that is replicated on each processor.

Each process in QIX has a tuple space that provides the "global" environment for that process. That tuple space is the only means of communication between the process and the rest of the system. A QIX process can be lightweight with few entries in the environment tuple space. A Unix-compatible process has a more complete Unix environment in its tuple space.

All processes communicate by reading a "Services" entry from the tuple space. The value is another tuple space of all the external services available to that process. For example:

• File: the file system
• Pipe: Unix pipe service
• TTY: serial ports
• Execute: the execution service
• Console: the system error console
• PIX: the parallel interactive executive
• Graphics: the graphics server
• Window: terminal emulator windows
• FTP: file transfer service
• Tape: file backup
• Null: the null device (like/dev/null)

A QIX process can communicate with services directly using Linda operations. Unix-compatible system calls are implemented using these Linda operations since those operations are the lowest-level means for a process to communicate with the rest of the system. One advantage of the indirection and generative nature of Linda is that services can be customized, replicated, and distributed without affecting the behavior of the communication.

Tuple spaces form a name-space of sorts on a per-process basis. This has some similarities with the Plan 9 OS "everything is a customizable file system" philosophy.

The following code creates a new process from a code block on disk and communicates with that process using an environment tuple space that consists of just two keys ("x" and "y"). The result of the process is brought back into the original process via a third key ("z") the tuple space. The original process waits for the result via the Linda blocking operation called "in".

// the new environment dictionary

Val new_env = createdict();

// the value of x is the integer 5

new_env.out("x", (Val) 5);

// the value of y is the integer 20

new_env.out("y", (Val) 20);

// read the executable file from disk

Val proc = createblockfromfile("foo");

// create a new process

int pid = new_env.execute(proc);

// collect results

Val result;

// read the value of z

new_env.in("z", result);

printf("z = %d", (int) result);

 The code for corresponding communication in the new process:

void main()
{
  // access my environment
  Val env = environment(); 

  Val x, y;
  // read the value of x and y
  env.rd("x", x);
  env.rd("y", y); 

  int z = (int) x + (int) y;

  // set the value of z
  env.out("z", (Val) z);
}

The article goes on to illustrate the use of Linda to implement flow control, dynamic load balancing, and server farms. One of the most interesting aspects of QIX is PIX, a parallel, interactive Postscript interpreter implementing the Sun NeWS window system. 

The original implementation of NeWS implements "green threads" and coordination within the Unix process applies a combination of shared memory with mutexes and message passing. PIX is a true parallel program with coordination using Linda operations. 

QIX provides a big lesson for today by illustrating how an innovative substrate can be used to provide an all new operating environment while maintaining a significant level of compatibility with the current world.