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.     

Experience acquiring and retargeting a portable Ada compiler

A technique for implementing Ada with reasonable effort on a piece of non-standard hardware is described. The target machine is a single processing element in an experimental multiprocessor based on NS32000. A portable Ada front-end compiler was used for retargeting, and the process of acquiring and evaluating the front end is described. Based on this experience, comments on the validation, quality and efficiency of Ada compilers are given, along with a detailed overview of the resultant system. The Ada system was built from scratch on the bare hardware. It has three main components: a code generator, a run-time system and an Ada kernel. The code generator is table driven and generates symbolic NS32000 assembler. This code is then assembled and linked by commercially available components. The run-time system and the kernel are implemented in assembly language and Concurrent Euclid and handle tasking, exceptions and scheduling. The result is a complete Ada implementation.     

A LIS compiler for GCOS-7

This paper describes the implementation of a LIS compiler for GCOS-7. LIS is a high level system implementation language developed at CII-Honeywell Bull during the middle 1970s, and experience with the language and its implementation have largely influenced the design of Ada. The design of the compiler was particularly aimed at efficient code generation. Design decisions concerning the run-time organization in relation to procedure call and separate compilation are discussed. The structure of the compiler is described. The articulation between the different phases of the code generator is emphasized. Experience with the bootstrap is related.     

A parallel Ada system on an experimental multiprocessor

This paper describes the development of a parallel Ada system on an experimental MIMD multiprocessor. The system enables a single unmodified Ada program, with a number of tasks, to execute in parallel on different processors. Allocation and migration strategies are controlled by mechanisms in the run-time system, and are thus transparent to the Ada programmer. The parallel Ada system is based on a validated portable front-end compiler. Implementation issues related to the multiprocessor environment are pointed out, and solutions to these issues are suggested. The experimental multiprocessor environment, consisting of both hardware and software, is described. Applicable resource allocation strategies in, and feasible experiments with, the Ada system are discussed. The complete experimental system provides unique possibilities to experiment with, and monitor the effects of, design decisions at different levels in a multiprocessor environment.     

基于网语言的Ada程序局部性质的分析和验证

旨在研究利用网语言讨论Ada程序性质和由此而引起的Ada网的状态爆炸问题.研究了Ada网的同步合成与分解,讨论了它们的语言性质,并利用这一结果分析和验证了Ada程序的安全性和活性,从而为复杂的Ada程序的分析与验证提供了一个新的有效途经.     

Two implementations of the Ada program library

The programming language Ada defines a separate compilation mechanism which must enforce the language rules in the same manner when compiling a program either in several units or as one compilation unit. Two implementations of the Ada program library required by this mechanism are described. Each has an associated compiler manager program which is the user's interface to the library. The first maintains a central map file containing the library structure. The second uses the UNIX tool make to maintain the library and permits more flexibility in the UNIX operating system environment. Higher level tools could use the second manager as a component part.     

Real-time interrupt handling in Ada

The Ada? programming language defines the semantics of interrupt handling as part of the tasking mechanism, making it possible to construct implementation-independent interrupt handlers. However, for the Ada mechanism to be effective, an implementation must provide support not specified by the Ada standard, such as for initializing hardware interrupting devices, handling unexpected interrupts and optimizing for real-time performance constraints. This paper analyses some of the constraints that efficient interrupt support places on an implementation. It develops a model for the interaction between interrupt hardware and Ada tasks and describes optimizations for Ada interrupt handlers. Implementation issues, including task priorities and task termination for interrupt handlers, are discussed in detail.     

A Comparison of Implementation Strategies for Nonuniform Data-Parallel Computations

Data-parallel languages allow programmers to easily express parallel computations by means of high-level constructs. To reduce overheads, the compiler partitions the computations among the processors at compile-time, on the basis of the static data distribution suggested by the programmer. When execution costs are nonuniform and unpredictable, some processors may be assigned more work than others. Workload imbalance can be mitigated by cyclically distributing data and associated computations or by employing adaptive strategies which build a more balanced schedule at run-time, on the basis of the actual execution costs. This paper discusses static and hybrid (static+dynamic) scheduling strategies which can be used to balance the workloads derived from the execution of nonuniform parallel loops. A multidimensional flame simulation kernel has been used to evaluate different implementation strategies on a Cray T3E. We fed the benchmark code with synthetic input data sets built on the basis of a load imbalance model and we report and compare the results obtained.     

The LTPL-E tasking proposals

The Long Term Procedural Language Committee of the International Purdue Workshop for the Standardization of Industrial Computer Systems has studied, over a number of years, the design of a programming language suitable for use in industrial real-time systems. Various parts of a language suitable for this kind of application have been designed during this period. This paper presents the results of part of this work. In particular it describes the tasking facilities that are seen to be necessary in the industrial real-time environment. The paper concludes with a comparison of the proposed features with those in Ada.     

一个Ada子集的编译设计与实现

Ａｄａ语言是美国国防部（ＤｏＤ）在国际范围内组织设计的软件工程语言。它具有实时性、模块性、并行性，在数据抽象，模块结构、并行控制和异常处理等方面提出一整套新概念、新方法，是现代计算机语言的成功代表。该文主要描述由ＰＣｘ８６／ＵＩＮＸ平台上的Ａｄｚ－ｚ编译系统的信息流导致的软件结构、结构内部的接口定义及每个软件元素的功能。     

一个实用的Ada源级调试器的设计和实现

Ada是美国国家军用标准编程语言。近年来,我国也开展了对Ada及其开发环境的研究工作。本文首先介绍高级语言开发环境中源级符号调试器的基本原理,然后给出了一个实用性的Ada源级调试器的设计和实现关键技术。     

Ada95语言评述

Ａｄａ９５语言是在Ａｄａ８３基础上修订而成的，它几乎提供了现代程序设计范型及程序设计实践所需要的一切设施，它可以支持面向对象的程序设计、大型程序设计、实时与并行程序设计等等。     

Normal form approach to compiler design

This paper demonstrates how reduction to normal form can help in the design of a correct compiler for Dijkstra's guarded command language. The compilation strategy is to transform a source program, by a series of algebraic manipulations, into a normal form that describes the behaviour of a stored-program computer. Each transformation eliminates high-level language constructs in favour of lower-level constructs. The correctness of the compiler follows from the correctness of each of the algebraic transformations.     

Experimenting with dynamic linking with ADA

An approach to achieving dynamic reconfiguration within the framework of Ada¹ is described. A technique for introducing a kernel facility for dynamic reconfiguration in Ada is illustrated, and its implementation using the Verdix VADS 5.5 Ada compiling system on a Sun3–120 running the 4.3 BSD Unix operating system is discussed. This experimental kernel allows an Ada program to change its own configuration dynamically, linking new pieces of code at run-time. It is shown how this dynamic facility can be integrated consistently at the Ada language level, without introducing severe inconsistencies with respect to the Standard semantics.     

An Analysis of Fixed-Priority Schedulability on a Multiprocessor

A new feasibility test for preemptive scheduling of periodic or sporadic real-time tasks on a single-queue m-server system allows for arbitrary fixed task priorities and arbitrary deadlines. For the special case when deadline equals period and priorities are rate monotonic, any set of tasks with maximum individual task utilization u_max and minimum individual task utilization u_min is feasible if the total utilization does not exceed . Ted Baker received the Ph.D. in Computer Science from Cornell University in 1973. He is a Professor in the Department of Computer Science at the Florida State University, which he chaired from 1998 to 2005. After spending several years doing research in computational complexity theory, he moved on to more practical aspects of computing and has worked in the area of both Ada compilation and real-time systems for the last two decades. A group he organized at FSU in 1979 produced one of the first validated Ada cross-compilers for embedded systems. Since then, he has done research, development, and consulting related to real-time embedded computing, from basic research on scheduling and concurrency control through development of kernels and run-time system support for real-time programming languages. He has also been active in IEEE (POSIX) and ISO standards work related to real-time systems. Dr. Baker was a member of the SEI Rate Monotonic Analysis group, served as real-time area expert for the Ada 9X language mapping and revision team. He directed the FSU teams that developed several software products, including the FSU POSIX threads library, the Florist implementation of IEEE Std 1003.5b-c (the POSIX/Ada API), a set of validation tests for the 1003.5b standards, and the multitasking run-time system for the Gnu Ada (GNAT) compiler. He directed the porting of the latter to several environments, including the Java Virtual Machine and RT Linux. His current research interests are real-time multiprocessor scheduling and real-time device driver architecture.     

The Lynx distributed programming language: Motivation, design and experience

A programming language can provide much better support for interprocess communication than a library package can. Most message-passing languages limit this support to communication between the pieces of a single program, but this need not be the case. Lynx facilitates convenient, typesafe message passing not only within applications, but also between applications and among distributed collections of servers. Specifically, it addresses issues of compiler statelessness, late binding, and protection that allow run-time interaction between processes that were developed independently and that do not trust each other. Implementation experience with Lynx has yielded important insights into the relationship between distributed operating systems and language run-time support packages and into the inherent costs of high-level message-passing semantics.     

Mumbo: A Rule-Based Implementation of a Run-time Program Generation Language

We describe our efforts to use rule-based programming to produce a model of Jumbo, a run-time program generation (RTPG) system for Java. Jumbo incorporates RTPG following the simple principle that the regular compiler — or, rather, its back-end — can be used both for ordinary, static compilation and for run-time compilation. This tends to produce a run-time compiler that is inefficient but potentially subject to improvement by partial evaluation. However, the complexity of the language and compiler have made it difficult for us to achieve actual optimization. The model, written in Maude, preserves all the essential ingredients of Jumbo, but operates on a simplified language, called Mumbo. The simplification in the language together with Maude's support for code rewriting has allowed us to make rapid progress. We discuss the model in detail, the kinds of optimizations we have obtained, and the impact on the Jumbo project.