Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book is a very common CPU instruction set, and the use of semaphores for which my book says that: a flag implemented using this way, is a semaphore. Does that mean that semaphores are a part of these instructions or the opposite? Also, if a operating system does not support semaphores, can it support test-and-set instructions and if yes, can you reach mutual exclusion this way? Thanks!


1 Answer 1


Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they specify an API for a mechanism and its semantics, but not its implementation.

Implementing such mechanisms correctly requires hardware support. One way to implement semaphores is using test-and-set. Another popular instruction is compare-and-swap. Both of these are examples of atomic instructions, which are instructions performing several operations that cannot be interrupted in the middle. Such atomic instructions are necessary to correctly implement mechanisms such as semaphores.

Typically these control mechanisms are implemented by the operating system. For example, POSIX-compliant systems implement POSIX semaphores. Semaphores are just one more service provided by the operating system. Under the hood, semaphores are implemented using atomic instructions provided by the CPU.

  • $\begingroup$ Thanks for the answer. Regarding my second question then, if there is no way to support semaphores, we cannot use test-and-set , and so mutual exclusion cannot be achieved this way right? We would have to move to locks or monitors if I am getting this correctly. $\endgroup$ Jan 28, 2021 at 10:41
  • 1
    $\begingroup$ It's exactly the opposite. In order to support any mutual exclusion mechanism – be it semaphores, locks or monitors – you need hardware support for some relevant atomic instruction. As a programmer, you don't (usually) use test-and-set directly. Rather, you use concepts at a higher level of abstraction, such as semaphores, locks, monitors, or coherent shared memory. $\endgroup$ Jan 28, 2021 at 11:22
  • $\begingroup$ You can implement mutexes using semaphores and vice versa. If semaphores are impossible to implement then locks, monitors etc are impossible as well. $\endgroup$
    – gnasher729
    Jan 29, 2021 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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