Challenges in Validating Timing Constraints in Priority Driven Systems

Challenges in validating Timing Constraints in Priority Driven System

The priority driven scheduling has many advantages overclock driven scheduling. It is better suited for applications with varying time and resource requirement since it needs less information a priori. This schedule is easy to implement and has small runtime overheads when we use simple priority assignment but it is not widely used in hard real-time systems and safety critical systems where timing requirements need to be deterministic. It is also difficult to validate whether the algorithm needs the deadline or not. This is a problem called validation problem.

The validation problem states that given a set of jobs, the set of resources available to the jobs and scheduling ot resource access control algorithm to allocate processors and resources to the jobs, determined whether all the jobs meet their deadlines.

For example, consider two identical processors P1 and P2 and jobs J1, J2, J3 and J4 as shown below. Also, consider that the jobs can be preempted but cannot be migrated.

The timing diagram for the given jobs with the execution time J2 is 6.

The best case schedule for J4 when the execution is equal to 5. J4 can execute as early as 15 and its completion time jitter exceeds the upper limit of 4. This phenomenon is called scheduling anomalies.

The scheduling anomalies indicate that the schedule looks like right but it is not in real. It is an unexpected timing behavior of the priority driven system. The scheduling anomalies can also occur for non-preemptive jobs when schedule in single processors.

Offline versus online scheduling

A clock-driven scheduler simply makes use of a pre-computed schedule of all hard real-time jobs. This schedule is computed off-line before the system begins to execute. The computation is based on the knowledge of the release times and processor-time or resource requirements of all the jobs for all times. When the operation mode of the system changes, the new schedule specifying when each job in the new mode executes is also pre-computed and stored for use. In this case, it is said that the scheduling is done off-line, and the pre-computed schedules are off-line schedules.

The main disadvantage of off-line scheduling is inflexibility. Offline scheduling is possible only when the system is deterministic which means that the system provides some ï¬Âxed set(s) of functions and that the release times and processor-time or resource demands of all its jobs are known and do not vary or may vary only slightly. However, for a deterministic system, off-line scheduling has many advantages. One of the advantages being the deterministic timing behavior of the resultant system. The complexity of the scheduling algorithm(s) used for this purpose is not important because the computation of the schedules is done off-line. (Liu, online versus offline scheduling 77-78)

Competitiveness of On-Line Scheduling.

It is said that scheduling is done on-line, if the scheduler makes each scheduling decision without having knowledge about the jobs which will be released in the future; the parameters of each job become known to the on-line scheduler only after the job is released. The priority-driven algorithms are on-line algorithms. The admission of each new task depending on the outcome of an acceptance test which is based on the parameters of the new task and tasks that were admitted earlier. This type of acceptance test is on-line. So, the future workload of an on-line scheduling is unpredictable. An on-line scheduler can accommodate dynamic variations in user demands and resource availability. The price of the flexibility and adaptability is a reduced ability for the scheduler to make the best use of system resources. The scheduler cannot make optimal scheduling decisions without prior knowledge about future jobs, while a clairvoyant scheduler can that knows about all future jobs.(Liu, online versus offline scheduling 78)

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.