Thread: waitable boolean class (concurrency)

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    108

    waitable boolean class (concurrency)

    Hello,

    I was playing with concurrency (and I'm relatively new to it). I made a class so that you can wait for a boolean value to become true, called the "WaitableBool":

    Code:
    class WaitableBool{
       public:
          // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
          Mutex mutex;
          Semaphore sem;
          int waitercount;
          bool value;
          // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
          WaitableBool(bool init):
             value(init),
             waitercount(0)
             {}
          // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
          void waitUntilTrue();
          // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
          void setValue(
          // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    };
    Code:
    void WaitableBool::waitUntilTrue(){
    
       if(value == true)
          return;
    
       mutex.Lock();
       waitercount++;
       mutex.Unlock();
    
       sem.Wait();
    }
    
    void WaitableBool::setValue(bool theval){
    
       mutex.Lock();
       value = theval;
       if(theval == true){
          // then all those waiting needs to be told that it's done.
    
          int i;
          for(i = 0; i < waitercount; i++){
             sem.Post();
          }
          waitercount = 0;
       }
       mutex.Unlock();
    
    
    }
    Now, the question that I have is.. is there an existing concurrency thing that lets you do this? Did I just reinvent the wheel? The idea is, many threads could be waiting for a boolean value to turn to "true", and many threads could also change the value of this bool.

    So yeah, what do you think?

    Thanks in advance
    Last edited by underthesun; 11-10-2007 at 04:46 AM.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    What you're looking for is similar to a "condition variable". POSIX has one (pthread_cond_t), Win32 events can be used for a similar purpose, although they're far trickier to use, since they don't automatically lock a mutex on waking up.

    That said, I can't see anything obviously wrong with your class, besides potential cache problems of the boolean. (Because your read access is not atomic or guarded in any way, the value might stay in the cache for a long time after another thread on another core has changed it.)

    Using POSIX condition variables, your class would be implemented like so:
    Code:
    class WaitableBool
    {
      pthread_cond_t cond;
      pthread_mutex_t mutex;
      volatile bool b;
    
      WaitableBool()
        : b(false)
      {
        pthread_cond_init(&cond, 0);
        pthread_mutex_init(&mutex, 0);
      }
    
      ~WaitableBool()
      {
        if(0 != pthread_mutex_destroy(&mutex)) throw something;
        if(0 != pthread_cond_destroy(&cond)) throw something;
      }
    
      void waitUntilTrue()
      {
        if(0 != pthread_mutex_lock(&mutex)) throw something;
        try {
          while(!b) {
            pthread_cond_wait(&cond, &mutex);
          }
        } catch(...) {
          pthread_mutex_unlock(&mutex);
          throw;
        }
        pthread_mutex_unlock(&mutex);
      }
    
      void setValue(bool theVal)
      {
        if(0 != pthread_mutex_lock(&mutex)) throw something;
        b = theVal;
        int res = pthread_cond_broadcast(&cond);
        pthread_mutex_unlock(&mutex);
        if(res != 0) throw something;
      }
    };
    Note that you really should use RAII lock objects, though. That saves you the stupid try block in waitForTrue and generally makes life easier.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    108
    Woah, thanks. I guess having pthreads must be good huh.. oh well, I'm only limited to mutexes and semaphores from a cross-platform mutex/semaphore/thread library that I got.

    With potential cache problems, that can be fixed just by setting the values as private right?

    thanks again

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by underthesun View Post
    With potential cache problems, that can be fixed just by setting the values as private right?
    No, that does not help.
    You would declare it as 'volatile' instead, but shortly after I've said that, someone will be telling you that even that is not enough.

    Basically implementing a critical section by the looks of it. I assume it's not something that runs under Windows then?
    Last edited by iMalc; 11-11-2007 at 12:35 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    108
    Hmm.. could you explain what a "potential cache problem" is? Is there a specific keyword I could search in google, to find out more about this?

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    RAM is slow. Compared to the CPU, anyway. For this reason, CPUs have several levels of high-speed cache directly on the CPU die. For one CPU, that's fine.
    If you have multiple CPUs, you have multiple caches. (Some multi-core designs may also have multiple caches.) Cache problems arise when the value of a variable in one CPU's cache differs from that in another CPU's cache. The only way to solve this is by using atomic operations and/or memory fences. I can't find the functions for atomic operations in POSIX.

    The problem when arguing about semantics of C++ code is that the C++ standard isn't aware of multi-threading, and thus completely ignores the issues. Thus, you invariably slide into implementation-specific areas. This will be a lot better when the new C++ standard comes out, since it will support multi-threading.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    108
    Woah, never thought of that.. thanks for the info.. That's making me a bit uncomfortable though..

    Basically implementing a critical section by the looks of it. I assume it's not something that runs under Windows then?
    Sorry for not answering this earlier. It actually runs under windows.. I just put "volatile" before the bool and the int declaration.. just being very cautious here, but in what way would that be not enough? Aspiring to a bug-free holiday project here

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by underthesun View Post
    Woah, never thought of that.. thanks for the info.. That's making me a bit uncomfortable though..



    Sorry for not answering this earlier. It actually runs under windows.. I just put "volatile" before the bool and the int declaration.. just being very cautious here, but in what way would that be not enough? Aspiring to a bug-free holiday project here
    In the way CornedBee just described actually.

    Well if this code is to run under Windows and doesn't need to be portable, then I strongly suggest you simply use a CriticalSection instead.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    108
    Hmm, I was using the cross platform thread I found at codeproject, and after inspecting how the mutex class works, turns out it was done using critical sections

    so if the mutex in the original class really are just critical sections, is all good now? oh and the linux version uses pthread_mutex_* functions.

    But according to this page, mutexes cover the functionalities of critical sections, so if i'm reading correctly, using mutexes in place of critical sections should be fine?

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    A critical section is one of a set of pieces of code that must not be executed by more than one thread at the same time. A mutex is an object that only one thread can own at any time. Mutexes are used to protect critical sections.

    In the Win32 API, a mutex is a kernel-level mutex that can be used to synchronize multiple processes. A critical section is a user-space mutex that only switches to kernel mode for actual blocking and thus is much faster for the non-contended case than a kernel mutex, but with the drawback that you cannot synchronize processes against each other, only threads within a single process.

    The terminology is confusing. Blame Microsoft.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    A critical section is one of a set of pieces of code that must not be executed by more than one thread at the same time. A mutex is an object that only one thread can own at any time. Mutexes are used to protect critical sections.
    Actually the two are flip sides of the same coin. If your fundamental object is a mutex, you can use that to create a critical section. And vice versa, if your fundamental object is a critical section, you can use this to implement a mutex. I'm talking in theory, not the specific MS terminology.

    In the Win32 API, a mutex is a kernel-level mutex that can be used to synchronize multiple processes. A critical section is a user-space mutex that only switches to kernel mode for actual blocking and thus is much faster for the non-contended case than a kernel mutex, but with the drawback that you cannot synchronize processes against each other, only threads within a single process.
    The user-space mutex sounds equivalent to the Linux "futex" which also doesn't require a context switch unless there is true contention. I wonder why Windows doesn't let you share these fast mutexes across processes. There's no reason it couldn't...

    By the way, I have prior art on these futex things. I implemented my own version for Linux 2.4 about 9 months before the futex was conceived, but I called them "User Wait Queues" which was a terrible name. Just goes to show that names can be everything to project success, sometimes

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by brewbuck View Post
    Actually the two are flip sides of the same coin. If your fundamental object is a mutex, you can use that to create a critical section. And vice versa, if your fundamental object is a critical section, you can use this to implement a mutex. I'm talking in theory, not the specific MS terminology.
    But that's the point. In multi-threading theory, a critical section is not an object at all. It's a number of code sections.

    OK, so there are multiple definitions. But given that mutexes and the object view of a critical section are exactly the same thing, it's pointless and confusing to use this definition.

    The user-space mutex sounds equivalent to the Linux "futex" which also doesn't require a context switch unless there is true contention. I wonder why Windows doesn't let you share these fast mutexes across processes. There's no reason it couldn't...
    Basically, because of its design. A futex is like a MS critical section in a block of shared memory, but you can't create a critical section in shared memory because you can't "partially initialize" (i.e. leave the core of the cs as it is, just make the kernel object that's used for hard blocking available in the current process) a critical section. Thus, sharing is not possible.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Class design problem
    By h3ro in forum C++ Programming
    Replies: 10
    Last Post: 12-19-2008, 09:10 AM
  2. Specializing class
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 09-28-2008, 04:30 AM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. class errors
    By romeoz in forum C++ Programming
    Replies: 3
    Last Post: 09-16-2003, 07:57 PM