Giotto provides a time-triggered programmer’s model for the implementation of embedded control systems with hard real-time constraints. Giotto’s precise semantics and predictabil- ity make it suitable for safety-critical applications. Giotto is based around the idea that time-triggered task invocation together with time-triggered mode switching can form a useful programming model for real-time systems. To substantiate this claim, we describe the use of Giotto to refactor the software of a small, autonomous helicopter. The ease with which Giotto expresses the existing software provides evidence that Giotto is an appropriate programming language for control systems. Since Giotto is a real-time programming language, ensuring that Giotto programs meet their deadlines is crucial. To study precedence-constrained Giotto scheduling, we first examine single-mode, single-processor scheduling. We extend to an infinite, periodic setting the classical problem of meeting deadlines for a set of tasks with release times, deadlines, precedence constraints, and preemption. We then develop an algorithm for scheduling Giotto programs on a single processor by representing Giotto programs as instances of the extended scheduling problem. Next, we study multi-mode, single-processor Giotto scheduling. This problem is different from classical scheduling problems, since in our precedence-constrained approach, the deadlines of tasks may vary depending on the mode switching behavior of the program. We present conditional scheduling models which capture this varying-deadline behavior. We develop polynomial-time algorithms for some conditional scheduling models, and prove oth- ers to be computationally hard. We show how to represent multi-mode Giotto programs as instances of the model, resulting in an algorithm for scheduling multi-mode Giotto programs on a single processor. Finally, we show that the problem of scheduling Giotto programs for multiple net- worked processors is strongly NP-hard.
1 - 237
Horowitz B. Giotto: A time-triggered language for embedded programming. 2003:1-237.
Horowitz, B. (2003). Giotto: A time-triggered language for embedded programming. University of California, Berkeley.
Horowitz, Benjamin. “Giotto: A Time-Triggered Language for Embedded Programming.” University of California, Berkeley, 2003.
B. Horowitz, “Giotto: A time-triggered language for embedded programming,” University of California, Berkeley, 2003.
Horowitz B. 2003. Giotto: A time-triggered language for embedded programming. University of California, Berkeley.
Horowitz, Benjamin. Giotto: A Time-Triggered Language for Embedded Programming. University of California, Berkeley, 2003, pp. 1–237.