Operating Systems
The HYDRAsystem is the “kernel” base for a collection of operating systems designed to exploit and explore the potential inherent in a multiprocessor computer system. Since the field of parallel processing in general, and multiprocessing in particular, is not current art, the design of HYDRAhas a dual goal imposed upon it: (1) to provide, as any operating system must, an en- vironment for effective utilization of the hardware resources, and (2) to facilitate the construction of such environments. In the latter case the goal is to provide a recta-environment which can serve as the host for exploration of the space of user-visible operating en- vironments.
The particular hardware on which HYDRAhas been implemented is C.mmp, a multiprocessor constructed at Carnegie- . Although the details of the design of C.mmp are not essential to an understand- ing of the material which follows, the following brief description has been included to help set the context
(a more detailed description may be found in [9]). C.mmp permits the connection of 16 processors to 32 million bytes of shared primary memory through a cross-bar switch. The processors are any of the various models of PDP-11l minicomputers. Each processor is actually an independent computer system with a small amount of private memory, secondary memories, I/O devices, etc. Processors may interrupt each other at any of four priority levels; a central clock serves for unique-name generation (see below) and also broadcasts a central time base to all process6rs. Relocation hard- ware on each processor’s bus provides mapping of virtual addresses on that bus to physical addresses in shared primary memory.
Copyright By PowCoder代写 加微信 powcoder
Design Philosophy
The design philosophy of HYDRAevolved from both the environment in which the system was to function and a set of principles held by its designers. The central goals of the system together with the attitudes expressed below suggest that, at the heart of the system, one should build a collection of facilities of “universal applicability” and “absolute reliability”–a set of mechanisms from which an arbitrary set of operating system facilities and policies can be conveniently, flexibly, efficiently, and reliably constructed. Moreover, lest the flexibility be constrained at any instant, it should be possible for an arbitrary number of systems created from these facilities to co-exist simultaneously. The collection of such basic facilities has been called the kernel or nucleus [1] of an operating system. The more specific considerations are listed below.
1. Multiprocessor environment. Although multiproces- sors have been discussed for well over a decade and a
1Manufactured by Digital Equipment Corpormion.
HYDRA:The Kernel of a Multiprocessor Operating System
W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. –
This paper describes the design philosophy of HYDRA –the kernel of an operating system for C.mmp, the Carnegie- -Mini-Processor. This philosophy is realized through the introductiot~ of a generalized notion of “resource,” both physical and virtual, called an “object.” Mechanisms are presented for dealing with objects, including the creation of new types, specification of new operations applicable to a given type, sharing, and protection of any reference to a given object against improper application of any of the operations defined with respect to that type of object. The mechanisms provide a coherent basis for extension of the system in two directions: the introduction of new facilities, and
the creation of highly secure systems.
Key Words and Phrases: operating system, kernel,
nucleus, protection, security CR Categories: 4.3, 6.2
Copyrightý 1974,AssociationforComputingMachinery,Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.
This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (F44620-70-C- 0107) and is monitored by the Air Force Officeof Scientific Research Authors’ address: Department of Computer Science, Carnegie- ,SchenleyPark, Pittsburgh, PA 15213.
Communications of
June 1974 Volume 17 Number 6
Introduction
few have been built, both the potentials and problems of these systems are dimly perceived. The design of hYDRA was constrained to be sufficiently conservative to insure its construction and utility in a reasonable time frame, yet flexible enough to permit experimental exploration within the design space bounded by its hardware capabilities.
2. Separation of mechanism and policy. Among the major causes of our inability to experiment with, and adapt, existing operating systems is their failure to properly separate mechanisms from policies. (Hansen [1] has presented cogent arguments for this separation.) Such separation contributes to the flexibility of the system, for it leaves the complex decisions in the hands of the person who should make them–the higher-level system designer.
3. Integration of the design with implementation meth- odology. It has been observed that the structure of ex- tant operating systems bears a remarkable resemblance to that of the organization which created them. This observation is one of a set which asserts the (practical) impossibility of separating the design from the meth- odology to be used in implementing-the design. The authors’ predisposition for implementation methodol- ogy is a hybrid of structured programming as advocated by Dijkstra and others [2] and the modularization philosophy of Parnas [8].
4. Rejection of strict hierarchical layering. The notion of a strict hierarchically layered system has become popular since first described by Dijkstra for the THE system [3]. While we believe that the system as viewed by any single user should be hierarchically structured, we reject the notion as a global design criterion. We believe that if the entire system is so structured, the design will severely limit the flexibility available to the high-level user and will strangle experimentation; in particular, there is no reason to believe that the same hierarchical relation should exist for control as for resource allocation, or as for protection, etc.
5. Protection. Flexibility and protection are closely related, but not inversely proportional. We believe that protection is not merely a restrictive device imposed by “the system” to insure the integrity of user operations, but is a key tool in the proper design of operating sys- tems. It is essential for protection to exist in a uniform manner through the system, and not to be applied only to specific entities (e.g. flies). The idea of capabilities
(in the sense of Dennis [5]) is most important in the laVORAdesign; the kernel provides a protection facility for all entities in the system. This protection includes not only the traditional read, write, execute capabilities, but arbitrary protection conditions whose meaning is determined by higher-level software.
6. Reliability. The existence of multiple copies of most critical hardware resources in C.mmp suggests the possibility of highly reliable operation. Our desire is to provide commensurate reliability in the software. Re- liability not only requires that the system be correct,
but that it be able to detect and recover from errors that do exist–as the result of hardware malfunction, for example.
Defining a kernel with all the attributes given above is difficult, and perhaps impractical at the current state of the art. It is, nevertheless, the approach taken in the HYDRAsystem. Although we make no claim either that the set of facilities provided by the HYDRAkernel is minimal (the most primitive “adequate” set) or that it is maximally desirable, we do believe the set provides primitives which are both necessary and adequate for the construction of a large and ihteresting class of operating environments. It is our view that the set of functions provided by HYDRAwill enable the user of C.mmp to create his own operating environment with- out being confined to predetermined command and file systems, execution scenarios, resource allocation policies, etc.
Given the general decision to adopt the “kernel system” approach, the question remains as to what belongs in a kernel and, perhaps more important, what does not. Nonspecific answers to this question are im- plicit in the attitudes enumerated earlier; e.g. a set of mechanisms may be appropriate in a kernel, but policy decisions certainly are not. For other, more specific, answers we must step outside these attitudes alone and consider the nature of the entity to be built using the facilities of a kernel.
If a kernel is to provide facilities for building an operating system and we wish to know what these facilities should be, then it is relevant to ask what an operating system /s or does. Two views are commonly held: (I) an operating system defines an “abstract machine” by providing facilities, or resources, which are more convenient than those provided by the “bare” hardware; and (2) an operating system allocates (hard- ware) resources in such a way as to most effectively utilize them. Of course these views are, respectively, the bird’s-eye and worm’s eye views of what is a single entity with multiple goals. Nevertheless, the important observation for our purposes is the emphasis placed, in both views, on the central role of resources–both physical and abstract.
The mechanisms provided by the HYDRAkernel are all intended to support the abstracted notion of a resource (incarnations of a resource are called objects). These mechanisms provide for the creation and represen- tation of new types of resources, as well as operations defined on them, protected access to instances of one or more resources within controlled execution domains, and controlled passing of both control and resources between execution domains. The key aspects of these facilities are the generalized notion of resource, the definition of an execution domain, and the protection mechanism which allows or prevents access to resources within a domain. The remainder of this paper focuses on these issues, thus deemphasizing several of the other issues raised earlier.
Communications of
June 1974 Volume 17 Number 6
Overview of the HYDRA Environment
Before proceeding to a detailed description of the mechanisms, it will be convenient to present a somewhat incomplete and simplistic view of the execution en- vironment created by the HYDRAkernel. The material presented in this section will be elaborated further in the following sections; however, the overview will at- tempt to provide the context necessary to understand the more detailed information.
In order to understand the execution environment which the kernel provides, one must clearly understand the interrelationships of three object types: procedure, LNS, and process.These primitive objects are provided by the kernel specifically for the purpose of creating and manipulating an execution environment.
The procedure object is simply an abstraction of the intuitive notion of procedure or subroutine; z that is, a procedure has some “code” and some “data” asso- ciated with it, it may accept parameters, and it may re- turn values. HYDRAprocedures go beyond this simple model by including protection facilities, as we shall see shortly. The act of creating a procedure object is analogous to the task of writing an Algol procedure; one produces a body of code, associates the code with a name, declares the data which the code requires, and specifies the nature of the parameters and return values which are involved. In more abstract terms, one creates a sequence of instructions and describes the environment in which they will ultimately execute; in HYDRAthis abstraction is made precise. Let us consider the environ- ment description first.
A procedure object contains a list of references to other objects which must be accessed during the execu- tion of the procedure’s code. This is, in fact, a list of capabilities [7] and, therefore, defines not only which objects the procedure may reference, but also what ac- tions it may perform on those objects. The capabilities which a procedure requires may be divided into two groups: those which are caller independent and those which are caller dependent. These groups naturally correspond to those objects which the procedure always accesses (at least potentially) and those objects which are considered parameters. Obviously, the former of these groups can be precisely specified at the time the procedure is created, while the latter can only be characterized since the actual objects passed as param- eters are unknown until execution time. Thus, the en- vironment defined by a procedure object contains some “holes” or “parameter positions” which are only par- tially specified at creation time. These holes are filled in for each execution of the procedure, using capabilities
2It should be noted however, that the cost of entering a HYDRA procedure is considerably greater than, say, a Fortran subroutine. We do not expect that simple subroutines, such as SIN, would use the HYDRA mechanism until better hardware is pro- vided. The reader should visualize a procedure as replacing rela- tivelylarge code units and/or at pointswhereprotection environ- ments must change.
provided by the caller. We will return to a discussion of the mechanism by which a procedure characterizes its parameters, but first we must examine the LNS.
A procedure is a static entity; an LNS (local name space) is the record of the execution environment of a procedure when that procedure is invoked (called). There is a unique LNS for each invocation, which dis- appears after the procedure terminates. The LNS for a particular invocation is the result of combining the caller-independent capabilities (listed in the procedure object) with caller-dependent actual parameters (only characterized in the procedure object) to form a single list of capabilities. The LNS defines the totality of cap- abilities available to a procedure during the execution resulting from a particular invocation. Note that the LNS, while heavily dependent upon the corresponding procedure for its initialization, is a wholly independent object thereafter, and alterations of the LNS do not affect the procedure object; this implies, among other things, that procedures are reentrant and potentially re- cursive.
Up to this point the term “capability” has been used in a somewhat loose and intuitive sense; subsequently it will be used in a technical sense. A capability con- sists of a reference to an object together with a collec- tion of “access rights” to that object. Possession of a capability is taken as prima facie evidence that the possessor may access the object in the ways, and in only the ways, described by the capability. Capabilities themselves are manipulated only by the kernel; hence it is impossible to “forge” a capability.
A procedure object may contain templates in addi- tion to the usual collection of caller-independent cap- abilities. Templates characterize the actual parameters expected by the procedure. When the procedure is called, the slots in the LNSwhich correspond to param- eter templates in the procedure object are filled with “normal” capabilities derived from the actual param- eters supplied by the caller. This “derivation” is, in fact, the heart of the protection-checking mechanism, and the template defines the checking to be performed. If the caller’s rights are adequate, a capability is con- structed in the (new) LNS which references the object passed by the caller and which contains rights formed by merging the caller’s rights with the rights specified in the template. This implies that a callee may have greater freedom to operate on an object than the caller who passed it as a parameter, but the caller can in no way obtain that freedom for himself. We shall see that this potential expansion of rights across environment domains is a key factor in achieving the flexibility goals of the kernel and in allowing us to reject enforced hierarchical structures without introducing chaos.
Before proceeding, let us review the major actions of the CALLmechanism. An executing body of code first notifies the kernel that it wishes to call a procedure. The kernel examines the actual parameter capabilities supplied by the caller and determines whether all pro-
Communications of
June 1974 Volume 17 Number 6
tection requirements are met. If so, the kernel creates a new LNSwhich defines the new environment; the caller’s LNS is superceded by this new LNS for the duration of the called procedure’s execution. The body of code associated with the callee receives control from the kernel and begins executing. When it completes its function, it will return control to its caller by way of the kernel. The kernel will delete the callee’s LNS and restore that of the caller, thus returning to the previous environment.
Up to this point, nothing we have described suggests any exploitation of the parallel processing capabilities of C.mmp. The actions involved in calling and returning from procedures are strictly sequential in nature, being in essence formalizations of traditional subroutine be- havior. We come now to the unit of asynchronous processing in HYDRA–the process. A process in the technical sense defined by HYDRA corresponds closely to one’s intuitive notion of a process. Viewed from the outside, it is the smallest entity which can be inde- pendently scheduled for execution. Viewed from the inside, it constitutes a precise record of the changes of environment induced by a sequence of calls. In other words, a process is a stack of LNS’Swhich represents the cumulative state of a single sequential task. HYDRA implements interprocess communication and synchro- nization by providing elementary message buffering
primitives and Dijkstra-style semaphore operations. These facilities have been treated in [4] and elsewhere and will not be discussed here.
The Protection Mechanism
The protection mechanism is at the heart of the HYDRA design. In describing the mechanism it is im- portant at the outset to distinguish between protection and security and to determine what is to be protected and against what.
In our view, protection is a mechanism; security is a policy. A system utilizing such a mechanism may be more or less secure depending upon policies governing the use of the mechanism (for example, passwords and the like are policy issues) and upon the reliability of the programs which manipulate the protected en- tities. Thus the design goal of the HYDRAprotection mechanism is to provide a set of concepts and facilities on which a highly secure system may be built, but not to inherently provide that security. A particular con- sequence of this philosophy has been to discard the notion of “ownership.” While ownership is a useful, perhaps even an important, concept for certain “secur- ity” strategies, to include the concept at the most prim- itive levels would be to exclude the construction of cer- tain other classes of truly secure systems.
Our rejection of hierarchical system structures, and especially ones which employ a single hierarchical rela- tion for all aspects of system interaction, is also, in
part, a consequence of the distinction between protection and security. A failure to distinguish these issues coupled with a strict hierarchical structure leads inevitably to a succession of increasingly privileged system components, and ultimately to a “most privileged” one, which gain their privilege exclusively by virtu
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com