Mutual exclusion and semaphores

Question

I am writing a program (for homework) that simulates a unisex bathroom. Only 4 people are allowed at a time and men and woman cannot enter if the other sex is already using the bathroom. My problem is with allowing a max of 4 people in the bathroom. As you can see from the output, only 1 person is getting into the restroom at a time. Here is my code:

const int Delayx = 60;
int i;
int restroom = 0;
int Menwaiting = 0;
int Womenwaiting = 0;
semaphore max_capacity;
semaphore woman;
semaphore man;
semaphore mutex;
semaphore restroomcount;
void Delay(void)
{
    int DelayTime;
    DelayTime = random(Delayx);
    for (i = 0; i<DelayTime; i++);
}

void Woman(void)
{
//  for(;;){
    Womenwaiting++;
    //wait(mutex);
    wait(woman);
    wait(max_capacity);
        //wait(woman);
        wait(mutex);
        wait(restroomcount);
        cout << "A Woman has entered Restroom"<<endl;
        cout << "People in the Restroom:" << restroom++ <<endl <<endl;
        signal(restroomcount);
        Womenwaiting--;
        Delay();
        wait(restroomcount);
        cout << "A woman has exited Restroom"<<endl;
        cout << "People in the Restroom:" << restroom-- <<endl<<endl;
        signal(restroomcount);
        signal(mutex);
        signal(max_capacity);
        if(Menwaiting > Womenwaiting){
              signal(man);
                  }
              else{
            signal(woman);
        }
        //signal(max_capacity);
    //signal(man);
//  }
}
void Man(void)
{
//  for(;;){
    Menwaiting++;
    //wait(mutex);
    wait(man);
    wait(max_capacity);
    //wait(man);
        wait(mutex);
        wait(restroomcount);
        cout <<"A Man has entered the Restroom"<<endl;
        cout <<"People in the Restroom:" << restroom++ <<endl<<endl;
        signal(restroomcount);
        Menwaiting--;
        //signal(mutex);
        Delay();
        //wait(mutex);
        wait(restroomcount);
        cout << "A man has exited the Restroom"<<endl;
        cout <<"People in the Restroom:" << restroom-- <<endl<<endl;
        signal(restroomcount);
        signal(mutex);
        signal(max_capacity);
        if(Womenwaiting > Menwaiting){
            signal(woman);
            }
        else{
            signal(man);
            }
        //signal(max_capacity);
        //signal(woman);
//}
}
void main()
{
    initialsem(woman,1);
    initialsem(man,1);
    initialsem(max_capacity,4);
    initialsem(mutex,1);
    initialsem(restroomcount,1);
    cobegin
    {
        Woman(); Woman(); Woman(); Woman(); Woman(); Man();  Man(); Man(); Man(); Man();
    }

}

This generates the following output:

A Man has entered the Restroom
People in the Restroom:1

A man has exited the Restroom
People in the Restroom:0

A Man has entered the Restroom
People in the Restroom:1

A man has exited the Restroom
People in the Restroom:0

A Woman has entered Restroom
People in the Restroom:1

A woman has exited Restroom
People in the Restroom:0

A Woman has entered Restroom
People in the Restroom:1

A woman has exited Restroom
People in the Restroom:0

And so on, forever.

Answer 1

is the use of semaphores a requirement? for example, in "c++" pseudo-code, a implementation would look like:

First lets create a state object and a function that validates transitions between states

struct BathRoomState
{
   int women;
   int men;

   BathRoomState( int w , int m ) : women(w) , men(m) {}

   bool hasWomen()
   { 
      if (women > 0 && men == 0)
         return true;
      return false;
   }

   bool isEmpty()
   {
      return (women + men == 0);
   }

   static bool isValidTransition( BathRoomState* a , BathRoomState* b )
   {
      if (a->HasWomen())
      {
        if ( (abs( a->women - b->women ) == 1) && (a->men == b->men) )
           return true;
        else false;
      } else if (a->isEmpty())
      {
          if ((b->women == 1 && b->men == 0)
               || (b->women == 0 && b->men == 1))
             return true else false;
      } else //a has men
      {
          if ((abs( a->men - b->men ) == 1) && ( a->women == b->women))
            return true else false;
      }
   }
}

Lets also create a global reference to the current state and a function to update the current state based on some next desired state

BathRoomState* currentBathroomState = 0;
bool TryToChangeState(BathRoomState* newState)
{ 
  BathRoomState* existingState = currentBathroomState;
  if (BathRoomState::isValidTransition( existingState , newState ))
  {
     //this atomic operation depends on library support
     bool success = CompareAndSwapAtomically( currentBathroomState , existingState , newState );
     return success;
  }
}

then we create a global vector to hold the states, and a function representing a women thread trying to go to the bathroom

std::vector< BathRoomState* > noGCinThisExample;
//thread functtion
void women()
{
   BathRoomState* existingState = currentBathroomState;
   BathRoomState* newState = new BathRoomState( existingState.women+1 , existingState.men );
   while (!TryToChangeState(newState))
   {
     //yield or sleep from time to time here to let other threads progress
     existingState = currentBathroomState;
     newState.women = existingState.women + 1;
     newState.men = existingState.men;
   }
   noGCinThisExample.push_back( newState ); //no GC in this example
   //the woman is in the bathroom now. lets give her some time
   delayForWomen();
   //lets try to get her out

   BathRoomState* exitState = new BathRoomState( existingState.women-1 , existingState.men );
   while (!TryToChangeState(exitState ))
   {
     //yield or sleep from time to time here to let other threads progress
     existingState = currentBathroomState;
     exitState.women = existingState.women - 1;
     exitState.men = existingState.men;
   } 
   noGCinThisExample.push_back( exitState); //no GC in this example
}

//homework: do a similar function for men

and the main function with process loop logic and initialization

void main()
{
  BathRoomState* initialState = new BathRoomState( 0 , 0);
  noGCinThisExample.push_back( initialState );
  currentBathroomState = initialState;
  while(some_condition)
  {
   if (random() > 0.5)
     thread( women() );
   else
     thread( men() );
  }
};

