NSF Support
This research is supported by the National Science Foundation, grant CCF-0615035.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Society is increasingly dependent on complex mission-critical engineered systems such as supervisory control and data access systems for power grid management, industrial control systems for automated manufacturing, and medical device systems for patient monitoring and treatment. The potential failure of these systems puts safety, health, and economic concerns of vital national interest in jeopardy. To protect these vital interests, it is crucial that these engineered systems maintain rigorous control over physical properties such as power flows, drug release rates, and spatial positioning. Furthermore, controlling these physical properties requires precise control over systemic properties such as communication and computation latencies, sensor sampling rates, and actuation response times. The system software that manages these engineered systems must monitor, evaluate, and respond to changes in the engineered system, while also coordinating computation, communication, sensing and actuation resources across heterogeneous and time-varying application requirements.
The current lack of integration among the following semantic domains limits the ability of system developers to exert precise control over physical and systemic properties of engineered systems: (1) application: application-specific quality of service (QoS) semantics required to ensure that high-fidelity control over the engineered system can be maintained; (2) system software: the QoS semantics of the system software components used to implement the application; (3) resource management: rigorous run-time resource management to ensure application-level QoS requirements can be met within the context of the system software QoS semantics; and (4) behavioral information: information about the observed run-time behavior of the system software and the engineered system itself. The problem that this research addresses is the disjointed manner in which these highly inter-dependent semantic domains are handled in the current state of the art, which limits the system developers’ ability to address key current challenges, such as preventing (or at least mitigating) cascading power grid system failures.
Our research group at the University of Kansas, in collaboration with researchers at Washington University in St. Louis and the University of Missouri-Rolla, is developing a revolutionary approach to system software for complex systems in which application QoS requirements, system software QoS semantics, resource management, and behavioral information are integrated through (1) mutually consistent formal and verifiable models of each semantic domain; (2) novel policies and mechanisms for exerting precise run-time control across semantic domains; and (3) detailed, efficient, and timely collection and dissemination of behavioral information to improve run-time control fidelity. Through rigorous integration of these semantic domains we aim to achieve a much greater correspondence among their respective semantics, and establish a foundation for revolutionary improvements in the state of the art, particularly for increases in system accuracy and reliability in producing desired behaviors (and in preventing undesired behaviors) in complex mission-critical engineered systems.
Investigators
Douglas Niehaus, Associate Professor, Electrical Engineering and Computer Science Department, is PI for collaborative research at the University of Kansas.
Christopher Gill, Associate Professor of Computer Science and Engineering, is PI for this research at Washington University in St. Louis.
Bruce McMillin, Professor, Department of Computer Science, is PI and Mariesa Crow, Professor, Department of Electrical and Computer Engineering, is co-PI for collaborative research at the University of Missouri-Rolla.
Students
Dillon Hicks, Undergraduate
Dillon has considerable general programming experience, and started working with the project at the beginning of the Summer of 2009. He has, so far, concentrated on Python based tools, including a GUI based tool for describing Group Scheduling hierarchies, which is useful in writing specialized applications and in describing and/or viewing the scheduling semantics of the system as a whole. He also took the lead in converting the KUSP software source tree from using the venerable but complex Autotools for configuring and building software, to using the increasingly popular and significantly simpler CMake. This is important in making the software more accessible, and increasing the possibility that the RT-Preemption Patch Group will adopt some or all of the KUSP software as its intended real-time scheduling testbed. Dillon is expanding his expertise to the Data Streams Port-Processing framework, and is considering ways to have it effectively use multiple CPUs in SMP machines.
Jared Straub, Graduate Student
Jared began working on this project at the beginning of February 2009. Jared has worked on rewriting the code for several subsystems to make it simpler, clearer, better commented, and more robust. Beyond improving the quality of the existing code, Jared’s reworking of the Data Streams subsystem has improved its concurrency control, improved support for Active Filters processing streams of events at run-time in for various reasons including, reduction of the instrumentation effect, dynamic measurement adjustment, and Discovery of Computation Structure. Jared has also implemented a deferred execution context using a work queue to expand the set of actions Active filters can take, since events are generated in any context, and some actions by active filters such as Group Scheduling SDF state variable or group membership modification can be forbidden in the context generating the triggering event. The result is a more robust system capable of supporting a wider range of run-time actions, thus increasing the range of system semantics that can be supported. Jared has also implemented the Computation Component Set Manager (CCSM) which tracks sets of system components and permits associating a string (name) with each set. This is convenient for creating a name space within which application components and sets of applications can be described when specifying a Group Scheduling hierarchy. The CCSM supports callback routine registration that can help Group Scheduling dynamically track computation components to improve scheduling control of applications, but can also be used by Data Streams to push state data from sockets, or any other portion of the system into GS in support of arbitrary programming models. Jared also serves as the lead system programmer providing guidance and advice to the other student participating in the project.
Tyrian Phagan, Graduate Student
Tyrian has been working unfunded with Noah Watkins on Noah’s Google Summer of Code project, which has used Tyrian’s Advanced Operating Systems class project from Spring 2009 as a starting place for implementing the PTides programming model under GS. In the class, Tyrian investigated implementation of Multi-Processor Generalized Data-Flow (MPGD) Group Scheduling (GS) Scheduling Decision Function (SDF). In this project he took the PTides model as a driving example, because it required obtaining state information from sockets connecting the actors within the PTides data-flow computation. After comparing several methods, a Data Streams based PUSH approach generating an event when data arrives at the socket, and an active filter then publishes the relevant state data to the GS SDF was selected. Tyrian and Noah are adapting this approach to support several types of sockets, beyond the simple socket pairs of his class project, and investigating ways of supporting user-level shared memory connections using imaginative library based implementations.
Noah Watkins, Graduate Student
Noah Watkins is a principle developer of Group Scheduling and the principle developer of Proxy Execution and related methods of integrating scheduling and concurrency control. Early in the project Noah worked on methods of creating a strong correspondence between the measured behavior of a computation and the behavior predicted by a model of the application. Noah worked primarily with the IF toolkit, but also experimented with Spin and studied BOGOR with the same intent. The results of this approach,however, were negative. It proved to be extremely difficult, with the main problem being that the modeling tools perform essentially breadth-first within the state space for the application, which makes it quite complicated to assemble a narrative corresponding to a single scenario We found that while it was possible to do so for comparatively simple example, the scalability of the approach was poor. As a result of these findings, we decided to approach the goal of increasing the correspondence between modeled and measured behavior from the other side. Noah this switched to working on the integration of concurrency control and scheduling under the KUSP Group Scheduling Framework. While this problem turned out to be at least twice as difficult as we anticipated, it was ultimately successful. As a result, of this excellent work by Noah, the KUSP software can now support direct implementation of programming models with a wide range of semantics. By direct implementation we mean that the state variable available for scheduling decisions and the logic used to make those decisions directly and clearly represent the desired semantics under which an application should execute. Noah left KU in Fall 2008 to start the PhD program at UC Santa Cruz. He received a Google Summer of Code award for 2009 to support working with Edward Lee’s Ptolemy group at UC Berkeley to implement direct support for the PTides programming model in Group Scheduling, including a wide range of connections among actors and a range of options for application semantics.
Devin Turner, Undergraduate
Devin joined the KUSP group as a relatively inexperienced undergraduate, offering to work unpaid in return for experience, and did a fine job accumulating and extending the library of Data Streams Post-Processing Filters and on the set of initial Data Streams Tutorial Examples. He learned a good deal, and demonstrated a good understanding of the code he worked on.
Work at the University of Kansas has concentrated on significantly improving the precision of run-time control of computation behavior and the precision with which computation and system behavior can be measured. Our approach to improving control precision has produced a system in which a wide range of application behavior semantics can be defined and used, and in which several different application semantics can coexist. The increase in precision of control is both complemented by an increase in precision of behavioral measurement and supported by it.
Increase in precision of control is complemented by an increase in measurement precision because the methods used to measure performance must match the level of precision used to control behavior in order to be able to measure behavior at a level sufficient to verify that the intended behavior, for which control is being exerted, is in fact being produced. The increase in precision supports the increased precision of control, in some cases, because it enables the use of system event data to be used as computation state data upon which the scheduling subsystem bases control decisions.
The increased precision of control and measurement, in turn, complements the third major goal of this research, which is to increase the precision with which system and application behavior can be formally modeled to improve our ability to verify system behavior. The result is a system in which application programming models can be designed with their formal verifiability in mind, implemented using the system support for semantic configurability, and have the measurement of their run-time behavior configured to match the semantics of their programming model to complement formal verification with empirical measurement.
The ability of the KUSP system to support implementation of programming models with essentially arbitrary semantics rests on two major components: Group Scheduling and Proxy Execution. Group scheduling for specifying scheduling hierarchies within which threads can be members of one or more groups, with an arbitrary Scheduling Decision Function which selects the “best” among the group members when invoked at run-time. Groups can be used to represent any semantics desired, but in our work so far we have primarily used them to represent the set of threads comprising an application-level computation. The SDF for such a group is thus in charge of ensuring the best possible execution of the application as a whole.
Since groups can be members of groups, as well as threads, a scheduling hierarchy for the system as a whole can be created. The lowest level groups in the hierarchy represent the group of threads implementing an application, while the higher level groups describe the semantics under which the system chooses among applications. The set of SDFs that we have implemented for GS include static and dynamic priority, CPU Share of two different types, explicit plan under which precise execution intervals for every thread are specified on a cyclic time line, Earliest Deadline First, and application-specific scenarios such as balanced progress.
We have exercised this capability to create programming models with arbitrary semantics in several ways, including: (1) a guided execution model under which arbitrary thread interleaving scenarios can be directly tests, (2) PTides real-time data flow model developed by Edward Lee and his students at UC Berkeley, (3) balanced progress for a set of pipeline computations that could be processing video, audio, or sensor data. We are continuing to develop a range of group scheduling examples that will explore the range of specialized semantics that are possible, and to exploring the uses to which those semantics may be put.
Guided Execution
The guided execution model is particularly useful for implementing the roughly 20 core regression tests for the Proxy Execution framework supporting generalized integration of scheduling and concurrency control under KUSP. These scenarios exercise specific interleavings among up to 7 threads as the use and block on a set of several semaphores. The guided execution framework can be used to implement tests for a wide range of concurrent software. Future work in this area will include using GDB to help manage scenario execution in cooperation with the SDF by setting breakpoints at thread context switch points, and modification of the GCC profiling option to insert instrumentation points crating a simple and efficient method for uniquely identifying the state of the application so that a given scenario can be recorded, replayed, or even synthesized.
PTides
The PTides programming model, developed within Edward Lee’s Ptolemy Group at UC Berkeley described a method of using an actor-based data flow computation to implement real-time applications under a formal model of the computation. Being actor based, the individual nodes of the data flow graph are influenced by other computations only though the receipt of messages. The PTides model goes further and calculates, under a formally derived mathematical model, the earliest safe release time for each message at each node. This work showed that GS can be used to implement programming models that can be formally modeled.
The formal basis and need for communication channel state used as part of the application state used to make scheduling decisions made the PTides model an excellent driving example for GS with Proxy execution. When a message arrives at an actor, its presence and its release time must be pushed to the GS SDF for use in deciding when each actor can execute. This required use to extend and refine the ability of the KUSP framework, including GS and Data Streams, to gather detailed performance data and made it available to other subsystems. In this case instrumentation points in the OS socket code note when messages arrive for actors, and give SDF-specific code a chance to run in order to extract the release time data. The state of each actor’s input queue, and the release times of each message on the queue, are the main state variables used by the PTides SDF to determine when each actor in the Data Flow graph implementing the application should execute.
Balanced Progress
This is an abstract example represent a class of computations including video processing, audio mixing, and sensor data analysis. In our abstract model, a given set of pipelines, often 6 but that is a selectable parameter are assumed to be processing parallel streams of messages, perhaps video frames. Each pipeline consists of the same number of stages, although they could have a different number if desired. Each stage of each pipeline is implemented with a thread, although we have occasionally tried a variation where each pipeline was implemented with a single thread. The application-specific semantics of this programming model are that each pipeline publishes a “progress state variable”, typically number of the frame most recently completed. The set of pipelines is described in a multi-level hierarchy with the lowest level group representing individual pipelines, and higher level SDFs deciding which pipeline should run next. Within a pipeline we usually adopt a priority based “drain” semantics under which later stages of a pipeline have better priority than earlier. Thus, when a message enters the pipeline, it drains to the end directly. The SDF selecting among pipelines chooses the one with the lowest value “progress state variable”. This will generally keep each pipeline within one or two frames of each other, but the largest tolerable gap between the fastest and slowest pipeline is tune-able.
To Appear, Invited Paper
Noah Watkins, Jared Straub, and Douglas Niehaus, “A Flexible Scheduling Framework Supporting Multiple Programming Models with Arbitrary Semantics in Linux”, Proceedings of the Real-Time Linux Workshop, Dresden Germany, September 2009.
The KUSP code and supporting documentation and tutorial examples is available through the KUSP WWW site: