Basic Priority Ceiling Protocol

Basic Priority Ceiling Protocol

The priority-ceiling protocol extends the priority-inheritance protocol to prevent deadlocks and to further reduce the blocking time. This protocol makes two key assumptions:

1. The assigned priorities of all jobs are fixed.
2. The resources required by all jobs are known a priori before the execution of any job begins

Definition of the Basic Priority-Ceiling Protocol

It can be defined by the following rules:

Scheduling Rule:

3. At its release time t, the current priority π(t) of every job J is equal to its assigned priority. The job remains at this priority except under the condition stated in rule 3.
4. Every ready job J is scheduled preemptively and in a priority-driven manner at its current priority π(t).

Allocation Rule:

Whenever a job J requests a resource R at time t, one of the following two conditions occurs:

1. R is held by another job. J’s request fails and J becomes blocked.
2. R is free.
3. If J’s priority π(t) is higher than the current priority ceiling π’(t), R is allocated to J.
4. If J’s priority π(t) is not higher than the ceiling π’(t) of the system, R is allocated to J only if J is the job holding the resource(s) whose priority ceiling is equal to π’(t); otherwise, J’s request is denied, and J becomes blocked.

Priority-Inheritance Rule:

When J becomes blocked, the job J_l which blocks J inherits the current priority π(t) of J. J_l executes at its inherited priority until the time when it releases every resource whose priority ceiling is equal to or higher than π(t); at that time, the priority of J_l returns to its priority π_l(t) at the time t when it was granted the resource(s).

Example below shows the schedule of the system of jobs.

Deadlock Avoidance by Priority-Ceiling Protocol

One of the way to avoid deadlock is to use the ordered resource technique i.e. the priority ceiling of the resources imposes a linear order on all the resources.

Consider three jobs J₁, J₂ and J₃ with priorities 1, 2 and 3 respectively. The release times are 3.5, 1 and o and their critical sections are orities1, 2, and 3, respectively. Their release times are 3.5, 1, and 0 and their critical sections are [Dotted; 1.5], [Black; 2[Shaded; 0.7]], and [Shaded; 4.2 [Black; 2.3]], respectively. The timing diagram for these jobs is shown below:

The executions of jobs can be described as follows:

1. At time t = 0, only T₃ is released and therefore, it starts execution. When J₃ requests shaded at time t = 0.5, no resource is allocated at that time and therefore J₃’s request is granted. When job J₂ becomes ready at time t = 1, it preempts J₃.
2. At time t = 2.5, J₂ request black. Because shaded is already allocated to J₃ and has priority ceiling of the system 2, which is equal to the priority of J₂. According to (ii) of part (b) of rule 2, J₂ is denied block even though the resource is free. Since, J₂ is blocked, J₃ inherits the priority 2, resumes and starts to execute.
3. When J₃ request black at time t = 3, it is holding the resource whose priority ceiling is the current ceiling of the system. According to (ii) of part (b) of rule 2, J₃ is granted the resource black and it continues to execute.
4. J₃ is preempted again at time t = 3.5 when J₁ becomes ready. When J₁ request dotted at time t = 4.5, the resource is free and the priority of J₁ is higher than the ceiling of system (i) of part (b) of rule 2 applies and the dotted resource is allocated to J₁ which complete at 7.2 and the process continues.

Stack Based Priority Ceiling (Ceiling Priority) Protocol

Stack-based priority ceiling protocol is simpler than the priority ceiling protocol but has the same worst-case performance. Two different definitions of stack based protocols can be obtained based on two different motivations.

1. To provide stack sharing capability
2. To simplify the priority ceiling protocol

Motivation and Definition of Stack Sharing Priority Ceiling Protocol

One of the resource in the system is the runtime stack. Each job may have its own runtime stack, but where the number of jobs is large. It may be necessary to share a common runtime stack in order to reduce the overall memory demand. The space in the stack is allocated to the jobs contiguously in the last in first out (LIFO) manner. Therefore, when a job executes, its stack space is on the top of the stack. The space is freed only when the job completes. When the job J is preempted , the preempting job has the stack space above J. J can resume execution only after all the jobs holding the stack space leave J’s stack space on the top of the stack.

In this protocol, deadline can occur. The causes of deadline can be:

1. When a high priority job preempts the low priority job and occupies the top of the stack space.
2. When the low priority job has already been using the resource that is required by the high priority job.

To ensure the deadlock-free sharing of the runtime stack among the jobs, no job should ever blocked because it is denied some resources once it begins execution. This condition leads to the modified version of priority ceiling protocol called stack based priority ceiling protocol. This protocol allows to share the runtime stack among the jobs if they never self-suspend.

The rules defining the basic stack-based priority ceiling protocol are

0 rule – Update of the current rule

