# Solutions to synchronization problem need to be executed in critical section

I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and compare_and_set() are performed atomically at the hardware level and in all other software solutions like mutex, semaphore the code needs to be executed atomically and hence these have to be executed in the critical section themselves.

Does this mean that these software solutions have limited use when compared to the hardware solutions, though it seems that the former are used extensively?

• If implemented properly, these primitives behave as if they were atomic. In their implementation, they use test_and_wait() or compare_and_set(). – Yuval Filmus Nov 12 '13 at 9:23
• @YuvalFilmus then why not just use the hardware implementations? Is it to avoid busy waiting? – user2555595 Nov 12 '13 at 10:54
• You are using the hardware implementation, you're just using different primitives which are easier to use. – Yuval Filmus Nov 12 '13 at 17:44

## Low-level atomicity primitives

At the level of the interface between hardware and software, atomicity is typically provided by an operation that combines a read and a write operation. Here are two common examples:

• test-and-set: read the old value of a memory location, and write a new value. This is an atomic operation: the read is always executed together with the subsequent write. If two threads execute test-and-set on the same location then one thread performs its read and its write first, then the other thread performs its read and its write.
• compare-and-swap: read the current value of a memory location, and if it has a given value, write a new value to it. This is an atomic operation: the read and comparison are always executed together with the subsequent write if any. If two threads execute compare-and-swap on the same location, then one thread performs its read and comparison and may or may not perform a write based on the current value, then the other thread compares the value that may or may not have changed and may or may not perform its write.

These primitives are awkward to use in applications for several reasons.

• They are not portable: different CPU types provide different atomic primitives. Unless you're writing software that's only meant for use on one particular CPU type, these primitives need to be wrapped inside a higher-level interface.
• They are not the whole story. This aspect is often neglected in introductory concurrency courses, which is understandable because it can get complicated. However, I've found that programmers who write low-level concurrent code are not always of it, which is more problematic. These primitives are not always sufficient to implement concurrency between threads that are running on different processors on a multiprocessor machine. (Here, by processor, I mean separate execution threads — you may prefer to use the word “core” instead.) If different processors share the same memory but have separate caches, then processor 1 may perform an atomic test-and-set to its cache while processor 2 performs an atomic test-and-set to its cache — and then there is no synchronization between the two processors. Depending on the processor type, the software may need to trigger a cache flush or invalidation.
• Continuing on “not the whole story”, even on a single processor, memory instructions may be executed out of order, to optimize the use of the memory bus. Consider for example a program uses one a CAS instruction to start a critical section that contains assignments. If the processor decides to reorder the assignments before the CAS instruction, the desired synchronization isn't happening! The software may need to generate appropriate memory barrier instructions.

Furthermore, these primitives only provide atomicity. Synchronization is more than that.

## Synchronization is atomicity plus events

Synchronization problems broadly fall into two categories:

• Avoid certain orders of operations which lead to wrong results — a common case is performing a series of elementary operations atomically.
• React to an event: do something when something else happens.

Consider what happens when two threads are competing for a critical section. One thread gets in, and the other thread doesn't thanks to the use of a low-level primitive. Now what? The other thread needs to wait until the resource is free.

At the hardware level, the most common mechanism to wait for an event is to wait for an interrupt. This is the pretty much universal mechanism to trigger software events from hardware events.

Interrupts are rarely applicable to synchronization between software. Waiting for a software event is usually provided by the operating system scheduler or the runtime library: the thread that needs to wait is suspended and placed on an event queue that is associated with the resource that the thread is waiting on. When the resource is released by its current holder, the thread at the front of the event queue is woken up. Depending on the design, it may either be assigned the resource at this point, or it may need to try acquiring the resource again.

There are cases when it is a good strategy to busy-wait: if the critical section is short and the threads are executing on separate processors in a multiprocessor machine, then it may be more efficient for the thread to try and try again until it managed to acquire the resource, than to go through the whole business with an event queue (which itself must be synchronized between the processors — see the part about cache coherency above). This is only a good strategy for short critical sections, otherwise the busy wait hogs the CPU (which can't be used to run other threads, and is consuming energy). This usually doesn't apply to single-processor systems as the active waiting is hogging the CPU, delaying the other thread from finishing, although it can sometimes be applicable to system with cooperative multiprocessing where the waiting thread yields execution to other threads.

A synchronization primitive such as a mutex is typically not executed as a critical section. For example, consider a typical spinlock operation (a mutex with busy-waiting) based on compare-and-swap in a coherent memory model (with no operation reordering and no need for cache operations). The mutex variable is initialized with the value 0. To acquire the mutex:

1. With CAS, set the mutex variable to 1 if it was equal to 0.
2. If CAS returns 0, the lock acquisition succeeded, so return to the caller.

There is no need for the logic in steps 2 and 3 to be synchronized with what other threads are doing.

Atomicity and mutual exclusion are different concepts that are related in that either can be used to implement the other. The important property of mutexes and semaphores is not so much that they are atomic as they guarantee that only one process can get past a particular point at a time. Atomic read-modify-write hardware primitives like test_and_set() and compare_and_swap() can be used to implement mutual exclusion, but it is not true that atomic hardware operations are required to implement mutual exclusion - Lamport, Leslie; The Mutual Exclusion Problem Has Been Solved, CACM 34(1):110, 1991.

Mutual exclusion requires two different primitives. For example with a mutex you need both a try_acquire() operation and a release() operation. You would typically use something like a test_and_set instruction to implement try_acquire(), but a simple store operation is usually sufficient to implement release(). (And test_and_set is not required to implement try_acquire() as demonstrated by Lamport, it's just easier if you have such an atomic instruction.) Similarly, a semaphore has different down() and up() operations.

Further, most mutexes provide acquire() operations that do more than just try_acquire(), they also provide an efficient way of waiting for the mutex to become available if the try_acquire() should fail.

Conversely: a mutex can be used to implement a complex atomic operation. Suppose you want to implement an atomic increment operation on a machine that has a mutex (perhaps implemented without atomicity by using something like Lamport's Bakery Algorithm) but you don't have direct access to any atomic instructions. Something like the following will work:

mutex   m
integer i

atomic_increment():
m.acquire()
i = i+1      # only one process at a time can be at this code point
m.release()


So neither mutual exclusion nor atomicity is more "fundamental" than the other, they are really two different things that can be used to implement each other.

Implementations of software primitives like mutexes and semaphores employ atomic hardware primitives such as test_and_wait() or compare_and_set(), and as a result they behave in an atomic fashion. Usually these software primitives are more powerful and easier to use than the hardware primitives, which is why you would rather use them. This is an example of the widespread idea of reduction: you can use any parallel primitive as long as it reduces to one of your hardware primitives, and so when hardware designers choose hardware primitives, they choose primitive which are powerful and versatile enough to enable implementation of as many other primitives as possible.

• When you claimed that "usually these software primitives like mutexes and semaphores are more powerful and easier to use than the hardware primitives like test_and_set() and compare_and_test()", are you referring to their theoretical power in solving problems? What are the problems which can be solved using mutexes , however cannot be solved using test_and_set()? – hengxin Dec 18 '13 at 7:18
• I'm referring to practical matters - how easy it is for a programmer to use them. Mutexes and semaphores can be implemented using these primitives, indeed probably implemented in software in a hardware-dependent manner. – Yuval Filmus Dec 18 '13 at 21:05