When should we use mutex and when should we use semaphore

Question

When should we use mutex and when should we use semaphore ?

Solution 1

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.

Solution 2

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 (P and V) used for claiming and releasing semaphores, it's because the inventor was Dutch. In that language:

• Probeer te verlagen: means to try to lower;
• 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.

Solution 3

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

Solution 4

While @opaxdiablo answer is totally correct I would like to point out that the usage scenario of both things is quite different. The mutex is used for protecting parts of code from running concurrently, semaphores are used for one thread to signal another thread to run.

/* Task 1 */
pthread_mutex_lock(mutex_thing);
    // Safely use shared resource
pthread_mutex_unlock(mutex_thing);



/* Task 2 */
pthread_mutex_lock(mutex_thing);
   // Safely use shared resource
pthread_mutex_unlock(mutex_thing); // unlock mutex

The semaphore scenario is different:

/* Task 1 - Producer */
sema_post(&sem);   // Send the signal

/* Task 2 - Consumer */
sema_wait(&sem);   // Wait for signal

See http://www.netrino.com/node/202 for further explanations

Solution 5

See "The Toilet Example" - http://pheatt.emporia.edu/courses/2010/cs557f10/hand07/Mutex%20vs_%20Semaphore.htm:

Mutex:

Is a key to a toilet. One person can have the key - occupy the toilet - at the time. When finished, the person gives (frees) the key to the next person in the queue.

Officially: "Mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section." Ref: Symbian Developer Library

(A mutex is really a semaphore with value 1.)

Semaphore:

Is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count - the count of keys - is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.

Officially: "A semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore)." Ref: Symbian Developer Library

View more solutions

Comments

[Karthik Balaguru]

Okay, I came across binary semaphore too. When should we need to go in for binary semaphore and when should we use mutex ?

[paxdiablo]

Conceptually, a binary semaphore is a mutex, and it's equivalent to a normal semaphore with a one-count. There may be differences in implementations of the concept such as efficiency, or ownership of the resource (can be released by someone other than the claimer, which I don't agree with BTW - a resource should only be releasable by the thread that claimed it).

[paxdiablo]

Another potential implementation difference is the recursive mutex. Because there's only one resource, a single thread may be allowed to lock it multiple times (as long as it releases it that many times as well). This isn't so easy with a multiple-instance resource since you may not know whether the thread wants to claim another instance or the same instance again.

[Jarosław Bielawski]

Recursive mutex are evil, they show that the ressource handling is not properly mastered.

[Omnifarious]

You're right. Even if you are using a semaphore with a count of one, you are implying something about what you're doing than if you used a mutex.

[paxdiablo]

They solve a specific problem. The fact that the problem they solve is people who don't quite grok mutexes, should in no way belittle the solution :-)

[paxdiablo]

I'm not sure I agree with that, though I don't disagree so vehemently that I'll downvote you :-) You say that the usage pattern of semaphores is to notify threads but that's exactly what mutexes do when there's another thread waiting on it, and exactly what semaphores don't when there's no threads in sema_wait :-) In my opinion, they're both about resources and the notification handed to other threads is a side-effect (very important, performance-wise) of the protection.

[Peer Stritzinger]

The urls to this site contain funky characters and do not work therefore... I'm working on it

[Peer Stritzinger]

A mutex is totally different from a binary semaphore. Sorry but this definition is wrong

[Admin]

You say that the usage pattern of semaphores is to notify threads One point about notifying threads. You can call sem_post from a signal handler safely (pubs.opengroup.org/onlinepubs/009695399/functions/…) but it is not recomended to call pthread_mutex_lock and pthread_mutex_unlock from signal handlers (manpages.ubuntu.com/manpages/lucid/man3/…)

[Prak]

@paxdiablo: There is one major difference between this mutex binary semaphore is maintaining the reference count. Mutex or you can say any conditional mutex does not maintain any count related to lock where as sempahore use to maintain the count. So sem_wait and sem_post are maintaining the count.

[legends2k]

@PeerStritzinger Agreed, your answer captures the ownership differences between them and the reason why mutexs are not used in synchronsing tasks while semaphores are. Thanks for the article and the answer.

[paxdiablo]

@legends2k, that was probably best as a comment on Peer's answer rather than mine. In any case, the ownership issue and other differences are covered in this answer, maybe not as detailed as Peer's but certainly there. You should also vote up Peer's answer if you haven't already done so.

[legends2k]

@paxdiablo: Yes, but I felt it a bit ambigious; the comment "binary semaphore is mutex" makes it more so. Yes, I did upvote his answer.

[ToolmakerSteve]

@paxdiablo - While this answer could be considered technically correct - indeed is similar to descriptions seen many other places - I agree with PeerStritzinger that it is not good to equate a mutex to a binary semaphor. Doing so leads to muddled thinking - demonstrated by your comment "a resource should only be releasable by the thread that claimed it". Semaphores exist so that responsibility can be handed off to someone else - like a baton in a baton race, or token passing. They wouldn't be useful if the original thread had to be involved in freeing the resource!

[ToolmakerSteve]

... A mutex is a statement "hands off until I am done"; for a resource that already is known to exist. And that will continue to exist after the mutex is released. A binary semaphore is appropriate when the resource does not exist until a producer provides it. After a consumer comes along and acquires that resource it is gone forever (unless/until a producer produces another one). These are different concepts. Yes, it is possible to mis-use mutex or semaphor for the other purpose. But that would be a mistake.

[ToolmakerSteve]

Hmm. Even the Wikipedia Semaphore article discusses using a counting semaphore to control a pool of resources. But doing so has severe risks, see Part 1 Semaphores. Unfortunately, I am not expert enough to resolve the discrepancy between practice and theory.

[paxdiablo]

@ToolmakerSteve, I'm not sure if you understood my intent there. I stated a mutex was like a semaphore with count one and the restriction that the claiming thread be the releasing one. I did not contend that a semaphore had that restriction. I'll try clean up the answer to better distinguish.

[parasrish]

to add to: semaphores and the mutex are two ways to provide synchronisation. semaphore, can be more related to signalling (e.g. producer and consumer problem scenario), and mutex, can be more related to allowing access to one at a time (several requests to access shared resource, but only one granted at a time). [nice article: geeksforgeeks.org/mutex-vs-semaphore/]

[prayagupa]

Selling tickets is a neat example. semaphore example is bit unclear (to me anyway).

[Yves]

@prayagupd Semaphore example is to make threads in some order whereas selling tickets doesn't need any order. If there are three people: a, b and c. When they come to buy tickets, we don't care the order of buying tickets at all. However, if we do such a calculation: x = getx(); y = gety(); z = x + y; For some reason, we use three threads to do the three things, now the order of threads is very important because we can't do x + y unless getx and gety have finished. In a word, semaphore is used when we care about the order of execution of multi-threading.

[prayagupa]

got you. It sounds similar to barrier. I can say that wait until threads x and y are completed, then calculate z = x + y. I know java has CyclicBarrier. Also, I'm not sure if I can say mapreduce is semaphore usecase too, because I can not reduce until all maps are completed.

[Yves]

@prayagupd Yes. You can say that.

[beroal]

The links are dead. The answer does not explain what is the difference between the specifications of binary semaphore and mutex. “The principle of ownership” is about how a synchronization primitive is used, hence it does not belong to a specification. Downvoting.

[Mohammad Kholghi]

@beroal I have edited this, and the links are updated. Wait till the update is accepted and enjoy reading them...

[John]

@paxdiablo As you say that 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 question arises, does the implementation of mutex and semaphore have any relation (for standard library)?

[John]

@paxdiablo "Dutch. Probeer te verlagen means to try and decrease while verhogen means to increase."? Any clerical error? What's that?

[John]

Highlight on "The mutex is used for protecting parts of code from running concurrently, semaphores are used for one thread to signal another thread to run"

[paxdiablo]

@John, P and V are the normal operations on a counting semaphore, I was just explaining where they came from. In terms of whether implementations are similar, it's possible. But, given how insanely efficient you'd want them to be and the fact that mutex operations are a lot simpler to implement, a mutex would likely not be done in terms of a semaphore. However, you could quite easily construct a counting semaphore using a mutex to control access to the count, but it probably depends on whether there's a better way in whatever architecture you're targeting.

[paxdiablo]

Just one possible nitpick, mutexes really protect resources, not code. Access to those resources may be performed in widely dispersed code sections so, as long as all those sections use the same mutex, everything should be fine. The way your answer reads (to me) is that the mutex protects only one section of code.