July 1975 - Vol. 18 No. 7

July 1975 issue cover image

Features

Research and Advances

Decomposability, instabilities, and saturation in multiprogramming systems

A step-by-step approach to model the dynamic behavior and evaluate the performance of computing systems is proposed. It is based on a technique of variable aggregation and the concept of nearly decomposable systems, both borrowed from Econometrics. This approach is taken in order to identify in multiprogramming paging systems (i) unstable regimes of operations and (ii) critical computing loads which bring the system into states of saturation. This analysis leads to a more complete definition of the circumstances in which “thrashing” can set in.
Research and Advances

A large semaphore based operating system

The paper describes the internal structure of a large operating system as a set of cooperating sequential processes. The processes synchronize by means of semaphores and extended semaphores (queue semaphores). The number of parallel processes is carefully justified, and the various semaphore constructions are explained. The system is proved to be free of “deadly embrace” (deadlock). The design principle is an alternative to Dijkstra's hierarchical structuring of operating systems. The project management and the performance are discussed, too. The operating system is the first large one using the RC 4000 multiprogramming system.
Research and Advances

The restriction language for computer grammars of natural language

Over the past few years, a number of systems for the computer analysis of natural language sentences have been based on augmented context-free grammars: a context-free grammar which defines a set of parse trees for a sentence, plus a group of restrictions to which a tree must conform in order to be a valid sentence analysis. As the coverage of the grammar is increased, an efficient representation becomes essential for further development. This paper presents a programming language designed specifically for the compact and perspicuous statement of restrictions of a natural language grammar. It is based on ten years' experience parsing text sentences with the comprehensive English grammar of the N.Y.U. Linguistic String Project, and embodies in its syntax and routines the relations which were found to be useful and adequate for computerized natural language analysis. The language is used in the current implementation of the Linguistic String Parser.
Research and Advances

Determining the minimum-area encasing rectangle for an arbitrary closed curve

This paper describes a method for finding the rectangle of minimum area in which a given arbitrary plane curve can be contained. The method is of interest in certain packing and optimum layout problems. It consists of first determining the minimal-perimeter convex polygon that encloses the given curve and then selecting the rectangle of minimum area capable of containing this polygon. Three theorems are introduced to show that one side of the minimum-area rectangle must be collinear with an edge of the enclosed polygon and that the minimum-area encasing rectangle for the convex polygon is also the minimum-area rectangle for the curve.
Research and Advances

A note on hash linking

In current machine designs, a machine address gives the user direct access to a single piece of information, namely the contents of that machine word. This note is based on the observation that it is often useful to associate additional information, with some (relatively few) address locations determined at run time, without the necessity of preallocating the storage at all possible such addresses. That is, it can be useful to have an effective extra bit, field, or address in some words without every word having to contain a bit (or bits) to mark this as a special case. The key idea is that this extra associated information can be found by a table search. Although it could be found by any search technique (e.g. linear, binary sorted, etc.), we suggest that an appropriate low overhead mechanism is to use hash search on a table in which the key is the address of the cell to be augmented.

Recent Issues

  1. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  2. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  3. August 2024 CACM cover
    August 2024 Vol. 67 No. 8
  4. July 2024 CACM cover
    July 2024 Vol. 67 No. 7