Challenges In Validating Timing Constraints In Priority Driven Approach

Since the range of execution time of every job is known, the maximal and minimal schedules of J can easily be constructed when the release-time jitters are negligible. (We assume that release times of all jobs are fixed and known for this discussion. How releasetime jitters further complicate the validation problem is beyond the scope of our discussion here.) In contrast, its actual schedule is unknown because the actual values of the execution times are unknown.

Validation Algorithms and Their Performance
The validation problem has many variants, and that of validating static priority-driven systems is an important variant. Recent advances in real-time scheduling and schedulability analysis have lead to several sufficient conditions and analytical bounds. (A validation algorithm allows us to determine whether all jobs in a system indeed meet their timing constraints despite scheduling anomalies.) While there are mature validation algorithms and tools for static systems, good validation algorithms for dynamic, priority-driven systems are not yet available.

Specifically, we say that a validation algorithm is correct if it never declares that all timing constraints are met when some constraints may not be. The merits of (correct) validation algorithms are measured in terms of their complexity, robustness, and accuracy. A validation algorithm is good when it achieves a good balance in performance according to these conflicting figures of merit. For example, some existing validation algorithms run in constant time or O(n) time, where n is the number of tasks in the system. They are well suited for on-line acceptance tests to determine whether the system should admit a new task. More complex ones run in pseudopolynomial time but have better performance in the other dimensions.

Every rigorous validation algorithm is based on a workload model. When applied to a system, the conclusion of the algorithm is correct if all the assumptions of the model are valid for the system. A validation algorithm is said to be robust if it remains correct even when some assumptions of its underlying workload model are not valid. The use of a robust validation algorithm significantly reduces the need for an accurate characterization of the applications and the run-time environment and, thus, the efforts in analysis and measurement of the individual applications for the purpose of validating the workload model.We will see in later chapters that existing validation algorithms based on the periodic task model are robust to a great extent. Although the model assumes that jobs in each task are released periodically and execute for an equal amount of time, such a validation algorithm remains correct in the presence of release-time jitters, variations in job execution time, and other deviations from periodic behavior. It is only necessary for us to know the ranges of task parameters (e.g., the minimum interrelease time and maximum execution time of jobs), which are much easier to obtain and validate, either by timing analysis or measurement, than the actual values or probability distributions of the parameters.

Efficiency and robustness can be achieved easily if we are not concerned with the accuracy of the validation test. A validation algorithm is inaccurate when it is overly pessimistic and declares tasks unable to meet their timing constraints except when system resources are unduly underutilized. A scheduler using an inaccurate validation algorithm for an acceptance test may reject too many new tasks which are in fact acceptable. Because most validation algorithms are based on conditions that are sufficient but not necessary, they are all inaccurate to some degree, which is the price paid for the sake of robustness. The accuracy of a validation algorithm depends on whether the actual characteristics of the application systems are accurately captured by the underlying workload model. For example, validation algorithms that are based on the periodic task model are sufficiently accurate for applications, such as digital control and constant bit-rate voice and video communications, which are well characterized by the periodic task model but may have poor accuracy when used to validate applications that have widely varying processor-time demands and large release-time jitters.