University of Houston

Real-time systems are those in which the correctness of program is measured both by its logical output as well as ability to complete execution within strict time limits. The implementation of real-time systems is usually done in traditional imperative programming languages like C or Java. Functional or declarative programming is another programming paradigm where programs are executed as functions and state and mutable data is not used. Reactive systems are a special class of real-time systems which continuously maintain interaction with their environment and execute tasks based on events triggered in their environment. Functional Reactive Programming (FRP) is a declarative approach for modeling and building reactive systems. FRP has been shown to be an expressive formalism for building graphics, robotic, and vision applications. Priority-based FRP (P-FRP) is a formalism that allows preemption of executing programs and guarantees real-time response. Since functional programs cannot maintain state and mutable data, changes made by programs that are preempted have to be rolled back. In P-FRP, a higher priority task can abort the execution of a lower priority task, and the aborted lower priority task will have to restart execution after the higher priority task has completed. Current real-time research is focused on the standard preemptive of non-preemptive modules of execution and several state-of-the-art methods have been developed to analyze the real-time guarantees of these systems. Unfortunately, due to its transactional nature where preempted tasks are aborted and have to restart, the execution semantics of P-FRP does not fit into the standard definitions of preemptive or non-preemptive execution. The abort and eventual restart in P-FRP makes the response time of a lower priority task completely dependent on the execution pattern of higher priority tasks which makes the analysis of this system more complicated than preemptive or non-preemptive systems. Hence, several mathematical and algorithm based techniques that have been developed over the past several years cannot be applied for ascertaining real-time guarantees in P-FRP. Techniques to determine such guarantees are required before this technology can be practically applied in safety and mission critical devices. In this work, we present several techniques that can be used to ascertain real-time properties of P-FRP. The techniques developed by us cover a whole range of real-time issues ranging from uniprocessor to multi-processor scheduling, accurate exponential and approximate polynomial time methods, to optimal energy use in battery powered devices. Apart from presenting algorithm based approaches for computing response time we also apply formal methods of Timed Automata and Time Petri Nets in determining real-time guarantees. To collect experimental results through our methods we had to run several simulation studies which were done using software. The development of a simulation environment as well as algorithms which were used in experimental analysis has also been discussed. Though developed for P-FRP, the benefits of this work also extend to real-time studies of other transaction based execution models like lock-free execution, hardware and software transactional memory and atomic critical sections in Java and other programming languages.