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

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.

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

Originally Posted by underthesun

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?

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?

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.

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

Originally Posted by underthesun

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.

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?

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.

Originally Posted by CornedBee

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

Originally Posted by brewbuck

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.