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?

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.

StackExchange Computer Science Q#17945, answer score: 5