Implementing a binary semaphore class in C++

Question

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);
    }
}

JRizzly · Accepted Answer · 2014-03-19 01:57:43Z

11

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
}

edited Mar 19, 2014 at 1:57

JRizzly

601 silver badge8 bronze badges

answered Mar 24, 2012 at 19:22

Kaz

59.1k10 gold badges113 silver badges167 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mfontanini Over a year ago

"The instructor provided this header file which I have not modified in any way".

Kaz Over a year ago

That may be so, but there is no need to mod down my answer because of that. Fact is, you do not have a binary semaphore here and I was correctly pointing that out. Perhaps the task is to implement it as a binary semaphore without changing the header; that can be done.

Ben Creighton Over a year ago

Thank you! Seeing your implementation gave me one of those "Ah HA!" moments. I think the instructor intentionally left the interface open ended so that we could decide what kind of semaphore to use. I ended up implementing a counting semaphore anyway to make modifying the program for different scheduling algorithms easier.

Kaz · Accepted Answer · 2012-03-24 20:37:46Z

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.

Collectives™ on Stack Overflow

Implementing a binary semaphore class in C++

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related