Difference between binary semaphore and mutex
They’re semantically the same, but in practice you will notice weird differences (especially on Windows).
I suppose weird wasn’t the correct expression. A mutex also supports ownership and sometimes reentry. This is the case in Windows. In addition, semaphores in Windows are implemented on top of Event objects, however, I’m unsure of the practical implications of this.
36 Answers 36
They are NOT the same thing. They are used for different purposes!
While both types of semaphores have a full/empty state and use the same API, their usage is very different.
Mutual Exclusion Semaphores
Mutual Exclusion semaphores are used to protect shared resources (data structure, file, etc..).
A Mutex semaphore is «owned» by the task that takes it. If Task B attempts to semGive a mutex currently held by Task A, Task B’s call will return an error and fail.
Mutexes always use the following sequence:
- SemTake - Critical Section - SemGive
Thread A Thread B Take Mutex access data . Take MutexBinary Semaphore
Binary Semaphore address a totally different question:
- Task B is pended waiting for something to happen (a sensor being tripped for example).
- Sensor Trips and an Interrupt Service Routine runs. It needs to notify a task of the trip.
- Task B should run and take appropriate actions for the sensor trip. Then go back to waiting.
Task A Task B . Take BinSemaphore Note that with a binary semaphore, it is OK for B to take the semaphore and A to give it.
Again, a binary semaphore is NOT protecting a resource from access. The act of Giving and Taking a semaphore are fundamentally decoupled.
It typically makes little sense for the same task to call both give and take on the same binary semaphore.
Isn't a mutex better than a binary semaphore then? Since it doesn't make sense if someone releases a lock which he doesn't actually hold.
They have different purposes. Mutex is for exclusive access to a resource. A Binary semaphore should be used for Synchronization (i.e. "Hey Someone! This occurred!"). The Binary "giver" simply notifies whoever the "taker" that what they were waiting for happened.
@Pacerier You are confusing the purpose. A mutex is intended protect a critical region. You are correct it doesn't make sense to use a Binary Semaphore. I'll update the answer to explain the purpose of each.
@Benoit So Can we say that Mutex are Used for atomicity and Binary Semaphore for Ordering perspective since Task B will be waiting for Task A to signal the release of lock inherently making sure of ordering of operations on a data strurcture?
- A mutex can be released only by the thread that had acquired it.
- A binary semaphore can be signaled by any thread (or process).
so semaphores are more suitable for some synchronization problems like producer-consumer.
On Windows, binary semaphores are more like event objects than mutexes.
Mutex can be released only by thread that had acquired it -- I just tried with a simple pthread_mutex based program, a thread can unlock mutex locked in main thread
@warl0ck As per the man page of pthread_mutex_lock linux.die.net/man/3/pthread_mutex_lock : "If the mutex type is PTHREAD_MUTEX_ERRORCHECK, then error checking shall be provided. If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned."
@warl0ck Please see stackoverflow.com/a/5492499/385064 'Pthreads has 3 different kinds of mutexes: Fast mutex, recursive mutex, and error checking mutex. You used a fast mutex which, for performance reasons, will not check for this error. If you use the error checking mutex on Linux you will find you get the results you expect.'
In our code we have used mutex also for synchronization purposes.The Thread which locks the mutex again tried to lock the mutex.Then it goes to blocked state.What we have seen is that we are able to unlock this from another thread .Thus achieving synchronization between the two.We are using posix standard only .So the major difference sited between mutex and binary semaphore seems vague.
@achoora I agree that it is wrong to specialize semaphore for synchronization. Actually all the mutex,binary-semaphore,barrier,pipelines are different patterns for synchronization. In design perspective, mutex are more like state-pattern where the algorithm that is selected by the state can change the state. The binary-semaphore are more like strategy pattern where the external algorithm can change the state and eventually the algorithm/strategy selected to run.
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
While what is said by david is correct, but it is NOT the answer to the question asked. Mladen Jankovic answer is the answer to the question asked, where point is made to differentiate "binary-semaphore" vs "mutex".
In other words: A binary semaphore is identical to a mutex. Downvoted for presenting the information of a one-liner in several paragraphs. And not even addressing the question being asked.
Nice articles on the topic:
From part 2:
The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it. If a task tries to unlock a mutex it hasn’t locked (thus doesn’t own) then an error condition is encountered and, most importantly, the mutex is not unlocked. If the mutual exclusion object doesn't have ownership then, irrelevant of what it is called, it is not a mutex.
Thanks for the link, the explanations there are excellent. The link has changed: feabhas.com/blog/2009/09/… (Use < Prev and Next >to navigate to the other two articles.
Note - the lack of ownership also prevents the operating system from working around priority inversion. For this reason, I generally use condition variables as opposed to semaphores for producer/consumer architectures.
+1 foe excellent article links. The best article explaining semaphore and mutex with "what-it-is" and "what-it-does" computing.llnl.gov/tutorials/pthreads I had used this article as my behind the scene reference, which technically does explain everything about mutex/conditionals and other constructs built on their top like semaphore/barrier/reader-writer, but nowhere explicit and concise about problems faced with constructs. In short it is reference. 🙂
Since none of the above answer clears the confusion, here is one which cleared my confusion.
Strictly speaking, a mutex is a locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.
Their synchronization semantics are very different:
- mutexes allow serialization of access to a given resource i.e. multiple threads wait for a lock, one at a time and as previously said, the thread owns the lock until it is done: only this particular thread can unlock it.
- a binary semaphore is a counter with value 0 and 1: a task blocking on it until any task does a sem_post. The semaphore advertises that a resource is available, and it provides the mechanism to wait until it is signaled as being available.
As such one can see a mutex as a token passed from task to tasks and a semaphore as traffic red-light (it signals someone that it can proceed).
At a theoretical level, they are no different semantically. You can implement a mutex using semaphores or vice versa (see here for an example). In practice, the implementations are different and they offer slightly different services.
The practical difference (in terms of the system services surrounding them) is that the implementation of a mutex is aimed at being a more lightweight synchronisation mechanism. In oracle-speak, mutexes are known as latches and semaphores are known as waits.
At the lowest level, they use some sort of atomic test and set mechanism. This reads the current value of a memory location, computes some sort of conditional and writes out a value at that location in a single instruction that cannot be interrupted. This means that you can acquire a mutex and test to see if anyone else had it before you.
A typical mutex implementation has a process or thread executing the test-and-set instruction and evaluating whether anything else had set the mutex. A key point here is that there is no interaction with the scheduler, so we have no idea (and don't care) who has set the lock. Then we either give up our time slice and attempt it again when the task is re-scheduled or execute a spin-lock. A spin lock is an algorithm like:
Count down from 5000: i. Execute the test-and-set instruction ii. If the mutex is clear, we have acquired it in the previous instruction so we can exit the loop iii. When we get to zero, give up our time slice. When we have finished executing our protected code (known as a critical section) we just set the mutex value to zero or whatever means 'clear.' If multiple tasks are attempting to acquire the mutex then the next task that happens to be scheduled after the mutex is released will get access to the resource. Typically you would use mutexes to control a synchronised resource where exclusive access is only needed for very short periods of time, normally to make an update to a shared data structure.
A semaphore is a synchronised data structure (typically using a mutex) that has a count and some system call wrappers that interact with the scheduler in a bit more depth than the mutex libraries would. Semaphores are incremented and decremented and used to block tasks until something else is ready. See Producer/Consumer Problem for a simple example of this. Semaphores are initialised to some value - a binary semaphore is just a special case where the semaphore is initialised to 1. Posting to a semaphore has the effect of waking up a waiting process.
A basic semaphore algorithm looks like:
(somewhere in the program startup) Initialise the semaphore to its start-up value. Acquiring a semaphore i. (synchronised) Attempt to decrement the semaphore value ii. If the value would be less than zero, put the task on the tail of the list of tasks waiting on the semaphore and give up the time slice. Posting a semaphore i. (synchronised) Increment the semaphore value ii. If the value is greater or equal to the amount requested in the post at the front of the queue, take that task off the queue and make it runnable. iii. Repeat (ii) for all tasks until the posted value is exhausted or there are no more tasks waiting. In the case of a binary semaphore the main practical difference between the two is the nature of the system services surrounding the actual data structure.
EDIT: As evan has rightly pointed out, spinlocks will slow down a single processor machine. You would only use a spinlock on a multi-processor box because on a single processor the process holding the mutex will never reset it while another task is running. Spinlocks are only useful on multi-processor architectures.