Binary semaphore to maintain concurrency

Question

I was trying to implement a multi-threaded program using binary semaphore. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>

int g = 0;

sem_t *semaphore;

void *myThreadFun(void *vargp)
{
    int myid = (int)vargp;
    static int s = 0;
    sem_wait(semaphore);
    ++s; ++g;
    printf("Thread ID: %d, Static: %d, Global: %d\n", myid, s, g);
    fflush(stdout);
    sem_post(semaphore);
    pthread_exit(0);
}

int main()
{   

    int i;
    pthread_t tid;
    if ((semaphore = sem_open("/semaphore", O_CREAT, 0644, 3))==SEM_FAILED) {
    printf("semaphore initialization failed\n");
    }


    for (i = 0; i < 3; i++) {
        pthread_create(&tid, NULL, myThreadFun, (void *)i);
    }

    pthread_exit(NULL);
    return 0; 
}

Now, when I opened the sempahore, I made the count 3. I was expecting that this wouldnt work, and I would get race condition, because each thread is now capable of decrementing the count.

Is there something wrong with the implementation? Also, if I make the count 0 during sem_open, wouldnt that initiate a deadlock condition, because all the threads should be blocked on sem_wait.

Answer 1

I'll get to the code in a bit that proves you had a race condition. I'll add a couple of different ways to trigger it so you can see how this works. I'm doing this on Linux and passing -std=gnu99 as a param to gcc ie

gcc -Wall -pedantic -lpthread -std=gnu99 semaphore.c -o semtex

Note. In your original example (assuming Linux) one fatal mistake you had was not removing the semaphore. If you run the following command you might see some of these sitting around on your machine

ls -la /dev/shm/sem.*

You need to make sure that there are no old semaphore sitting on the filesystem before running your program or you end up picking up the last settings from the old semaphore. You need to use sem_unlink to clean up.

To run it please use the following.

rm /dev/shm/sem.semtex;./semtex

I'm deliberately making sure that the semaphore is not there before running because if you have a DEADLOCK it can be left around and that causes all sorts of problems when testing.

Now, when I opened the sempahore, I made the count 3. I was expecting that this wouldn't work, and I would get race condition, because each thread is now capable of decrementing the count.

You had a race condition but sometimes C is so damned fast things can appear to work because your program can get everything it needs done in the time the OS has allocated to the thread ie the OS didn't preempt it at an important point.

This is one of those cases, the race condition is there you just need to squint a little bit to see it. In the following code you can tweak some parameters to see the a deadlock, correct usage and Undefined Behavior.

#define INITIAL_SEMAPHORE_VALUE CORRECT

The value INITIAL_SEMAPHORE_VALUE can take three values...

#define DEADLOCK  0
#define CORRECT   1
#define INCORRECT 2

I hope they're self explanatory. You can also use two methods to cause the race condition to blow up the program.

#define METHOD sleep

Set the METHOD to spin and you can play with the SPIN_COUNT and find out how many times the loop can run before you actually see a problem, this is C, it can get a lot done before it gets preempted. The code has most of the rest of the information you need in it.

#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h> 
#include <unistd.h>
#define DEADLOCK  0 // DEADLOCK
#define CORRECT   1 // CORRECT
#define INCORRECT 2 // INCORRECT
/*
 * Change the following values to observe what happen.
 */
#define INITIAL_SEMAPHORE_VALUE CORRECT
//The next value provides to two different ways to trigger the problem, one
//using a tight loop and the other using a system call.
#define METHOD sleep

#if (METHOD == spin)
/* You need to increase the SPIN_COUNT to a value that's big enough that the
 * kernel preempts the thread to see it fail. The value set here worked for me 
 * in a VM but might not work for you, tweak it. */
#define SPIN_COUNT 1000000
#else 
/* The reason we can use such a small time for USLEEP is because we're making
 * the kernel preempt the thread by using a system call.*/
#define USLEEP_TIME 1
#endif
#define TOT_THREADS 10

static int g = 0;
static int ret = 1729;
sem_t *semaphore;

