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

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1230

2003

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.

---

BibTeX citation:

@techreport{Henzinger:CSD-03-1230,
    Author= {Henzinger, Thomas A. and Kirsch, Christoph M. and Matic, Slobodan},
    Title= {Schedule-Carrying Code},
    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