Dataflow graphs are a generalized model of computation. Uninterpreted dataflow graphs with nondeterminism resolved via probabilities are shown to be isomorphic to a class of Petri nets known as free choice nets. Petri net analysis methods are readily available in the literature and this result makes those methods accessible to dataflow research. Nevertheless, combinatorial explosion can render Petri net analysis inoperative. Using a previously known technique for decomposing free choice nets into smaller components, it is demonstrated that, in principle, it is possible to determine aspects of the overall behavior from the particular behavior of components.

In this paper, a new model for parallel computations and parallel computer systems that is based on data flow principles is presented. Uninterpreted data flow graphs can be used to model computer systems including data driven and parallel processors. A data flow graph is defined to be a bipartite graph with actors and links as the two vertex classes. Actors can be considered similar to transitions in Petri nets, and links similar to places. The nondeterministic nature of uninterpreted data flow graphs necessitates the derivation of liveness conditions.

A model for a t,me-shanng operating system is developed in order to assess the effects of dynamic quantum allocation and overhead vanabdity on central processing unit (CPU) efficiency CPU efficiency is determmed by the proportion of time devoted to user-oriented (problem state) tasks within a busy period Computational results indicate that a dynamic quantum allocation strategy produces significant differences in CPU efficiency compared to a constant quantum The differences are affected significantly by the variability among allocated quantum values and the demand on the system Overhead variability also has a pronounced effect.A function that depicts overhead as decreasing with demand produces more stable values of CPU efficiency The interaction between demand and the amount of overhead is observed to be significant KEY WORDS AND PHRASES dynamic quantum allocation, overhead vanabihty, semi-Markov model, time-sharing system, CPU efficiency CR CATEGORIES 4 35 1. Introductzon DESIGN CONSIDERATIONS IN TIME-SHARING OPERATING SYSTEMS.With a timesharing operating system, a single program is given control of the central processing unit (CPU) until execution is completed or a maximum ume limit is reached.This time slice, called a quantum, is followed by a period during which the CPU is controlled by the operating system while control of the CPU is removed from one program and assigned to another.This duration is called the overhead.A quite natural view is that the quantum represents a period of effective processing while the overhead is a necessary but nonproductive time requirement (see Mullery and Driscoll [18]).As Wichman [13, p. 194] states, "What one wants is some cheap method, in terms of processor time, of controlling what's going on."However, in a relauvely heterogeneous environment, characterized by several program prlonty levels, the scheduling Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the pubhcat,on and its date appear, and notice is given that copying is by permission of the AsSoclaUon for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission This report is a major revision containing corrections to and extensions of results given m "Dynamic Quantum Allocation and Swap-Time Vanabihty in Time-Sharing Operating Systems," VPI & SU Technical Report CS73001-R and SMU Technical Report CP-73009

Analytical results in terms of Laplace-Stieltjes transforms for the busy period distribution of a time-sharing system with a central processing unit (CPU) and N peripheral units are derived in an earlier paper by Bhat and Nance.Assumptions of the model are that job arrivals are Poisson, required processing time for each job is an independent exponential random variable, and a feedback type discipline governs CPU access.The steady-state results of the earlier work are extended to gain information about the transient behavior of the CPU, Approximate results for the busy period distribution function are presented through numerical inversion of the transforms.Using these results qualitative conclusions are drawn regarding the sensitivity of system performance to changes in the number of peripheral units, quantum size, and CPU capability.

Abstract A mathematical definition of an information network is constructed with the purpose of developing a theory useful in answering practical questions concerning information transfer. An information network includes: (1) users, (2) information resources, (3) information centers, and (4) the total information transfer structure linking (1), (2), and (3). Emphasis is placed on the message transfer structure, as distinguished from the document transfer structure, to identify some basic network configurations. Any message transfer structure is shown in graph theory concepts to be either isographic or nonisographic. Among the isographic structures, the cyclic and decentralized networks are defined. The strictly hierarchical network is also defined, and the 2‐regular network, reflected in the ARPA design, is identified. Measures of network structure, in particular the accessibility and flexibility in message transfer, are developed. These measures for the basic structures are used to characterize more general structures. While some comparisons of message transfer structures can be made, development of more comprehensive measures is a necessity.

article Free Access Share on Busy Period Analysis of a Time-Sharing System Modeled as a Semi-Markov Process Authors: U. Narayan Bhat Institute of Technology, Computer Science/Operations Research Center, Southern Methodist University, Dallas, Texas Institute of Technology, Computer Science/Operations Research Center, Southern Methodist University, Dallas, TexasView Profile , Richard E. Nance Institute of Technology, Computer Science/Operations Research Center, Southern Methodist University, Dallas, Texas Institute of Technology, Computer Science/Operations Research Center, Southern Methodist University, Dallas, TexasView Profile Authors Info & Claims Journal of the ACMVolume 18Issue 2April 1971 pp 221–238https://doi.org/10.1145/321637.321643Published:01 April 1971Publication History 10citation367DownloadsMetricsTotal Citations10Total Downloads367Last 12 Months7Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF