CODEWITHSUNDEEP
c++pthreadssemaphore
Ben Creighton
Ben Creighton

Reputation: 91

Implementing a binary semaphore class in C++

So, I am working on a scheduler in one of my classes. Basically, we are pretending that only one thread can be executing at a time. We are supposed to use a semaphore class to allow these threads to block themselves to simulate the thread waiting for the CPU.

The problem is, the threads seem to block at the wrong time and execute at the wrong time. I was wondering if I am missing some conceptual understanding of a semaphore and how to implement it. I was wondering if I could get some feedback on my implementation. The instructor provided this header file which I have not modified in any way:

class Semaphore {
private:
  int             value;
  pthread_mutex_t m;
  pthread_cond_t  c;

public:

  /* -- CONSTRUCTOR/DESTRUCTOR */

  Semaphore(int _val);

  //~Semaphore();

  /* -- SEMAPHORE OPERATIONS */

  int P();
  int V();
};

This is my implementation using posix stuff:

Semaphore::Semaphore(int _val){
    value = _val;
    c = PTHREAD_COND_INITIALIZER;
    m = PTHREAD_MUTEX_INITIALIZER;
}

int Semaphore::P(){
    if(value <= 0){
        pthread_cond_wait(&c, &m);
    }
    value--;
}

int Semaphore::V(){
    value++;
    if(value > 0){
        pthread_cond_signal(&c);
    }
}

Upvotes: 3

Views: 15322

Answers (2)

Kaz
Kaz

Reputation: 58500

You are neglecting to lock the mutex.

Secondly, what you have here is a counting semaphore, not a binary semaphore. A binary semaphore has only two states, and so a bool variable is appropriate:

class Semaphore {
private:
  bool            signaled;   // <- changed
  pthread_mutex_t m;
  pthread_cond_t  c;

  void Lock() { pthread_mutex_lock(&m); }          // <- helper inlines added
  void Unlock() { pthread_mutex_unlock(&m); }
public:

  /* -- CONSTRUCTOR/DESTRUCTOR */

  Semaphore(bool);

  //~Semaphore();

  /* -- SEMAPHORE OPERATIONS */

  void P();   // changed to void: you don't return anything
  void V();
};

Impl:

// consider using C++ constructor initializer syntax.

Semaphore::Semaphore(bool s){        // don't use leading underscores on identifiers
    signaled = s;
    c = PTHREAD_COND_INITIALIZER;    // Not sure you can use the initializers this way!
    m = PTHREAD_MUTEX_INITIALIZER;   // they are for static objects.

    // pthread_mutex_init(&m); // look, this is shorter!
}

void Semaphore::P(){
    Lock();              // added
    while (!signaled){   // this must be a loop, not if!
        pthread_cond_wait(&c, &m);
    }
    signaled = false;
    Unlock();
}

void Semaphore::V(){
    bool previously_signaled;
    Lock();
    previusly_signaled = signaled; 
    signaled = true;
    Unlock();  // always release the mutex before signaling
    if (!previously_signaled)
      pthread_cond_signal(&c); // this may be an expensive kernel op, so don't hold mutex
}

Upvotes: 11

Kaz
Kaz

Reputation: 58500

Your counting semaphore algorithm is missing a while loop, and signals the semaphore unnecessarily.

Original logic, with locks added (see other answer):

int Semaphore::P(){
    Lock();
    if(value <= 0){
        pthread_cond_wait(&c, &m);
    }
    value--;
    Unlock();
}

int Semaphore::V(){
    Lock();
    value++;
    if(value > 0){
       pthread_cond_signal(&c);
    }
    Unlock(); 
}

The correct way:

int Semaphore::P(){
    Lock();
    while (value <= 0){   // not if
        pthread_cond_wait(&c, &m);
    }
    // value is now > 0, guaranteed by while loop
    value--;
    // value is now >= 0
    Unlock();
}

int Semaphore::V(){
    Lock();
    int prior_value = value++;
    Unlock();

    // E.g. if prior_value is 50, should we signal? Why?

    if (prior_value == 0) // was not signaled previously, now is.
        pthread_cond_signal(&c);
}

For efficiency, gather information about whether to signal or not inside the mutex, but then do the signal outside the mutex. Mutexes should be held over as few machine instructions as possible because they add contention, reducing concurrency. The signal operation can take hundreds of cycles (trip to the kernel to do wait queue manipulation).

You have to use a loop when waiting on a condition variable because there can spurious wakeups. Also, if you signal outside of the mutex, condition signal does not always go to the "intended" thread. Between the unlock and the signal, some thread can sneak in and call P and decrement the mutex. Then the one which wakes up on the condition must re-evaluate the test, otherwise it will incorrectly proceed.

Upvotes: 3

Related Questions