Preemption Ceiling Protocol

Preemption Ceiling Protocol

Preemption Levels of Jobs and Periodic Tasks

The parameter that is used to indicate the possibility that a job J_i will preempt another job is called preemption level and represented by ψ. The preemption levels of jobs are functions of their priorities and released times. According to a valid preemption level assignment, for every pair of jobs J_i and j_k, the preemption level ψ of J_i being equal to or higher than preemption level ψ of J_k means that it is never possible for J_k to preempt J_i. That is validating condition: if π_i is higher than π_k & r_i > r_k then ψ_i is higher than ψ_k.

This can be illustrated with the help of the following example having jobs J1, J2, J3, J4 & J5 with release times r₄<r₅<r₃<r₁<r₂.

Definitions of Protocols and Duration of Blocking

A preemption-ceiling protocol makes decisions on whether to grant a free resource to any job based on the preemption level of the job in a war similar to the priority-ceiling protocol. This protocol also assumes that the resource requirements of all the jobs are known a priori. After assigning preemption levels to all the jobs, the preemption ceiling of each resource is determined. Specifically, when there is only 1 unit of each resource, that is assumed is the case here, the preemption ceiling ψ(R) of a resource R is the highest preemption level of all the jobs which require the resource. For the example in the figure above (i.e a schedule according to the preemption -ceiling protocol) the preemption ceiling of Black is 1, while the preemption ceiling of Shaded is 2.

The ceiling of the system ψ'(t) at any time t is the highest preemption ceiling of all the resources which are in use at t. When the context is clear and there is no chance of confusion, we will simply refer to ψ'(t) as the ceiling of the system. Ω is used to denote a preemption level that is lower than the lowest preemption level among all jobs since there is no possibility of confusion. When all the resources are free, it is said that the ceiling of the system is Ω. (Liu 310-311)

Rules of Basic Preemption-Ceiling Protocol

1 and 3

The scheduling rule (i.e., rule 1) and priority inheritance rule (i.e., rule 3) are the same as the corresponding rules of the priority-ceiling protocol.

Allocation Rule:

Whenever a job J requests 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. (a) If J’s preemption level ψ(t) is higher than the current preemption ceiling ψ'(t) of the system, R is allocated to J. (b)If J’s preemption level ψ(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 preemption ceiling is equal to ψ(t); otherwise, J’s request is denied, and J becomes blocked.

Controlling Access to multiple Unit Resource

We describe an extension to priority ceiling and preemption ceiling protocol so that they can deal with the general case where there may be more than 1 unit of each resource type.

Priority (Preemption) Ceilings of Multiple Unit Resource

The first step in extending the priority-ceiling protocol is to modify the definition of the priority ceilings of resources. We let ∏(R_i, k), for k ≤ v_i, denote the priority ceiling of a resource R_i when k out of the ν_i (≥ 1) units of R_i are free. If one or more jobs in the system require more than k units of R_i, ∏(R_i ,k) is the highest priority of all these jobs. If no job requires more than k units of R_i, ∏(R_i ,k) is equal to Ωthe non-existing lowest priority. In this notation, the priority ceiling ∏(R_j) of a resource R_j that has only 1 unit is ∏(Rj,0).

Let k_i(t) denote the number of units of R_i that are free at time t. Because this number changes with time, the priority ceiling of R_i changes with time. The (current) priority ceiling of the system at time t is equal to the highest priority ceiling of all the resources at the time.(Liu 313)

For example,

Controlling Concurrent Accesses to Data objects

Data objects are a special type of shared resources. When jobs are scheduled preemptively, their accesses to (that is, reads & writes) data objects may be interleaved. For ensuring data integrity, it is common to require that the reads and writes be serializable. A sequence of reads and writes by a set of jobs is serializable if the effect produced by the sequence on all the data objects shared by the jobs is the same as the effect produced by a serial sequence (that is, the sequence of reads and writes when the jobs execute according to a non-preemptive schedule).(Liu 317-318)

Convex-Ceiling Protocol

The resource access-control protocols described in earlier sections do not ensure serializability. For eg., both the NPCS and PC (Priority- and Preemption-Ceiling) protocols allow a higher-priority job J_h to read and write a data object X between two disjoint critical sections of a lower-priority job J_l during which J_l also reads and writes X. The value of X thus produced may not be the same as the value produced by either of the two possible serial sequences (that is, all the reads and writes of J_l either proceed or follow that of J_h).

Motivation and Assumptions

Two Phase Locking (2PL) is a well-known way of ensuring serializability. According to this protocol, a job never requests any lock once it releases some lock. Thus, the critical sections of J₁ and J₃ in Figure below:

Satisfy this protocol, but the critical sections of J₂ do not. Under the 2PL protocol, J₂ would have to hold the locks on R₂ and R₃ until time 16. (This is because the critical sections are also required to be properly nested.) We can easily get concurrency-control protocols that not only ensure serializability but also prevent deadlock and transitive blocking by augmenting the protocols described in earlier sections with the two-phase locking rule. As a result, we have the NPCS-2PL and the PCP2PL protocols. The augmented protocols have an obvious shortcoming: prolonged blocking. Following the 2PL rule, a job may hold a data object even when it no longer require the object. As a result, it may block other jobs for a longer duration.

References

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