🚀 go-pugleaf

In article <1992Aug31.124322.2555@hubcap.clemson.edu> iane@werple.pub.uu.oz.au (Ian Evans) writes:
> Let's say that there is a system (unfortunately there is) where some
> person (me) wants to get a few different computers communicating reliably,
> and the only available mechanism is reading a shared memory location, or
> writing a location, but there is no atomic set & test type instruction.
> It is possible, however, to get a unique system-wide process ID.

A working algorithm is described (in a Pascalish dialect) in "Operating
Systems Concepts", by Silberschatz et al.  I know it works because I've
tested it on an 8-cpu multiprocessor.

I translated it into C, and it's pretty small, so what the heck!
here it is ...

------ begin spinlock.c -----
/*
 * spinlock.c -- critical regions support
 *
 * This algorithm is from "Operating System Concepts, 2nd Ed., Peterson &
 * Silberschatz; Addison Wesley"; chapter 9, Algorithm 5.
 * Algorithm is due to Eisenberg and McGuire 1972.
 */

/*
 * Instructions:
 *
 * Define a spin-lock structure with the macro DEF_SPIN().
 * Lock a critical region by calling lock() and passing the address
 *  of a spin-lock structure to it.
 * Un-lock the critical region by calling unlock() with the same address.
 *
 * You must supply a routine my_proc_id() that yields a system-wide unique
 * integer identifier for each cpu, and a value for the macro MAX_CPU.
 *
 * Example:
 *
 *   DEF_SPIN(lck)
 *
 *   one_at_a_time()
 *   {
 *       lock(&lck);
 *       ...
 *       unlock(&lck);
 *   }
 */

#include "spinlock.h"

/*
 * attempt to lock a critical region; spin until successful.
 */
void
lock(SPIN *c)
{
	register int j, i = my_proc_id();

	for (;;) {
		c->flag[i] = WANT_IN;
		j = c->turn;
		while (j != i)
			if (c->flag[j] != IDLE)
				j = c->turn;
			else
				j = (j+1) % MAX_CPU;
		for (c->flag[i] = IN_CS;
		     j < MAX_CPU && (j == i || c->flag[j] != IN_CS);
		     j++)
			; /* empty */
		if (j >= MAX_CPU && (c->turn == i || c->flag[c->turn] == IDLE))
			break;
	}
	c->turn = i;
}

/*
 * unlock a critical region.
 */
void
unlock(SPIN *c)
{
	int j = (c->turn+1) % MAX_CPU;
	while (c->flag[j] == IDLE)
		j = (j+1) % MAX_CPU;
	c->turn = j;
	c->flag[my_proc_id()] = IDLE;
}
------ end spinlock.c -----

------ begin spinlock.h -----
/*
 * spinlock.h -- critical regions def'ns
 */

#ifndef _SPINLOCK_H_
#define _SPINLOCK_H_

typedef struct {
	int turn;
	int flag[MAX_CPU];
} SPIN;

/* flags */
#define IDLE	0
#define WANT_IN	1
#define IN_CS	2

#define DEF_SPIN(x)	SPIN x = {0}	/* initialize whole thing to zero */

/* critical.c */
void lock(SPIN *c);
void unlock(SPIN *c);

#endif /* _SPINLOCK_H_ */
------ end spinlock.h -----

ObEnjoy: Enjoy!

--
"The path of my life is strewn with cowpats from the devils' own herd."
                                          -- Edmund Blackadder II
bmw@isgtec.com   [ ...!uunet.ca!isgtec!bmw ]  Bruce Walker