APPLICATION OF REAL-TIME MONITORING TO SCHEDULING TASKS WITH RANDOM EXECUTION TIMES

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 execution time. Thus, scheduling tasks based on WET could result in a severe under-utilization of CPU cycles and under-estimation of the system's 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 processors (TMP's), and used to measure accurately, with minimal interference, the true execution time which consists of 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%, 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. A set of example tasks are experimentally measured in a simulated environment while varying their characteristics and the measured data are analyzed, demonstrating the utility and power of the proposed real-time monitor.