A lock word is true sharing: every contender needs its logical state, so padding can remove unrelated fields from its line but cannot make the word private. What the lock algorithm decides is how many coherence messages each spin and each handoff costs. Put the lock word X alone in its line, 0 = free and 1 = held, with memory = 0 initially. Use the course model with MSI: H collects the Inv-Acks, and a line held in M by another cache takes the four-hop route of Three-Hop Versus Four-Hop. An atomic swap or fetch-add needs M, as in Atomics and RMW at the Cache.
Take N contending cores: C0 holds the lock and C1 to C(N-1) wait. Three message costs cover every case. A request that finds the line in another cache's M costs four messages (GetM or GetS, Fwd, Data to H, Data). A GetM that finds k sharers costs 2 + 2k (GetM, k Inv, k Inv-Ack, Data), so the upgrade from shared with one sharer costs four. A GetS with no M holder costs two (GetS, Data).
Lock | While C0 holds the lock | At each release | Cost per handoff |
|---|---|---|---|
Test-and-set: every spin is an atomic swap | Every attempt is a GetM. With two or more waiters the line is always in another waiter's M, so each attempt costs four messages and steals the line. The first attempt steals it from C0. A lone waiter keeps M after its first steal and then spins locally. | C0 has lost the line, so its release store is another four-message GetM, and the next swap takes the line from C0 again. | Unbounded: four messages per failed attempt for as long as the lock is held. |
Test-and-test-and-set: spin on a load, swap only when X reads 0 | After one GetS miss each, the waiters spin on S copies: zero messages. | C0's upgrade (GetM, N - 1 Inv, N - 1 Inv-Ack, Data: 2N messages), then every waiter's GetS miss (2N), then the atomic GetMs: the winner invalidates N - 1 copies (2N), the N - 2 losers' failed swaps cost four each, and the losers miss again (2N - 4). | 12(N - 1) messages for N of 4 or more: O(N) per handoff, O(N^2) for N handoffs. |
Ticket lock: fetch-add a ticket on arrival, spin on now-serving | Waiters spin on S copies of now-serving: zero messages. | The holder's upgrade still invalidates N - 1 copies and every waiter misses again, but only the waiter whose ticket matches proceeds, so there are no failed atomics. | O(N), without the failed-swap term. It also serves waiters in arrival order. |
Queue lock (MCS or CLH) | Each waiter spins on its own flag line, held in S: zero messages. | The holder writes only its successor's flag: a GetM with one sharer (four messages), then the successor's GetS miss from the holder's M (four). | Eight messages, whatever N is: O(1) transfers per handoff. |
Queue locks: MCS from Mellor-Crummey and Scott, "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors" (ACM TOCS, 1991); CLH from Craig (1993) and Magnusson, Landin and Hagersten (1994). Real implementations differ in detail; the message counts here are for the course model.
For N = 4 the test-and-test-and-set release costs 8 + 8 + 8 + 8 + 4 = 36 messages: C0's upgrade invalidating three copies, three misses (four for the first, which finds C0 in M, then two each), the winner's GetM invalidating three copies, two failed swaps at four each, and the losers' re-reads (four for the first, the last loser still holds M). The same handoff with a queue lock costs eight. The block below runs the four algorithms on a small directory model and checks each cost from N = 2 to 8.
# Course model: MSI, H collects Inv-Acks, dirty data takes the four-hop route.
# Simplified: each request completes atomically (no transient states or races),
# H updates its record at once, and only messages are counted, not latency.
class Home:
def __init__(self):
self.st, self.val = {}, {} # (core, line) -> "S" or "M"
def others(self, c, line):
return {o: s for (o, l), s in self.st.items() if l == line and o != c}
def load(self, c, line):
if (c, line) in self.st:
return 0 # hit on an S or M copy
held = self.others(c, line)
self.st[(c, line)] = "S"
for o, s in held.items():
if s == "M": # GetS, Fwd-GetS, Data to H, Data
self.st[(o, line)] = "S"
return 4
return 2 # GetS, Data
def getm(self, c, line): # stores and atomics need M
if self.st.get((c, line)) == "M":
return 0
held = self.others(c, line)
for o in held:
del self.st[(o, line)]
self.st[(c, line)] = "M"
if "M" in held.values(): # GetM, Fwd-GetM, Data to H, Data
return 4
return 2 + 2 * len(held) # GetM, Inv and Inv-Ack each, Data
def swap(self, c, line): # test-and-set writes 1
n = self.getm(c, line)
old, self.val[line] = self.val.get(line, 0), 1
return n, old
def held_by_c0(n, test_first, spins=3):
h = Home(); h.swap(0, "X") # C0 acquires the lock
if test_first:
for w in range(1, n):
h.load(w, "X") # warm-up misses
cost = [h.load(w, "X") if test_first else h.swap(w, "X")[0]
for _ in range(spins) for w in range(1, n)]
return cost, h
def ttas_release(h, holder, waiters):
m = h.getm(holder, "X"); h.val["X"] = 0 # release: the holder's upgrade
m += sum(h.load(w, "X") for w in waiters) # every waiter misses, sees 0
results = [(w,) + h.swap(w, "X") for w in waiters]
m += sum(n for _, n, _ in results) # one wins, the rest fail
losers = [w for w, _, old in results if old == 1]
m += sum(h.load(w, "X") for w in losers) # losers spin again
return m, results[0][0], losers
per, total = {}, {}
for n in range(2, 9): # C0 holds, C1..C(n-1) wait
tas, _ = held_by_c0(n, False)
assert sum(tas) > 0 and tas[0] == 4 # the first spin steals from C0
assert all(c == 4 for c in tas) or n == 2 # with 2+ waiters, every spin
spin, h = held_by_c0(n, True)
assert sum(spin) == 0 # S copies: no messages
per[n] = ttas_release(h, 0, list(range(1, n)))[0]
_, h = held_by_c0(n, True)
holder, waiters, total[n] = 0, list(range(1, n)), 0
while waiters: # every waiter acquires once
m, holder, waiters = ttas_release(h, holder, waiters)
total[n] += m
q = Home() # queue lock: one flag per waiter
assert sum(q.load(w, ("flag", w)) for w in range(1, n)) == 2 * (n - 1)
assert sum(q.load(w, ("flag", w)) for w in range(1, n)) == 0
assert q.getm(0, ("flag", 1)) + q.load(1, ("flag", 1)) == 8
assert all(per[n] == 12 * (n - 1) for n in range(4, 9))
assert [per[n + 1] - per[n] for n in range(2, 8)] == [10, 14, 12, 12, 12, 12]
second = [total[n + 2] - 2 * total[n + 1] + total[n] for n in range(3, 7)]
assert second == [12] * 4 # quadratic over all handoffs
print("PASS: test-and-set spins cost 4 messages, TTAS spins cost 0 but 12(N-1) per release, a queue lock costs 8 per handoff")Backoff after a failed swap spaces out test-and-set attempts and thins the release storm, but it trades traffic for handoff latency and changes only which request H serves next, not what it returns: see fairness on a contended line.
An eventual-acquisition claim needs eventual release by the holder, continued representation of the waiting request, reliable delivery, finite protected resources and fair service of relevant actions. No finite backoff delay alone establishes those conditions. A permanently held lock is not repaired by a faster coherence path.
84 and 8. The test-and-test-and-set release invalidates seven S copies, all seven waiters miss, the winner invalidates seven copies again and six swaps fail: 12(N - 1) = 84. The queue-lock holder touches only its successor's flag line: four messages to write it and four for the successor to read it.
Not as independent updates to the same logical word. Its coherence and atomicity order still serialize the conflicting effect; placement may change cost, not remove that dependency.