Path: news.mitre.org!blanket.mitre.org!philabs!newsjunkie.ans.net!newsfeeds.ans.net!news-was.dfn.de!news-fra1.dfn.de!news-ber1.dfn.de!news-lei1.dfn.de!news-nue1.dfn.de!uni-erlangen.de!newsfeed.nacamar.de!news.maxwell.syr.edu!rill.news.pipex.net!pipex!main.de.uu.net!Dortmund.Germany.EU.net!dortmund.de.uu.net!spock.skd.de!not-for-mail
From: "Stephan Wolf" <swolf@syskonnect.de>
Newsgroups: comp.os.ms-windows.programmer.nt.kernel-mode
Subject: Re: algorithm for my own spinlock ?
Date: Fri, 16 Jan 1998 12:17:47 GMT
Organization: SysKonnect
Lines: 162
Message-ID: <34bf44c4.3043896@spock>
References: <34be28a8.18649987@news.ibm.net.il>
NNTP-Posting-Host: swolf.skd.de
X-Newsreader: Forte Free Agent 1.11/32.235

On Thu, 15 Jan 1998 15:21:13 GMT, vampire@cross.garlic ((vampire))
wrote:

>Can anyone remind me of the algorithm for implementing a critical
>section/exclusive resource using plain C, with out special LOCK op
>codes ?

What's wrong with NT's spinlocks? Anyway:

[Anyone who has more/better/different information please correct me.]

Below you'll find some code examples, which I found in my private
archive. They are not to be used in this form, but they should give an
idea how this can be implemented. The examples can be used in MP
systems and in UP systems where more than one thread can access the
same critical data or can enter the same critical code path. Note that
the NOP (no-operation) comment must be replaced by some function call
that will do a task switch to some non-blocking process (thread) at
least in UP systems.

Some further thoughts:

1. All variables that are to be accessed by more than one CPU (and/or
DMA device) in an SMP system must be declared as 'volatile' in C.

2. AFAIK, in an Intel x86 SMP system, cache coherency is implemented
in hardware, i.e. there is no need to use the LOCK instruction, *if*
and only if some memory location is only to be accessed by CPUs and
not by any DMA devices (i.e. I/O memory, even if UC (uncached)).

Some background info on critical sections in SMP systems can be found
at:

"A Fast Mutual Exclusion Algorithm" (by Leslie Lamport):


http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-007.html

"A Survey of Mutual-Exclusion Algorithms for Multiprocessor Operating
Systems" (by Lawrence Kesteloot):

	http://tofu.alt.net/~lk/242.paper/242.paper.html

I think Gary Peterson's algorithm below is ingenious and shows the
real spirit of how one should write code: keep it simple but
effective! (Did you know that before he presented this algorithm
everyone thought that mutex cannot be implemented without special
hardware?)

Note that the term "processor" can be replaced by "process" in the
examples below.
-----
Implementing Mutual Exclusive Access to Data on Multiprocessor Systems

17-Aug-1994 sw	Gary Peterson's 1981 algorithm.
10-Feb-1997 sw	Added Leslie Lamport's 1977 algorithm.

--==( Critical Section )==--

/* Gary Peterson's algorithm (1981) for two processors. */

volatile int flag[2] ;
volatile int turn ;

start_critical_section(
int processor_id)	/* 0 or 1 */
{
	/* set flag of this CPU */
	flag[processor_id] = 1 ;
	/* set turn to this CPU */
	turn = processor_id ;
	/* wait until other CPU not in crit. sect. */
	while ((flag[1 - processor_id] != 0)
		&& (turn != processor_id))
		/* NOP */ ;
}

end_critical_section(
int processor_id)
{
	flag[processor_id] = 0 ;
}

/* Gary Peterson's algorithm for N processors. */

/* N=8:
 *	  ____o____
 *	 /	   \
 *     _o_	   _o_
 *    /	  \	  /   \
 *   o	   o	 o     o
 *  / \	  / \	/ \   / \
 * o   o o   o o   o o	 o
 * 0   1 2   3 4   5 6	 7 <- processor id
 */

typedef struct s_Node {
	char flag[2] ;
	char turn ;
} NODE ;

volatile NODE tree[N-1] ;

mutex(
int pid)	/* processor id (0..N-1) */
int lev ;	/* tree "level" (1..N), initially N */
{
	int index ;	/* index within node */
	int partner ;	/* partner node in binary tree, i.e. same
father */

	index = pid & 1 ;
	partner = index ^ 1 ;
	/* partner = 1 - index ; */
	/* partner = !index ; */

	pid >>= 1 ;
	node = &tree[lev-1 + pid] ;

	node->flag[index] = TRUE ;
	node->turn = partner ;
	while (node->flag[partner] && node->turn == partner)
		/* NOP */ ;

	if (lev > 0)
		mutex(pid, lev >> 1) ;
	else {
		/* start critical section */

		/* end critical section */
	}
	node->flag[index] = FALSE ;
}

--==( Atomic Access to Data Structure )==--

/* Leslie Lamport's algorithm (1977). */

volatile int v1, v2 ;

/* Algorithm for writer. */
Write()
{
	v1++ ;
	/* write data... */
	v2 = v1 ;
}

/* Algorithm for reader. */
Read()
{
	int temp ;

	do {
		temp = v2 ;
		/* read data... */
	} while (v1 != temp) ;
}
-----

Stephan Wolf <swolf@syskonnect.de> http://www.syskonnect.de
SysKonnect - The Server Connectivity Company