Thread: Semaphore review

I have need of a semaphore, but I have been unable to find any good ones on the web, only some source.
So I modified the source to roll out my own simplistic semaphore, and thus I'd like for some other people to look it over and see that I haven't done something stupid.
If you know of a good (and fast!) semaphore out there already, I'd also be interested.

Code:

#include <boost/thread/condition_variable.hpp>
#include <boost/thread/mutex.hpp>    
#include <tbb/atomic.h>

class XSemaphore
{
	//The current semaphore count.
	tbb::atomic<unsigned int> m_count;

	//mutex_ protects count_.
	//Any code that reads or writes the count_ data must hold a lock on
	//the mutex.
	boost::mutex m_mutex;

	//Code that increments count_ must notify the condition variable.
	boost::condition_variable m_condition;

public:
	explicit XSemaphore(unsigned int initial_count)
	{
		m_count = initial_count;
	}

	unsigned int get_count() const //for debugging/testing only
	{
		//The "lock" object locks the mutex when it's constructed,
		//and unlocks it when it's destroyed.
		//boost::unique_lock<boost::mutex> lock(mutex_);
		return m_count;
	}

	void signal() //called "release" in Java
	{
		++m_count;

		//Wake up any waiting threads. 
		//Always do this, even if count_ wasn't 0 on entry. 
		//Otherwise, we might not wake up enough waiting threads if we 
		//get a number of signal() calls in a row.
		m_condition.notify_one(); 
	}

	void wait() //called "acquire" in Java
	{
		while (m_count == 0)
		{
			boost::unique_lock<boost::mutex> lock(m_mutex);
			m_condition.wait(lock);
		}
		--m_count;
	}

};

O_o

It seems fine to me.

But I must say, I find it strangely funny that you are using primitives of more utility to me to build a semaphore. ^_^;

[Edit]Clarified.[/Edit]

[Edit]Yes. I'm well aware; I still find it funny.[/Edit]

Soma

Semaphores have their use, too, but many libraries do not seem to agree, and hence exclude them o_O

You could get stuck in a wait() while m_count != 0.
notify_one() will only release a waiting thread. If there is no waiting thread then the notify is lost.

Eg.
- T1 context switch on line 46
- T2 runs signal()
- T1 is stuck in wait()

gg

Would changing lock on line 48 to a timed_lock be a better solution?

Originally Posted by phantomotap

No.

Keep track of the number of threads that are waiting separately and always notify at least one thread if there is at least one thread waiting.

This requires that you change the order of operations. Notify first, update later.

What if there are no threads waiting?
What if there is a context switch just after the while (m_count == 0) loop and one thread completes the signaling method?
By that time, there are no threads waiting, and hence notify won't do anything.

Eventcounts - 1024cores

[edit]Dmitry's blog is some of the best lockfree reading on the net that I've seen.[/edit]
http://www.1024cores.net/

gg

boost says:
For wait:

Atomically call lock.unlock() and blocks the current thread. The thread will unblock when notified by a call to this->notify_one() or this->notify_all(), or spuriously

For notify_one:

If any threads are currently blocked waiting on *this in a call to wait or timed_wait, unblocks one of those threads.

I see no guarantees it will unblock a thread which isn't waiting (or hasn't had a chance to yet).

Eventcount speaks of some condition var, with no source code. There was some source in the download section, but it's for Windows only, which doesn't work for me. It needs to work on Windows and Linux.

Second attempt:

Code:

#include <boost/thread/condition_variable.hpp>
#include <boost/thread/mutex.hpp>    

class XSemaphore
{
	//The current semaphore count.
	unsigned int m_count;

	//mutex_ protects count_.
	//Any code that reads or writes the count_ data must hold a lock on
	//the mutex.
	boost::mutex m_mutex;

	//Code that increments count_ must notify the condition variable.
	boost::condition_variable m_condition;

public:
	explicit XSemaphore(unsigned int initial_count)
	{
		m_count = initial_count;
	}

	unsigned int get_count() const
	{
		//The "lock" object locks the mutex when it's constructed,
		//and unlocks it when it's destroyed.
		//boost::unique_lock<boost::mutex> lock(mutex_);
		return m_count;
	}

	void down() //called "release" in Java
	{
		boost::unique_lock<boost::mutex> lock(m_mutex);
		++m_count;

		//Wake up any waiting threads. 
		//Always do this, even if count_ wasn't 0 on entry. 
		//Otherwise, we might not wake up enough waiting threads if we 
		//get a number of signal() calls in a row.
		m_condition.notify_one(); 
	}

	void up() //called "acquire" in Java
	{
		boost::unique_lock<boost::mutex> lock(m_mutex);
		while (m_count == 0)
			m_condition.wait(lock);
		--m_count;
	}

	void wait()
	{
		down();
		up();
	}
};

There's a link at the bottom of the blog: Eventcount (gate) proposa ... - Intel® Software Network

You pay the price of complexity for the scalability it provides. To be honest, my KISS sensibilities would prevent me from copying and using that code. If it makes its way into TBB (with the peer review I assume that comes with it), that would be different.

Only if a straight-forward boost::mutex/condition_variable implementation proves to be a scalability bottleneck, would I then look for alternatives.

>> Second attempt:

• Uncomment lock in get_count()
• Suggest rename get_count() -> debug_get_count(), which implies its usefulness.
• Down = P = decrement or block
• Up = V = increment and signal
• wait() - this makes no sense to me.

gg

Originally Posted by Codeplug

Uncomment lock in get_count()

Fixed.

Suggest rename get_count() -> debug_get_count(), which implies its usefulness.

I find it pretty useful to use in release builds, too. It can be used for try lock.

Down = P = decrement or block
Up = V = increment and signal

P and V makes little sense to me in naming. Up and down makes perfect sense since they increment or decrement the semaphore's value. Since it's my implementation, I'll stick with that. Obviously, this is a matter of what naming scheme one likes best.

wait() - this makes no sense to me.

Wait until a condition is true. Similar to CreateEvent/WaitForSingleObject.
An event shall stay signaled until reset. Unfortunately, down breaks that, so an up is required.
Well, at least this is how my mind works. If I want any number of threads to be able to wait for an event, then I use this scheme. If I only use down, the other threads won't understand that the event is still true.

>> I find it pretty useful to use in release builds, too
It's not very useful. As soon as the copy is returned, its value is stale. Making decisions based on that stale value can easily lead to synchronization/data-race bugs. Feel free to post code that tries to make use of it and we'll try to code review it.

Down/P and Up/V are the traditional names. I was only trying to point out that you have them backwards. "Up" should "increment" and signal.

>> Similar to CreateEvent/WaitForSingleObject.
You're creating a semaphore, not a [Win23] event...

Code:

class XEvent
{
    bool m_bSignaled;
    bool m_bManualReset;
    boost::mutex m_mutex;
    boost::condition_variable m_condition;
 
public:
    XEvent(bool bSignaled, bool bManualReset) 
        : m_bSignaled(bSignaled), m_bManualReset(bManualReset)
    {
    }
    
    void set_event()
    {
        boost::unique_lock<boost::mutex> lock(m_mutex);
        m_bSignaled = true;
        if (m_bManualReset)
            m_condition.notify_all(); 
        else
            m_condition.notify_one();
    }
    
    void wait()
    {
        boost::unique_lock<boost::mutex> lock(m_mutex);
        while (!m_bSignaled)
            m_condition.wait(lock);
        
        if (!m_bManualReset)
            m_bSignaled = false;
    }
    
    void reset_event()
    {
        boost::unique_lock<boost::mutex> lock(m_mutex);
        m_bSignaled = false;
    }
};

gg