Small computers are emerging as important components of the contemporary computing scene. Their operating systems vary from specialized software for an embedded system to the same style of OS used on a generic desktop or server computer. This article describes a course in which systems are classified by their hardware capability and the traditional OS topic areas are then dissected, augmented, reassembled, and reorganized to illustrate the aspects of each topic as applicable to each class of small computers. Ultimately, the course covers the same material as a conventional OS course, but from a new perspective.

The traditional assumption about memory is that a read returns the value written by the most recent write. However, in a shared memory multiprocessor several processes independently and simultaneously submit reads and writes resulting in a partial order of memory operations. In this partial order, the definition of most recent write may be ambiguous. Memory consistency models have been developed to specify what values may be returned by a read given that memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work, we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.Our unified theory provides several benefits. First, we claim that these four properties capture the underlying structure of memory consistency. That is, the goal of memory consistency is to ensure certain declarative properties which can be intuitively understood by a programmer, and hence allow him or her to write a correct program. Our unified theory provides a uniform, formal definition of all previously described consistency models, and in addition some combinations of properties produce new models that have not yet been described. We believe these new models will prove to be useful because they are based on declarative properties which programmers desire to be enforced. Finally, we introduce the idea of selecting a consistency model as an on-line activity. Before our work, a shared memory program would run start to finish under a single consistency model. Our unified theory allows the consistency model to change as the program runs while maintaining a consistent definition of what values may be returned by each read.

A memory consistency model specifies certain aspects of the behavior of a memory system. Stronger consistency models are easier for programmers to use, but provide less flexibility for optimizing the memory implementation. More relaxed consistency models are just the opposite. The goal of our work is to develop a framework that captures the relationships among existing models, and maps the territory of possible models that have not yet been discovered. This work is based on the idea of orthogonal consistency properties. hypothesize that all consistency models can be represented by different combinations of a few primitive properties. The work comes from examining the PRAM, cache, processor, and causal consistency models. Processor is a combination of PRAM and cache, and causal is a combination of PRAM plus an additional requirement. These factors suggest an underlying structure to the models.

In contemporary computers and networks of computers, various application domains are making increasing demands on the system to move data from one place to another, particularly under some form of soft real-time constraint. A brute force technique for implementing applications in this type of domain demands excessive system resources, even though the actual requirements by different parts of the application vary according to the way it is being used at the moment. A more sophisticated approach is to provide applications with the ability to dynamically adjust resource requirements according to their precise needs, as well as the availability of system resources. This paper describes a set of principles for designing systems to provide support for soft real-time applications using dynamic negotiation. Next, the execution level abstraction is introduced as a specific mechanism for implementing the principles. The utility of the principles and the execution level abstraction is then shown in the design of three resource managers that facilitate dynamic application adaptation: Gryphon, EPA/RT-PCIP, and the DQM architectures.

High bandwidth applications with time-dependent resource requirements demand certain resource level assurances in order to operate correctly. Quality of service resource management techniques are being successfully developed that allow network systems to provide such assurances. These solutions generally assume that the operating system at either end of the network is capable of handling the throughput requirements of the applications. However, real operating systems have to manage many concurrent applications with varying resource requirements. Without specialized support, the operating system cannot guarantee the resources needed for any particular application. In support of these kinds of applications we have developed a middleware agent called a dynamic QoS manager (DQM) that mediates application resource usage so as to ensure that applications get the resources they need in order to provide adequate performance. The DQM employs a variety of algorithms to determine application resource allocations. Using application QoS levels, it provides for resource availability based algorithmic variation within applications and varying application periods. It also allows for inaccurate application resource usage estimates through a technique we have developed called dynamic estimate refinement. The paper discusses new developments in the design of the DQM and presents results showing DQM performance with both real and synthetic applications.

