互斥和信号量

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

我认为你的信号量太多了。您的男性/女性信号量一次选通至 1 个人。考虑使用一些受互斥锁保护的状态变量（浴室的当前性别、浴室中的人数）而不是这么多不同的信号量。

您是否保持排队顺序，或者人们可以根据当前的洗手间性别跳过排队吗？例如，如果有女人，女人，女人，男人，女人，是第4个女人允许跳过男人进入洗手间，或者3个女人退出，然后男人进入/退出，然后女人可以进入？这是一个比允许跳过更容易的问题。

Answer 2

是否需要使用信号量？例如，在“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( 地址、 old_value 、 new_value ) （比较和交换）。该原语以原子方式比较指针（地址），如果它仍然包含（old_value），则为其分配 new_value 并成功，否则失败。另外，您仍然需要 std::vector 的全局锁来存储我未包含在代码中的状态（您也可以泄漏它们，但我将它们存储在某个地方，这样您就可以认为一旦您知道这些状态就应该被删除） GC 如何在这些情况下工作）

由于我所有的中间状态都是不可变的（lisp/clojure 风格的不可变性），线程的争用（以及因此的饥饿）大大改善。在您的示例中，状态集很小（只是一群人），我们不删除已使用的状态还不错。

然而，即使有我提到的问题，我想你也会同意正在发生的事情的逻辑更加明确和可读。

Answer 3

问题的问题
原来的代码不太OO。

卫生间队列的处理应该与队列中人员的生成分开 - 如果至少在队列填满后不运行单独的线程。

假设男性和女性基本上是分开的队列 - 不以某种固定的顺序混合，否则使用信号量的问题没有任何意义。

问题不是描述条件合适的情况下有多少人可以进入，男厕所男多了，你是填到4个还是只填到男的队列再次少于女的？

即使如此，在我看来，所描述的问题（并且基于没有线程的示例代码）对于信号量来说并不能很好地工作，主要问题是信号量不容易产生计数，并且成功的等待会改变计数。

我在这个问题中看到的有趣的事情是，在几乎相等的队列长度和不允许另一个同性进入厕所与厕所中的剩余人离开之前同性数量再次变大的机会之间进行权衡时效率低下。让我们面对现实吧，它是男女皆宜的，因此无论性别如何，都应该允许 4 人进入；）

建议的解决方案
所以你需要使用信号量，信号量的有趣之处在于记录多次使用（与互斥体不同），如果没有可用空间，那么它可能会等待。然而，它不会区分等待的人，它只会告诉您有空闲空间。

有 1 个信号量，并认为当有人进入队列或有人离开卫生间时应该检查信号量。

然后，您可以为男性和女性各安排 1 个“队列”（从给定的情况来看，这基本上是一个计数）。这些队列在条目方面并不真正相关或相互限制，因此与信号量无关。每个都可以遵循无锁定提供程序模式，但您可能会发现使用互斥体进行同步更容易，以便您可以检查队列的大小并操作它们。在下面，我直接使用了计数，而应该使用某种形式的 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();
}