When should we use mutex and when should we use semaphore

Here is how I remember when to use what -

Semaphore:Use a semaphore when you (thread) want to sleep till some other thread tells you to wake up. Semaphore 'down' happens in one thread (producer) and semaphore 'up' (for same semaphore) happens in another thread (consumer)e.g.: In producer-consumer problem, producer wants to sleep till at least one buffer slot is empty - only the consumer thread can tell when a buffer slot is empty.

Mutex:Use a mutex when you (thread) want to execute code that should not be executed by any other thread at the same time. Mutex 'down' happens in one thread and mutex 'up' must happen in the same thread later on.e.g.: If you are deleting a node from a global linked list, you do not want another thread to muck around with pointers while you are deleting the node. When you acquire a mutex and are busy deleting a node, if another thread tries to acquire the same mutex, it will be put to sleep till you release the mutex.

Spinlock:Use a spinlock when you really want to use a mutex but your thread is not allowed to sleep. e.g.: An interrupt handler within OS kernel must never sleep. If it does the system will freeze / crash. If you need to insert a node to globally shared linked list from the interrupt handler, acquire a spinlock - insert node - release spinlock.

A mutex is a mutual exclusion object, similar to a semaphore but that only allows one locker at a time and whose ownership restrictions may be more stringent than a semaphore.

It can be thought of as equivalent to a normal counting semaphore (with a count of one) and the requirement that it can only be released by the same thread that locked it^(a).

A semaphore, on the other hand, has an arbitrary count and can be locked by that many lockers concurrently. And it may not have a requirement that it be released by the same thread that claimed it (but, if not, you have to carefully track who currently has responsibility for it, much like allocated memory).

So, if you have a number of instances of a resource (say three tape drives), you could use a semaphore with a count of 3. Note that this doesn't tell you which of those tape drives you have, just that you have a certain number.

Also with semaphores, it's possible for a single locker to lock multiple instances of a resource, such as for a tape-to-tape copy. If you have one resource (say a memory location that you don't want to corrupt), a mutex is more suitable.

Equivalent operations are:

Counting semaphore          Mutual exclusion semaphore--------------------------  --------------------------  Claim/decrease (P)                  Lock  Release/increase (V)                Unlock

Aside: in case you've ever wondered at the bizarre letters used for claiming and releasing semaphores, it's because the inventor was Dutch. Probeer te verlagen means to try and decrease while verhogen means to increase.

^(a) ... or it can be thought of as something totally distinct from a semaphore, which may be safer given their almost-always-different uses.

It is very important to understand that a mutex is not a semaphore with count 1!

This is the reason there are things like binary semaphores (which are really semaphores with count 1).

The difference between a Mutex and a Binary-Semaphore is the principle of ownership:

A mutex is acquired by a task and therefore must also be released by the same task.This makes it possible to fix several problems with binary semaphores (Accidental release, recursive deadlock, and priority inversion).

Caveat: I wrote "makes it possible", if and how these problems are fixed is up to the OS implementation.

Because the mutex has to be released by the same task it is not very good for the synchronization of tasks. But if combined with condition variables you get very powerful building blocks for building all kinds of IPC primitives.

So my recommendation is: if you got cleanly implemented mutexes and condition variables (like with POSIX pthreads) use these.

Use semaphores only if they fit exactly to the problem you are trying to solve, don't try to build other primitives (e.g. rw-locks out of semaphores, use mutexes and condition variables for these)

There is a lot of misunderstanding between mutexes and semaphores. The best explanation I found so far is in this 3-Part article:

Mutex vs. Semaphores – Part 1: Semaphores

Mutex vs. Semaphores – Part 2: The Mutex

Mutex vs. Semaphores – Part 3 (final part): Mutual Exclusion Problems