No abstract available.

Most new computer architectures are concerned with maximizing performance by providing suitable instruction sets for compiled code and providing support for systems functions. We argue that the most effective design methodology must make simultaneous tradeoffs across all three areas: hardware, software support, and systems support. Recent trends lean towards extensive hardware support for both the compiler and operating systems software. However, consideration of all possible design tradeoffs may often lead to less hardware support. Several examples of this approach are presented, including: omission of condition codes, word-addressed machines, and imposing pipeline interlocks in software. The specifics and performance of these approaches are examined with respect to the MIPS processor.

A frame buffer architecture is presented that reduces the overhead of frame buffer updating by three means. First, the bit-map memory is (x,y) addressable, whereby a string of pixels can be accessed in parallel. Second, the pixel-change operation is performed by hardware in a single read-modify-write cycle. Third, multiple objects in the frame buffer are addressable simultaneously by a set of address registers. The remaining task of generating (x,y) addresses and providing new data can be managed rapidly by current microprocessors or DMA-devices.With a modest expenditure of hardware, this architecture eliminates all the bit-shifting, bit-masking, and bit-manipulation conventionally associated with frame buffer graphics, while retaining the full generality of user-programmable control. The particular implementation described allows raster manipulation at full bit-map memory bandwidth. It can paint a 16×16 pixel character into the frame buffer in 16 microseconds and can modify a 1024×1024 pixel raster in 64 milliseconds.

This paper describes the fundamentals and some of the details of task communication in DEMOS, the operating system for the CRAY-1 computer being developed at the Los Alamos Scientific Laboratory. The communication mechanism is a message system with several novel features. Messages are sent from one task to another over links. Links are the primary protected objects in the system; they provide both message paths and optional data sharing between tasks. They can be used to represent other objects with capability-like access controls. Links point to the tasks that created them. A task that creates a link determines its contents and possibly restricts its use. A link may be passed from one task to another along with a message sent over some other link subject to the restrictions imposed by the creator of the link being passed. The link based message and data sharing system is an attractive alternative to the semaphore or monitor type of shared variable based operating system on machines with only very simple memory protection mechanisms or on machines connected together in a network.

We have designed and built a computer terminal that provides low cost, high quality graphics and programmable text processing by taking advantage of the latest memory and microprocessor technology. A microprocessor control element allows most of the control functions to be programmed so that all of the control electronics require less than 100 integrated circuits. The graphic image is generated by a microprocessor which accepts vector commands intended for a Tektronix storage tube display terminal. The microprocessor maps those vector commands into a random access memory, and the resulting bit map of the graphic image is displayed on a standard TV monitor. Reasonable resolution in the graphic image requires a large number of bits in the bit map, but with the use of 4K memory chips, less than 100 integrated circuits are required for the bit map memory in our design. At 1975 small-quantity prices, the parts cost for the terminal is approximately $2000.

The joint equihbrmm distribution of queue sizes in a network of queues containing N service centers and R classes of customers m derived The equilibrium state probabillUes have the general form P(S) = Cd(S) fl(xl)f2(x2) .fN(x~), where S is the state of the system, x, is the configuration of customers at the ~th service center, d(S) is a function of the state of the model, f, is a function that depends on the type of the zth service center, and C is a normalizing constant It is assumed that the eqmhbrlum probabfl~tles exmt and are unique Four types of service centers to model central processors, data channels, terminals, and routing delays are considered The queuemg dlSclphnes associated with these service centers include first-come-first-served, processor sharing, no queueing, and last-come-first-served Each customer belongs to a single class of customers while awaiting or receiving serwce at a service center, but may change classes and service centers according to fixed probabditms at the completion of a service request For open networks, state dependent arrival processes are considered Closed networks are those with no exogenous arrivals A network may be closed with respect to some classes of customers and open with respect to other classes of customers At three of the four types of serwce centers, the service times of customers are governed by probablhty dmtrlbutions hawng ratmnM Laplace transforms, different classes of customers hawng different distributions At first-come-first-served-type service centers, the service time distribution must be identical and exponentml for all classes of customers.Examples show how different classes of customers can affect models of computer systems.

The modehng and analysis of drum-hke storage units are discussed.Two common forms of drum organizations and two common scheduhng dlsclphnes are considered the file drum and the paging drum; first-m-first-out (FIFO) scheduh ~g and shortest-latency-time-first (SLTF) scheduhngThe modehng of the I/O requests to the drum is an important aspect of this analysis Measurements are presented to mdmate that ~t ~s reahstm to model requests for records, or blocks of mformatron to a file drum, as requests that have starting addresses umformly dmtrlbuted around the circumference of the drum and transfer times that are exponentially distributed with a mean of ½ to of a drum revolution The arrival of I/O requests is first assumed to be a Polsson process and then generalized to the case of a computer system with a finite degree of multlprogrammmg An exact analyms of all the models except the SLTF file drum ts presented; m th~s case the complexity of the drum orgamzatlon has forced us to accept an approximate analysis In order to examine the error introduced into the analysis of the SLTF file drum by our approximations, the results of the analytm models are compared to a simulatmn model of the SLTF file drum.Comparisons of the models indicate that the scheduhng dlsclphne is more important to performance than drum orgamzation

An algorithm that finds the k nearest neighbors of a point, from a sample of size N in a d-dimensional space, with an expected number of distance calculations is described, its properties examined, and the validity of the estimate verified with simulated data.

According to the authors this book treats "the most important formal methods that have been applied to the study of operating systems algorithms." The emphasis of the book is on the mathematical analysis of models of computing systems, which means that there are several important methods and concepts in the theory of operating systems that are not treated. However, the book is the first serious attempt in this area and is a valuable addition to the reference and text books in computer science.

The stationary distribution of the number of jobs being served by a processor-sharing central server is independent of both the distribution of service times and the distribution of interarrival times when those distributions have rational Laplace-Stieltjes transforms. This result holds for both finite source and infinite source models. The steady state is identical to the steady state when all distributions are exponential. The expected response time, queue size, and central processor idle time of the finite source model under processor-sharing and FCFS scheduling are compared. These measures of system performance are all larger under processor-sharing for a class of central processor service time distributions with a coefficient of variation less than one. The measures are all smaller under processor-sharing for a class of distributions with a coefficient of variation greater than one. Experiments with data collected from actual computer systems indicate that these results extend to more general models and have practical applications in existing computer systems.