this code should work ( i haven't tested it ). I've cheated a bit because i'm not deleting any of the provisional states created, so each state persist until the process dies. proper garbage collection would require a technique called hazard pointer management.

Note that i dont use any mutex semaphores or lock, the only locking primitive i am using is the CAS( address, old_value , new_value ) (compare and swap). This primitive atomically compares a pointer (address) and if it still contains (old_value) then it assign it new_value and succeeds, otherwise it fails. Also, you still need a global lock for the std::vector storing the states that i have not included in the code (you can also just leak them, but i store them somewhere so you can think that those should be deleted once you know how GC could be made to work in these cases)

Since all my intermediate states are inmutable (lisp/clojure style inmutabilitity) the contention (and hence, starvation) of the threads vastly improves. In your example the set of states is small (just a bunch of persons) its not too bad that we don't delete the used states.

however, even with the problems i've mentioned, i think you would agree that the logic of what is happening is much more explicit and readable.

Answer 2

I think you have too many semaphores. Your man/woman semaphores are gating to 1 person at a time. Consider using some state variables protected by mutexes (current sex of bathroom, number of people in bathroom) rather than so many different semaphores.

Do you maintain a line ordering or can people skip based on the current restroom sex? For instance, if you have woman,woman,woman,man,woman, is the 4th woman allowed to skip the man and go into the restroom, or do the 3 women exit, then the man enters/exits, then the woman can enter? This is an easier problem than allowing a skip.

Answer 3

Issues with the question
The original code isn't very OO.

The processing of the bathroom queue should be seperate from the generation of the people in the queue - if not running a seperate thread at least after the queue is filled.

Making the assumption that there are basically separate queues of men and women - not intermixed in some fixed order, otherwise the problem doesn't make any sense to use a semaphore.

The problem doesn't describe how many people get to enter when the condition is right, male toilet with more men, do you fill it to 4 or only until the queue of men is less than women again?

Even so the problem as described (and based on sample code with no threading) doesn't work well with a semaphore in my opinion, the main problem is that the semaphore doesn't yield the count easily and a successful wait changes the count.

The interesting thing I see in the problem is the inefficiency in a near equal queue length and trading between disallowing another of the same sex into the toilet and the chance that before the remaining persons in the toilet leave the number of the same sex becomes larger again. Lets face it, it's unisex and so it should allow 4 people in regardless of gender ;)

Proposed solution
So you need to use a semaphore, the interesting things about a semaphore is the recording of multiple uses (unlike mutex) and if there is not free space then it will possibly wait. It does not discriminate however between those waiting, it will only tell that there is space free.

Have 1 semaphore and think you should check the semaphore when a person enters the queue or when somebody leaves the bathroom.

You could then have 1 'queue' each for men and women (from given this is basically a count). These queues are not really related or limiting on each other in terms of entry and so have nothing to do with semaphores. Each could follow a locking free provider pattern, but you might find it easier to use a mutex to synchronise so that you can examine the size of the queues and manipulate them. In the following I've just used the count directly, instead it should be using some form of InterlockedIncrement and InterlockedDecrement to protect against adding and removing people from the same queue.

In the rough, Bathroom.h

class Bathroom
{
public:
    Bathroom(void);
    ~Bathroom(void);

    AddMan();
    AddWoman();
    Run();
private:
    StateChange();

    int m_Menwaiting;
    int m_Womenwaiting;
    semaphore max_capacity;

    enum Users {
        NOBODY ,
        WOMEN,
        MEN
    } m_inUseBy;
};

Bathroom.cpp

Bathroom::Bathroom(void)
    : m_Menwaiting(0)
    , m_Womenwaiting(0)
    , m_inUseBy(NOBODY)
{
    initialsem(max_capacity,4);
}


Bathroom::~Bathroom(void)
{
    freesem(max_capacity);
}

Bathroom::AddMan(){
    ++m_Menwaiting;
    StateChange();
}

Bathroom::AddWoman(){
    ++m_Womenwaiting;
    StateChange();
}

Bathroom::StateChange() {

    // extra at a time
    if( m_Menwaiting > m_Womenwaiting && inUseBy != WOMEN ) {
        if( wait(max_capacity,0 delay) != timeout )
            m_Menwaiting--;
    }

    if( m_Womenwaiting > m_Menwaiting && inUseBy != MEN ) {
        if( wait(max_capacity,0 delay) != timeout )
            m_Womenwaiting--;
    }

    // all available slots
    if( m_Menwaiting > m_Womenwaiting && inUseBy != WOMEN ) {
        while( wait(max_capacity,0 delay) != timeout )
            m_Menwaiting--;
    }

    if( m_Womenwaiting > m_Menwaiting && inUseBy != MEN ) {
        while( wait(max_capacity,0 delay) != timeout )
            m_Womenwaiting--;
    }

}

Bathroom::run(){
// people leaving bathroom simulated
    while(1) {
        Delay();
        signal(max_capacity);
        StateChange();
    }
}

Program.cpp

Bathroom b1;

addPeople() {
  while(true) {
  // randomly add people
    Delay();
    b1.AddMen();
    b1.AddWomen();
  }
}

int main(){

  thread( addPeople );

  b1.run();
}

Answer 4

Edit 5 (I realize this may be too little too late, as this was likely a homework assignment, but I just thought of a way to do this using only semaphores.)

okay here's my pseudocode:

//shared variables
//the # of men or women in the bathroom
int menCountIn=0;
int womenCountIn=0; 

//the # of men or women waiting
int menCountWtg=0;
int womenCountWtg=0;

//whose turn it is to go next
int turn = -1;
//-1 = anybody can go
//0 = only men can go
//1 = only women can go

#define capacity 4

//semaphores
semaphore mutex; //a sort of bathroom key
//mutex will protect menCountIn, womenCountIn, and turn
semaphore waiting; 
//waiting protects the variable count of how many people are waiting

//Female thread:
bool in = false; //a thread-specific variable telling me whether I'm in or not
//will be used in an almost-spinlocking type of way

wait(waiting);
womenWaiting++;
signal(waiting);

while(!in){
   thread.sleep(60); //to avoid constant spinlock
   wait(mutex);
   if (menCountIn ==0 && (turn == -1 || turn == 1) && womenIn < capacity)
   {
      wait(waiting);
      womenWtg---; //no longer waiting to get in
      signal(waiting);
      womenCountIn++; // a women entered
      cout << "Woman entered restroom" << endl;
      in=true;
   }
}//end while loop

thread.sleep(60);//in bathroom taking care of business!

wait(mutex);
womenIn--;
cout << "A woman left the restoom." << endl;
wait(waiting);
if(menWaiting > womenWtg)
{
   turn = 0; //men should get in at next opportunity
   cout << "It's mens' turn!" << endl;
}
else if (menWaiting == womenWtg == 0)
{
   turn = -1; //anybody should be able to get in
}
signal(waiting);
signal(mutex);

The "Man" thread should behave similarly. Keep in mind that waiting and mutex semaphores protect both men and women variables.

---

You are signalling the mutex before a man/woman has "exited" the bathroom. If I understand correctly, the mutex is so that only one sex is in the bathroom at any time. Since you are signalling it before outputting "A Man has exited the bathroom", a woman can get the mutex and get in.

Since men and women are initially waiting on two different semaphores It's understandable that some will get in to that initial semaphore. From there it appears you are getting the mutex (shared between men and women) then after getting in you release it before they exit. Perhaps you mean to be signalling the "man" or "woman" semaphore here instead?

Edit: I guess the gist of my answer is this: The mutex is shared between men and women. In your code, when a person gets the mutex they say they're in, you decrement that they're waiting, then you release the mutex. Think about that last step a little more deeply. If you're releasing the mutex before they've left, what's possible here?

Edit2 (in response to your comments): What does your new code look like (Edit your original post)?

This will help us abstract the code away to the logic and then we can try to structure your logic properly and compare what we think is right to what your code is doing.

Edit3: Okay, it looks like you're getting closer. Here's some things to think about (I'm not posting a complete solution because this is homework and I want you to learn!)

• What is mutex protecting?
• What is man/woman protecting?
• What is restroomCount protecting?
• What is maxCapacity protecting?
• In what order should a person obtain these semaphores?
• ...i.e. Which semaphores protect which other semaphores and how?

Think especially hard about the restroom count semaphore... (HINT: It may be more important than simply protecting the count variable. It may need to be protecting the releasing of other semaphores...)

Edit 4: So I finally realized that you are trying to avoid starvation in this problem (as indicated by comments below). Though your homework is very similar to the readers/writers problem, the additional constraint to avoid starvation by either thread type makes it difficult to implement. I personally do not know how to do this without using Events to set preference (http://msdn.microsoft.com/en-us/library/dd492846.aspx), and even then there is no guarantee that starvation could never happen, which if I understand the Wikipedia (http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem) article on this topic properly, is the only way to do it.

Are you allowed to use events?

I must apologize for not completely grokking this additional readers/writers constraint of no starvation. Hopefully somebody else can help you better.