男女通用卫生间优先算法

Question

我正在尝试制作 Semaphores and concurrent programming 中给出的男女通用浴室算法，那里的解决方案非常有效。但我需要添加另一个功能，如果任何时候有女性进入浴室，那么所有女性都必须 enter/leave 男性才能进入浴室。

下面是原始代码，没有其他问题的优先级特征，在 "Semaphores and concurrent programming" 问题这里 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);
}

为了增加优先级，我添加了两个整数，left_men 和 left_women 来计算剩下的男人和女人的数量。还有一个 int stopped_men 来检查我们之前是否停止了 msem。

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

在这种情况下，我遇到了死锁，因为如果 "man" 函数去获取 "z" 信号量，而不是尝试获取 "msem" 信号量，但它无法获取，因为 "woman" 首先启动并通过将计数器减少到 0 以 sem_wait(&msem) 停止它，并且在没有女人离开之前不会离开它，但是由于男人线程得到了 "z" 信号量 "woman"不能继续输入更多的女人，所以"woman"等待"z"，男人等待"msem"所以我们陷入僵局。

我也有如下更改 "man" 函数的想法，但这也会导致死锁，假设 "man" 获取 "msem" 信号量而不是等待 "z" 信号量，因为第一个 "woman" 线程得到它，当 women 函数进入 sem_wait(&msem) 时它将停止在那里，因为 "msem" 计数器从 "man" 函数开始减少.

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

Answer 1

我找到了一个解决方案，它可能不是最好的，但它似乎有效。

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

c

algorithm

concurrency

multithreading

semaphore