Trace driven simulation has been shown to be an effective means of studying the detailed effect of a program on a specific execution architecture, particularly for memory systems. The technique often depends on taking a trace on one configuration of a machine, then effectively extrapolating the trace so that it represents the detailed behavior of the program on a related configuration. This paper proposes a hierarchical framework in which to study the effects of program non-determinism on program executions. Our goal is to ultimately characterize the complexity of trace extrapolation. We present some preliminary results and applications of the framework to related problems.

Computer systems will increasingly rely on distributed components in order to increase performance while providing autonomous computing facilities.This evolution implies that a corresponding advance must take place in the state of the art of system analysis and evaluation.This paper describes an experimental modeling system developed to study distributed office information systems.The modeling system is unusual in that the simulation component is itself a distributed program.Support facilities and the organization of the simulator are presented.

This paper describes a simulation study of a class of carrier sense multiaccess buses with collision detection, similar to the Xerox Ethernet. The driving loads for the network models are similar to ones that might be found in an office information system which integrates data and voice communication. Various backoff algorithms are considered, to investigate the suitability of the approach and to suggest an appropriate family of architectures for communication within this medium.

A wide variety of uses have been proposed for the spectrum of currently available microprocessor systems. Included in this set of applications is the use of microprocessors for implementing larger systems; here, the possibility of employing bit slice microprocessors for various parts of a multiple control unit SIMD processor is discussed. A brief summary of bit slice microprocessor architecture is given, followed by an outline of individual applications to various components such as control units and arithmetic/logic units of the SIMD processor.

The multiassociative processor (MAP) system is a hypothetical machine composed of eight control units (CU's) and an arbitrary number of processing elements (PE's). Each CU is allocated a subset of the identical PE's in order to process a single-instruction-stream-multiple-data-stream program. The eight CU's must be able to access a common main memory system and transmit data to subsets of the PE's over a shared data bus system. This paper discusses the analysis of these two components of the system where this analysis relies heavily on three simulation programs. The first program interprets assembly language programs for the hypothetical machine and the other two programs model the memory system and the data bus system. The interpreter is driven by both realistic array processor programs and synthetic programs designed specifically to test the components of the system.

Three different operating system strategies for a parallel processor computer system are compared, and the most effective strategy for given job loads is determined. The three strategies compare uniprogramming versus multiprogramming and distributed operating systems versus dedicated processor operating systems. The level of evaluation includes I/O operations, resource allocation, and interprocess communication. The results apply to architectures where jobs may be scheduled to processors on the basis of processor availability, memory availability, and the availability of one other resource used by all jobs.

Abstract The characteristics of jobs that constitute the mix for lower division FORTRAN classes in a university are investigated. Samples of these programs are also benchmarked on a large central site computer and two minicomputer systems. The conclusion of this study is that a carefully chosen minicomputer system could offer service at least the equivalent of the service provided by the central site system, and that certain aspects of this service could be distinctly better.

An extension of Petri nets called evaluation nets (E-nets) has been developed for use in representation of computer systems. These lead to interpreted graphs for use in human communication and to machine-interpretable descriptions. They may be used as aids in development of simulations and planning of measurements for examining characteristics such as throughput, turnaround time, and utilization of resources. This paper reviews the five primitives used to form nets expressing logical interactions among tokens (or tasks) flowing through the net and system resources represented by the net. Inherent in the use of the primitives is the ability to express time delays associated with the flow of tokens through the network and the modification of attributes of these tokens. This paper extends previous work on evaluation nets through the use of macro nets that represent structures made up of the primitives, allowing compression of the net for easier understanding. The macro nets are ``open-ended'' in the sense that the user can develop new macros to suit the needs of a particular study. Evaluation nets can be used informally like flow charts or block diagrams, although they provide greater power of expression than either. They can also be used more formally to develop machine aids, e.g., for on-line editing of evaluation nets or for development of simulation programs. Some examples of evaluation nets are provided that model a CDC 6400 and the cooperation of n independent sequential processes.