Nonblocking Concurrent Objects with Condition Synchronization

Nonblocking Concurrent Objects with Condition Synchronization", by W. N. Scherer III and M. L. Scott.  18th Annual Conf. on Distributed Computing, Oct. 2004

 

http://www.cs.rochester.edu/u/scott/synchronization/pseudocode/duals.html

 

写道

Pseudocode from article of the above name in DISC'04. Michael L. Scott and William N. Scherer III.

The dualstack is derived from the non-dual version due to Treiber. [R. K. Treiber. Systems Programming: Coping with Parallelism. RJ 5118, IBM Almaden Research Center, April 1986.] Satisfies pending requests in LIFO order using a mechanism in which adjacent reservation and data nodes “annihilate” each other. Assumes the availability of a double-width CAS instruction, to avoid the ABA problem; could easily use single-width LL/SC instead. Spinning threads impose no contention on either cache-coherent or non-cache-coherent machines.

The dualqueue is derived from the non-dual version due to Michael and Scott. Takes its name from the firmware-supported dualqueues of the c.1982 BBN Butterfly Parallel Processor. Satisfies pending requests in FIFO order. Assumes the availability of a double-width CAS instruction, to avoid the ABA problem; could easily use single-width LL/SC instead. Spinning threads impose no contention on a cache-coherent machine; an extra level of indirection would be required on non-cache-coherent machines.

The dualqueue constitutes, trivially, a previously unknown queue-based mutual exclusion lock. When initialized with k items it constitutes a contention-free spin-based semaphore. When paired with a test-and-set lock it provides a “limited contention” spin lock that balances fairness against locality on a distributed memory machine.