A method for handling process overruns and underruns in real-time embedded systems

In this paper, we introduce a new method for effectively handling process underruns and overruns. The method computes a “latest-start-time schedule” for uncompleted periodic processes in which the beginning of the time slot of each uncompleted process is the “latest start time” for that process. At run-time, a run-time scheduling method uses the latest start times and the order of the end times of the time slots of the processes in the latest-start-time schedule, to handle process underruns and overruns while scheduling the processes. With this method, the only times at which a process is interrupted is when its deadline has expired, or when the latest start time of another process has been reached. Processes which overrun, are able to utilize any spare processor capacity in the system, including any additional unused processor capacity made available at run-time by process underruns, to maximize their chances of still meeting deadlines despite overrunning. The method thus increases both system utilization and robustness in the presence of inaccurate estimates of the worst-case computations of the real-time processes, while simultaneously satisfying important constraints and dependencies, such as offsets, release times, precedence relations, and exclusion relations.