8
$\begingroup$

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is devoted to them.

I'm wondering what are the practical situations where one might need these algorithms during engineering of a concurrent system, rather than use typical language- and OS-provided synchronization primitives (say, provided by the pthread library)?

I can think of many special cases where I'd imagine the standard primitives are not specifically tuned for them, e.g. "one frequent reader and one infrequent writer", or vice versa, or "exactly one write operation, many readers", etc. - are any of the textbook mutual exclusion algorithms significantly better in practice in such situations?

To put it shortly: Which mutual exclusion algorithms are of practical relevance to an engineer who already has a typical language-provided library of concurrency primitives at their disposal?

$\endgroup$
  • $\begingroup$ this was an active area of research decades ago in creating these "primitives" and has changed substantially in engineering practice. also some of this was theoretical work about possibilities that was not necessarily meant to be practically applied. some of the constructions are somewhat artificial and answer open theoretical questions. they are useful exercises in understanding the many/ surprising subtleties of concurrency and building an intuition in the area. $\endgroup$ – vzn Nov 25 '14 at 16:54
6
$\begingroup$

Answer: none. That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about. In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the pthread library, they are showing you how it is implement the equivalent of the pthread library.

Chapter 2 of Herlihy and Shavit is titled "Mutual Exclusion." It gives a variety of classic algorithms for implementing the equivalent of pthread_mutex_lock() with only sequentially consistent shared memory. My answers https://cs.stackexchange.com/a/12632/7459 and https://cs.stackexchange.com/a/30249/7459 discuss the importance of these implementations, and have a pointer to one that is practical for use on machines that have no built-in hardware synchronization operations. (Lamport's 1987 paper in ACM Trans. on Computer Systems).

Chapter 7 of Herlihy and Shavit gives a variety of spin and queue lock implementations of the equivalent of pthread_mutex_lock(), and Chapter 8 expands to discuss pthread_cond_t (condition variables), pthread_rwlock_t (reader/writer locks), and briefly touches on semaphores. There may be situations in which pthread_rwlock_t could be used as an alternative to pthread_lock_t for performance reasons (but usually not) and in Posix you need to use semaphores for inter-process synchronization.

Chapters 9 through 16 are mostly discussing applications (various kinds of concurrent containers). Chapter 17 briefly discusses the equivalent of pthread_barrier_t.

All that said, Herlihy and Shavit are two of the most vocal proponents of transactional memory and a variety of kinds of non-blocking (and wait-free) synchronization. These techniques are intended as alternatives to mutual exclusion in certain cases. Herlihy and Shavit sprinkle various non-blocking implementations throughout Chapters 9 through 16, and then go into detail on transactional memory in Chapter 18.

Transactional memory and other non-blocking synchronization techniques are intended to deal with the problem that some poorly designed algorithms require threads to hold their critical sections for a very long time. Transactional memory and truly non-blocking synchronization are not currently practical alternatives in any real situation, but the techniques for transforming blocking data structures into non-blocking data structures are useful in practice for minimizing the amount of time a blocking data structure stays in its critical section. (Often you can reduce the size of the critical section down to just a couple of machine instructions.)

$\endgroup$

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.