Multics 826 entries
16 Feb 2014

Glossary - P

Glossary of Multics acronyms and terms. Entries by Tom Van Vleck ([THVV]) unless noted.

Index| A| B| C| D| E| F| G| H| I| J| K| L| M| N| O| P| Q| R| S| T| U| V| W| X| Y| Z|
packed pointer
[BSG] Hardware feature on the 6180, and a much rarer software format on the 645, that encodes a virtual memory pointer (segment and word number, plus EIS bit offset on the 6180) in one 36-bit word. While 50% more storage-efficient than the two-word ITS pointer, a packed pointer cannot be used for indirection (see eppbp) or the storage of a value where ring number had to be saved (see TRR). Also, only twelve bits are available for the segment number (instead of 15 in an ITS pointer), and this is the tightest limit on the maximum number of segments in a process, far too small. The PL/I compiler made heavy internal use of packed pointers (which have to be loaded with a special instruction, again, see eppbp), but because of the above, their use in general system code is quite uncommon.

Fixed size piece of memory. The hardware supports both paged and unpaged segments. The SDW for a paged segment points to a page table, an array of PTWs (stored in the AST). Each PTW points to a page in core, or has a fault tag and an indication of where on secondary storage the page's contents can be found. The 645 hardware supported two page sizes, 64 words and 1024 words. Bookkeeping and storage pool management was so complex that small pages were eliminated in 1968.

page control
[BSG] Ring 0, wired software responsible for managing the transfer and mapping of pages in and out of memory. Only a small amount of this is the famous "page replacement algorithm" (see clock algorithm) due to Corbató; most of this code, almost all complex and highly-optimized assembler language, is the management of I/O and state, the multilevel paging hierarchy management, and interaction with and services provided for segment control and other areas of the system. Page control is perhaps the most asynchronous, difficult, and critical component of the whole system. Successive gurus who worked there and left their marks were Stan Dunten, Steve Webber, and Bernie Greenberg.

page fault
Still called that, or "missing page exception." When an instruction references a page whose PTW says it's not present, the hardware takes a page fault. The hardware fault vectors point to the FIM, (or wired_fim) which saves the machine state and invokes page control.

page multilevel
[BSG] Scheme implemented in MSS 16.0 (1971? 72?) by Steve Webber and Rick Gumpertz to dynamically optimize the use of storage of three (or conceivably more) technologies and size/cost/speed tradeoffs by migrating data (in Multics, pages) "down" to successively slower, larger finite stores as more recently used data is moved "up", replacing it in the faster, smaller levels, as the system runs. An extension of the notion of demand-paged, least-recently-used (LRU)-managed core to many levels, PML was similar to schemes being innovated on other operating systems at the time. [documented in Webber & Greenberg, "The Multics Multilevel Paging Hierarchy", Proc 1975 IEEE Intercon, 1975].

Multics PML arose (on the 645) as the culmination of various schemes utilizing the small, fast firehose drum for "the most used" segments, temporary process directory segments, and other ultimately unsatisfactory formulae broadly classified as "static migration." PML, in contrast, by operating on pages and not segments as the system runs, is in essence the ultimate dynamic migration scheme. Multics PML had only one intermediate level, generically known as the "paging device", which was at first the firehose drum and then (on the 6180) the bulk store.

PML occasioned the largest and most radical rewrite of page control in its history, a quantum escalation of the even theretofore unwieldy complexity of this ALM-coded supervisor subsystem. PML's interaction with segment control (activation and deactivation) was particularly complex (and a source of bugs), and the support of pages of non-active segments on the paging device was abandoned with NSS. Although PML was wholly excised from Multics in the early 80s when the economics of memories rendered the bulk store obsolete, PML remains IMHO one of Steve Webber's titanic masterpieces.See Read-Write Sequence.

page table
[BSG] Array of hardware control words (Page Table Words, or PTWs) that define the actual location in core of the pages of a segment (or page control data to locate the page on secondary storage if it is not in core.) The essence of the Multics virtual memory is that there is one page table per segment, as opposed to other schemes (e.g., Intel) where one or more page tables define some larger linear address space of which segments are subsetted. Page tables (like the segments they define) are per-system, not per-process. The Segment Descriptor Word for a segment in the DSEG of each process in which the segment is known (see also active) contains the (same) absolute address of its page table.

A segment's page table is part of its AST entry, and thus all page tables reside in one wired, unpaged segment, the SST (System Segment Table). Page tables come in four sizes, corresponding to segments of 4K words, 16K, 64K, and 256K, the sizes of these pools of each being system tuning parameters (see config deck), and are kept in lists by pool for purposes of multiplexing. The limitation on page tables residing in one segment (built into the ALM code of page control everywhere) ultimately proved to be a major bottleneck [latter-day Guru: was this ever addressed?]. See AST trickle.

page trace
Ring-buffer in the first page of a process's PDS in which an entry is made for every page paged in since a process gained eligibility. This is used to drive the pre-paging algorithm.

(1) The division (by the 645 /6180 appending hardware) of a segment into fixed-size pieces, called pages, which can be present in core or not. If a page is not in core, a reference to it causes the CPU to fault, and the software that handles this fault (page control) finds a free core frame and fetches the page's contents from secondary storage (i.e., disk).

(2) The system's activity of handling page faults, fetching requested pages, and writing out other pages to make room. See "The Multics Virtual Memory: Concepts and Design."

paging device
Device used as the intermediate level store in a multilevel paging hierarchy ("page multilevel"), at first the firehose drum, then later the bulk store.

(Pedagogic Algorithmic Language) Programming linguistics language created by Art Evans, using ideas from Martin Richards. Used in the first course taught using Multics, 6.231, in the summer of 1969.

Palyn Report
Report prepared in 1978 by Palyn Associates for Honeywell corporate, recommending long range large systems plans. Story: "The Palyn Report".

[Earl Boebert] (1) GE-speak acronym for "Purchased and Rented Computers." Not used in Honeywell until after the merger in 1970, then common amongst beancounters and marketing weasels. "Churning the PARC" was the term for getting your rented machines back before you had squeezed every dime out of the customer. Used frequently in arguments against a strong Multics marketing effort.

[THVV] (2) Xerox Palo Alto Research Center, source of many innovations.

Contiguous region of a disk volume. The BOS PART configuration card defined partitions.

Grenoble wrote a Pascal compiler for Multics in the 1980s, and James Gosling wrote a Pascal at Calgary for Multics.

[Ian G Batten] The Multics Pascal compiler had a flag to accept French keywords. SI, ALORS, FIN, all that.

[JHS] Secret character string used to authenticate the claimed identity of a person.

[THVV] Multics passwords are stored in the PNT encrypted by a one-way function. They are eight characters long, and the login command has optional arguments to generate a pronounceable password for you. (Code written by Morrie Gasser of MITRE in connection with Project Guardian.) This facility can be invoked automatically after a password has expired. Story: "Multics Security".

The DOCKMASTER site implemented one-time passwords using the WATCHWORD device.

path name
Multics segments are named by a sequence of entry names, separated by > characters, e.g. >udd>m>vv> This path name provides a path from the root directory to the segment. Pathnames are absolute (descend from the root) or relative to the current working directory.

PC support
Support for file transfer and terminal emulation between a PC and Multics. Feature in MR11.0? See MOWSE.

(or PDD, process_dir_dir). Alternate names of the directory >process_dir_dir, whose subdirectories are users' process directories, created and destroyed as processes are created and destroyed. Compare UDD.

[BSG] Process Data Segment. A per-process, ring 0 segment, containing per-process supervisor data (other than the KST and descriptor segment) as well as the ring 0 stack of the process. The PDS has the same segment number in every process, and contains many symbolically-referenced data objects. When a process is made eligible by the scheduler, the first page of the PDS, which contains data needed by wired code, including places for faults to store SCU data, is wired. Compare PRDS.

Project Definition Table. The per-project segment that defines which users may log in on a project to User Control. A project administrator can update this segment online by editing an ASCII PMF file, compiling it with cv_pmf, and sending the answering service a request to install it with up_pmf. The project administrator could specify optional per-user resource and spending limits here.

[David Schroth] Multics site: A software engineering solutions company in Calgary Alberta, Canada, formerly known as ACTC Inc. Spinout (1983) from the University of Calgary, partly owned by Bull. Did contract maintenance for all Multics sites. Acquired by CGI Group Inc. subsidiary CGI Information Systems and Management Consultants Inc. in September 1998. At that time CGI operated a dual 8/70M in Calgary. Formal support is no longer offered to the Multics community.

[THVV] The Perigon machine was shut down in July 2000. See the UC site history.

Multics registers individual people in the Person Name Table (PNT). Each person has a name, a password, a default project, and some historical information. This registration is done by the system administrators. Project administrators can then register persons on their projects, creating a user entry in the project's PDT. One person can be registered as more than one user.

