Levy Capability-Based Computer Systems 1984

This document is a book titled "Capability-Based Computer Systems" by Henry M. Levy, published in 1984. It serves as an introduction, survey, history, and evaluation of computer systems that utilize capability-based addressing and object-based design principles.

The book's primary purpose is to provide a single, comprehensive source of information on capability-based systems, which aim to address limitations in conventional computer architectures regarding information sharing, protection, and reliable system construction.

Key Concepts Explained:

• Capability: Defined as a "token, ticket, or key" that grants the possessor permission to access an entity or "object" within the computer system. A capability typically consists of a unique object identifier and a set of access rights (e.g., read, write, execute). It functions as a uniform mechanism for addressing and protecting both hardware and software resources, including memory segments, files, and processes.
• Object-Based Approach: The book introduces this as a system design philosophy that decomposes problems into abstract object types and operations on them. Capabilities are crucial for supporting object-based systems by providing a secure and flexible way to name, address, and control access to objects.

Historical and System Survey: The book surveys the evolution of capability-based systems through case studies of various influential computer architectures and operating systems:

1. Early Descriptor Architectures: Discusses systems developed before the formal definition of capabilities, such as the Burroughs B5000, the Rice University Computer, and the Basic Language Machine (BLM). These machines used "descriptors" or "codewords" that functioned similarly to capabilities for memory segmentation and protection.
2. Early Capability Architectures: Examines the conceptual design of a capability-based supervisor by Dennis and Van Horn (MIT, 1966), and early implementations like the MIT PDP-1 Timesharing System, the Chicago Magic Number Machine, and the CAL-TSS system (UC Berkeley).
3. Operational Capability Systems: Highlights the Plessey System 250 (UK, 1969), noted as the first commercially available capability-based computer system, and Cambridge University's CAP computer (UK, 1970), the first successful university implementation of capability hardware.
4. Object-Based Multiprocessor Operating Systems: Delves into Hydra (Carnegie-Mellon University, 1971) and STAROS (CMU, 1975), which were pioneering object-based operating systems designed for multiprocessor environments, leveraging capabilities for object-level addressing and protection.
5. Commercial Systems: Covers the IBM System/38 (1978), the first major commercial system to adopt object-based methodology for business computing, and the Intel iAPX 432 (1981), the first highly-integrated object-based microprocessor.

Design Issues and Evaluation: The final chapter reviews common design challenges and trade-offs in capability-based architectures, including:

• Segmentation: Its role in structuring memory and providing logical entities.
• Storage of Capabilities: Different approaches like C-lists (Capability Lists) versus tagging.
• Capability Representation: The structure and size of capabilities, and how they relate to object identifiers and physical memory mapping.
• Object Lifetimes and Garbage Collection: Managing objects that can persist indefinitely and the need for garbage collection to reclaim unused resources.
• Object Locking and Revocation: Mechanisms for controlling concurrent access and retracting access rights.
• Protected Procedures and Type Extension: How capabilities enable users to extend system functionality and create new, protected object types.

The book emphasizes the examination of both the conceptual aspects and the practical hardware and operating system implementations of these systems, highlighting their respective features, advantages, and disadvantages within their historical context.