From: agn@bovic.Eng.Sun.COM (Andreas G. Nowatzyk)
Newsgroups: comp.parallel
Subject: Re: Wanted: efficient software lock
Summary: Software Lock without atomic instructions
Keywords: mutual exclusion, memory models, locks
Date: 16 Dec 92 19:55:24 GMT
Reply-To: agn@bovic.Eng.Sun.COM
Organization: Sun Microsystems, Inc.

In article 7384@hubcap.clemson.edu, gottlieb@allan.ultra.nyu.edu (Allan Gottlieb) writes:
In article <1992Dec14.133731.18997@hubcap.clemson.edu> engler@cs.arizona.edu (Dawson R. Engler) writes:

>>   I need the algorithm for an efficient software lock that does not use
>>   atomic instructions (except perhaps assignment).  Fairness is unnecessary:
>>   in the situation I need this for, ~90% of the accesses are by the same
>>   process, and if the accesses are by someone else, they are allowed to
>>   have extra overhead.
>>   ...
>
> I would suggest peterson's algorithm.  For two processes it is simply
> Code for process 1		  Code for process 2
> ------------------		  ------------------
> P1Wants <- TRUE                   P2Wants <- TRUE
> Turn <- P2                        Turn <- P1
> while P2Wants and Turn=P2	    while P1Wants and Turn=P1
>
> critical section                  critical section
>
> P1Wants <- FALSE                  P2Wants <- FALSE
>
> (the while loops have empty bodies)
>
> For N processes (plus a proof and references) see Hofri's article in
> Operating Systems Review January 90.
>
> Allan Gottlieb

It might be of interest to note that the above algorithm (and many similar ones)
assume that memory operations are sequentially consistent (SC). There is a significant
performance advantage for systems that provide SC memory only when needed. These
weaker memory models generally require ordering or synchronization instructions
to appear SC.

For example, if Peterson's algorithm were used on a Sparc based multiprocessor,
without using an atomic instruction (swap, test-and-set or compare-and-swap), you
would still need ordering instructions. In the current version 8, this means adding a store-barrier instruction *and* a "swap" that is used as a load-barrier (it is not possible to implement this particular algorithm without "swap" or "ldstub" on V8
machines). Eventually, in the next version of the Sparc architecture, a generalized
ordering directive (membar) can be used to implement Peterson's Algorithm correctly
in all supported memory models (TSO, PSO and RMO).

[ The idealized Sparc assembly code below was verified with a tool that can prove
  assertions for small pieces of code for all future Sparc based
  multiprocessors. The critical section increments a shared variable [A] such
  that lack of mutual exclusion would allow a sequence of events that results in
  A != 2. Given that all possible execution paths are considered, A == 2 is a
  usefull assertion that the critical section is properly guarded. ]

/*
 * Peterson's Algorithms for mutual exclusion
 */

Processor 1:
	(0)		st	#1,[P1wants]
			membar	#StoreStore	! required in PSO and RMO only
	(1)		st	#1,[Turn]
			membar	#StoreLoad	! required in all memory models

	(2)	retry:	ld	[Turn],%l0
	(3)		cmp	#1,%l0
			bne	ok
	(4)		ld	[P2wants],%l0
	(5)		cmp	#0,%l0
			bne	retry

	(6)	ok:	ld	[A],%l1		! *** Critical section:
	(7)		add	%l1,#1,%l1	! *** increments A
	(8)		st	%l1,[A]		! *** will fail with broken lock

			membar	#StoreStore	! required in PSO and RMO only
	(9)		st	#0,[P1wants]

Processor 2:
	(10)		st	#1,[P2wants]
			membar	#StoreStore
	(11)		st	#0,[Turn]
			membar	#StoreLoad

	(12)	retry:	ld	[Turn],%l0
	(13)		cmp	#0,%l0
			bne	ok
	(14)		ld	[P1wants],%l0
	(15)		cmp	#0,%l0
			bne	retry

	(16)	ok:	ld	[A],%l1
	(17)		add	%l1,#1,%l1
	(18)		st	%l1,[A]

			membar	#StoreStore
	(19)		st	#0,[P2wants]

Assertions:
A1: A == 2

Possible values under all memory models:
1:l0  1:l1  2:l0  2:l1   P1wants  Turn  P2wants  A
  0     1     0     2     0        0     0       2 
  0     2     0     1     0        1     0       2   
  0     2     1     1     0        1     0       2
Newsgroups: comp.parallel