Skip to content

Instantly share code, notes, and snippets.

@sguzman
Last active May 20, 2022 04:02
Show Gist options
  • Save sguzman/9594227 to your computer and use it in GitHub Desktop.
Save sguzman/9594227 to your computer and use it in GitHub Desktop.
#include <mutex>
#include <condition_variable>
using namespace std;
class semaphore
{
public:
semaphore(int count_ = 0) : count{count_}
{}
void notify()
{
unique_lock<mutex> lck(mtx);
++count;
cv.notify_one();
}
void wait()
{
unique_lock<mutex> lck(mtx);
while(count == 0)
{
cv.wait(lck);
}
--count;
}
private:
mutex mtx;
condition_variable cv;
int count;
};
Copy link

ghost commented May 22, 2016

Note that if you test this, you'll see that this implementation is a "weak" semaphore, and some threads will starve others.

@Ezzz-dev
Copy link

Could you explain how will this starve other threads.

@AlexMeuer
Copy link

AlexMeuer commented Jul 15, 2016

@TwistedScorpio
Assume Thread_A acquires the semaphore, and Thread_B and Thread_C are waiting for it.
When Thread_A releases the semaphore, either B or C will acquire it.
So now B has the semaphore, we would assume that C will acquire it next.
However, A has started waiting for the semaphore again. And herein lies the problem.
A could acquire the semaphore again and C will still be waiting. This can become very serious if C is kept waiting for a long time and can be disastrous with many threads.

You can solve this by ensuring that each thread acquires the semaphore in the order they started waiting for it. The ticket algorithm is one example of how to accomplish this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment