提高Ada并发效率的一种途径

Ada的会合机制使我们能在高级语言一级上描述系统的并发活动,从而避免了在使用低级通信原语时所不可避免的问题。但由于会合机制是一种完全同步的实现机制,因此其并发效率较低。为此,本文提出：采用基于Ada保护对象的（异步）信箱机制实现Ada会合的服务模型,使之既具有会合机制的高可靠性,又能提高系统的并发度和实现效率。     

Administrators and multiprocessor rendezvous mechanisms

This paper discusses rendezvous on multiprocessors. Three different approaches are compared, represented by three specific systems: Ada, Harmony and BNR Pascal. All three permit tasks to run on multiple processors and use blocking communications primitives, but there are significant differences. For example, control over replying to messages out of sequence and over the allocation of tasks to processors is omitted in Ada, but is available in Harmony. The approach represented by BNR Pascal follows a middle road between Harmony and Ada: a low level protocol, invisible to the programmer, is used to ensure communications reliability, but the programmer is aware of when a rendezvous is remote. If performance considerations and verbosity and robustness are ignored, all three approaches are equivalent. To illustrate this equivalence, and to demonstrate clearly the complexity of the Ada rendezvous, an Ada rendezvous administrator written using Harmony is described. A second method of adapting Harmony to Ada is also presented, in which the Harmony primitives are modified to be closer to Ada. In practice, using Harmony primitives directly will usually result in better programs. It is argued that something very much like the rendezvous adminstrator is needed for any actual implementation of the Ada rendezvous.     

提高Ada并发效率的一种途径

Ａｄａ的会合机制使我们能在高级语言一级上描述系统的并发活动,从而避免了在使用低能通信原语时所不可避免的问题,但由于会合机制是一种完全同步的实现机制,因此其并发效率较低。为此,本文提出：采用基于Ａｄａ保护对象的（异步）信箱机制实现Ａｄａ会合的服务模型,使之既具有会合机制的高可靠性,又能提高系统的并发度和实现效率。     

BB图的枚举特征

在并发程序复杂性度量研究中，我们曾定义了一种B图，用以作为Ada并发程序中一种会合关系的模型。我们将B图推广到BB图。n节点BB图是在n个节点的串联树上再添加若干条边，其约束条件是：每个节点的入度不大于二，每个节点的出度也不大于二。给出BB图的若干若干枚举特征，指出同第二类Stiding数的密切关系。     

Concurrent programming in the Ada® language: The polling bias

The rendezvous is an important concept in concurrent programming—two processes need to synchronize, i.e. rendezvous, to exchange information. The Ada programming language is the first programming language to use the rendezvous as the basis of its concurrent programming facilities. Our experience with rendezvous facilities in the Ada language shows that these facilities lead to and encourage the design of programs that poll. Polling is generally, but not always, undesirable because it is wasteful of system resources. We illustrate and examine the reasons for polling bias in the Ada language. We give suggestions on how to avoid polling programs, and suggest changes to the rendezvous facilities to eliminate the polling bias. The ramifications of these changes to the implementation of the Ada language are also discussed. Although we have focused on the rendezvous facilities in the Ada language our analysis is also applicable to other languages. A polling bias can occur in any concurrent programming language based on the rendezvous mechanism if it does not provide appropriate facilities.     

A novel approach to coordination of multiple robots with communication failures via proximity graph

In this paper, we investigate the coordination problem of multiple robots with limited communication ranges and communication failures. A novel rendezvous algorithm via proximity graph is developed so that the robot group can achieve rendezvous when the communication links satisfy an ergodic assumption. The convergence proof of the algorithm is established based on the tools from rooted graph theory. The effectiveness of the algorithm is illustrated by numerical examples in a 3D space.     

ARTK-M2: A kernel for Ada tasking requirements: An implementation and an automatic generator

A run-time kernel, ARTK-M2, supporting Ada tasking semantics is discussed; full support for task creation, synchronization, communication, scheduling, and termination is provided, together with all options of the Ada rendezvous. An implementation in Modula-2 is presented and a method for automatically translating Ada programs into semantically equivalent Modula-2 programs with corresponding kernel calls is introduced. A parser generator and an attribute grammar were used for the automatic translation. A subset of the Ada Compiler Validation Capability was processed to test the implementation and to illustrate the translation mechanism. The kernel is applicable to the study of real-time control systems; it can also serve as a baseline for studying implementation alternatives of Ada concepts, such as new scheduling algorithms, and for analysing new language constructs. Work is under way to implement some of the changes to the Ada tasking model being proposed as a result of the language revision (Ada9X). Finally, through proper extensions, ARTK-M2 can form an integral part of programming tools such as an Ada compilation system and a distributed kernel for multi-processing environments.     

Deterministic Rendezvous in Graphs

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n²) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.     

Transformations for optimizing interprocess communication and synchronization mechanisms

This paper presents source-level transformations that improve the performance of programs using synchronous and asynchronous message passing primitives, including remote call to an active process (rendezvous). It also discusses the applicability of these transformations to shared memory and distributed environments. The transformations presented reduce the need for context switching, simplify the specific form of communication, and/or reduce the complexity of the given form of communication. One additional transformation actually increases the number of processes as well as the number of context switches to improve program performance. These transformations are shown to be generalizable. Results of hand-applying the transformations to SR programs indicate reductions in execution time exceeding 90% in many cases. The transformations also apply to many commonly occurring synchronization patterns and to other concurrent programming languages such as Ada and Concurrent C. The long term goal of this effort is to include such transformations as an otpimization step, performed automatically by a compiler.This work was supported by NSF under Grant Number CCR88-10617.     

Remote rendezvous

BNR Pascal is a systems programming language intended for the implementation of the systems software of distributed computing systems. It supports the Ada Rendezvous model of tasking and communication, uniformly extended to support communications between tasks distributed over the computing nodes of a system. BNR Pascal was designed and implemented in 1980, and has since been used to implement the operating systems and real-time applications software for Northern Telecom's Meridian family of products. In total, more than 2 million lines of BNR Pascal exist. This paper describes the BNR Pascal remote rendezvous: the extension of rendezvous to interprocessor communication. It discusses the implementation of remote rendezvous, describing the advantages and disadvantages of several options. Finally, it details BNR's experience in using remote rendezvous in building substantial, practical distributed systems used in products.     

Ada并发软件的图形化设计方法研究

研究的目标：为Ada并发软件的设计提供一种图形化的方法和支撑工具，以便用图形表达并发软件的设计，并生成并发程序的框架（并发程序单元的划分和它们之间的通信）。这样做的好处在于提高软件的生产率，改善软件质量。在提出用于并发软件理解的会合次序图的基础上，给出了并发设计语言CONDL的语法、语义描述和图形化表示（泳道），并简单介绍了所研制的一个工具CONDLAS（生成Ada代码框架）。     

基于Petri网的一种时序分析方法

Ｐｅｔｒｉ网由于有强大的建模能力和成熟的理论支持,被广泛应用于各种系统的建模．本文通过把Ｐｅｔｒｉ网转换成转移系统,利用转移系统和Ｋｒｉｐｋｅ结构给出时序逻辑语义的解释,从而建立了一种在Ｐｅｔｒｉ网上进行时序分析的方法．这种方法是根据不动点理论,用模型检查验证公式正确性．通过对Ａｄａ程序会合性质进行模型检查,验证了这种方法的有效性．     

Specifying Ada server tasks with executable formal grammars

The author shows how a class of concurrent programming problems can be specified with formal grammars. These grammars, more powerful than path expressions, translate readily into Ada server tasks using the rendezvous and select-statement, though they may also be applied to other synchronization constructs. The grammars may be used to clarify informal specifications, to compare different specifications, and to analyze the behavior of implementations of such specifications. They may also be easily converted into Prolog programs that can be executed to generate the strings of events accepted by a grammar or by the Ada task being modeled. The automated translation from Ada to such grammars, and from grammatical specifications to Ada is discussed. The former facilitates the analysis of Ada programs; the latter yields Ada code of high quality     

Rendezvous facilities: Concurrent C and the Ada language

The concurrent programming facilities in both Concurrent C and the Ada language are based on the rendezvous concept. Although these facilities are similar, there are substantial differences. Facilities in Concurrent C were designed keeping in perspective the concurrent programming facilities in the Ada language and their limitations. Concurrent C facilities have also been modified as a result of experience with its initial implementations. The authors compare the concurrent programming facilities in Concurrent C and Ada and show that it is easier to write a variety of concurrent programs in Concurrent C than in Ada     

On the Rendezvous Problem for Multiple Nonholonomic Agents

In this note, a decentralized feedback control strategy that drives a system of multiple nonholonomic unicycles to a rendezvous point in terms of both position and orientation is introduced. The proposed nonholonomic control law is discontinuous and time-invariant and using tools from nonsmooth Lyapunov theory and graph theory the stability of the overall system is examined. Similarly to the linear case, the convergence of the multi-agent system relies on the connectivity of the communication graph that represents the inter-agent communication topology. The control law is first defined in order to guarantee connectivity maintenance for an initially connected communication graph. Moreover, the cases of static and dynamic communication topologies are treated as corollaries of the proposed framework     

Measurements of Ada overhead in OSI-style communications systems

A discussion is given on whether the Ada model of concurrency is suitable for implementing the seven-layer OSI reference model. Using the communications model introduced by R.J.A. Buhr (1984), they determine the overhead introduced by Ada when the model is implemented on two single-processor machines, a VAX 11/785 and a Rational 1000. The authors then calculate a lower bound on expected message delay. A novel model using server tasks is proposed and shown to have better performance. The authors investigate performance on an eight-processor Sequent Model 821 and a 14-processor Encore Multimax 320 by implementing the Buhr model, the server task model and a third model which abandons the Ada rendezvous in favor of procedure calls. They determine the Ada overhead per message as a function of the number of processors and calculate lower bounds on expected message delay attributable to Ada overhead for all three communications models     

Adam: An Ada-based language for multiprocessing

Adam is a high-level language for parallel processing. It is intended for programming resource scheduling applications, in particular supervisory packages for run-time scheduling of multiprocessing systems. An important design goal was to provide support for implementation of Ada and its run-time environment. Adam has been used to implement Ada task supervision and also as a high-level target language for compilation of Ada tasking. Adam provides facilities corresponding to the Ada sequential constructs (including subprograms, packages, exceptions, generics). In addition, it provides specialized module constructs for implementation of packages that may be shared between parallel processes, and new predefined types for scheduling. The parallel processing constructs of Adam are more primitive than Ada tasking. Strong restrictions are enforced on the ways in which parallel processes can interact. A compiler for Adam has been implemented in MacLisp on DEC PDP-10 computers. Runtime support packages in Adam for scheduling (on a single CPU) and I/O are also provided. The compiler contains a library manipulation facility for separate compilation. The Adam compiler has been used to build an Ada compiler for most of the July 1980 Ada, including task types and rendezvous constructs. This was achieved by implementing the translation of Ada tasking into Adam parallel processing as a preprocessor to the Adam compiler. This present Ada compiler, which has been operational since December 1980, uses a procedure call implementation of tasking. It can be easily modified to other implementations. Compilation of Ada tasking into a high-level target language such as Adam facilitates studying questions of correctness and efficiency of various compilation algorithms, and code optimizations specific to tasking, e.g. elimination of unnecessary threads of control. This paper gives an overview of Adam and examples of its use. Emphasis is placed on the differences from Ada. Experience using Adam to build the experimental Ada system is evaluated. Design of a run-time supervisor in Adam is discussed in detail.     

How to meet when you forget: log-space rendezvous in arbitrary graphs

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph.     

On the Implementation and Use of Ada on Fault-Tolerant Distributed Systems

In this paper, we discuss the use of Ada® on distributed systems in which failure of processors has to be tolerated. We assume that tasks are the primary object of distribution, and that communication between tasks on separate processors will take place using the facilities of the Ada language. It would be possible to build a separate set of facilities for communication between processors, and to treat the software on each machine as a separate program. This is unnecessary and undesirable. In addition, the Ada language Reference Manual states specifically that a system consisting of communicating processors with private memories is suitable for executing an Ada program.