Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

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:;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;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:;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

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

while( count >= N ) {
wait( has_empty, m); // wait the has_empty event
signal(m, has_item);//

while( count <=0 ) {
wait( has_item, m); // wait the has_item event
signal(has_empty, m);//

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


libc/glibc: mutex, conditional variable, semaphore

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

Java: synchronized, wait/notify




Leave a Reply

Your email address will not be published. Required fields are marked *