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?

You could get stuck in a wait() while m_count != 0.

Nice catch!

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

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.

Semaphores have their use

You'll note that I didn't say that a semaphore isn't useful. It just happens that I rarely ever break work up in such a way as to call on a technique involving collaborating threads. (Threads producing data others threads will consume in full or partial serial fashion.) I almost always break work up into transactions. (Threads produce data that is cataloged with or without a sequence identifier to be consumed "whenever".) That makes the mutex and condition variable more useful to me.

*shrug*

To be honest, I don't think I've actually had to use any of those low level primitives in a long while.

Higher level constructs for the win. ^_^v

Soma

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.

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.

*shrug*

I admit I know nothing about `boost::condition_variable'.

If you do what I said, and the primitives work correctly, that situation is impossible. There would always be at least one thread waiting. (Specifically, the thread that called wait last.)

Soma

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.

Okay, I just read a little documentation... wow.

I now know that you aren't doing any locking in `signal'.

Yea, I admit I need to pay more attention to the primitives you are actually using instead of making assumptions about the facilities that those primitives offer.

You need to explicitly lock in `signal'. It is nice and all that you are using an atomic numeric, but I think that's what is hurting you. (That is, you assume that the atomic operation on the numeric is sufficient.) All operations relating to the semaphore must be atomic. So for example, taking my suggestions by adding another atomic numeric would not work.

Code:

tbb::atomic<unsigned int> m_count;
tbb::atomic<unsigned int> m_waiting_threads; // addition

with

Code:

--m_count;
--m_waiting_threads; //addition

You don't have anything in place to make sure that both of those operations finish before another thread of execution attempts to do something with them. You are only making sure each operations finishes. That is not at all sufficient.

Change the atomic numeric to a simple native, make the changes I've suggest, update the code to order (make them atomic) operations on that native, and then reason about any unfortunate conditions.

When you've posted back with that we can worry over any new issues.

[Edit]
^_^;

And just so as you know laserlight, I'm certainly guilty of assuming to much even if paying attention.
[/Edit]

Soma

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