THE LISP MACHINE · HOW IT RUNS
What happens when a Lisp Machine boots, and how one processor then runs many things at once.
For readers who want more than what it is. Each part is read from MIT’s own sources: the Lisp Machine Manual, the microcode and the Lisp system’s files.
Four words recur on this page, each explained where it first appears: the band, a saved Lisp world; the stack group, one computation’s state; the wait function, how a process says what it waits for; and the sequence break, how the scheduler gets the processor back.
What is said here holds for the CADR and for QUUX; where the two differ, it says so.
01 / THE BOOT
Three programs run in turn: the boot PROM loads the microcode, the microcode brings back a Lisp world, and the microcode then enters one Lisp function, which does the rest.
At power-on, by the boot button, or from the keyboard: holding both Control keys and both Meta keys and pressing Rubout cold-boots a CADR, and Return in place of Rubout warm-boots it. The keyboard itself recognizes the keys and sends a boot code. The processor starts in its boot PROM; on QUUX, whose PROM has control store addresses of its own, a reset starts it there.
It tests the hardware a bit at a time — the ALU’s carries, the byte hardware, the scratch memories and the PDL buffer — because a fault found here is better than a world that boots wrong. Then it clears the processor’s memories and both levels of the map, so that their parity is good.
The disk names its current microcode partition: the CADR’s in a label in its first block, QUUX’s with an attribute bit in a GPT partition table. The partition is a series of sections — the microinstructions for the control store, the dispatch memory, a part of main memory, and the scratch memories — and the PROM loads each where it belongs. Then it jumps to location 6 of the new microcode, where both programs keep the same small loop, so the handover happens in the middle of it.
It reads the keyboard. A warm boot keeps the Lisp world already in virtual memory. A cold boot brings back a band: the microcode sizes main memory, finds the paging partition and the band on the disk, and sets up the map; QUUX’s microcode first asks which machine it runs on.
A band is a saved Lisp world, and loading one does not mean reading it into main memory. It is copied into the disk’s paging partition, which becomes the backing store of virtual memory; only the few pages that must always be in memory are read in, and everything else arrives later, a page at a time, when it is first touched.
The microcode copies a few values out of the band into its own registers, among them the function to start with, LISP-TOP-LEVEL. It builds one stack frame for that function by hand and falls into its main instruction loop. Nothing jumps to an address in the band: the first macroinstruction the machine executes is that function’s call to LISP-REINITIALIZE.
LISP-REINITIALIZE resets the system’s state and runs its lists of initializations. Among them the process system makes the scheduler and the initial process and turns on the clock’s sequence breaks, and the window system leaves the first Lisp Listener on the screen and selected.
It prints the herald: the site, which band is running, the physical and virtual memory, and the version of each system loaded. Then the initial process runs the Lisp Listener’s loop: it reads a Lisp form, evaluates it and prints the value, and waits for the next.
A warm boot takes the same path from the microcode’s start and enters the same function, which is why it keeps the world and loses what was on the stack; the process that was running is reset, or stopped so that it can be examined. MIT’s own comment on it: “WARM BOOTING IS STRONGLY DISCOURAGED.”
02 / MEMORY
Every Lisp object, the system’s and the user’s, is in one virtual address space, shared by every process. Main memory holds the part of it in use; the disk holds the rest.
A reference to memory goes through the map. On the CADR it turns a 24-bit virtual address into a 22-bit physical one in two levels, both in hardware, inside one microcycle; a page is 256 words, and the low eight bits of an address pass through it unchanged. An address the map has no entry for is refused, and the refusal is a page fault.
The microcode takes the fault. It looks the page up in the page hash table, a table in memory of the pages it knows. If the page is in main memory, it only loads the map again. If it is not, it finds a page frame to use — one that has not been used lately, if there is one — writes the page there out to the disk if it was changed, reads the wanted page in, and restarts the reference.
On QUUX a TLB stands in for the map: a miss walks a page table in main memory in hardware, over 32-bit virtual addresses and pages of 1024 words, and there is no page hash table (what QUUX changes).
The disk behind it is the paging partition, where the running Lisp world resides; the band was copied there at the cold boot. Saving a world with disk-save writes it back out into a band of its own.
A page fault does not give the processor to another process: time spent waiting for the disk is charged to the process that faulted, as if it had been computing. MIT did it this way for simplicity, so that the whole process system could live in ordinary virtual memory, and thought the cost small on a personal computer, where usually only one process at a time is ready to run.
03 / PROCESSES
The editor, a Lisp Listener, the keyboard and the network all run at the same time, each in a process of its own, and a scheduler written in Lisp shares the processor among them.
A process is like a processor simulated by software: it has its own program counter, its own stack of function calls and its own bindings of special variables. All processes run in the same address space and share the same Lisp objects, so they talk through them: one process can tell another of an event simply by changing a global variable. Locks and without-interrupts guard the places where two must not interfere.
A process is built on a stack group, the Lisp object that holds a computation’s state: its stack of calls, its stack of bindings, and the machine registers. Only one stack group runs at a time. Switching to another saves the running computation’s state into its stack group and restores the other’s, and the microcode does the switch.
A process waits by calling process-wait with a wait function: a predicate that says whether what it waits for has happened. The scheduler calls it; while it returns false the process waits, and once it returns true the process is ready to run. sleep is such a wait, its function comparing the time; the keyboard process waits on one that asks whether a key has arrived. A wait function runs in the scheduler, not in its process, so it should be quick and should not fail.
The scheduler is a stack group of its own, running one loop for ever:
Control comes back to the scheduler in two ways: the process waits, or a sequence break takes the processor from it. Most processes have priority 0; the keyboard and mouse processes have 30 and the network’s receiver 35, so they run as soon as they are ready.
04 / INTERRUPTS
A device’s interrupt is handled in microcode, without Lisp. What Lisp sees is a sequence break, and a sequence break only ever means one thing: return to the scheduler.
The devices interrupt the processor: the keyboard when a key is pressed, the network interface when a packet arrives, the disk when a transfer is done, and the tick, about sixty times a second. On the CADR the tick is the display’s frame; on QUUX it is an interval timer.
The microcode looks for a pending interrupt between macroinstructions and at its memory cycles, and handles it itself. Its handler may not bring in a page from the disk; it saves what it must, does the device’s urgent work — a key goes into the keyboard’s buffer, a packet onto the network’s receive list, a finished disk transfer is completed, the mouse’s motion is tracked — and returns to the interrupted work.
A sequence break is the interrupt Lisp sees: when one happens, the scheduler is resumed. The microcode requests one by setting a bit. The tick’s handler counts down and requests one every 60th tick, about once a second; a key or a packet can request one too, if enabled with si:sb-on, but the system enables only the clock.
The microcode takes the break at the next check. If inhibit-scheduling-flag is set, as it is inside without-interrupts, it notes the break and takes it once the flag is cleared; the devices’ interrupts go on meanwhile. Otherwise it saves the running process’s stack group and enters the scheduler’s. So a process that never waits still gives up the processor about once a second, and the scheduler decides who runs next — possibly the same process again.
05 / WINDOWS AND THE KEYBOARD
Many programs share the screen, each in its window; one window at a time is selected, and the keyboard’s input goes to it.
A program’s window usually has a process of its own. A Lisp Listener’s includes the process that runs its read-eval-print loop; the editor’s frame has one too. So the editor can wait for a key while a listener computes and the network answers a request.
A key takes this path. The keyboard interrupts, and the microcode puts the key into a buffer in memory. The keyboard process, at priority 30, waits for a key in that buffer, turns it into a character, acts at once on the Terminal and System keys and on Abort and Break, and puts every other character in its own buffer. A process reading its window’s input takes characters from the keyboard only if its window’s buffer is the selected one.
The System key followed by a letter selects a program: E the editor, L a Lisp Listener, I the Inspector, P Peek, which shows the processes; System Help lists the rest. What was typed before the System key belongs to the window that was selected, and what comes after it to the new one.
The mouse is tracked by the microcode at every tick and served by a mouse process of its own. The who-line at the bottom of the screen shows the state of a process: run, or why it is waiting, the reason it gave to process-wait, such as Keyboard.
06 / FILES AND THE NETWORK
The Lisp Machine’s network is the Chaosnet. Its basic service is a connection between two processes on different machines, a reliable channel of packets; a host is named by a 16-bit address. The interface interrupts on a packet, the microcode puts it on a receive list, and the Chaos Receiver, a process at priority 35, reads them from there; a Chaos Background process retransmits and probes. A server on the machine, such as its TELNET server, runs in a process of its own.
QUUX’s network is Ethernet instead, with ARP, IPv4 and TCP written in Lisp, and its TELNET server is reached over TCP (what QUUX changes).
A Lisp Machine usually reads and writes files on a file server, a computer that serves a whole community of machines, reached over the Chaosnet. A file is opened as a stream and read or written like any other stream. The CADR gets its files and the time from such a host; in this project that host is ozd.
QUUX reads and writes files on its host instead: a file device of its own serves folders of the host under one pathname host, FILES, and its system’s own files come from there. What QUUX changes has the rest.