Skedbooks
←
Real Time Systems

Use Of Priority-ceiling Protocol In Dynamic Priority Systems

USE OF PRIORITY-CEILING PROTOCOL IN DYNAMIC-PRIORITY SYSTEMS: While both versions of the priority-ceiling protocol are relatively simple to implement and perform well when periodic tasks are scheduled on a fixed-priority basis, it is another matter in a dynamic-priority system. In a dynamic-priority system, the priorities of the periodic tasks change with time while the resources required by each task remain constant. As a consequence, the priority ceilings of the resources may change with time.

As an example, let us look at the EDF schedule of two tasks T1 = (2, 0.9) and T2 = (5, 2.3) in Figure 6–4. In its first two periods (i.e., from time 0 to 4), T1 has priority 1 while T2 has priority 2, but from time 4 to 5, T2 has priority 1 and T1 has priority 2. Suppose that the task T1 requires a resource X while T2 does not. The priority ceiling of X is 1 from time 0 to 4 and becomes 2 from time 4 to 5, and so on.

For some dynamic systems, we can still use the priority-ceiling protocol to control resource accesses provided we update the priority ceiling of each resource and the ceiling of the system each time task priorities change. This is the approach taken by the dynamic-priorityceiling protocol proposed by Chen and Lin [ChLi]. As it will become evident shortly, except for this update, the priority-ceiling protocol can be applied without modification in job-level fixed-priority systems. In such a system, the priorities of jobs, once assigned, remain fixed with respect to each other. In particular, the order in which jobs in the ready job queue are sorted among themselves does not alter each time a newly released job is inserted in the queue. This assumption is true for systems scheduled on the EDF and LIFO basis, for example.

Implementation ofPriority-Ceiling Protocol in Dynamic-Priority Systems: One way to implement the basic priority-ceiling protocol in a job-level fixed-priority system is to update the priority ceilings of all resources whenever a new job is released. Specifically, when a new job is released, its priority relative to all the jobs in the ready queue is assigned according to the given dynamic-priority algorithm. Then, the priority ceilings of all the resources are updated based on the new priorities of the tasks, and the ceiling of the system is updated based on the new priority ceilings of the resources. The new priority ceilings are used until they are updated again upon the next job release. Chen and Lin [ChLi] showed that the protocol remains effective (i.e., it prevents deadlock and transitive blocking and no job is ever blocked for longer than the length of one critical section) in a job-level fixed-priority system.

The example in Figure 8–18 illustrates the use of this protocol in an EDF system. The system shown here has three tasks: T1 = (0.5, 2.0, 0.2; [Black; 0.2]), T2 = (3.0, 1.5; [Shaded; 0.7]), and T1 = (5.0, 1.2; [Black; 1.0 [Shaded; 0.4]). The priority ceilings of the two resources Black and Shaded are updated at times 0, 0.5, 2.5, 3, 4.5, 5, 6, and so on. We use consecutive positive integers to denote the priorities of all the ready jobs, the highest priority being 1.2 In the following description, we focus primarily on how priority ceilings of resources and ceiling of the systems are updated and leave to you many details on how the priority-ceiling protocol works to produce the schedule segment shown in this figure. To emphasize that the priority ceiling of a resource Ri may change with time, we denote it by t (Ri ).

  1. At time 0, there are only two ready jobs, J2,1 and J3,1. J2,1 (and hence T2) has priority 1 while T3 has priority 2, the priority of J3,1. The priority ceilings of Black and Shaded are 2 and 1, respectively. Since J2,1 has a higher priority, it begins to execute. Because no resource is in use, the ceiling of the system is Ω. At time 0.3, J2,1 acquires Shaded, and the ceiling of the system rises from Ω to 1, the priority ceiling of Shaded.
  2. At time 0.5, J1,1 is released, and it has a higher priority than J2,1 and J3,1. Now the priorities of T1, T2, and T3 become 1, 2, and 3, respectively. The priority ceiling t (Black) of Black is 1, the priority of J1,1 and T1. The priority ceiling t (Shaded) of Shaded becomes 2 because the priority of J2,1 and T2 is now 2. The ceiling of the system based on these updated values is 2. For this reason, J1,1 is granted the resource Black. The ceiling of the system is 1 until J1,1 releases Black and completes at time 0.7. Afterwards, J2,1 continues to execute, and the ceiling of the system is again 2. When J2,1 completes at time 1.7, J3,1 commences to execute and later acquires the resources as shown.
  3. At time 2.5, J1,2 is released. It has priority 1, while J3,1 has priority 2. This update of task priorities leads to no change in priority ceilings of the resources. Since the ceiling of the system is at 1, J1,2 becomes blocked at 2.5. At time 2.9, J3,1 releases Black, and J1,2 commences execution.
  4. At time 3.0, only T1 and T2 have jobs ready for execution. Their priorities are 1 and 2, respectively. The priority ceilings of the resources remain unchanged until time 4.5.
  5. At time 4.5, the new job J1,3 of T1 has a later deadline than J2,2. (Again, T3 has no ready job.) Hence, the priority of T1 is 2 while the priority of T2 becomes 1. This change in task priorities causes the priority ceilings of Black and Shaded to change to 2 and 1, respectively.
  6. At time 5 when J3,2 is released, it is the only job ready for execution at the time and hence has the highest priority. The priority ceilings of both resources are 1. These values remain until time 6.

 

 

 

 

 

 

 

 

 

7. At time 6, both J2,3 and J3,2 are ready, and the former has an earlier deadline. We now have the same condition as at time 0.

In a system with ρ resources, each of which is required by n periodic tasks on average, the time required to update the priority ceilings of all resources is O(ρ) each time a new job is released. This is a significant amount of overhead. For systems where the release-time jitters are negligible, we can save this run-time overhead by precomputing and storing the priority ceilings of all the resources for every time interval between consecutive releases of all N jobs in the entire hyperperiod. Each time a new job is released, we use the precomputed priority ceilings of the interval beginning from the release time of the job. The storage overhead for this purpose is O(Nρ).

It is easy to see that the stack-based priority-ceiling protocol can also be used without modification for job-level fixed-priority assignments. Each time a new job is released, the question is whether its priority is sufficiently high for it to join the ready job queue.