SLICING REAL-TIME PROGRAMS FOR ENHANCED SCHEDULABILITY

In this article we present a compiler-based technique to help develop correct real-time systems. The domain we consider is that of multiprog rammed real-time applications, in which periodic tasks control physica l systems via interacting with external sensors and actuators. While a system is up and running, these operations must be performed as speci fied-otherwise the system may fail. Correctness depends not only on ea ch program individually, but also on the time-multiplexed behavior of all of the programs running together. Errors due to overloaded resourc es are exposed very late in a development process, and often at runtim e. They are usually remedied by human-intensive activities such as ins trumentation, measurement, code tuning and redesign. We describe a sta tic alternative to this process, which relies on well-accepted technol ogies from optimizing compilers and fixed-priority scheduling. Specifi cally, when a, set of tasks are found to be overloaded, a scheduling a nalyzer determines candidate tasks to be transformed via program slici ng. The slicing engine decomposes each of the selected tasks into two fragments: one that is ''time critical'' and the other ''unobservable. '' The unobservable part is then spliced to the end of the time-critic al code, with the external semantics being maintained. The benefit is that the scheduler may postpone the unobservable code beyond its origi nal deadline, which can enhance overall schedulability. While the opti mization is completely local, the improvement is realized globally, fo r the entire task set.