Schedule-Carrying Code

Thomas A. Henzinger, Christoph M. Kirsch and Slobodan Matic

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1230
February 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1230.pdf

The interactions of real-time tasks with each other and with the environment can be specified in a platform-independent machine language called E code. E code is time safe if it can be scheduled on a given platform so that all its timing constraints are met. For specifying static, dynamic, and conditional schedules, we propose again an executable machine language, called S code. A compiler for real-time programs, then, consists of a platform-independent and a platform-dependent part. The former produces E code; the latter generates S code that ensures the time-safe execution of the E code. The run-time system consists of an implementation of the E machine, which interprets E code that manages interrupts from the environment, and of the S machine, which interprets S code that manages task execution on the processors.

Generating nonpreemptive schedules for periodic tasks is NP-hard. However, for E code that specifies periodic tasks, and S code that specifies a corresponding nonpreemptive schedule, we show that time safety can be checked in linear time. This suggests the notion of schedule-carrying code (SCC), where E code is annotated with S code before being sent to an execution host. The host, if it does not trust the sender, can then check the time safety of the code at a cost that is far below the cost of generating a feasible schedule.


BibTeX citation:

@techreport{Henzinger:CSD-03-1230,
    Author = {Henzinger, Thomas A. and Kirsch, Christoph M. and Matic, Slobodan},
    Title = {Schedule-Carrying Code},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5349.html},
    Number = {UCB/CSD-03-1230},
    Abstract = {The interactions of real-time tasks with each other and with the environment can be specified in a platform-independent machine language called E code. E code is time safe if it can be scheduled on a given platform so that all its timing constraints are met. For specifying static, dynamic, and conditional schedules, we propose again an executable machine language, called S code. A compiler for real-time programs, then, consists of a platform-independent and a platform-dependent part. The former produces E code; the latter generates S code that ensures the time-safe execution of the E code. The run-time system consists of an implementation of the E machine, which interprets E code that manages interrupts from the environment, and of the S machine, which interprets S code that manages task execution on the processors. <p>Generating nonpreemptive schedules for periodic tasks is NP-hard. However, for E code that specifies periodic tasks, and S code that specifies a corresponding nonpreemptive schedule, we show that time safety can be checked in linear time. This suggests the notion of schedule-carrying code (SCC), where E code is annotated with S code before being sent to an execution host. The host, if it does not trust the sender, can then check the time safety of the code at a cost that is far below the cost of generating a feasible schedule.}
}

EndNote citation:

%0 Report
%A Henzinger, Thomas A.
%A Kirsch, Christoph M.
%A Matic, Slobodan
%T Schedule-Carrying Code
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1230
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5349.html
%F Henzinger:CSD-03-1230