lvs@ndm20 (03/03/86)
In an effort to implement a recoverable locking mechanism for a
database across a wide range of machines I need an algorithm to
implement the standard P & V operators without assuming the machine
has some form of a "test and set" operation. I also can not assume
the machine supports any form of shared memory or messaging system
for interprocess communication. As you can see from these
restrictions the only mechanism left available is some form of disk
based algorithm. Disk i/o operations are guaranteed to be atomic,
even if the order of the operations, between different processes, can
not be guaranteed.
Do not rule out shared memory schemes or semaphore methods, they
could possibly be converted to a disk based form and still be usable.
As a matter of fact, don't rule out anything, I'm desperate. My need
for an algorithm to accomplish this task is very urgent and any help
I receive would be greatly appreciated.
Thanks,
Larry V. Streepy
Nathan D. Maier Consulting Engineers
(214)739-4741
Usenet: ...!{allegra|ihnp4}!convex!smu!ndm20!lvs
CSNET: ndm20!lvs@smu
ARPA: ndm20!lvs%smu@csnet-relay.ARPAberry@tolerant.UUCP (David W. Berry) (03/08/86)
In article <2000005@ndm20> lvs@ndm20 writes: > >In an effort to implement a recoverable locking mechanism for a >database across a wide range of machines I need an algorithm to >implement the standard P & V operators ... One possible solution, although is intended for usage in a common memory environment, is Dekker's algorithm. The original publishing was of an algoritm to implement true locking on a two processor system and was published in CACM some years ago. There was also a later issue of CACM which published corrections to the algorithm and a yet later issue which presented a modification of the algorithm that was generalized for N processors. Sorry I can't give you more information but I implemented it several years ago from somebody else's issue of CACM. David -- David W. Berry dwb@well.UUCP Delphi: dwb {ucbvax,pyramid,idsvax,bene,oliveb}!tolerant!berry I'm only here for the beer.
geof@imagen.UUCP (Geoffrey Cooper) (03/10/86)
Mutex locking among N processors can be implemented using N single bit variables. The only restriction is that it be possible to write any one variable without affecting the others. It is not necessary that reads and writes be atomic. The algorithm works by having one variable associated with each processor. Each processor writes to its own variable and reads the variables of all others. Fairness is assumed not to be at issue. I leave the details to you. - Geof Cooper Imagen
root@icst-cmr (UNIX 4.2 BSD) (03/18/86)
/* From unix-sources-request@BRL.ARPA Fri Mar 14 19:27:55 1986 From: Doug Gwyn <gwyn@brl-smoke.arpa> Subject: Re: P & V Algorithms needed To: unix-sources@brl-smoke.arpa In article <300@imagen.UUCP> geof@imagen.UUCP (Geoffrey Cooper) writes: >Mutex locking among N processors can be implemented using N single bit >variables. The only restriction is that it be possible to write any >one variable without affecting the others. It is not necessary that >reads and writes be atomic. > >The algorithm works by having one variable associated with each >processor. Each processor writes to its own variable and reads the >variables of all others. Fairness is assumed not to be at issue. If I understand you correctly, this scheme does not work. Consider: Start with all flags clear. Processor A wants to enter a critical region, so it starts to set the A-flag (after reading all the other processor flags and finding them all clear). It's the other way around Doug. First you set your own flag, then look at whether anyone else set their flags. `Shoot first & ask questions later.' When either guy finds someone elses flag set, they back off & try later (everyone equal), or possibly the lowest (or highest) guy spins waiting for the other guys to accede (priority access). Concurrently, processor B wants to enter the same critical region, so it starts to read the processor flags to see if some other processor is in the region. In particular, it tries to read the A-flag. Dependent on the outcome of a timing race, it is now possible for both processors to be executing in the critical region. 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. You just did. In fact, I have heard it called `Dijkstra's algorithm.' Unfortunately, it can become unwieldy with a high collision rate, somewhat like ethernet. Your buddy, Root Boy Jim (Cottrell) <rbj@cmr> */
Wax.OsbuSouth@Xerox.COM (03/18/86)
"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." Dekker's algorithm does not use it as far as I know. An encoding of it can be found on page 291 of Per Brinch Hansen's book "Operating System Principles" (C) 1973 by Prentice Hall. Allan Wax ARPA: Wax.OsbuSouth@Xerox.COM