Locks for multithreaded applications are commonly implemented by augmenting suspend locking with spin locking. This allows locking and unlocking operations in the absence of contention to be performed as highly as spin locking, involving only a few instructions in the user space. However, as far as we know, all the existing algorithms are double-atomic, requiring two atomic operations, one in locking and the other in unlocking, in the uncontended path.
We propose a novel, single-atomic spin-suspend algorithm. It centers on a generalized technique for converting a spin-wait loop into a suspend-wait loop, while the timing dependency cleverly created upon the failing atomic operation guarantees that any suspend-waiting thread is eventually signaled. We also present an intriguing variation for multiprocessor systems with relaxed memory models, which does not require an additional memory barrier.
By: Tamiya Onodera
Published in: RT0369 in 2002
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .