Подтвердить что ты не робот

Взаимное исключение и семафоры

Я пишу программу (для домашней работы), которая имитирует унисекс-ванную. Только 4 человека допускаются одновременно, и мужчины и женщины не могут войти, если другой секс уже использует ванную. Моя проблема заключается в том, что в ванной может быть не более 4 человек. Как вы можете видеть на выходе, только один человек входит в туалет одновременно. Вот мой код:

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

И так далее, навсегда.

4b9b3361

Ответ 1

Я думаю, что у вас слишком много семафоров. Семафоры с мужчиной/женщиной строят до 1 человека за раз. Рассмотрите возможность использования некоторых переменных состояния, защищенных мьютексами (текущий пол ванной комнаты, количество людей в ванной комнате), а не столько разных семафоров.

Поддерживаете ли вы заказ строки или можете пропустить людей в зависимости от текущего пола в туалете? Например, если у вас есть женщина, женщина, женщина, мужчина, женщина, это 4-я женщина, которой разрешено пропустить мужчину и пойти в туалет, или выйти из трех женщин, затем человек входит/выходит, тогда женщина может войти? Это более простая проблема, чем разрешение пропустить.

Ответ 2

является использование семафоров требованием? например, в псевдокоде "С++", реализация будет выглядеть так:

Сначала создадим объект состояния и функцию, которая проверяет переходы между состояниями

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 можно было бы заставить работать в этих случаях)

Так как все мои промежуточные состояния являются inmutable (lisp/clojure стиль inmutability), утверждение (и, следовательно, голодание) потоков значительно улучшается. В вашем примере множество состояний невелико (просто группа людей), что не так уж плохо, что мы не удаляем используемые состояния.

однако, даже с упомянутыми проблемами, я думаю, вы согласитесь, что логика происходящего гораздо более ясна и читаема.

Ответ 3

Изменить 5 (я понимаю, что это может быть слишком поздно, поскольку это, скорее всего, домашнее задание, но я просто подумал о том, как это сделать, используя только семафоры.)

ok здесь мой псевдокод:

//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 mens' turn!" << endl;
}
else if (menWaiting == womenWtg == 0)
{
   turn = -1; //anybody should be able to get in
}
signal(waiting);
signal(mutex);

Поток "Человек" должен вести себя аналогичным образом. Имейте в виду, что семафоры ожидания и мьютекса защищают как переменные, так и женщины.


Вы сигнализируете мьютекс, прежде чем мужчина/женщина "выйдет" из ванной. Если я правильно понимаю, мьютекс - это то, что только один секс находится в ванной в любое время. Поскольку вы сигнализируете об этом перед выходом "Человек вышел из ванной", женщина может получить мьютексы и войти.

Поскольку мужчины и женщины изначально ждут двух разных семафоров, понятно, что некоторые из них попадут в этот начальный семафор. Оттуда, кажется, вы получаете мьютекс (разделяемый между мужчинами и женщинами), а затем после того, как вы входите в него, освободите его, прежде чем они выйдут. Может быть, вы хотите сказать, что вместо этого здесь вместо семафора "мужчина" или "женщина"?

Изменить. Я думаю, суть моего ответа такова: мьютекс разделяется между мужчинами и женщинами. В вашем коде, когда человек получает мьютекс, они говорят, что они находятся, вы уменьшаете их ожидания, затем вы отпускаете мьютекс. Подумайте об этом последнем шаге немного глубже. Если вы отпустите мьютекс, прежде чем они уйдут, что возможно здесь?

Edit2 (в ответ на ваши комментарии). Как выглядит ваш новый код (отредактируйте исходное сообщение)?

Это поможет нам отвлечь код от логики, а затем мы сможем попытаться правильно структурировать вашу логику и сравнить то, что, по нашему мнению, правильно для вашего кода.

Edit3: Хорошо, похоже, вы приближаетесь. Вот некоторые вещи, о которых нужно подумать (я не отправляю полное решение, потому что это домашнее задание, и я хочу, чтобы вы учились!)

  • Что такое защита мьютексов?
  • Что защищает мужчина/женщина?
  • Что такое restroomCount protection?
  • Что такое защита maxCapacity?
  • В каком порядке человек должен получить эти семафоры?
  • ... т.е. Какие семафоры защищают другие семафоры и как?

Особенно сильно подумайте о семафоре счетчика туалета... (СОВЕТ: Это может быть более важно, чем просто защита переменной счетчика. Возможно, потребуется защитить освобождение других семафоров...)

Изменить 4: Итак, я наконец понял, что вы пытаетесь избежать голодания в этой проблеме (как указано в комментариях ниже). Хотя ваша домашняя работа очень похожа на проблему с читателями/писателями, дополнительное ограничение, чтобы избежать голодания по типу нити, затрудняет реализацию. Я лично не знаю, как это сделать, не используя Events для настройки предпочтения (http://msdn.microsoft.com/en-us/library/dd492846.aspx), и даже тогда нет никакой гарантии, что голод может никогда не бывает, что, если я правильно понимаю статью Wikipedia (http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem), это единственный способ сделать это.

Разрешено ли вам использовать события?

Я должен извиниться за то, что вы не полностью избавляетесь от этих дополнительных читателей/писателей, которые не испытывают голода. Надеюсь, кто-то еще может вам помочь.

Ответ 4

Проблемы с вопросом
Исходный код не очень 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();
}