Phase One
Integration milestone during Multics development. The first time that Multics booted from tape and came up to type on the operator's TTY. Accomplished December 1967 by Noel Morris and Tom Van Vleck. Story: "Phase One".

Privileged HardCore Supervisor gate. A gate which allows semi-privileged operations, such as examining the contents of ring 0, but doesn't let the user do things that might crash the system. A user with access to phcs_ is trusted, since this gate can be used to examine passwords in the input buffers. Compare with hphcs_.

Page Has been Modified. Flag set by the CPU in a PTW when a page is stored into, used by the page control replacement algorithm. (See clock algorithm.)

City in Arizona, where LISD built computers. Used metonymically to refer to LISD management. Home of PMDC.

Feature of compose.

Page Has been Used. Flag set by the CPU in a PTW when a page is read, used by the page control replacement algorithm. (See clock algorithm.)

[BSG] "Page used in quantum (time since made eligible)". A software PTW flag set whenever the clock algorithm passed over a PHU and turned it off. Thus, PHU means "used since last pass of the clock hand" and PHU1 "used in quantum."

physical volume (PV)
[BSG] NSS term meaning "a disk pack". The contrast is with logical volumes, groups of PV's: users can specify on which LV a segment is to reside, but not on which PV - that is up to the system alone. PV's, however, are the unit of data integrity and recovery, and this non-transparency in the illusion is apparent.

Unix feature added to the Multics shell in the mid 80s. One could get the effect of pipes using io_call and stream manipulation from the beginning of the system, but the vertical bar pipe syntax was added to make this more convenient.

Process Initialization Table. Per-process segment in the process directory where the system stores constants determined at process creation time. Accessed only through the user_info_ subroutine.

[BSG] Programming Language #1, invented by George Radin of IBM in 1964. Combining scientific features from FORTRAN, business features like records from COBOL, and block structuring from Algol, PL/I's future looked rosy in 1965 when the team chose it for the Multics systems programming language and the idea of coding an operating system in a "higher level language" was radical. Multics's storage models, procedure models, data types, and run-time architecture were all designed around those of the PL/I language, and all system APIs were given in PL/I. Use of any other language for systems programming tasks was actively and officially discouraged. Nonetheless, over the years certain critical subsystems of substantive complexity and bulk (notably page control and the scheduler) were recast into assembler language to optimize performance. The version 2 Multics PL/I implementation (Bob Freiburghouse and Barry Wolman, chief architects), was arguably the preeminent PL/I implementation of record. Paper: "The Multics PL/I Compiler" by Bob Freiburghouse.

Segment referred to by every compiled PL/I program, containing open code (threaded code) cliches for common constructs, including call/save/return. Normally every process shares the same (wired) copy of the segment, but a user can modify the operator pointer in the stack root to switch operators to, for example, test a new version or to turn on call tracing.

[BSG] Print with Line Numbers. A private command by Max Smith that was used heavily in the development community, very similar to UNIX grep. Although the Multics product had nothing like it, widespread feeling that it was not Multicious, as it had no obvious place in an organized, extant or proposed suite of tools, and an immensely useful feature of "knowing" about the insides of archives that raised questions about other commands, prevented it from ever being made part of the product. While pln's many fans were often frustrated by the double-edgedness of the at-times conservative sword of Multiciousness, and could not understand why the world at large could not benefit from this incredibly useful tool, precisely such a profusion of diverse, unrelated tools is in fact one of Unix's most well-known flaws.

Phoenix Multics Development Center. The group of Multicians located in Phoenix at the Honeywell Camelback Road Facility. Worked on MRDS, compose, system release, trouble report handling, and communications.

Project Master File. A per-project ASCII file that can be compiled into a PDT with cv_pmf by a project administrator.

MSS 16.0 and page control jargon for Page Multilevel.

Person Name Table. User Control's password and user name registration database.

