Mutual Exclusion and Semaphores

Question

Hello. 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

etc etc forever.

Answer 1

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.

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

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.

Also 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.

Since all my intermediate states are inmutable (lisp/clojure style inmutabilitity) the contention (and hence, starvation) of the threads vastly improves. Since 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. BTW, 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)

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 4

Since you want to know how to code your algorithm for 1 restroom, I have done so in C. It will be a fairly simple task to convert it into C--, as all the semaphore constructs appear quite similar.

From what I could make of your answer,

C: sem_wait()  C--: wait()
   sem_post()       signal()
   sem_t            semaphore()
   sem_init()       initialsem() 

Bear in mind, as stated, I have worked out the problem for 1-restroom only. Since this is homework, I expect you to expand it into the 2-restrooms form yourself.

Working one's way from the Readers-writers problem to our "Unisex Restroom" problem, we make use of the following global variables:

int mcount,wcount; // count of number of men/women in restroom
sem_t x,y,z;       // semaphores for updating mcount & wcount values safely
sem_t wsem,msem;   // semaphores to block other genders' entry  
sem_t cap;         // capacity of the restroom

Incorporating these semaphores & counters into the man thread function,

void *man(void *param)
{           
    sem_wait(&z);                
        sem_wait(&msem);        
            sem_wait(&x);
                mcount++;
                if(mcount==1)   
                { sem_wait(&wsem); } // first man in, make women wait
            sem_post(&x);
        sem_post(&msem);
    sem_post(&z);

    sem_wait(&cap);  //wait here, if over capacity

    printf("\t\tman in!\n");
    delay();
    printf("\t\t\tman out!\n");

    sem_post(&cap);  //one man has left, increase capacity

    sem_wait(&x);
        mcount--;
        if(mcount==0)
        {sem_post(&wsem);}  // no man left, signal women 
    sem_post(&x);
}

Similarly, the woman thread function, substitutes mcount with wcount, msem with wsem, and x with y. Only z remains as is in the man function, so that both man & woman threads queue up on the same common semaphore. (Due to this, the code invariably has FIFO-like behaviour, which ensures fairness/non-starvation)

The complete code is as follows: (To compile, use gcc filename -lpthread)

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

int mcount,wcount;
sem_t x,y,z,wsem,msem,cap;

void delay(void)
{
    int i;
    int delaytime;
    delaytime = random();
    for (i = 0; i<delaytime; i++);
}

void *woman(void *param)
{
    sem_wait(&z);
        sem_wait(&wsem);
            sem_wait(&y);
                wcount++;
                if(wcount==1)
                { sem_wait(&msem); }
            sem_post(&y);
        sem_post(&wsem);
    sem_post(&z);

    sem_wait(&cap);

    printf("woman in!\n");
    delay();
    printf("\twoman out!\n");

    sem_post(&cap);     

    sem_wait(&y);
        wcount--;
        if(wcount==0)
        { sem_post(&msem); }
    sem_post(&y);
}

void *man(void *param)
{           
    sem_wait(&z);
        sem_wait(&msem);
            sem_wait(&x);
                mcount++;
                if(mcount==1)
                { sem_wait(&wsem); }
            sem_post(&x);
        sem_post(&msem);
    sem_post(&z);

    sem_wait(&cap);

    printf("\t\tman in!\n");
    delay();
    printf("\t\t\tman out!\n");

    sem_post(&cap);

    sem_wait(&x);
        mcount--;
        if(mcount==0)
        {sem_post(&wsem);}
    sem_post(&x);
}

int main(void)
{
    int i;
    srandom(60);

        mcount = 0;
        wcount = 0;
        sem_init(&x,0,1);  // for sem_init, initial value is 3rd argument
        sem_init(&y,0,1);
        sem_init(&z,0,1);
        sem_init(&wsem,0,1);
        sem_init(&msem,0,1);
        sem_init(&cap,0,4);  // eg. cap initialized to 4

        pthread_t *tid;
        tid = malloc(80*sizeof(pthread_t));

    // You can use your cobegin statement here, instead of pthread_create()     
    // I have forgone the use of pthread barriers although I suppose they would nicely imitate the functionality of cobegin. 
    // This is merely to retain simplicity.

    for(i=0;i<10;i++)
    {
        pthread_create(&tid[i],NULL,woman,NULL);
    }
    for(i=10;i<20;i++)
    {     
            pthread_create(&tid[i],NULL,man,NULL);
    }
    for(i=0;i<20;i++)
    {     
            pthread_join(tid[i],NULL);
    }

    return(0);
}

While converting into the 2-restrooms form, make note of which semaphores & counter variables you would need to duplicate to satisfy all the conditions. Happy semaphoring!