Ccna final exam - java, php, javascript, ios, cshap all in one. This is a collaboratively edited question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
Friday, May 18, 2012
Difference between binary semaphore and mutex
Is there any difference between binary semaphore and mutex or they are essentialy same?
Mutex can be released only by thread that had acquired it, while you can signal semaphore from any other 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.
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
MUTEX VS. SEMAPHORES – PART 1: SEMAPHORES MUTEX VS. SEMAPHORES – PART 2: THE MUTEX MUTEX VS. SEMAPHORES – PART 3 (FINAL PART): MUTUAL EXCLUSION PROBLEMS
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.
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 atask 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
Here is a simple example:
Thread A Thread B Take Mutex access data ... Take Mutex <== Will block ... Give Mutex access data <== Unblocks ... Give Mutex
Binary 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 <== wait for something Do Something Noteworthy Give BinSemaphore do something <== unblocks
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 so a give and a take on the same binary semaphore.
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 implementation is 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 they 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.
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).
On Windows, there are two differences between mutexes and binary semaphores:
A mutex can only be released by the thread which has ownership, i.e. the thread which previously called the Wait function, (or which took ownership when creating it). A semaphore can be released by any thread. A thread can call a wait function repeatedly on a mutex without blocking. However, if you call a wait function twice on a binary semaphore without releasing the semaphore in between, the thread will block.
Modified question is - What's the difference between A mutex and a "binary" semaphore in "Linux"?
Ans: Following are the differences – i) Scope – The scope of mutex is within a process address space which has created it and is used for synchronization of threads. Whereas semaphore can be used across process space and hence it can be used for interprocess synchronization.
ii) Mutex is lightweight and faster than semaphore. Futex is even faster.
iii) Mutex can be acquired by same thread successfully multiple times with condition that it should release it same number of times. Other thread trying to acquire will block. Whereas in case of semaphore if same process tries to acquire it again it blocks as it can be acquired only once.
The answer may depend on the target OS. For example, at least one RTOS implementation I'm familiar with will allow multiple sequential "get" operations against a single OS mutex, so long as they're all from within the same thread context. The multiple gets must be replaced by an equal number of puts before another thread will be allowed to get the mutex. This differs from binary semaphores, for which only a single get is allowed at a time, regardless of thread contexts.
The idea behind this type of mutex is that you protect an object by only allowing a single context to modify the data at a time. Even if the thread gets the mutex and then calls a function that further modifies the object (and gets/puts the protector mutex around its own operations), the operations should still be safe because they're all happening under a single thread.
{ mutexGet(); // Other threads can no longer get the mutex.
// Make changes to the protected object. // ...
objectModify(); // Also gets/puts the mutex. Only allowed from this thread context.
// Make more changes to the protected object. // ...
mutexPut(); // Finally allows other threads to get the mutex. }
Of course, when using this feature, you must be certain that all accesses within a single thread really are safe!
I'm not sure how common this approach is, or whether it applies outside of the systems with which I'm familiar. For an example of this kind of mutex, see the ThreadX RTOS.
A Mutex controls access to a single shared resource. It provides operations to acquire() access to that resource and release() it when done.
A Semaphore controls access to a shared pool of resources. It provides operations to Wait() until one of the resources in the pool becomes available, and Signal() when it is given back to the pool.
When number of resources a Semaphore protects is greater than 1, it is called a Counting Semaphore. When it controls one resource, it is called a Boolean Semaphore. A boolean semaphore is equivalent to a mutex.
Thus a Semaphore is a higher level abstraction than Mutex. A Mutex can be implemented using a Semaphore but not the other way around.
Apart from the fact that mutexes have an owner, the two objects may be optimized for different usage. Mutexes are designed to be held only for a short time; violating this can cause poor performance and unfair scheduling. For example, a running thread may be permitted to acquire a mutex, even though another thread is already blocked on it. Semaphores may provide more fairness, or fairness can be forced using several condition variables.
In windows the difference is as below. MUTEX: process which successfully executes wait has to execute a signal and vice versa. BINARY SEMAPHORES: Different processes can execute wait or signal operation on a semaphore.
Mutexes have ownership, unlike semaphores. Although any thread, within the scope of a mutex, can get an unlocked mutex and lock access to the same critical section of code,only the thread that locked a mutex should unlock it.
Mutex can be released only by thread that had acquired it, while you can signal semaphore from any other thread (or process), so semaphores are more suitable for some synchronization problems like producer-consumer.
ReplyDeleteOn Windows, binary semaphores are more like event objects than mutexes.
The Toilet example is an enjoyable analogy:
ReplyDeleteMutex:
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
Nice articles on the topic:
ReplyDeleteMUTEX VS. SEMAPHORES – PART 1: SEMAPHORES
MUTEX VS. SEMAPHORES – PART 2: THE MUTEX
MUTEX VS. SEMAPHORES – PART 3 (FINAL PART): MUTUAL EXCLUSION PROBLEMS
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.
They are NOT the same thing. They are used for different purposes!
ReplyDeleteWhile 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 atask 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
Here is a simple example:
Thread A Thread B
Take Mutex
access data
... Take Mutex <== Will block
...
Give Mutex access data <== Unblocks
...
Give Mutex
Binary 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 <== wait for something
Do Something Noteworthy
Give BinSemaphore do something <== unblocks
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 so a give and a take on the same binary semaphore.
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 implementation is different and they offer slightly different services.
ReplyDeleteThe 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 they 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.
Their synchronization semantics are very different:
ReplyDeletemutexes 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).
On Windows, there are two differences between mutexes and binary semaphores:
ReplyDeleteA mutex can only be released by the thread which has ownership, i.e. the thread which previously called the Wait function, (or which took ownership when creating it). A semaphore can be released by any thread.
A thread can call a wait function repeatedly on a mutex without blocking. However, if you call a wait function twice on a binary semaphore without releasing the semaphore in between, the thread will block.
Modified question is - What's the difference between A mutex and a "binary" semaphore in "Linux"?
ReplyDeleteAns: Following are the differences –
i) Scope – The scope of mutex is within a process address space which has created it and is used for synchronization of threads. Whereas semaphore can be used across process space and hence it can be used for interprocess synchronization.
ii) Mutex is lightweight and faster than semaphore. Futex is even faster.
iii) Mutex can be acquired by same thread successfully multiple times with condition that it should release it same number of times. Other thread trying to acquire will block. Whereas in case of semaphore if same process tries to acquire it again it blocks as it can be acquired only once.
The answer may depend on the target OS. For example, at least one RTOS implementation I'm familiar with will allow multiple sequential "get" operations against a single OS mutex, so long as they're all from within the same thread context. The multiple gets must be replaced by an equal number of puts before another thread will be allowed to get the mutex. This differs from binary semaphores, for which only a single get is allowed at a time, regardless of thread contexts.
ReplyDeleteThe idea behind this type of mutex is that you protect an object by only allowing a single context to modify the data at a time. Even if the thread gets the mutex and then calls a function that further modifies the object (and gets/puts the protector mutex around its own operations), the operations should still be safe because they're all happening under a single thread.
{
mutexGet(); // Other threads can no longer get the mutex.
// Make changes to the protected object.
// ...
objectModify(); // Also gets/puts the mutex. Only allowed from this thread context.
// Make more changes to the protected object.
// ...
mutexPut(); // Finally allows other threads to get the mutex.
}
Of course, when using this feature, you must be certain that all accesses within a single thread really are safe!
I'm not sure how common this approach is, or whether it applies outside of the systems with which I'm familiar. For an example of this kind of mutex, see the ThreadX RTOS.
A Mutex controls access to a single shared resource. It provides operations to acquire() access to that resource and release() it when done.
ReplyDeleteA Semaphore controls access to a shared pool of resources. It provides operations to Wait() until one of the resources in the pool becomes available, and Signal() when it is given back to the pool.
When number of resources a Semaphore protects is greater than 1, it is called a Counting Semaphore. When it controls one resource, it is called a Boolean Semaphore. A boolean semaphore is equivalent to a mutex.
Thus a Semaphore is a higher level abstraction than Mutex. A Mutex can be implemented using a Semaphore but not the other way around.
Mutex work on blocking critical region, But Semaphore work on count.
ReplyDeleteApart from the fact that mutexes have an owner, the two objects may be optimized for different usage. Mutexes are designed to be held only for a short time; violating this can cause poor performance and unfair scheduling. For example, a running thread may be permitted to acquire a mutex, even though another thread is already blocked on it. Semaphores may provide more fairness, or fairness can be forced using several condition variables.
ReplyDeleteIn windows the difference is as below.
ReplyDeleteMUTEX: process which successfully executes wait has to execute a signal and vice versa. BINARY SEMAPHORES: Different processes can execute wait or signal operation on a semaphore.
Mutexes have ownership, unlike semaphores. Although any thread, within the scope of a mutex, can get an unlocked mutex and lock access to the same critical section of code,only the thread that locked a mutex should unlock it.
ReplyDelete