StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Your counting semaphore algorithm is missing a while loop, and signals the semaphore unnecessarily.</p> <p>Original logic, with locks added (see other answer):</p> <pre><code>int Semaphore::P(){ Lock(); if(value <= 0){ pthread_cond_wait(&c, &m); } value--; Unlock(); } int Semaphore::V(){ Lock(); value++; if(value > 0){ pthread_cond_signal(&c); } Unlock(); } </code></pre> <p>The correct way:</p> <pre><code>int Semaphore::P(){ Lock(); while (value <= 0){ // not if pthread_cond_wait(&c, &m); } // value is now > 0, guaranteed by while loop value--; // value is now >= 0 Unlock(); } int Semaphore::V(){ Lock(); int prior_value = value++; Unlock(); // E.g. if prior_value is 50, should we signal? Why? if (prior_value == 0) // was not signaled previously, now is. pthread_cond_signal(&c); } </code></pre> <p>For efficiency, gather information about whether to signal or not inside the mutex, but then do the signal outside the mutex. Mutexes should be held over as few machine instructions as possible because they add contention, reducing concurrency. The signal operation can take hundreds of cycles (trip to the kernel to do wait queue manipulation).</p> <p>You have to use a loop when waiting on a condition variable because there can spurious wakeups. Also, if you signal outside of the mutex, condition signal does not always go to the "intended" thread. Between the <code>unlock</code> and the <code>signal</code>, some thread can sneak in and call <code>P</code> and decrement the mutex. Then the one which wakes up on the condition must re-evaluate the test, otherwise it will incorrectly proceed.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload