Mixed-Criticality Processing Pipelines

Dionisio de Niz1, Bjorn Andersson1, Hyoseung Kim2, Mark Klein1, Linh Thi Xuan Phan3 and Raj Rajkumar1
1Carnegie Mellon University
2U.C. Riverside
3University of Pennsylvania


While a number of schemes exist for mixedcriticality scheduling in a single processor setting, no solution exists to cover the industry need for end-to-end scheduling across multiple processors in a pipeline. In this paper, we present an end-to-end zero-slack rate-monotonic scheme (ZSRM) based on realtime pipelines, called the ZSRM pipeline scheduler, that addresses this need. Under ZSRM, each task is associated with a parameter called zero-slack instant, and whenever a higher-criticality job has not finished at its zero-slack instant relative to its arrival time, all jobs of lower criticality are suspended to meet the deadline of the higher-criticality job. We develop a new schedulability test and algorithm for computing the zero-slack instants of tasks scheduled across a pipeline.

Full Text (PDF)