Bounding the stack size of interrupt -driven programs

A widely-used class of real-time, reactive, embedded systems is called interrupt-driven systems [8]. Programming of interrupt-driven systems is notoriously difficult and error-prone. This is because such systems are usually equipped with a small amount of memory while being asked to handle as many external interrupts as possible. Furthermore, such systems demand responsive handling of interrupts. Due to the fact that an interrupt may happen at any time, a handler can be interrupted by another interrupt, making the stack grow in order to store the context information for the current handler. The problem with such a scenario is that it may lead to stack overflow. Traditionally, this problem has been avoided by forbidding other interrupts during the execution of the handler. However, doing this puts tremendous limit on the number of interrupts which can be handled. Moreover, it greatly increases the response time for interrupts, resulting in an inefficient system and causing a potential predictability problem: the handling of an interrupt can be so long that the next interrupt occurrence is missed. In this thesis, we lay a formal framework, which, to the best of our knowledge, is the first in the field, to ensure stack boundedness, to give the tightest possible upper bound of the stack usage for interrupt-driven programs, and to guarantee predictability. Specifically, we develop two formal languages, interrupt calculus and periodic interrupt calculus, to capture the characteristics of interrupt-driven systems. We advocate intersection types and union types from the field of programming languages as a convenient vehicle to solve these problems. We base our analysis on two type systems which are designed for the two calculi. Our results show that the calculi demonstrate the desired capability for characterizing interrupt-driven programs. We show that once an interrupt calculus program type checks, there can be no stack overflow; we prove that the type inference problem for interrupt calculus is in PSPACE. For type-checked periodic interrupt calculus programs, we show that not only can the stack not overflow, but that it is also guaranteed that no single interrupt can be missed. In addition, our building of the types and type derivations of the periodic interrupt calculus programs unveils an equivalence relation between model checking and type systems, which may be of interest in its own right