Intel ITANIUM ARCHITECTURE - SOFTWARE DEVELOPERS VOLUME 3 REV 2.3, Руководство пользователя

Страница: 778 / 1898

2:530 Volume 2, Part 2: MP Coherence and Synchronization
2.4.4 Lamport’s Algorithm
Like Dekker’s algorithm, Lamport’s algorithm [L85] also provides mutual exclusion for
critical sections of code. Lamport’s algorithm is very simple and, in the case of
non-contested locks, only requires two read and two write memory accesses to enter
the critical section. The algorithm uses two shared variables,
x
and
y
, and a shared
array, b, that identify the process entering and using the critical section. Figure 2-7
presents Lamport’s algorithm 2 [L85].
Lamport’s algorithm expects that a processor that enters the critical section performs
the set of operations: S = {store
x
, load
y
, store
y
, load
x
}
1
. To enforce this ordering,
the Itanium architecture requires a memory fence in the middle of the {store
x
, load
y
}
sequence and the {store
y
, load
x
} sequence. No combination of ordered semantics on
the operations in each of these sequences will guarantee the correct ordering.
It is not possible for the store
y
in the second sequence to pass the load
y
in the first
sequence because of the data dependency from the load
y
to the compare and branch.
If the processor reaches the store
y
in the second sequence, the load of
y
from the first
sequence must be visible. Likewise, it is not possible for memory operations in the
critical section to move ahead of the final load
x
because of the data dependency
between this load and the compare and branch that guards the critical section.
The accesses to the b array allow the algorithm to correctly handle contention for the
lock. In such cases, the algorithm backs off and re-trys.
Figure 2-6. Dekker’s Algorithm in a 2-way System
// The flag_me variable is zero if we are not in the
// synchronization and critical section code and non-zero
// otherwise; flag_you is similarly set for the other processor.
// This algorithm does not retry access to the
// resource if there is contention.
//
dekker:
mov r1 = 1 ;; // my flag = 1 (i want access!)
st8 [flag_me] = r1
mf ;; // make st visible first
ld8 r2 = [flag_you] ;; // is other’s flag 0?
cmp.ne p1, p0 = 0, r2
(p1) br.cond.spnt cs_skip ;; // if not, resource in use
cs_begin:
// critical section code goes here...
cs_end:
cs_skip:
st8.rel [flag_me] = r0 ;; // release lock
1. There are some additional operations on the b array that are interposed in this sequence when con-
tention for the resource occurs.