Semaphores and concurrent programming

Question

Hello. For a homework assignment i need to program the following scenario. This is going to be done using semaphores using BACI (which is C--)

There are 2 unisex restrooms that can hold 4 people each. Since it is unisex only people of the same sex can be in the restroom at the same time and FIFO is not important. I have the basic "algorithm" in my head to handle 4 men and 4 woman for 1 restroom. But i don't know how to code this. Any help would be greatly appreciated. Here is what I have.

Woman:

Check to see if there are any men in the restroom. If so "wait".
If no men check to see if there are 4 people. If so "wait".
If no men and not 4 use restroom. When leaving signal there is a vacancy.
If last woman signal the men if they are waiting if not signal the woman.


Man:

check to see if there are any woman in the restroom. if so "wait"
If no woman check to see if there are 4 people. If so "wait".
If no woman and not 4 use restroom. when leaving signal there is a vacancy.
if last man signal the women if they are waiting if not signal the men.

These additional instructions were provided

• Use random FOR loops to simulate the passage of time in the appropriate places. This can be easily done by using a Delay function:

  void Delay (void)
  { 
    int i;
    int DelayTime;
    DelayTime = random (DELAY);
    for (i = 0; i < DelayTime; i++):
  }
  

• where const int DELAY = some number from 10 to 100.

• Print and format output nicely and print messages in such a way that by reading the output, one can trace the execution order.
• Set the processes up to loop forever, and use control C (or control break) to stop your program.

Answer 1

Here is what I have. This allows 1 person in the restroom at a time without deadlock or starvation. I'm in need of assistance with how to make it so 4 people can be in the restroom at a time.

const int Delayx = 60;
int i;
semaphore max_capacity;
semaphore woman;
semaphore man;
semaphore mutex;

void Delay(void)
{
    int DelayTime;
    DelayTime = random(Delayx);
    for (i = 0; i<DelayTime; i++);
}

void Woman(void)
{
    wait(woman);
    wait(max_capacity);
    wait(mutex);
    cout << "A Woman has entered Restroom"<<endl;
    Delay();
    cout << "A woman has exited Restroom"<<endl;
    signal(mutex);
    signal(max_capacity);
    signal(man);
}

void Man(void)
{
    wait(man);
    wait(max_capacity);
    wait(mutex);
    cout <<"A Man has entered the Restroom"<<endl;
    Delay();
    cout << "A man has exited the Restroom"<<endl;
    signal(mutex);
    signal(max_capacity);
    signal(woman);
}

void main()
{
    initialsem(woman,1);
    initialsem(man,1);
    initialsem(max_capacity,4);
    initialsem(mutex,1);
    cobegin
    {
        Woman(); Woman(); Woman(); Woman(); Woman(); Woman(); Woman(); Woman(); Man();  Man(); Man(); Man(); Man(); Man(); Man(); Man();
    }
}

Answer 2

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!