kre@munnari.OZ (Robert Elz) (03/16/86)
In article <1828@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn) writes: > I have never heard of a mutual exclusion scheme that did not > at root depend on the existence of an interlocked test-and-set > operation of some kind. I would be interested in hearing some > details about other schemes if they exist. What about CSMA/CD - an ethernet is a shared resource, with no interlocked test & set, yet it seems that its occasionally possible to get exclusive access to the thing... The important properties are the ability to detect that a collision has occurrred, and the ability to go back and start again. I have used this scheme in the more conventional case of two processors with shared memory, and no test&set to do interlocking, the algorithm goes like this .. look see if the other processor has the resource locked, if so, wait set my lock bit look see if the other processor has the resource locked, if so, reset my lock bit, and go back to the start I own it. The "wait" can be a busy wait, or it can mean just try for the resource sometime later, whichever is appropriate. The "go back to the start" step should have some random delay associated with it to avoid continuous collisions (deadlock). I'd be interested to know if anyone can discover any way that this can be defeated (very interested, since this algorithm is actually in use, right now, on some hardware I have here...). I haven't actually thought this through for a case of N processors, N > 2, but I can't immediately see any reason it wouldn't function, after all, ethernets work with more than 2 processors... Robert Elz kre@munnari.oz seismo!munnari!kre ps: I am moving this discussion into net.sources.d where it belongs
geof@imagen.UUCP (Geoffrey Cooper) (03/17/86)
> In article <1828@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn) writes: > > I have never heard of a mutual exclusion scheme that did not > > at root depend on the existence of an interlocked test-and-set > > operation of some kind. You are correct, the scheme that you outlined doesn't work. The hint is that the correct scheme isn't fair. Try this code: #define N <number of processors> #define TRUE 1 #define FALSE 0 shared boolean locks[N]; lock(me) int me; /* my processor number */ { int i; do { locks[me] = TRUE; for ( i = 0; i < me-1 && ! locks[i]; i++ ); if ( i < me-1 ) locks[me] = FALSE; } while ( ! locks[me] ); do { for ( i = me+1; i < N && ! locks[i]; i++ ) } while ( i < N ); } unlock(me) int me; /* my processor number */ { locks[me] = FALSE; } Gold star to Robert Elz. I agree that there is a great similarity with aloha contention (and csma/cd). In these schemes, static priorities are replaced by random backoff times. This eliminates static priority but gives only a probablistic (though high) chance of success. The probablistic schemes are also somewhat fairer under expected network traffic than a static scheme would be. Note that each processor writes to only one variable and reads from all the others. Thus test-and-set is not needed. I developed this algorithm one day in deciding whether read-modify-write cycles were an absolute requirement for a bus architecture. Interestingly, atomic reads and writes are also unecessary, since no processor writes the lock belonging to any other processor. However, glitching of a value from true to false and back is not allows. I refer you to 3rd PODC Conference Proceedings, ACM 1984 (reprinted in SIGOPS OS.review Oct. 85: "Solved Problems, Unsolved Problems, and Nonproblems in Concurrency" by Leslie Lamport. The 2-processor version of the above is outlined as an oft-forgotten solved problem. Actually, there is a bug in the algorithm as presented in the paper, but it's probably a typo. As Chris Torek pointed out, a token contention scheme can also be used. This is a "fairer" scheme, but does require active participation on the part of all parties, even when they are not interested in the state of the lock. - Geof Cooper