void *myThreadFun(void *vargp) {
  int myid = (int)vargp;
  int w = 0;
  static int s = 0;
  if((w = sem_wait(semaphore)) != 0) {
    fprintf(stderr, "Error: %s\n", strerror(errno));
    abort();
  };
/* This is the interesting part... Between updating `s` and `g` we add
 * a delay using one of two methods. */
  s++;
#if ( METHOD == spin )
  int spin = 0;
  while(spin < SPIN_COUNT) {
    spin++;
  }
#else
  usleep(USLEEP_TIME);
#endif
g++;
  if(s != g) {
    fprintf(stderr, "Fatal Error: s != g in thread: %d, s: %d, g: %d\n", myid, s, g);
    abort();
  } 
  printf("Thread ID: %d, Static: %d, Global: %d\n", myid, s, g);
  // It's a false sense of security if you think the assert will fail on a race
  // condition when you get the params to sem_open wrong It might not be
  // detected.
  assert(s == g);
  if((w = sem_post(semaphore)) != 0) {
    fprintf(stderr, "Error: %s\n", strerror(errno));
    abort();
  };
  return &ret;
} 

int main(void){
  int i;
  void *status;
  const char *semaphore_name = "semtex";
  pthread_t tids[TOT_THREADS];
  if((semaphore = sem_open(semaphore_name, O_CREAT, 0644, INITIAL_SEMAPHORE_VALUE)) == SEM_FAILED) {
    fprintf(stderr, "Fatal Error: %s\n", strerror(errno));
    abort();
  }
  for (i = 0; i < TOT_THREADS; i++) {
    pthread_create(&tids[i], NULL, myThreadFun, (void *) (intptr_t) i);
  }
  for (i = 0; i < TOT_THREADS; i++) {
    pthread_join(tids[i], &status);
    assert(*(int*)status == 1729);
  }
  /*The following line was missing from your original code*/
  sem_unlink(semaphore_name);
  pthread_exit(0);
}

Answer 2

Now, when I opened the sempahore, I made the count 3. I was expecting that this wouldnt work, and I would get race condition, because each thread is now capable of decrementing the count.

And how do you judge that there isn't any race? Observing output consistent with what you could rely upon in the absence of a data race in no way proves that there isn't a data race. It merely fails provide any evidence of one.

However, you seem to be suggesting that there would be a data race inherent in more than one thread concurrently performing a sem_wait() on a semaphore whose value is initially greater than 1 (otherwise which counter are you talking about?). But that's utter nonsense. You're talking about a semaphore. It's a synchronization object. Such objects and the functions that manipulate them are the basis for thread synchronization. They themselves are either completely thread safe or terminally buggy.

Now, you are correct that you open the semaphore with an initial count sufficient to avoid any of your threads blocking in sem_wait(), and that therefore they can all run concurrently in the whole body of myThreadFun(). You have not established, however, that they in fact do run concurrently. There are several reasons why they might not do. If they do run concurrently, then the incrementing of shared variables s and g is indeed of concern, but again, even if you see no signs of a data race, that doesn't mean there isn't one.

Everything else aside, the fact that your threads all call sem_wait(), sem_post(), and printf() induces some synchronization in the form of memory barriers, which would reduce the likelihood of observing anomalous effects on s and g. sem_wait() and sem_post() must contain memory barriers in order to function correctly, regardless of the semaphore's current count. printf() calls are required to use locking to protect the state of the stream from corruption in multi-threaded programs, and it is reasonable to suppose that this will require a memory barrier.

Is there something wrong with the implementation?

Yes. It is not properly synchronized. Initialize the semaphore with count 1 so that the modifications of s and g occur only while exactly one thread has the semaphore locked.

Also, if I make the count 0 during sem_open, wouldnt that initiate a deadlock condition, because all the threads should be blocked on sem_wait.

If the semaphore has count 0 before any of the additional threads are started, then yes. It is therefore inappropriate to open the semaphore with count 0, unless you also subsequently post to it before starting the threads. But you are using a named semaphore. These persist until removed, and you never remove it. The count you specify to sem_open() has no effect unless a new semaphore needs to be created; when an existing semaphore is opened, its count is unchanged.

Also, do have the main thread join all the others before it terminates. It's not inherently wrong not to do so, but in most cases it's required for the semantics you want.