Optimal unified data allocation and task scheduling for real-time multi-tasking systems

Many real-time (RT) embedded systems can ben-efit from a memory hierarchy to bridge the proces-sor/memory speed gap. These RT embedded systems usually utilize a cacheless architecture to avoid the time variability which complicates the timing analysis essen-tial for RT systems. In the absence of a cache the burden of allocating the data objects to the memory hierarchy is on the programmer/compiler. There has been much research into allocating data objects into the memory hierarchy for efficient execution. However, ex-isting methods have limited scope and ignore some as-pects of RT multitasking embedded systems. In this paper we propose a synergistic, optimal ap-proach to allocating data objects and scheduling real-time tasks for embedded systems. We allocate data using integer linear programming (ILP) to minimize each task’s worst-case execution time (WCET), then perform preemption threshold scheduling (PTS) on the tasks to reduce stack memory requirements while still meeting hard RT deadlines. The memory reduction of PTS allows these steps to be repeated. The data objects now require less memory, so more can fit into faster memory, further reducing WCET. The increased slack time can be used by PTS to reduce preemptions further, until a fixed point is reached. We evaluate the technique with several levels of data object granularity using both synthetic workloads and a realtime benchmark and find it to be highly effective. 1