Unisex bathroom algorithm with priority

Question

I am trying to make a Unisex bathroom algorithm as given in Semaphores and concurrent programming ,the solutions there work great. But I need to add another feature, if at anytime a women enters the bathroom than all the women will have to enter/leave the bathroom before the males can start to enter it.

Below is the original code without priority feature from the other question at the "Semaphores and concurrent programming" question here at SO.

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

To add priority I have added two integers, left_men and left_women to count the number of left men and women. And an int stopped_men to check if we have stopped msem earlier.

int left_man, left_women, stopped_men;

void *woman(void *param)
{
    sem_wait(&z);
        sem_wait(&wsem);
            sem_wait(&y);
                left_women--;
                wcount++;
                if(wcount==1 && stopped_man == 0)
                {
                    stopped_man = 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 && left_women == 0 && stopped_man == 1)
        {
             sem_post(&msem);
             stopped_man = 0;
         }
    sem_post(&y);
}

In this case I have a deadlock, since if "man" function goes and gets the "z" semaphore than tries to get the "msem" semaphore, but it can not get since "woman" started first and stopped it with sem_wait(&msem) by decreasing the counter to 0 and will not leave it until no woman is left, but since man thread got the "z" semaphore the "woman" can not continue to input more woman, so "woman" waits for "z", man waits for "msem" so we have a deadlock.

I also had the idea to change the "man" function as below, but this will result in deadlock as well, lets say "man" gets "msem" semaphore than wait for "z" semaphore since the first "woman" thread got it, when the women function goes to sem_wait(&msem) it will halt there since "msem" counter decreased earlier from "man" function.

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

Actually my algorithm has to do with another thing not women an men, but to make it easy I referred to the algorithm that was already here in SO. — edoniti, Sep 23 '16 at 14:44
You should have used the other things. Not all people have a problem with unisex bathrooms ... — too honest for this site, Sep 23 '16 at 14:51
http://stackoverflow.com/questions/8274098/possibility-of-starvation-of-dining-philosophers — stark, Sep 23 '16 at 18:51
@stark how do you relate the Dining Philosophers problem to this one? Any hint? — edoniti, Sep 23 '16 at 21:19
Dining philosophers refers to the general problem of deadlock over resource conflicts. — stark, Sep 24 '16 at 11:51

score 0 · Accepted Answer · answered Sep 25 '16 at 00:45

I have found a solution, it might not be the best one but it seems to work.

sem_wait(&z);
if(stopped_man == 1)
{
    /* It means that someone stopped us, so release the "z" semaphore
       and wait for the thread that stopped us to signal us */
    sem_post(&z);

    sem_wait(&msem);
        sem_wait(&z);
            sem_wait(&x);
                mcount++;
                if(mcount==1)
                { sem_wait(&wsem); }
            sem_post(&x);
        sem_post(&z);
    sem_post(&msem);
}
else
{
        sem_wait(&msem);
            sem_wait(&x);
                mcount++;
                if(mcount==1)
                { sem_wait(&wsem); }
            sem_post(&x);
        sem_post(&msem);
    sem_post(&z);
}

Unisex bathroom algorithm with priority

1 Answers1