Distributed Operating Systems and DSM
You have a rack of machines. The dream — old, beautiful, and mostly defeated — is that they should not
feel like a rack of machines. They should feel like one big computer: a single pool of
CPUs, one memory, one file system, one process space, where you launch a program and the operating system
transparently runs it wherever there is room, and it can touch any memory and any file as if everything
were local. This is the single-system-image (SSI) distributed operating system, and in
the 1980s it looked like the obvious future.
It is not how we build datacenters today. We build them out of a pile of ordinary machines, each running
its own boring Linux, glued together by middleware —
RPC,
message queues, Kubernetes — that runs above the OS, not inside it. This lesson is about that
beautiful defeat: the real distributed OSes (Amoeba, Sprite, Plan 9), the seductive-but-doomed idea of
distributed shared memory, why the transparent single-system dream lost to
clusters, and how — the twist — nearly every idea survived and won somewhere else.
Three attempts at one computer
The classic distributed OSes each attacked the dream from a different direction, and each left a durable
idea behind:
- Amoeba (Tanenbaum, VU Amsterdam) — a processor pool model: cores are a
shared commodity the OS hands out; you don't know or care which machine your process runs on.
Capability-based, RPC everywhere. The purest "the network is the computer" system.
- Sprite (Berkeley) — a Unix-compatible network OS famous for
process migration (move a running process to an idle workstation) and a
single shared network file system with aggressive caching + strict cache consistency.
- Plan 9 (Bell Labs, by the Unix team) — the most influential. Its radical bet:
everything is a file, and every resource — a remote CPU, a window, a network connection, a
process's memory — appears as a file in a per-process namespace, reachable over one protocol
(9P). You assemble your "computer" by mounting other machines' file trees into your
own namespace.
Notice the common move: take an OS abstraction you already trust locally — a process, a file — and stretch
it transparently across the network. The question is always the same: what breaks when "local"
silently becomes "remote"?
Distributed shared memory — the most seductive idea
Of all the stretches, the boldest is distributed shared memory (DSM): make the physical
memory of many machines look like one shared address space, so a program on any node can just read
and write \texttt{x} and the OS makes it coherent across the network — no
explicit messages, no RPC, just load and store. Ivy (Kai Li, 1986) showed how, and the
trick is gorgeous: reuse the paging hardware you already have.
Each shared page lives on some owner node. When a node touches a page it doesn't hold, its
MMU
raises an ordinary page fault — but instead of reading from a local disk, the fault
handler fetches the page from the owning node over the network. Reads can be replicated
(many read-only copies); a write must invalidate all other copies and take ownership — exactly the
invalidation protocol
of a cache-coherent multiprocessor, but with the "cache line" being a 4 KB page and the "bus" being an
Ethernet. Watch one read fault travel:
Where DSM hurts: false sharing at 4 KB, and the consistency tax
DSM is transparent, which is precisely its curse — the programmer cannot see the network cost hiding under
an innocent \texttt{x = x + 1}. Two problems dominate:
- False sharing, amplified. The coherence unit is a whole page (4 KB),
not a cache line (64 B). If two nodes update two different variables that happen to sit on the
same page, the page ping-pongs across the network on every write — a millisecond each way — even though
the variables never actually conflict. On a cache-coherent CPU false sharing wastes tens of nanoseconds;
on page-based DSM it wastes milliseconds. Same bug, five orders of magnitude worse.
- The consistency-model tax. Providing strict
sequential
consistency means every write may have to synchronise globally — brutal over a network. So
DSM systems (Munin, TreadMarks) invented relaxed models — release consistency,
lazy release consistency — that only reconcile memory at explicit \texttt{acquire}/
\texttt{release} (lock) points. Faster, but now the "transparent" shared
memory has a subtle contract the programmer must understand — so it was never really transparent
after all.
Page ownership, simulated
Model a single-writer/multiple-reader DSM page as a sequence of accesses from different nodes. A read by a
non-holder fetches a copy; a write invalidates every other copy and seizes ownership. Count the network
transfers — and watch two nodes write-fighting turn into a ping-pong.
// Single-writer / multiple-reader DSM for ONE page.
// reads add a read-only copy; a write invalidates all other copies and takes the (sole) writable copy.
type Access = { node: string; write: boolean };
let owner = "B"; // node B starts as the writable owner
let readers = new Set<string>(["B"]); // nodes holding a valid copy
let transfers = 0;
const trace: Access[] = [
{ node: "A", write: false }, // A reads -> fetch copy from owner
{ node: "C", write: false }, // C reads -> fetch copy
{ node: "A", write: true }, // A writes -> invalidate B,C ; A becomes owner
{ node: "B", write: true }, // B writes -> invalidate A ; B becomes owner (ping!)
{ node: "A", write: true }, // A writes -> invalidate B ; A becomes owner (pong!)
];
for (const a of trace) {
if (a.write) {
const invalidated = [...readers].filter((n) => n !== a.node);
transfers += invalidated.length + (readers.has(a.node) ? 0 : 1);
readers = new Set([a.node]);
owner = a.node;
console.log(`${a.node} WRITE -> invalidate [${invalidated.join(",") || "-"}], ${a.node} now sole owner`);
} else {
if (!readers.has(a.node)) { transfers++; readers.add(a.node); }
console.log(`${a.node} READ -> copies held by {${[...readers].sort().join(",")}}`);
}
}
console.log(`\ntotal network page transfers = ${transfers}`);
console.log("note: the A/B write-fight ping-pongs the page every time — that is false-sharing pain.");
Why the dream lost — and where every idea won anyway
Transparent single-system-image OSes and DSM never took over the datacenter. The reasons are sobering and
worth stating plainly, because they are a lesson about abstraction itself:
- The transparency was a lie the network could not sustain. Making remote look exactly
like local hides the one thing you most need to see: that a memory access might now cost a million times
more and can fail independently. Leaky abstraction over a lossy, partitionable network is a trap
(this is the heart of the
fallacies of
distributed computing).
- Fault isolation beat fault transparency. A cluster of independent machines has a
killer feature a single-system image lacks: when one node dies, the others don't. Explicit RPC +
stateless services + orchestration (Kubernetes) gives you scaling and resilience the SSI model fought.
- Commodity + middleware was cheaper and good enough. Google/Amazon-scale computing was
built on racks of cheap boxes and software that embraces partial failure, not an OS pretending
it away.
And yet — the ideas are everywhere, just moved up or sideways:
| Old distributed-OS idea | Where it lives now |
|---|
| Plan 9's "everything is a file" + per-process namespaces | Linux namespaces & bind mounts — the machinery under containers; \texttt{/proc}, \texttt{/sys}; the 9P protocol still shipping (WSL2, QEMU, Docker) |
| Sprite process migration | live VM/container migration; datacenter schedulers rebalancing load |
| Amoeba processor pool | cluster schedulers (Borg, Kubernetes, Mesos): you submit work, not a target machine |
| Distributed shared memory | RDMA (read remote memory in ~1 µs) and memory disaggregation — DSM's dream on hardware that finally makes it pay |
The single-system OS lost the battle and won the war: we didn't build one giant transparent computer, but
we plundered its ideas for the cluster we built instead. RDMA in particular is DSM reincarnated — remote
memory at microsecond, not millisecond, latency — which is why "the datacenter as a computer" is the theme
of this module's final lesson.
Plan 9 came from the very people who wrote Unix, and by almost every measure it is cleaner: one
protocol (9P) for all resources, genuinely composable per-process namespaces, no exceptions bolted on the
side. It should have won. It didn't — and the reason is one of computing's hardest laws:
incumbency beats elegance. By the time Plan 9 matured (early 1990s) Unix already had the
applications, the drivers, the users, and the momentum; "better, but incompatible, and you must rewrite
everything" is a losing pitch no matter how good the "better" is. So Plan 9 became the most influential OS
almost nobody runs: its ideas were quietly strip-mined into everyone else's systems —
\texttt{/proc}, UTF-8 (invented for Plan 9, by Thompson and Pike, on a diner
placemat), union mounts, namespaces — while the OS itself stayed a research curiosity. Elegance is
portable even when the system is not.
The tempting misread of DSM is "great, now I can ignore the network and just use shared variables." That is
exactly backwards. DSM does not remove the network cost; it conceals it behind ordinary
loads and stores, so you can no longer see where you are paying it. An explicit RPC at least
announces "this is a remote call, it is slow and can fail." A DSM \texttt{x = x + 1}
looks free but may trigger a 4 KB page fetch, an invalidation storm, or a false-sharing ping-pong — silently,
millions of times worse than the same line on one machine. The lesson generalises far beyond DSM: a leaky
abstraction that hides a cost gradient (local vs remote, cached vs uncached, memory vs disk) is dangerous
precisely because it is convenient. Transparency is not free; someone always pays the latency, and
if you can't see it, you can't fix it.