We consider end-to-end latency specifications for hard real-time embedded systems. We introduce a discrete-event programming model generalizing such specifications, and address its schedulability problem for uniprocessor systems. This turns out to be rather idiosyncratic, involving complex, time-dependent release predicates and precedence constraints, quite unlike anything we have seen in the hard real-time computing literature. We prove the optimality of the earliest-deadline-first scheduling policy, and provide an algorithmic solution, reducing the schedulability problem to a reachability problem for timed automata.

Ptolemy‡is an open-source and extensible modelling and simulation framework. It offers heterogeneous modeling capabilities by allowing different models of computation, both untimed and timed, to be composed hierarchically in an arbitrary fashion. This paper proposes a formal semantics for Ptolemy that is modular in the sense that atomic actors and their compositions are treated in a unified way. In particular, all actors conform to an executable interface that contains four functions: fire (produce outputs given current state and inputs); postfire (update state instantaneously); deadline (how much time the actor is willing to let elapse); and time-update (update the state with the passage of time). Composite actors are obtained using composition operators that in Ptolemy are called directors. Different directors realise different models of computation. In this paper, we formally define the directors for the following models of computation: synchronous- reactive, discrete event, continuous time, process networks and modal models.

High-performance concurrent libraries, such as lock-free data structures and custom synchronization primitives, are notoriously difficult to write correctly. Such code is often implemented without locks, instead using plain loads and stores and low-level operations like atomic compare-and-swaps and explicit memory fences. Such code must run correctly despite the relaxed memory model of the underlying compiler, virtual machine, and/or hardware. These memory models may reorder the reads and writes issued by a thread, greatly complicating parallel reasoning. We propose RELAXER, a combination of predictive dynamic analysis and software testing, to help programmers write correct, highly-concurrent programs. Our technique works in two phases. First, RELAXER examines a sequentially-consistent run of a program under test and dynamically detects potential data races. These races are used to predict possible violations of sequential consistency under alternate executions on a relaxed memory model. In the second phase, RELAXER re-executes the program with a biased random scheduler and with a conservative simulation of a relaxed memory model in order to create with high probability a predicted sequential consistency violation. These executions can be used to test whether or not a program works as expected when the underlying memory model is not sequentially consistent. We have implemented RELAXER for C and have evaluated it on several synchronization algorithms, concurrent data structures, and parallel applications. RELAXER generates many executions of these benchmarks with violations of sequential consistency, highlighting a number of bugs under relaxed memory models.

When a running program becomes unresponsive, it is often impossible for a user to determine if the program is performing some useful computation or if it has entered an infinite loop. We present LOOPER, an automated technique for dynamically analyzing a running program to prove that it is non-terminating. LOOPER uses symbolic execution to produce simple non-termination arguments for infinite loops dependent on both program values and the shape of heap. The constructed arguments are verified with an off-the-shelf SMT solver. We have implemented our technique in a prototype tool for Java applications, and we demonstrate our technique's effectiveness on several non-terminating benchmarks, including a reported infinite loop bug in open-source text editor jEdit. Our tool is able to dynamically detect infinite loops deep in the execution of large Java programs with no false warnings, producing symbolic arguments that can aid in debugging non-termination.