pointer register
[BSG] Register on the 6180 (or "pointer pair" on the 645) containing a segment number and a word number within that segment (and on the 6180, a ring number and a bit number for EIS), i.e., a generic pointer into the segmented address space. Other than constant and code references, Multics instructions usually make references relative to pointer registers, for the same reasons of relocatability that obtain in any architecture. On the 6180, the pointer registers visible to the Multics instructions are actually fabricated illusions constructed of "address registers" shared with the non-Multics (GCOS) CPUs and segment and ring registers managed by the appending unit, which lock-step mimics every CU operation on the "address registers" to create the software illusion of pointer registers. On the 645, the "pointer pairs" were wholly within the base frame, being built of 8 ABRs which could function either as segment or word pointers and be associated into pairs. During normal Multics PL/I code, pointer registers are reserved for the stack frame, the entry vector of pl1_operators_, and less strictly, the procedure's actual parameter list, its linkage section, and the operator table at the base of the current stack. In addition to numbers 0, 1 ... 7, the pointer registers also had names, ap, ab, bp, bb, lp, lb, sp, sb, based upon their conventional use in Multics PL/I object code. .

Port Logic
[BSG] That portion of the 6180 processor that takes absolute addresses and stores or returns data for them. The cache is an integral part of the port logic, whose main database is the (single, global) CPU 72-bit memory data bus. The port logic also has to deal with many non-memory operations that are implemented in the SCU, such as clock reading and interrupt generation, and is responsible for selecting ports based upon address. As main memory (i.e., the SCU) is a fully asynchronous external component, the port logic can manage simultaneous, overlapped operations on different SCUs, and route the completion notifications back to the right module of the CPU (see Control Unit, Appending Unit). This facilitates interlace, a port logic featurette whereby alternate word-pairs are addressed to alternate SCUs for maximum overlap. The 6180-proper port logic has a four-element hardware ring buffer in which it queues and from which it processes requests and notifications.

To hasten the eviction of "a process's pages" from core at the time it lost eligibility. See pre-paging

[BSG] Procedure Pointer Register - a tripartite processor register defining the segment, ring, and location of the next instruction to be executed, the Multics equivalent of the "instruction counter", which is the "location" component of the above. The processor actually implemented the three components on three different boards in three different ways, but Multics chose to conceptualize it as one. The ring component ("PRR") defines the current ring of execution. Compare TPR, TRR.

[BSG] Processor Data segment. A per-processor, fully-wired ring 0 segment, containing not only symbolically-referenced per-processor data but a stack used when running fault and interrupt handlers that cannot take page faults or interrupts, such as page control itself, and the scheduler. The processor carries around the SDW for the PRDS from process to process like a carpet-bag, dropping it in the same slot in the descriptor segment of each process as the processor moves from process to process, literally holding it in the accumulator during every process-switching instruction (LDBR). Compare PDS.

[BSG] Feature of the page control/ traffic control interaction which tries to hasten the eviction of a "process's pages" from memory at the time it loses eligibility, and to read those pages in in parallel at the time a process regains eligibility, before letting that process run. The notion of "a process's pages", of course, does not flow naturally from the virtual memory concept, and the choice of which pages that a process had referenced since becoming eligible (see page trace) were to be considered for pre-paging and/or post-purging is controlled by a bit map that maps various criteria, such as being a process-directory page, being used since the last sweep of the page-replacement clock algorithm (see PHU, PHU1), being modified (see PHM), being on the drum or paging device into the decisions to pre-page, post-purge and "turn off the used bit". If my memory serves me well, as it were, this mechanism sported more controls than anyone knew how to use. See swapping.

[BSG] (1) The Multics supervisor is pre-linked statically at system bootload time by a pair of assembly-language programs known as the "prelinker".

(2) In the late 70s, the capability of pre-linking select users' address spaces as a performance boon was added. This function is done by a separate "prelinker."

Multics site: Puerto Rican Highway Authority. San Juan, Puerto Rico. Installed 1977. See PRHA site history.

Prime Computer's operating system. Heavily influenced by Multics and Multicians.

[BSG] Multics supported the standard-issue GE and Honeywell line printers of the era of fanfold paper, fitted with special type-bars and chains to support the ASCII character set. As these printers were designed for a 6-bit BCD character set (and were thus incredibly fast at printing foot-thick dumps and the like), printing upper-and-lower-case characters required odd modes and complex escape sequences. Although softwarily possible, users never attach printers or direct output to them -- the only mode of printer use is to queue ASCII files to be printed by the Printer daemon, using the dprint (later enter_output_request) command.

Before the era of GUIs and WYSIWYG editing, fanfold listings were an invaluable aid in developing and debugging programs. Story: "Multics Printer Software". Info segment for enter_output_request command

