Controlling Concurrent Accesses To Data Objects
CONTROLLING CONCURRENT ACCESSES TO DATA OBJECTS: Data objects are a special type of shared resources. When jobs are scheduled preemptively, their accesses to (i.e., reads and writes) data objects may be interleaved. To ensure 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 (i.e., the sequence of reads and writes when the jobs execute according to a nonpreemptive schedule).
Convex-Ceiling Protocol: The resource access-control protocols described in earlier sections do not ensure serializability. For example, both the NPCS and PC (Priority- and Preemption-Ceiling) protocols allow a higher-priority job Jh to read and write a data object X between two disjoint critical sections of a lower-priority job Jl during which Jl 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 (i.e., all the reads and writes of Jl either proceed or follow that of Jh ).
Motivation and Assumptions. A well-known way to ensure serializability is Two- Phase Locking (2PL). According to the 2PL protocol, a job never requests any lock once it releases some lock. Hence, the critical sections of J1 and J3 in Figure 8–1 satisfy this protocol, but the critical sections of J2 do not. Under the 2PL protocol, J2 would have to hold the locks on R2 and R3 until time 16. (This is because we also require the critical sections 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 PCP- 2PL 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 consequence, it may block other jobs for a longer duration.
The convex-(priority-) ceiling protocol [Naka] described below is another extension of the priority-ceiling protocol. It is an improvement over the PCP-2PL protocol because it reduces the duration of blocking. In the description below, we assume that there is only one of each data object.
Priority-Ceiling Function. As with the PCP-2PL protocol, the convex-ceiling protocol assumes that the scheduler knows a priori the data objects require by each job and, therefore, the priority ceiling of each data object. In addition, each job notifies the scheduler immediately after it accesses each of its required objects for the last time. We call a notification sent by a job Ji after it accesses Rk for the last time the last access notification for Rk by Ji and the time of this notification the last access time of Rk by Ji .
For each job Ji in the system, the scheduler generates and maintains the following two functions: the remainder priority ceiling, RP(Ji , t) and the priority-ceiling function, (Ji , t). RP(Ji , t) is the highest priority ceiling of all data objects that Ji will require after time t.When Ji is released, RP(Ji , t) is equal to the highest priority ceiling of all data objects required by the job. The scheduler updates this function each time when it receives a last access notification from Ji . When the job no longer requires any object, its remainder priority ceiling is Ω.
When each job Ji starts execution, its priority-ceiling function (Ji , t) is equal to Ω. When Ji is allowed to access an object Rk for the first time, (Ji , t) is set to the priority ceiling (Rk ) of Rk if the current value of (Ji , t) is lower than (Rk ). Upon receiving a last access notification from Ji , the scheduler first updates the function RP(Ji , t). It then sets the priority-ceiling function (Ji , t) of the job to RP(Ji , t) if the remainder priority ceiling is lower.
Figure 8–23 gives an example. The job Ji requires three data objects: Dotted, Black, and Shaded. Their priority ceilings are 1, 2, and 3, respectively. Figure 8-23(a) shows the time intervals when the job executes and accesses the objects. The two functions of the job are shown in Figure 8–23(b). At time 0, RP(Ji , 0) is 1. The job sends last access notifications at times 4, 6, and 8 when it no longer needs Dotted, Black, and Shaded, respectively. The scheduler updates RP(Ji , t) at these instants; each time, it lowers the remainder priority ceiling to the highest priority ceiling of all objects still required by the job in the future. Initially, (Ji , t) is equal to Ω. At time 2 when Ji accesses Black for the first time, its priority ceiling function is raised to 2, the priority ceiling of Black. (Ji , t) stays at 2 until time 3 and is raised to 1 at time 3 when Ji accesses Dotted for the first time. At time 4 when the last access notification for Dotted is received, (Ji , t) is set to 2, the updated value of RP(Ji , t). Similarly, (Ji , t) is lowered to 3 and Ω at the last access times 6 and 8 of Black and Shaded, respectively.
By definition, RP(Ji , t) is a nonincreasing function of t . The priority-ceiling function (Ji , t) first raises as the job is allowed to access more and more data objects. Its value, once lowered, never rises again. In other words, the priority-ceiling function of every job is “two-phase”; it has only one peak.
Definition and Capability. As with the priority-ceiling protocol, at any time t when the scheduler receives a request to access an object R for the first time from any job J, it computes the system ceiling ˆ (t). ˆ (t) is equal to the highest priority of the priority-ceiling functions of all the jobs in the system. The convex-ceiling protocol defined by the following rules.
Rules of Convex-Ceiling Protocol
1. Scheduling Rule: At any time, jobs that are not suspended are scheduled on the processor in a preemptive, priority-driven manner. Upon its release, the current priority of every job Ji is its assigned priority πi . It executes at this priority except when the inheritance rule is applied.
2. Allocation Rule: When a job Ji requests to access a data object R for the first time,
(a) if Ji ’s priority is higher than the system ceiling Π (t), J is allowed to continue execution and access R;
(b) if Ji ’s priority is not higher than Π (t),
i. if Π (t) is equal to (Ji , t), Ji is allowed to access R;
ii. otherwise, J is suspended.