[comp.arch] H/W Write Buffers, S/W Synchron

grunwald@uiucdcsm.UUCP (11/16/87)

The paper ``A Fast Mutal Exclusion Algorithm'' by Leslie Lamport,
DEC-SRC publication number 7, provides the implementation and correctness
proof for a non-fair, arguably minimal-time-under-no-contention mutex
operation.

He argues, based on other data, that you want to reduce the time for a non-
contention situtation since that's your most common condition.

The algorithm presented is:

	start:

	b[i] := true
	x := i
	if (y != 0) {
		b[i] = false;
		await y == 0;
		goto start::
	}
	y := i;
	if (x != i) {
		b[i] := false;
		for j := 1 to N do 
			await not b[j]
		if (y != i) {
			await y == 0
			goto start
		}
	}

	critical section


	y := 0
	b[i] := false

Initiall, b[i] is fall. `i' is the processor number.

With no contention, this takes seven memory accesses. It is mutex & deadlock
free. A starvation-free algorithm takes one additional memory reference in
the abscence of contention.