privileged mode
[BSG] The GCOS versions of the Multics processors implemented a traditional one-bit hardware user/supervisor distinction: the CPU privileged mode ("master mode" on the 645) enabled system-control instructions, which were otherwise illegal. In Multics, privileged became a bit (see REWPUG) in the SDW, effectively ANDed with ring of execution being ring 0. Very few supervisor segments had this bit. Today, modern processors only have rings.

Multics high-level PL/I source language debugger. See debug. Info segment for probe command

An address space and a locus of control. A Multics process is a complex object, because it has a complicated address space.

Story: Multics Execution Environment.

process directory
[BSG] Directory created when a process is created for exclusive use of that process, namely per-process and scratch segments, including stacks (including the PDS) and combined linkage segment. Disk quota in the process directory is not charged against the user. All process directories are subdirectories of >PDD

process overseer
Procedure called at process initialization time. It sets up the process environment and then calls the process's listener. load Control has a table of process overseers and their load control weights.

process preservation
Multics can save a process across a communications interruption. A user can later reestablish communications and connect to or destroy the preserved process.

(1) Facility to count the number of times each source statement in a program is executed. Compile a program with the -profile option, run it, and then use print_profile to print out per-statement counters in its static section. See Multics Execution Environment.

(2) Per-user segment used by the abbrev command to store abbreviations. Info segment for profile command

After a QUIT signal or fault in an interactive program that establishes a new shell command level, a user can issue the program_interrupt, pi command. This command signals the PL/I condition "program_interrupt". If the interactive program has established a handler for program_interrupt, the handler will re-enter the interactive command loop. The qedx editor, for example, has such a handler, so that if a user issues a very long-running command and then repents, he can QUIT and issue the pi command to resume editing, discarding the whole command execution safely. Info segment for program_interrupt command

[BSG] Group of Multics users working together, for the same firm or organizational division, for whom Multics can pool all disk record quota and establish common access rights, and grant other group privileges. The system registers a name and password for each person; when a person logs in, he or she specifies a project (possibly by default), and the combination is called a user. The PDT lists a project's users and records resource consumption for each.

project administrator
[BSG] Person who administers a Multics project. Among the responsibility of the Project Administrator is registering and deregistering users on the project (a user can only log in if he or she has a project to log in to), and creating home directories under the project directory.

[THVV] Decentralized management of the user community is an important feature of User Control; the system administrators establish the registration of persons, and their initial passwords, but project administrators can register persons as users of their projects without consulting the system administration, and modify users' resource limits and get reports of current usage.

project directory
[BSG] Directory for a given project, always a subdirectory of >udd. The subdirectories of the project directory are users' home directories. In the directory pathname >udd>Multics>Morris, >udd>Multics is the project directory.

[THVV] Project administrators can move disk quota from the project directory to individual users' home directories.

Project MAC
MIT Project MAC, suggested by J.C.R. Licklider, was the organization that began the research that led to Multics. It is now called the MIT Laboratory for Computer Science.

[Kenneth Flamm] Project MAC was a large and well-funded effort. Its initial grant from DARPA for a little over $2 million per year was quickly raised. Funding peaked at $4.3 million in 1969, slumped to under $3 million in 1973, and rose again in the late 1970s. Project MAC's research staff peaked in 1967 at 400.

Procedure Ring Register. Part of the PPR. Stored in the SCU data.

[BSG] Page Table Lock. More accurately, a lock on all the data-bases of page control, that is, PTWs, core frame tables, and paging device map. This lock, protecting a huge amount of performance- and integrity-critical data, is used only by wired code masked against interrupts, including interrupt and page fault handlers, so it was designed as a "spin lock", which would only be found locked on multi-processor systems. As Multics grew, the necessity of alleviating this growing performance bottleneck resulted first in the Cow's Stomach, and later in an extremely non-modular tryst of traffic control and page control, also by Greenberg, allowing processes to wait (see notify) on the Page Table lock as a highly special case.

Page Table Word. 36-bit word interpreted by the hardware, which contains the absolute address of a page, or a fault tag and an indicator of where the page is on secondary storage.

pure procedure
Multics compilers all generate code that does not modify itself. This may seem like a no-brainer, but it was quite radical when introduced: OS/360 struggled with the concept of "reentrant" (same thing as pure procedure), "serially reusable," and another flavor, forget the name, of program. CTSS stored into its code in lots of places, but we realized that this would be very bad on a multiprocessor system.

Physical Volume Table. NSS table listing physical volumes.

Process exchange, switch stack, the ALM-coded module which performed Multics processor scheduling and dispatching. Source code: pxss.alm.