Semaphore vs. Mutex

[Trond]

Question: Is there anything you can do with a semaphore that you can't do with a mutex?

Background information:
http://en.wikipedia.org/wiki/Semaphore_(programming)
http://en.wikipedia.org/wiki/Mutex

A semaphore could have the value 0, indicating that no wakeups were saved, or some positive value if one or more wakeups were pending.

Dijkstra proposed having two operations, down and up (which are generalizations of sleep and wakeup, respectively). The down operation on a semaphore checks to see if the value is greater than 0. If so, it decrements the value (i.e., uses up one stored wakeup) and just continues. If the value is 0, the process is put to sleep without completing the down for the moment. Checking the value, changing it, and possibly going to sleep is all done as a single, indivisible, atomic action.

The up operation increments the value of the semaphore addressed. If one or more processes were sleeping on that semaphore, unable to complete an earlier down operation, one of them is chosen by the system (e.g., at random) and is allowed to complete its down. Thus, after an up on a semaphore with processes sleeping on it, the semaphore will still be 0, but there will be one fewer process sleeping on it. No process ever blocks doing an up.

A mutex is a variable that can be in one of two states: unlocked or locked. Consequently, only 1 bit is required to represent it, but in practice an integer often is used, with 0 meaning unlocked and all other values meaning locked. Two procedures are used with mutexes. When a process (or thread) needs access to a critical region, it calls mutex_lock. If the mutex is currently unlocked (meaning that the critical region is available), the call succeeds and the calling thread is free to enter the critical region.

On the other hand, if the mutex is already locked, the caller is blocked until the process in the critical region is finished and calls mutex_unlock. If multiple processes are blocked on the mutex, one of them is chosen at random and allowed to acquire the lock.

[netmaestro]

The main difference is that a semaphore has an initial count and a maximum count, both of which are settable at creation:

lInitialCount
[in] Initial count for the semaphore object. This value must be greater than or equal to zero and less than or equal to lMaximumCount. The state of a semaphore is signaled when its count is greater than zero and nonsignaled when it is zero. The count is decreased by one whenever a wait function releases a thread that was waiting for the semaphore. The count is increased by a specified amount by calling the ReleaseSemaphore function.

lMaximumCount
[in] Maximum count for the semaphore object. This value must be greater than zero.

[Trond]

Yes, yes, I know that. But what can that count be used for that can't be done with a mutex anyways?

[freak]

The idea (atleast with mutex/semaphores in the Windows API) is that a mutex protects a resource that can only be accessed by one user/thread at a time,
while a semaphore protects a resource that multiple users can access at once, but which has a limit on the ammount of users.

A wait-function call for a semaphore will succeed as long as its count is above zero (meaning there is still free capacity to use the shared resource)
When the count reaches zero, new waits are blocked until somebody else releases his lock.
So its basically just a mutex that can be "owned" by N threads/users at once instead of just one.

You could simply emulate this with a mutex + a counter, but it would probably be less efficient.

A custom "LockSemaphore()" could look somewhat like this:
* lock mutex that protects counter
* check counter, if > 0 then perfect, access granted
* if counter = 0, release mutex
* wait for a period of time
* try again

The not so perfect part here is the "wait for a period of time". The most intuitive way would
be to put a Delay(x) and simply try again.
Two problems: first it is no real wait, as the thread wakes up every x milliseconds to do work,
and secondly the wait does not immediately stop when the counter is > zero,
as the delay will first fully expire before the thread tries again.

With a semaphore you have a real "waitable" object, where you call
WaitForSingleObject(), and it will put the thread fully to sleep for exactly
the time needed until the object becomes available, not longer.

Other than this, it really is just a mutex + a counter.

[Trond]

The idea (atleast with mutex/semaphores in the Windows API) is that a mutex protects a resource that can only be accessed by one user/thread at a time,
while a semaphore protects a resource that multiple users can access at once, but which has a limit on the ammount of users.

Ok, thanks, although I don't see why one would ever want that.

[freak]

Ok, thanks, although I don't see why one would ever want that.

Same here.
A networkserver with a maximum for allowed simultanous transfers maybe or something along these lines.

[freak]

I just stumbled upon this by accident:
http://blogs.msdn.com/oldnewthing/archi ... 96248.aspx

The no-owner concept indeed allows some things a mutex cannot do.

[Trond]

The no-owner concept indeed allows some things a mutex cannot do.

Yes, but nothing you can't do in another and cleaner way. Why would you want to share a lock between multiple threads? It defeats the entire purpose of locking! The only safe time to do that, is when there is only one path of execution through the lock spaghetti, which means that you should wrap it in a thread and use a normal mutex. (Which is also less prone to programmer errors.)
The work count thing can also be done easily with a mutex that protects a count variable, or without blocking at all with an atomic counter (LOCK XADD 1/-1).

Either I am missing something big, or someone else is!

[Mistrel]

A semaphore is great because you can tell a thread to wait until a particular piece of code needs to be processed. Also with a semaphore you can tell it to do something a number of times by what you set the counter.

For example:

Code: Select all

MaxJobs=50
JobRuns=2

hThreadB=CreateSemaphore_(#Null,0,MaxJobs,"hThreadB")
hWaitThreadB=CreateSemaphore_(#Null,0,1,"hWaitThreadB")

Procedure ThreadA(Null)
	Shared hThreadB,hWaitThreadB,JobRuns
	Repeat
		ReleaseSemaphore_(hThreadB,JobRuns,@Count)
		If WaitForSingleObject_(hWaitThreadB,#INFINITE)=#WAIT_OBJECT_0
			Debug "ThreadA"
			Delay(200) ; Precious code
		EndIf
	ForEver
EndProcedure

Procedure ThreadB(Null)
	Shared hThreadB,hWaitThreadB,JobRuns
	Repeat
		If WaitForSingleObject_(hThreadB,#INFINITE)=#WAIT_OBJECT_0
			Debug "ThreadB"
			Delay(200) ; Precious code
			JobsComplete+1
		EndIf
		If JobsComplete=JobRuns
			ReleaseSemaphore_(hWaitThreadB,1,@Count)
			JobsComplete=0
		EndIf
	ForEver
EndProcedure

CreateThread(@ThreadA(),0)
CreateThread(@ThreadB(),0)

Repeat: Delay(1)
	; main process
ForEver

Through clever coding most tasks for a semaphore could probably be done with a mutex instead but it would be very cumbersome to do so. I like semaphores because they have no owner and can be waited upon until signaled. That's not an easy thing to synchronize with a mutex.

I'm not well versed enough in the theoretical differences between a mutex and a semaphore. Someone else can comment on whether there are cases where a mutex cannot do something that a semaphore can.

This article doesn't talk about mutexes but it does give a few great examples for semaphores in its benchmarks.
http://www.belshe.com/2007/11/20/semaph ... s-showdown

This is also an excellent read: The Little Book of Semaphores

[pdwyer]

The no-owner concept indeed allows some things a mutex cannot do.

Yes, but nothing you can't do in another and cleaner way. Why would you want to share a lock between multiple threads? It defeats the entire purpose of locking! The only safe time to do that, is when there is only one path of execution through the lock spaghetti, which means that you should wrap it in a thread and use a normal mutex. (Which is also less prone to programmer errors.)
The work count thing can also be done easily with a mutex that protects a count variable, or without blocking at all with an atomic counter (LOCK XADD 1/-1).

Either I am missing something big, or someone else is!

Maybe if you are building a RDBS or something, you have an enormous data file that the engine uses multiple threads through the one lock on the data so that queries can run in tandem. I've never written a database engine though.

The idea of store.exe reading the exchange data store spring to mind, big stuff

[Trond]

All I can see Mistrel's code doing is put out "B" JobRuns times and "A" one time, which I can do with a mutex and ten lines less code (the lines are much shorter as well).

Code: Select all

Global JobRuns = 3
Global JobMutex = CreateMutex()

Procedure ThreadA(Null)
  Repeat
    LockMutex(JobMutex)
    Debug "A"
    Delay(200) ; Precious code
    UnlockMutex(JobMutex)
  ForEver
EndProcedure

Procedure ThreadB(Null)
  Repeat
    LockMutex(JobMutex)
    For JobsComplete = 0 To JobRuns-1
      Debug "BBBBBBBBBBBBBB"
      Delay(200) ; Precious code
    Next
    UnlockMutex(JobMutex)
  ForEver
EndProcedure

CreateThread(@ThreadA(),0)
CreateThread(@ThreadB(),0)

Repeat: Delay(1)
   ; main process
ForEver

[Thalius]

Semaphores can be used to priotitize access on global ressources by threads dynamically by aquiring more semaphore-ressources on-demand basis.

Using Semaphores you can Release a global ressource from a thread that is not the owner of the ressource ( this is to be used with care - advanced ). This tho leaves some interesting construct possibilities in load balancing especially on multicore-cpu systems to for example process an image on all cores simultaniously and switch dynamically thru the processes based on ressource-demand.

Altho alot is doable with Mutex and Criticalsections also. Semaphores tho have their flavour in certain conditions tho. Some people say Semaphores are easer to understand than Mutexes . .however i think its a matter of taste. The Mutex Model generally while also a bit simpler is more compact. But yeah, writing load critical Software with lots of thread usage can be more efficient with Semaphores.

Few Semaphore Examples:
http://www.beunited.org/bebook/The%20Ke ... e_Examples

Thalius