Semaphore review

This is a discussion on Semaphore review within the C++ Programming forums, part of the General Programming Boards category; I have need of a semaphore, but I have been unable to find any good ones on the web, only ...

  1. #1
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777

    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;
    	}
    
    };
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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
    Last edited by phantomotap; 02-17-2012 at 07:39 AM.

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    Semaphores have their use, too, but many libraries do not seem to agree, and hence exclude them o_O
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    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

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    Would changing lock on line 48 to a timed_lock be a better solution?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    Quote Originally Posted by phantomotap View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    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

  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    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();
    	}
    };
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    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

  14. #14
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,777
    Quote Originally Posted by Codeplug View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #15
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    >> 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

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-14-2010, 10:14 AM
  2. semaphore
    By menzeli in forum Linux Programming
    Replies: 12
    Last Post: 04-15-2007, 09:26 AM
  3. semaphore
    By menzeli in forum C Programming
    Replies: 1
    Last Post: 03-24-2007, 11:34 AM
  4. Mutex vs. Semaphore
    By cjschw in forum C++ Programming
    Replies: 1
    Last Post: 07-22-2003, 07:03 PM
  5. semaphore
    By laasunde in forum C Programming
    Replies: 0
    Last Post: 11-01-2002, 10:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21