We have designed, implemented, and evaluated AtomCaml, an extension to Objective Caml that provides a synchronization primitive for atomic (transactional) execution of code. A first-class primitive function of type (u...
详细信息
We have designed, implemented, and evaluated AtomCaml, an extension to Objective Caml that provides a synchronization primitive for atomic (transactional) execution of code. A first-class primitive function of type (unit -> 'a) -> 'a evaluates its argument (which may call other functions, even external C functions) as though no other thread has interleaved execution. Our design ensures fair scheduling and obstruction-freedom. Our implementation extends the Objective Cam] bytecode compiler and run-time system to support atomicity. A logging-and-rollback approach lets us undo uncompleted atomic blocks upon thread pre-emption, and retry them when the thread is rescheduled. The mostly functional nature of the Caml language and the Objective Caml implementation's commitment to a uniprocessor execution model (i.e., threads are interleaved, not executed simultaneously) allow particularly efficient logging. We have evaluated the efficiency and ease-of-use of AtomCaml by writing libraries and microbenchmarks, writing a small application, and replacing all locking with atomicity in an existing, large multithreaded application. Our experience indicates the performance overhead is negligible, atomic helps avoid synchronization mistakes, and idioms such as condition variables adapt reasonably to the atomic approach.
Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvi...
详细信息
Transient faults that arise in large-scale software systems can often be repaired by re-executing the code in which they occur. Ascribing a meaningful semantics for safe re-execution in multi-threaded code is not obvious, however. For a thread to correctly re-execute a region of code, it must ensure that all other threads which have witnessed its unwanted effects within that region are also reverted to a meaningful earlier state. If not done properly, data inconsistencies and other undesirable behavior may result. However, automatically determining what constitutes a consistent global checkpoint is not straightforward since thread interactions are a dynamic property of the program. In this paper, we present a safe and efficient checkpointing mechanism for concurrent ML (CML) that can be used to recover from transient faults. We introduce a new linguistic abstraction called stabilizers that permits the specification of per-thread monitors and the restoration of globally consistent checkpoints. Safe global states are computed through lightweight monitoring of communication events among threads (e.g. message-passing operations or updates to shared variables). Our experimental results on several realistic, multithreaded, server-style CML applications, including a web server and a win-dowing toolkit, show that the overheads to use stabilizers are small, and lead us to conclude that they are a viable mechanism for defining safe checkpoints in concurrent functional programs.
THUDS is a highly available distributed computer system whose communication software is composed of two layers: communication layer and service support layer. This paper gives the design and analysis of both layers. F...
详细信息
THUDS is a highly available distributed computer system whose communication software is composed of two layers: communication layer and service support layer. This paper gives the design and analysis of both layers. For the communication layer, the protocol is described on the basis of its state transition diagrams. For the service support layer, process communication, synchronization, and scheduling, which constitute its basic functions, are discussed.
High-level specification of patterns of communications such as protocols can be modeled elegantly by means of session types [Honda, K., V. Vasconcelos and M. Kubo, Language primitives and type discipline for structure...
详细信息
High-level specification of patterns of communications such as protocols can be modeled elegantly by means of session types [Honda, K., V. Vasconcelos and M. Kubo, Language primitives and type discipline for structured communication-based programming, in: Proc. of ESOP'98, LNCS (1998), pp. 122–138]. However, a number of examples suggest that session types fall short when finer precision on protocol specification is required. In order to increase the expressiveness of session types we appeal to the theory of correspondence assertions [Clarke, E. and W. Marrero, Using formal methods for analyzing security, Information Survivability Workshop (1998), Gordon, A. and A. Jeffrey, Typing correspondence assertions for communication protocols, in: Seventeenth Conference on the Mathematical Foundations of programming Semantics (MFPS 2001), number 45 in ENTCS (2001)]. The resulting type discipline augments the types of long term channels with effects and thus yields types which may depend on messages read or written earlier within the same session. We prove that evaluation preserves typability and that well-typed processes are safe. Also, we illustrate how the resulting theory allows us to address the shortcomings present in the pure theory of session types. Keywords: concurrent programming, pi-calculus, type systems, session types, correspondence assertions.
In this paper real-time simulation of water distribution system is presented. Purpose of the system is to help understanding water distribution system performances, to prepare plans for normal and emergency conditions...
详细信息
In this paper real-time simulation of water distribution system is presented. Purpose of the system is to help understanding water distribution system performances, to prepare plans for normal and emergency conditions and dispatcher training. Special attention is paid to software design which allows real-time model behavior, multi-user interaction, ad hoc processing of input commands, and various CRT displays. Software architecture is parallel: the system is divided into three independent processes (input, output, calculation). Processes execute concurrently and special primitives are defined for their communication and synchronization. Man-machine interface is designed to meet requirement of user-friendly interaction. The system provides two regimes of work and several speeds of simulation. It records simulation history, allows repetition of a previous simulation starting from the arbitrarily chosen time point, and provides efficient tools for monitoring and analyzing behavior of the large scale water distribution system.
Implementation of atomic actions by means of concurrent programming constructs is discussed. It is shown that several trade-offs between performance and reliability may be obtained when an atomic action is defined thr...
详细信息
Implementation of atomic actions by means of concurrent programming constructs is discussed. It is shown that several trade-offs between performance and reliability may be obtained when an atomic action is defined through the composition of constructs and not as an elementary one Several alternative implementations are then discussed with reference to the ECSP concurrent language Emphasis is placed on process structuring, parallel activation and termination
Traditional methods for specifying and reasoning about concurrent systems work for rear-time systems. Using TLA (the temporal logic of actions), we illustrate how they work with the examples of a queue and of a mutual...
详细信息
Traditional methods for specifying and reasoning about concurrent systems work for rear-time systems. Using TLA (the temporal logic of actions), we illustrate how they work with the examples of a queue and of a mutual-exclusion protocol. In general, two problems must be addressed: avoiding the real-time programming version of Zeno's paradox, and coping with circularities when composing real-time assumption/guarantee specifications. Their solutions rest on properties of machine closure and realizability.
When explicit control predicates rather than dummy variables are used, the Owicki-Gries method for proving safety properties of concurrent programs can be strengthened, making it easier to construct the required progr...
详细信息
When explicit control predicates rather than dummy variables are used, the Owicki-Gries method for proving safety properties of concurrent programs can be strengthened, making it easier to construct the required program annotations.
We present the first shape analysis for multithreaded programs that avoids the explicit enumeration of execution-interleavings. Our approach is to automatically infer a resource invariant associated with each lock tha...
详细信息
We present the first shape analysis for multithreaded programs that avoids the explicit enumeration of execution-interleavings. Our approach is to automatically infer a resource invariant associated with each lock that describes the part of the heap protected by the lock. This allows us to use a sequential shape analysis on each thread. We show that resource invariants of a certain class can be characterized as least fixed points and computed via repeated applications of shape analysis only on each individual thread. Based on this approach, we have implemented a thread-modular shape analysis tool and applied it to concurrent heap-manipulating code from Windows device drivers.
Today, synchronization of shared data structures in multithreaded software is mostly implemented using locks, which leads to difficult to understand and error-prone programs. Software Transactional Memory allows lock-...
详细信息
Today, synchronization of shared data structures in multithreaded software is mostly implemented using locks, which leads to difficult to understand and error-prone programs. Software Transactional Memory allows lock-free concurrent programming by handling the synchronization of shared variables implicitly. We show how to implement different instances of the widely-used taskpool pattern (global and private taskpools with and without task stealing) using both lock-based and lock-free synchronization mechanisms in the functional programming language Haskell. We examine their performance using two synthetic algorithms and LU decomposition and report our observations about parallel performance and the complexity of the implementation. Our results show that lock-free taskpools are not only on par with lock-based implementations concerning parallel performance but are also easier to comprehend and develop.
暂无评论