next up previous
Next: Causal Logging Up: Protocol Description Previous: Overview

Dependency Tracking


The state intervals or the intervals of the LRC memory model can partially be ordered according to the happened-before-1 relation[3], as follows: An interval, I(i,a), is said to precede another interval, I(j,b), if I(i,a) ends with a release(x) and I(j,b) begins with the acquire(x) for the same lock x. An interval, I(i,a), also precedes its following intervals, and the happened-before-1 relation is also transitive. As for the barrier operation, the arrival to the barrier is considered as a release operation, and the departure from the barrier is considered as an acquire operation.


  
Figure 3: An Example of Dependency Tracking
[IMAGE ]


The vector clock associated with each interval reflects the precedence order in the happened-before-1 relation. For example, in Figure 3.(a), the vector clock for Acq(a) of pk must be the entry-wise maximum of the vector clocks of its preceding intervals. In the figure, the circled release operations denote the ones following a write operation, and the ones without any circle denote the release operations having no write operation before. Since the i-th entry of a vector clock Vi is updated only at the release time after a write operation, the acquire operations and the release operations without any circle need not be considered for the vector clock calculation. As a result, only the vector clocks for Rel(a) and Rel(b) of pi, Rel(c)of pj, and Rel(d) of pk need to be used to calculate the vector clock for Acq(a) of pk.


Figure 3.(b) represents the happened-before-1 relation as a graph, in which the release operations without any write are omitted since they do not influence the vector clocks. The arrow from a node NA to NB in the figure denotes the fact that NB precedes NA. Now, the vector clock for any acquire operation can be obtained as the entry-wise maximum of the release operations reachable from that acquire. Let P.Seti,a be the set of release operations preceding the a-th acquire operation of pi, and P.Seti,a* be the set of release operations which are reachable by a path from that acquire operation, but no other release operation exists before in that path. For example, in Figure 3.(b), P.Setk,Acq(a)= Rel(a), Rel(b), Rel(c), Rel(d) and P.Setk,Acq(a) = Rel(b), Rel(c), Rel(d) . Then, we can notice from the definition that the vector clock obtained from P.Seti,a* must be equal to the one obtained from P.Seti,a.


next up previous
Next: Causal Logging Up: Protocol Description Previous: Overview
Park TaeSoon
1999-11-30