相互排斥和信号量

Question

我正在写一个模拟一个男女皆宜的浴室的程序（用于作业）。一次只允许4人入住，如果另一个人已经在使用浴室，男人和女人不能入住。我的问题是允许最多4人在浴室。从输出中可以看到，一次只有1人进入洗手间。这里是我的代码：

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

} 

这将生成以下的输出：

一名男子进入洗手间
人们在厕所：1

的人已经退出了厕所
洗手间里的人：0

一个男人已经进入洗手间
人们在厕所：1

的人已经退出了厕所
人们在厕所：0

一个女人进入厕所
人们在厕所：1

一个女人已退出厕所
人们在厕所：0

一个女人进入厕所 在洗手间
人：1

一个女人已经离开厕所
人们在厕所：0

依此类推，直到永远。

Answer 1

编辑5（我知道这可能是太少太迟，因为这很可能一个家庭作业，但我只是想到了一个办法做到这一点只用信号灯。）

好，这里是我的伪代码：

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

“Man”线程的行为应该类似。请记住，等待和互斥信号量可以保护男性和女性的变量。

---

在男人/女人“退出”浴室之前，您正在发出互信号。如果我理解正确，互斥是这样的，任何时候只有一个性别在浴室里。既然你在输出“男人已经离开浴室”之前发出信号，那么女人可以得到互斥并进入。

由于男人和女人最初都在等待两个不同的信号灯，所以有些人会接受初始信号量。从那里开始，看起来你已经获得了互斥体（在男性和女性之间共享），然后在你进入之后释放它，然后退出。也许你的意思是在这里发出信号“男人”或“女人”的信号？

编辑：我想我的答案的要点是这样的：互斥是男性和女性共享的。在你的代码中，当一个人得到他们所说的互斥体时，你会减少他们正在等待的内容，然后释放互斥体。更深入地思考最后一步。如果你在他们离开之前释放互斥锁，这里有什么可能？

编辑2（回复您的评论）：你的新代码是什么样的（编辑你的原始文章）？

这将帮助我们将代码抽象到逻辑上，然后我们可以尝试正确地构建您的逻辑，并比较我们认为正确的代码是干什么的。

编辑3：好吧，看起来你越来越近了。这里有一些事情要考虑（我没有发布完整的解决方案，因为这是作业，我希望你学习！）

• 什么是互斥保护？
• 什么是男人/女人保护？
• 什么是restroomCount保护？
• 什么是maxCapacity保护？
• 这些信号应该以什么顺序获得 ？
• ......即，其中信号量保护哪些其他信号量以及如何？

想想尤其是好好的，厕所计数信号......（提示：这可能比简单地保护计数变量更重要的是它可能需要保护其他信号量的释放...。）

编辑4：所以我终于意识到，你正试图避免在这个问题上的饥饿（如下面的评论所示）。虽然你的作业与读者/作者的问题非常相似，但避免任何线程类型的饥饿的额外约束使得难以实现。我个人不知道如何做到这一点，而不使用事件设置偏好（http://msdn.microsoft.com/en-us/library/dd492846.aspx），即使如此，也不能保证饥饿永远不会发生，如果我正确理解关于此主题的维基百科（http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem）文章是唯一的方法来做到这一点。

你被允许使用事件吗？

我不得不道歉，因为没有完全维护这个额外的读者/作家的不饥饿约束。希望别人能更好地帮助你。

Answer 2

我认为你有太多的信号量。你的男人/女人信号量一次只能对一个人开门。考虑使用一些受互斥体保护的状态变量（卫生间的当前性别，浴室中的人数），而不是那么多不同的信号量。

您是否保持排队顺序或可以根据当前的厕所性别跳过？例如，如果你有女人，女人，女人，男人，女人，是第四名被允许跳过男人进入洗手间的女人，或者让3名女人出口，那么男人出入，那么女人可以进入？这是一个比允许跳过更容易的问题。

Answer 3

是使用信号量的一个要求吗？例如，在“C++”伪代码，实现类似于：

首先让我们创建一个状态对象，各国之间的验证转换

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

让我们也创造了一个全球性的参考函数目前的状态和功能的基础上

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

然后我们创建一个全球矢量持有美国未来的一些期望的状态来更新当前状态，并表示女人的功能线程试图去洗手间

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 

，并用处理循环逻辑和初始化

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

此代码应工作（ⅰ没有测试它）的主要功能。我已经欺骗了一点，因为我没有删除任何创建的临时状态，所以每个状态都会一直存在，直到进程终止。正确的垃圾收集将需要一种称为危险指针管理的技术。请注意，我不使用任何互斥信号或锁，我使用的唯一锁定原语是CAS（address，old_value，new_value）（比较和交换）。这个原语自动比较一个指针（地址），如果它仍然包含（old_value），那么它分配它new_value并成功，否则失败。另外，你仍然需要一个std :: vector的全局锁，用于存储我没有包含在代码中的状态（你也可以泄漏它们，但是我把它们存储在某个地方，所以你可以认为这些应该在你知道的时候被删除在这些情况下GC如何工作）

由于我所有的中间状态都是不可变的（lisp/clojure风格inmutabilitity），所以线程的争用（因此，饥饿）大大提高。在你的例子中，状态集合很小（只是一堆人），它不是太糟糕，我们不删除使用的状态。然而，即使我提到的问题，我认为你会同意发生的事情的逻辑更加明确和可读。

Answer 4

与问题
原代码的问题是不是很OO。

浴室队列的处理应该与队列中的人的生成分开 - 如果至少在队列填满之后没有运行单独的线程。

假设男女基本上都是分开排队的 - 不是以某种固定的顺序混合在一起的，否则这个问题对于使用信号灯没有任何意义。

问题并没有描述当条件成熟时有多少人进入，男性厕所多于男性，你是否填充到4或直到男性队列再次少于女性？

即使如此，所描述的问题（以及基于没有线程的示例代码）在我看来并不适用于信号量，主要问题是信号量不容易计数并且成功地等待改变计数。

我在这个问题上看到的有趣的事情是，在排队长度接近相等的情况下效率低下，并且在禁止同一性别进入厕所之间进行交易，以及在厕所中剩余人员离开相同数量之前进行交易性再次变得更大。让我们面对它，这是男女皆宜的，所以它应该允许4人，不分性别;）

建议的解决方案
所以你需要使用一个信号，关于信号的有趣的事情是多种用途的记录（不像互斥体），如果没有空闲空间，那么它可能会等待。然而，它并不区分那些等待的人，它只会说明有空间。

有1个信号灯，并认为你应该检查信号灯，当一个人进入队列或有人离开浴室。

然后，你可以为男性和女性分别设置1个“队列”（从这个基本上算是一个计数）。这些队列在进入方面并没有真正相关或限制，所以与信号量无关。每个可以遵循一个无锁定的提供者模式，但是你可能会发现使用一个互斥体更容易同步，这样你就可以检查队列的大小并对它们进行操作。在下面我刚刚直接使用了count，而应该使用某种形式的InterlockedIncrement和InterlockedDecrement来防止在同一队列中添加和删除人员。

在粗糙，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(); 
}