How are mutex and lock structures implemented?

Question

I understand the concept of locks, mutex and other synchronization structures, but how are they implemented? Are they provided by the OS, or are these structures dependent on special CPU instructions for the CPUs MMU?

Answer 1

You may want to look at these links, but the main one is the Test-and-set on Wikipedia: http://en.wikipedia.org/wiki/Test-and-set

http://stackoverflow.com/questions/1485924/how-are-mutexes-implemented

You can also look at this patent: http://www.faqs.org/patents/app/20080222331

Answer 2

Most mutual exclusion and synchronization mechanisms use hardware atomic operations, as others have pointed out. However, it is possible to implement mutual exclusion entirely in software. See Dekker's algorithm, and also related algorithms by Peterson and Lamport. Although these are primarily of historical interest now that hardware atomics are ubiquitous, I have worked on "interesting" systems (still in production) where software techniques are still necessary.