18
$\begingroup$

Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these?

Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, namely, interrupt disabling, test-and-set and swap?

$\endgroup$
13
$\begingroup$

Yes, you can implement mutual exclusion with only memory load and store instructions. There is a long tradition of devising successively simpler solutions to this problem.

The earliest version that I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968. There have been dozens of solutions since then. I will discuss only a few of the more notable ones.

Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974 introduces the "Bakery algorithm" (because it is based on the analogy of people taking numbers to determine the order in which they will be served at the bakery shop). One of the particularly notable features of this algorithm is that it demonstrates that no hardware atomicity at all is required to solve the mutual exclusion problem. Reads that overlap writes to the same location can return any value and the algorithm still works. Lamport discusses this a bit in the description of the paper on his home page.

Peterson's solution, Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981, is one that is specifically designed to be easy to understand, and reason about. Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987. In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section. It guarantees mutual exclusion and deadlock freedom, but not fairness. It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention. (When there is contention, it falls back on an O(N) test.) He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses. (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

Apparently people who work on the problem of solving mutual exclusion using just memory reads and writes get frustrated by other people's (lack of) understanding of the problem and its solutions. This is demonstrated partly by the title of Peterson's paper ("Myths about the mutual exclusion problem") and partly by a short note that Lamport published in 1991: Lamport, Leslie; "The Mutual Exclusion Problem Has Been Solved", Comm ACM 34(1):110, 1991, which Lamport describes somewhat bitterly on his homepage.

So to answer your second question: No. There are many more than three categories of hardware level solutions to the critical section problem (using just loads and stores is one, others involve compare-and-swap instructions, load-linked/store-conditional instructions (using the cache coherence protocol to test for atomicity), and fetch-and-add instructions.) In another sense there's really just one category of solutions: those that involve getting a bunch of asynchronous processes to agree on a global order of events.

(Note that this answer is an (extensive) edit of an earlier answer I gave for a very different question.)

$\endgroup$
  • $\begingroup$ ll/sc can, of course, be extended to a more general transactional memory which covers the entire critical section rather than just the lock acquisition. The distinction between what guarantees hardware provides also seems significant; forward progress is sometimes guaranteed (i.e., one agent will win the race to get a lock at a given time), but even weak concepts related to fairness seem to be usually punted to software (somewhat understandably). $\endgroup$ – Paul A. Clayton Jun 11 '16 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.