Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsm!grunwald
From: grunwald@uiucdcsm.UUCP
Newsgroups: comp.arch
Subject: Re: H/W Write Buffers, S/W Synchron
Message-ID: <3300011@uiucdcsm>
Date: Mon, 16-Nov-87 13:02:00 EST
Article-I.D.: uiucdcsm.3300011
Posted: Mon Nov 16 13:02:00 1987
Date-Received: Thu, 19-Nov-87 05:05:24 EST
References: <1112@cadnetix.UUCP>
Lines: 42
Nf-ID: #R:cadnetix.UUCP:1112:uiucdcsm:3300011:000:900
Nf-From: uiucdcsm.cs.uiuc.edu!grunwald    Nov 16 12:02:00 1987


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.