Whenever all the resources are free, the ceiling of the system is Ω. The ceiling π’(t) is updated each time a resource is allocated or freed.

Scheduling Rule:

After a job is released, it is blocked from starting execution until its assigned priority is higher than the current ceiling π’(t) of the system. At all times, jobs that are not blocked are scheduled on the processor in a priority-driven, preemptive manner according to their assigned priorities.

Allocation Rule:

Whenever a job requests a resource, it is allocated the resource.

Consider the following jobs

Definition of ceiling Priority Protocol

The worst case performance of the stack based and basic priority ceiling protocols are the same. But the stack-based protocol is simpler and has a lower context switch overhead. Due to these reasons, the stack based protocols are preferred if the job never self-suspend. When the resource requirement of the jobs are known, the jobs holding any resource are allowed to execute at the highest priority of all the jobs requiring the resource. This is called ceiling priority protocol.

The rules defined by this protocol are

Scheduling protocol

1. Every job executes at its assigned priority when it does not hold any resource. Jobs of the same priority are scheduled on the FIFO basis.
2. The priority of each job holding any resource is equal to the highest of the priority ceilings of all resources held by the job.

Allocation Rule:

Whenever a job requests a resource, it is allocated the resource.

Use of Priority Ceiling Protocol in Dynamic Priority Systems

In a dynamic priority systems, the priorities of periodic task change with the time, while the resources required by each task remain constant. As a result, the priority ceilings of the resources may change with time. For some dynamic systems, we can use the priority ceiling protocol to control resources accesses provided by the priority ceiling of each resource and the ceiling of the system is updated each time the priority change.

Implementation of Priority Ceiling Protocol in Dynamic Priority System

The priority ceiling protocol can be used in job level fixed priority system by updating the priority ceiling of all the resources whenever a new job is released. 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. After this, priority ceilings of all the resources are updated based on the new priorities of the task and the ceiling of the system is updated based on the new priority ceiling is used until it is updated again when the next job releases. This protocol is considered effective because 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.

Consider the following three tasks.

T₁ = (0.5, 2.0, 0.2; [Black; 0.2]),

T₂ = (3.0, 1.5; [Shaded; 0.7]), and

T₁ = (5.0, 1.2; [Black; 1.0 [Shaded; 0.4])

The priority ceilings of the two resources black and shaded are updated at 0, 0.5, 2.5, 3, 4.5, 5, 6 and so on. The priorities of the ready jobs are indicated by positive integers with one (1) having highest priority. The following timing diagram illustrates the use of basic priority ceiling protocol in an EDF system of above jobs.

The timing diagram can be described as follows:

1. At time t = 0, only two jobs J_2,1 and J_3,1 are released. Since, the deadline of J_2,1 is earlier than the deadline of J_3,1, i.e. 3 & 5. Therefore, J₁ has priority 1 & J₃ has 2. The priority of the resources black and shaded are 2 & 1 respectively. Therefore, job J_2,1 starts execution and since no resources has been used in the beginning, the priority ceiling of the system is omega (Ω). At time t = 0.3, J_2,1 acquires resources shaded and the ceiling of the system moves from omega to 1.
2. At time t = 0.5, the first job J_1,1 of T₁ is released and it has the highest priority i.e. 1. The priorities of J_2,1 & J_3,1 are 2 & 3 respectively. Since, J_2,1 requires the resource black, the ceiling of the resource also becomes 1 and the ceiling of the shaded becomes 2. Therefore, the resource black is granted to the high priority job J_1,1 and it completes by the time t = 0.7. After that the job J_2,1 continues to execute and the ceiling of the system falls back to 2 which is equal to the priority ceiling of resource shaded.
3. At time t = 2.5, J_1,2 is released and its priority is 1 because it has the earliest deadline, the priority of the ready job J_3,1 is 2. This update of the task priorities have no change in priority ceiling of the resource. Since the ceiling of the system at t = 2.5 is 1, job J_1,2 becomes blocked. It can be the resource block at t = 2.9.
4. At time t = 3, T₁ & T₂ have the jobs ready for execution and the priorities are 1 & 2 respectively. Therefore, the priority ceiling of the system remains unchanged until the next release of 4.5.
5. At time t = 4.5, job J_1,3 is released and its deadline is 6.5 which is later than the J_2,2 i.e. 6. Therefore, the priority of J_2,2 becomes 1 and J_1,3 becomes 2. This change in the priorities of task causes the change in the priority ceiling of black and shaded to 2 & 1.
6. At time t = 5, J_3,2 is released and starts execution because there are no other ready jobs. The priority ceilings of both the resources are 1 which remains same until t = 6.
7. At time t = 6, both J_2,3 and J_3,2 are ready & J_2,3 has earlier deadline. Therefore, the same cycle starting from t = 0 is repeated.

References

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