UNIX is a general-purpose, multi-user, interactive operating system for the Digital Equipment Corporation PDP-11/40 and 11/45 computers. It offers a number of features seldom found even in larger operating systems, including: (1) a hierarchical file system incorporating demountable volumes; (2) compatible file, device, and inter-process I/O; (3) the ability to initiate asynchronous processes; (4) system command language selectable on a per-user basis; and (5) over 100 subsystems including a dozen languages. This paper discusses the nature and implementation of the file system and of the user command interface.
Software Engineering and Programming Languages
Advertisement
Protection and the control of information sharing in multics
The design of mechanisms to control the sharing of information in the Multics system is described. Five design principles help provide insight into the tradeoffs among different possible designs. The key mechanisms described include access control lists, hierarchical control of access specifications, identification and authentication of users, and primary memory protection. The paper ends with a discussion of several known weaknesses in the current protection mechanism design.
A theorem-proving language for experimentation
Because of the large number of strategies and inference rules presently under consideration in automated theorem proving, there is a need for developing a language especially oriented toward automated theorem proving. This paper discusses some of the features and instructions of this language. The use of this language permits easy extension of automated theorem-proving programs to include new strategies and/or new inference rules. Such extendability will permit general experimentation with the various alternative systems.
The minimization of spatially-multiplexed character sets
The paper describes a technique for compacting character sets in a digital computer while retaining fast access to individual bits. It considers the problem of minimizing the storage needed to contain such tables. Reduction techniques are developed, and the problem is shown to reduce to a covering problem.
Compact representation of contour plots for phone line transmission
Methods for the compact representation of contour plots are described and tested. These are intended to reduce the cost of transmitting contour plots over phone lines. We feel some of these methods could be used to transmit contour plots over voice grade phone lines.
HYDRA: the kernel of a multiprocessor operating system
This paper describes the design philosophy of HYDRA—the kernel of an operating system for C.mmp, the Carnegie-Mellon Multi-Mini-Processor. This philosophy is realized through the introduction 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.
An information-theoretic approach to text searching in direct access systems
Using direct access computer files of bibliographic information, an attempt is made to overcome one of the problems often associated with information retrieval, namely, the maintenance and use of large dictionaries, the greater part of which is used only infrequently. A novel method is presented, which maps the hyperbolic frequency distribution of text characteristics onto a rectangular distribution. This is more suited to implementation on storage devices.
This method treats text as a string of characters rather than words bounded by spaces, and chooses subsets of strings such that their frequencies of occurrence are more even than those of word types. The members of this subset are then used as index keys for retrieval. The rectangular distribution of key frequencies results in a much simplified file organization and promises considerable cost advantages.
Two languages for estimating program efficiency
Two languages enabling their users to estimate the efficiency of computer programs are presented. The program whose efficiency one wishes to estimate is written in the first language, a go-to-less programming language which includes most of the features of Algol 60. The second language consists of interactive commands enabling its users to provide additional information about the program written in the first language and to output results estimating its efficiency. Processors for the two languages are also described. The first processor is a syntax-directed translator which compiles a program into a symbolic formula representing the execution time for that program. The second processor is a set of procedures for algebraic manipulation which can be called by the user to operate on the formula produced by the first processor. Examples of the usage of the two languages are included. The limitations of the present system, its relation to Knuth's work on the analysis of algorithms, and some of the directions for further research are also discussed.
Order-n correction for regular languages
A method is presented for calculating a string B, belonging to a given regular language L, which is “nearest” (in number of edit operations) to a given input string &agr;. B is viewed as a reasonable “correction” for the possibly erroneous string &agr;, where &agr; was originally intended to be a string of L. The calculation of B by the method presented requires time proportional to |&agr;|, the number of characters in &agr;. The method should find applications in information retrieval, artificial intelligence, and spelling correction systems.
The treatment of data types in EL1
In constructing a general purpose programming language, a key issue is providing a sufficient set of data types and associated operations in a manner that permits both natural problem-oriented notation and efficient implementation. The EL1 language contains a number of features specifically designed to simultaneously satisfy both requirements. The resulting treatment of data types includes provision for programmer-defined data types and generaic routines, programmer control over type conversion, and very flexible data type behavior, in a context that allows efficient compiled code and compact data representation.
Reduction of compilation costs through language contraction
Programming languages tailored to particular groups of users can often be constructed by removing unwanted features from a general purpose language. This paper describes the use of simulation techniques to predict the savings in compilation cost achievable by such an approach. The results suggest a function which describes the effect of changes in the power of a language on the compilation cost of an algorithm expressed in that language: when features not actually used by the algorithm are removed from the language, the cost of compiling the algorithm decreases moderately, but when features that are needed are removed, the compilation cost increases sharply.
A model for masking rotational latency by dynamic disk allocation
This paper presents the background and algorithms for masking the rotational latency of a disk or drum. It discusses the anticipatory input and output of blocks of data to buffer and primary memories for a mono-programmed computer system. A basic permutation algorithm and several variations are given. Because of the anticipatory nature of the I/O scheduling, these algorithms are restricted to classes of programs with predictable behavior. While the methods are not restricted to numerical computations, matrix and partial differential equation methods are typical examples of their use. It is shown that latency may be masked using a small amount of buffer memory. The methods discussed are independent of the overall size of the data base being considered.
More on algorithms that reveal properties of floating point arithmetic units
In the interests of producing portable mathematical software, it is highly desirable for a program to be able directly to obtain fundamental properties of the environment in which it is to run. The installer would then not be obliged to change appropriate magic constants in the source code, and the user would not have to provide information he may very well not understand. Until the standard definitions of programming languages are changed to require builtin functions that provide this information [1, 3], we will have to resort to writing routines that discover it.
Computation of page fault probability from program transition diagram
An algorithm is given for calculating page fault probability in a virtual memory system operating under demand paging with various memory sizes and replacement rules. A first order Markov model of program behavior is assumed, and a representation of the system based on memory states, control states, and memory substates is presented. The algorithm is general in the sense that the page fault probabilities can be calculated for nonpredictive replacement rules applied to any program represented by a one-step Markov chain. A detailed example is given to illustrate the algorithm for Random and Least Recently Used (LRU) replacement rules.
Copying list structures using bounded workspace
Two new algorithms are presented for list structure copying using bounded workspace. The first, of primarily theoretical interest, shows that without cell tag bits the task can be performed in time n2. The second algorithm, assuming one tag bit in each cell, delivers attractive practical speed. Any noncyclic structure is copied in linear speed, while cyclic structures are copied in average time less than n log n. No foreknowledge of cycle absence is necessary to achieve linear speed. A variation of the second algorithm solves an open problem concerning list structure marking. That result demonstrates that marking can be done in average time n log n without the aid of supplemental tag bits or stacks.
Execution characteristics of programs in a page-on-demand system
h show the execution characteristics of two types of commonly used programs in a large-scale, time-shared computer system. A software monitoring facility built into the supervisor was used for data collection during normal system operation. These data were analyzed, and results of this analysis are presented for a Fortran compiler and an interactive line file editor.
Probability distribution functions and other data are given for such things as CPU intervals, I/O intervals, and the number of such intervals during execution. Empirical distributions are compared with simple theoretical distributions (exponential, hyperexponential, and geometric). Other data show paging characteristics of tasks as a function of the number of pages those tasks have in core.
An improved program-synthesizing algorithm and its correctness
An improved program-synthesizing algorithm based on the algorithm proposed by Waldinger and Lee in 1969 is given. In the old algorithm, the program-synthesizing problem is translated into a theorem-proving problem, and a program is obtained by analyzing a proof. For the improved algorithm, the analysis is not necessary, and a program is obtained as soon as the proof is completed. This is achieved by using a modified variable tracing mechanism invented by Green in 1969. The correctness of the improved algorithm is also proved; i.e. the program thus obtained always satisfies the specification.
Two methods for employing parallelism in tape-sorting are presented. Method A is the natural way to use parallelism. Method B is new. Both approximately achieve the goal of reducing the processing time by a divisor which is the number of processors.
A probabilistic model of a multiprogramming system is exercised in order to determine the conditions under which the dynamic repacking of main memory is beneficial. An expression is derived for the maximum interference that a repacking process may introduce before the original performance of the system is degraded. Alternative approaches to repacking are discussed, and the operating conditions that lead to improved system throughput through repacking are delineated.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More