mutex , semaphore, monitor, condition variable

mutex, semaphore, monitor, condition variable are basic computer science concepts, but can easily get confused. some notes here.

mutex: thread has ownership, released by the one who acquired it. no execution order ( motivation for semaphore’s schedule constraint)

it is usually available in the libc/glibc pthread implementation.

source code of pthread_mutex_lock() at:

https://sourceware.org/git/?p=glibc.git;a=blob;f=nptl/pthread_mutex_lock.c;h=493fe4377821c3e14382eeb32a6c6ef414a9289c;hb=e0043e17dfc52fe1702746543127cb4a87232bcd

semaphore: basically manipulate the integer, threads/process has no ownership, and wait/signal are commutative, the result are the same regardless the order of execution.

user cases:

(1) mutual exclusive like( mutex),

(2) counting semaphore to control access to a pool of a shared resources,

(3) scheduling constraint ( need wait(), and value can be negative, but some implementations does not allow negative value). cause one thread to wait for a specific action to be signaled from another thread ( execution order).

cons: no linguistic connection between semaphore and data it tried to control, multiple purposes, thus hard to get it right.

libc/glibc implementation: sem_wait

https://sourceware.org/git/?p=glibc.git;a=blob;f=nptl/sem_wait.c;h=fce7ed43ee4cde0ba3417571398c1683341bdc01;hb=e0043e17dfc52fe1702746543127cb4a87232bcd

conditional variable: wait(), signal() does not keep history, under mutex, it is basically some kind of wait queue ( mesa semantics, so need to recheck the conditions again in while loop when the thread are waked up!)

libc/glibc implementation: https://sourceware.org/git/?p=glibc.git;a=blob;f=nptl/pthread_cond_wait.c;h=0d6558b642f02b8191c502ff067c6414f105cd74;hb=e0043e17dfc52fe1702746543127cb4a87232bcd

monitor = mutex + conditional variable

Bounded Producer/Consumer example using semaphore:

//using the producer_slots, consumer_slots seems  easier  
// to  understand than empty, full.
// normally called empty slot, associated wait queue for the producer
semaphore producer_slots = N;
// normally called full, filled slot, wait queue for consumer  
semaphore consume_slots = 0; 
mutex m;  // can be implemented using semaphore using binary semaphore.

producer() {  // several producer's threads/processes
 wait(producer_slots); // grab a producer slot,if no put into producer's wait queue
m.lock();  put_one_item_into_shared_buffer();  m.unlock();
signal( consumer_slots ); // add a consumer slot,  signal threads in consumer's wait queue to wake up
}

consumer(){
wait( consumer_slots ) ; /// grab a consumer slot, wait for something in the buffer
m.lock(); pull_one_item_from_the_shared_buffer(), m.unlock();
signal( producer_slots ); //add a producer slot, wake producer's queue
}

Bounded Producer/Consumer example using monitor ( mutex + conditional variables):

int count = 0 ;// how many items on the buffer N;  
mutex m; // protect count
cond has_empty; // at least one empty slot event
cond has_item;  // at least one item event

producer(){
m.lock();
while( count >= N ) {
wait( has_empty, m); // wait the has_empty event
}
put_one_item_into_shared_buffer();
count++;
signal(m, has_item);//
m.unlock();
}

consumer(){
m.lock();
while( count <=0 ) {
wait( has_item, m); // wait the has_item event
}
pull_one_item_from_the_shared_buffer();
count--;
signal(has_empty, m);//
m.unlock();
}

code using mutex conditional variable seems easy to understand than the semaphore counterpart.

Implementations:

libc/glibc: mutex, conditional variable, semaphore

C/C++11 : mutex and conditional variable, does not have native semaphore

Java: synchronized, wait/notify http://www.oracle.com/us/technologies/java/index-140767.html

References

http://chris.dragan.name/2013/05/28/those-pesky-mutices/

https://www.quora.com/What-is-the-difference-between-a-mutex-and-a-semaphore

https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-1-semaphores/

https://blog.feabhas.com/2009/09/mutex-vs-semaphores-%E2%80%93-part-2-the-mutex/

https://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/sema-vs-monitor.html

https://www.quora.com/Semaphore-vs-mutex-vs-monitor-What-are-the-differences