Application of Real-Time Monitoring to Scheduling Tasks with Random

A real-time monitor is employed to aid in scheduling tasks with random execution times in a real-time computing system. Scheduling algorithms are usually based on the worst-case execution time (WET) of each task. Due to data-dependent loops and conditional branches in each program and resource sharing delay during execution, this WET is usually difficult to obtain and could be several orders of magnitude larger than the true exception time. Thus, scheduling tasks based on WET could result in a severe underutilization of CPU cycles and under-estimation of systems schedulability.To alleviate the above problem, we propose to use a real-time monitor as a scheduling aid. The real-time monitor is composed of dedicated hardware, called Test and Measurement Processor (TMP), and used to measure accurately, with minimal interference, the true execution time which consists of the pure execution time and resource sharing delay. The monitor is a permanent and transparent part of a real-time system, degrades system performance by less than 0.1 percent, and does not interfere with the host system's execution.Using the measured pure execution time and resource sharing delay for each task, we have developed a mechanism which reduces the discrepancy between the WET and the estimated execution time. This result is then used to decide at an earliest possible time whether or not a task can meet its deadline.

ICSI Technical Report TR-89-028

Technical Report