Mutual exclusion and semaphores

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.

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.

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.

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