3

Let’s assume there is a function EventHandler that is called on multiple threads at different points in time.

EventHandler has to call SomeOtherFunction, but these calls shall only happen on one thread at a time.

That means: If a call to SomeOtherFunction is currently active on thread A, and EventHandler gets called again (on some other thread B), then SomeOtherFunction must not be called on thread B, but SomeOtherFunction shall be called when it returns on thread A.

Something like this (pseudo-code):

function EventHandler()
{
  numberPendingCallsSemaphore.Release();    // increase
  if (mayCallSemaphore.Acquire())           // (i)
  {
    while (numberPendingCallsSemaphore.Acquire())  // decrease
    {
      SomeOtherFunction();
    }
    // (ii)
    mayCallSemaphore.Release();
  }
}

Of course, this code does not work because of a race: One thread is at position (ii) with mayCallSemaphore still being taken, and another at position (i) not being able to take mayCallSemaphore.

I wrote working code using a lock, but the code is quite long and ugly. On the other, this problem looks quite simple at first sight, thus:

Is there a simple, potentially straightforward solution for this I was not able to find or currently don’t see?

  • 3
    It's called "blocking on synchronous functions." When you call a function, it blocks the flow of execution until it is completed, thereby allowing the next function to execute. It's not a software pattern; it's merely the inevitable consequence of calling functions. – Robert Harvey Feb 27 '18 at 14:25
  • 1
    Mutex provides exclusive access to the Condition Variable, which controls the sleep / wakeup behavior. Your code is almost identical to what it should be, just grok the Condition Variable semantics and you have it. I guess the question is whether you actually need a counting semaphore - you might not be placing a limit - but that is my take on your question. I used it, it works in industrial strength situation. And can be implemented portably on all OS. If I had my code from my old job, I would give it as an Answer. Sorry. – user251748 Feb 27 '18 at 14:51
  • 4
    Related: Producer–consumer problem – k3b Feb 27 '18 at 15:54
  • 2
    I feel like finding a library that provides an implementation of a Concurrent Queue (thread-safe queue) could solve this problem? You could have the event handlers just add the items to the queue, and a worker thread that dequeues and executes them. – Filip Milovanović Feb 27 '18 at 16:14
  • 1
    Threads are going cheap these days. I remember back when I was implementing a method to share modems across a Novell network of DOS PCs, I had to handle the problem of re-entrancy for Interrupt Service Routines that called in to the DOS core code (never designed to be re-entrant). Somehow I managed this, with the help of a book about writing Interrupt routines from the local bookstore (this was 1992). Had to buy a second book because there was an error in the first that had me stumped - missing line of code. Debugging DOS TSRs is a lonely job. Read up on re-entrancy / thread-safety? – user251748 Feb 28 '18 at 15:00
3

Your proposed solution has two control objects. mayCallSemaphore looks like a Mutex based on how you are using it, and numberPendingCallsSemaphore appears to serve as a Condition Variable. You have it almost correct, but as you surmised, having two control structures that operate independently leads to race conditions, deadlock or both depending on the topology and situation. Lost wakeups and other things are also possible.

If you take a close look at this GitHub documentation about how to construct a Counting Semaphore using both a Mutex and a Condition Variable, you will see that the CV actually uses (cooperates with) the Mutex internally, so there can be no races or deadlocks. I will copy and paste the example solution right here for convenience:

typedef struct sem_t {
  int count; 
  pthread_mutex_t m;
  pthread_condition_t cv;
} sem_t;

int sem_init(sem_t *s, int pshared, int value) {
  if (pshared) { errno = ENOSYS /* 'Not implemented'*/; return -1;}

  s->count = value;
  pthread_mutex_init(&s->m, NULL);
  pthread_cond_init(&s->cv, NULL);
  return 0;
}

sem_post(sem_t *s) {
  pthread_mutex_lock(&s->m);
  s->count++;
  pthread_cond_signal(&s->cv); /* See note */
  /* A woken thread must acquire the lock, so it will also have to wait until we call unlock*/

  pthread_mutex_unlock(&s->m);
}

sem_wait(sem_t *s) {
  pthread_mutex_lock(&s->m);
  while (s->count == 0) {
      pthread_cond_wait(&s->cv, &s->m); /*unlock mutex, wait, relock mutex*/
  }
  s->count--;
  pthread_mutex_unlock(&s->m);
}

Simply protect your call to SomeOtherFunction() by calling sem_wait() before and then calling sem_post() after. The internals of the methods will take care of all of the details, causing concurrent accesses to block, allowing only one execution of your code's critical section at a time. This is all based on the Posix primitives which are part of the OS and cannot go wrong. In your case, the count should be restricted to one, so you can either simplify this code, or initialize the semaphore with 1 and make use of the same code for another situation later.

I have used this same approach - taken from the POSIX manual pages (about 20 years ago) - to create a multi-threaded, multi-process database transaction server before the Apache web server was multi-threaded. I had one main thread that accepts incoming TCP connections, and creates up to 'N' work threads at a time (transient, not a pool). It worked for a long time in a very large site with many users. Unix gives you the tools to construct proper solutions, you just need to put them together.

  • Note: you must have a While loop around the call to pthread_cond_wait() even if you restrict the maximum count to 1. There are various possibilities for false wakeups, etc that are handled by this loop. – user251748 Mar 1 '18 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.