KUSP: Kernel/User Systems Programming

The Kernel and User Systems Programming (KUSP) work at the University of Kansas has a long history of research in a wide variety of areas relating to the design, implementation, modeling and performance evaluation of computer system components at both the user and kernel levels. Specific projects have varied over time, including improving native Linux support for real-time computations (UTIME and KURT-Linux), high performance emulation and simulation of ATM/TCP/UDP networks (PNNI and Proteus), tool support for network performance evaluation (Netspec), customized programming model support for sets of software agents negotiating resource allocation (ANTS), a unified programming model for computations implemented at both the hardware and software levels (Hybrid Threads), tools and Linux kernel modifications supporting highly configurable computation oriented scheduling and creation of customized programming models (Group Scheduling), and tools supporting fine-grain performance evaluation of user and kernel level computational activity in end-systems (Data Streams), and distributed systems (Global Time Line Construction).

The main theme of the KUSP work is precise computation description, control, and measurement that significantly exceeds the capabilities of current practice in most systems. The work is presented as modifications to Linux, but demonstrates methods that should apply to any other system to which those interested have source access and sufficient motivation to create equivalent modifications using these as a guide.

Role of the RT Preemption Patch

It is important to note that in recent years the KUSP Kernel code has been developed as a patch on top of the popular RT Preemption Patch for Linux. The initial, and in many ways the most essential, aspect of this patch is its modification of Linux concurrency control to allow for preemption of threads while inside the OS and holding resources. This significantly decreases the latency of switching a CPU from running one process to running another, which is an essential part of OS support for real-time computation. However, it also requires significant effort to avoid deadlocks and other forms of system freezes. This work includes code to track all owners of resources and threads waiting for those resources, as well as a protocol to permit resource owning threads to inherit the priorities of those waiting, which permits implementation of the popular Priority Inheritance Protocol.

Other elements of the RT-Patch have included: thread context for all hardware interrupts handlers (Hard-IRQ) and software interrupt handlers (Soft-IRQ), high resolution timers, and a variety of other features of interest in the general area of support for real-time computation within the standard Linux kernel. Over the last several years many features originally in the RT-Patch have been accepted into the mainline source, and many now in the patch are likely to be accepted in the future.

KUSP Extensions to Linux

The KUSP extensions to Linux address a variety of interesting research questions related to precise computation description, execution control, and measurement. In the area of system monitoring, the Data Streams (DS) subsystem provides the ability to flexibly configure the set of system events it can generate for processing both at experiment time and after the experiment is over.

The Group Scheduling (GS) subsystem provides the ability to group computation components and control their execution under a variety of standard Scheduling Decision Functions (SDF) or to be controlled by a customized SDF specific to the application. Controlling thread execution so precisely also requires complete integration of scheduling and concurrency control. GS significantly generalizes the RT-Patch’s priority inheritance based integration of concurrency control and scheduling to support arbitrary scheduling semantics, implementing a semantics we call proxy execution. GS permits the implementation of programming models with arbitrary semantics, which has been useful for implementing a variety of interesting application, including: frame progress for parallel video processing pipelines, guided execution which forces multi-threaded applications to follow a specific interleaving scenario,the PTIDES model for real-time Data Flow, and support for general data flow computations executing in an SMP system.

The Computation Component Set Manager (CCSM) supports tracking of arbitrary sets of computation components which is useful in a wide variety of ways. The CCSM permits associating names with threads, which is useful in creating analyzable and reproducable experiments, is useful in support of GS semantics definition for an application, can be used to specify how a computation’s behavior is measured, and can be used during discovery of a computation’s structure and integrated with GS to ensure the components are managed as a group.

Getting Started with KUSP

KUSP offers a variety of capabilities that can be useful in a wide range of situations. Those who wish to learn more and give the system a try should start with the initial sequence presented below. Those wishing to read in greater detail about individual KUSP subsystems can do so by following links at the bottom of this section.

Initial KUSP Setup and Tutorial Sequence:

Further Reading

Overview of KUSP subsystems and projects that have used or are using KUSP.

The following are links to documentation introducing KUSP subsystems and methods through a set of tutorial examples, followed by links to subsystem user and internals manuals. After that, are links for documents providing miscellaneous but useful data about KUSP, and description of some experiments using KUSP.

Tutorial Examples

DSUI: Data Streams User Interface

User-Level introduction to Data Streams concepts and example post-processing

  1. Simple DSUI : First KUSP example explains instrumentation and analysis of program behavior using events from the user-level.
  2. Signal Pipeline DSUI : More complex instrumentation example, still at the user level

DSKI: Data Streams Kernel Interface

Addition of Kernel-Level data for a more complex, and realistic example of recording and then analyzing application behavior

  1. Signal Pipeline DSKI : Adds the simplest possible set of kernel events to the Signal Pipeline DSUI example to note execution intervals of threads implementing pipeline stages
  2. Active Filtering: Adds use of an active filter to the previous example to filter out context-switch events for all threads except those specified as part of the experiment, thus greatly reducing the volume of data that must be processed

Group Scheduling: Highly Configurable Hierarchical scheduling Framework

Examples showing various ways to place applications under GS control and to configure the behavioral semantics of the applications by specifying a Group Scheduling Hierarchy. The first 5 examples are part of the Initial Group Scheduling Tutorial Sequence.

  1. Signal Pipeline GS PID : Places the Signal Pipeline threads under GS control using the simple PID based API
  2. Signal Pipeline GS CCSM : Places the Signal Pipeline threads under GS control using the simple CCSM API directly
  3. Signal Pipeline GS CCSM GM : Places the Signal Pipeline threads under GS control using a GS configuration file read by the Group Maker tool and CCSM support for thread naming
  4. Socket Pipeline GS : using sockets to pass actual messages among pipeline stages, with threads managed by pid using the group scheduling API.
  5. Socket Pipeline GS CCSM : using sockets to pass actual messages among pipeline stages, with threads managed by name using the group scheduling and ccsm APIs.
  6. Socket Pipeline GM : using sockets to pass actual messages among pipeline stages, with threads managed by name using a group scheduling configuration file..
  7. Balanced Progress Pipeline GS : Using a balanced progress SDF to control the socket pipeline stage execution

Computation Component Set Manager (CCSM)

Group Scheduling (GS)

KUSP Software Practicalities

Information required to write your own KUSP applications, to modify components of the KUSP system, and to add new KUSP components.

KUSP Work Spaces

All on-going project work and experiments have their own source trees in the “workspaces” area of the SVN source tree.

Multi-Processor General Data-Flow Programming Model

Multi-Processor General Data-Flow Programming Model

This programming model consists of the MPGD Group Scheduling SDF and associated infrastructure to support the programming model, including user libraries. The PM provides support for general data data-flow computations on single CPU and multi-processor platforms. The semantics controlling node (actor) execution within the computation can be configured to be application specific. However, the first driving example for this project is the PTides programming model semantics where timestamps are used to specify the release times of messages as eligible for processing by the receiving actor.

KUSP Group Members

KUSP Group Member Page

Indices and tables