Exclusion mutuelle et sémaphores

je pense que vous avez trop de sémaphores. Vos sémaphores homme/femme vont à 1 personne à la fois. Envisagez d'utiliser certaines variables d'état protégées par des Mutex (sexe actuel de salle de bains, nombre de personnes dans la salle de bains) plutôt que tant de sémaphores différents.

est-ce que vous maintenez un ordre de ligne ou les gens peuvent sauter basé sur le sexe des toilettes actuelles? Par exemple, si vous avez femme, Femme, Femme, Homme, Femme, est la 4ème femme autorisée à sauter l'homme et aller dans le toilettes, ou est-ce que les 3 femmes sortent, puis l'homme entre/sort, puis la femme peut entrer? Il s'agit d'un problème plus facile que d'autoriser un saut.

est l'utilisation de sémaphores une exigence? par exemple, dans le pseudo-code" c++", une implémentation ressemblerait à:

permet D'abord de créer un objet d'état et une fonction qui valide les transitions entre les États

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

permet également de créer une référence globale à l'état actuel et une fonction pour mettre à jour l'état actuel basé sur un prochain état désiré

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

alors nous créons un vecteur global pour tenir les états, et une fonction représentant une femme thread en essayant d'aller à la salle de bain

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

et la fonction principale avec la logique de boucle de processus et l'initialisation

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

ce code devrait fonctionner ( Je ne l'ai pas testé ). J'ai triché un peu parce que je ne supprime aucun des États provisoires créés, donc chaque état persiste jusqu'à ce que le processus meurt. bonne collecte des ordures nécessiterait une technique appelée danger pointeur de gestion .

Notez que je n'utilise pas tout mutex, sémaphores ou de verrouillage, la seule verrouillage primitive que j'utilise est le CAS( adresse, old_value , nouvelle_valeur ) (comparer et swap). Cette primitive compare atomiquement un pointeur (adresse) et s'il contient encore (old_value) alors il lui attribue new_value et réussit, sinon il échoue. En outre, vous avez encore besoin d'un verrouillage global pour le std::vector stockant les états que je n'ai pas inclus dans le code (vous pouvez aussi simplement les faire fuiter, mais je les stocke quelque part afin que vous puissiez penser qu'ils devraient être supprimés une fois que vous savez comment GC pourrait être fait pour fonctionner dans ces cas-là)

étant donné que tous mes états intermédiaires sont inmutables (style lisp/clojure inmutabilité), la prétention (et donc la famine) des fils s'améliore considérablement. Dans votre exemple l'ensemble des États est petit (juste un groupe de personnes) ce n'est pas trop mal que nous ne supprimons pas les États utilisés.

cependant, malgré les problèmes que j'ai mentionnés, je pense que vous conviendrez que la logique de ce qui se passe est beaucoup plus explicite et lisible.

Edit 5 (je me rends compte que c'est peut-être trop peu en retard, car c'était probablement un devoir à la maison, mais j'ai juste pensé à une façon de le faire en utilisant seulement des sémaphores.)

voilà mon pseudo:

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

le fil "homme" doit se comporter de la même manière. Gardez à l'esprit que l'attente et mutex sémaphores protéger à la fois les hommes et les femmes variables.

---

vous signalez le mutex avant qu'un homme / une femme ait "quitté" la salle de bain. Si je comprends bien, le mutex est tellement qu'un seul sexe est dans la salle de bain à tout moment. Puisque vous le signalez avant de sortir "un homme a quitté la salle de bain", une femme peut obtenir le mutex et entrer.

comme les hommes et les femmes attendent d'abord sur deux sémaphores différents, il est compréhensible que certains vont entrer dans ce sémaphore initial. De là, il apparaît que vous obtenez le mutex (partagé entre les hommes et les femmes) puis après être entré vous le relâchez avant qu'ils sortent. Peut-être voulez-vous signaler le sémaphore "homme" ou "femme" à la place?

Edit : je suppose que l'essentiel de ma réponse est ceci: le mutex est partagé entre les hommes et les femmes. Dans votre code, lorsqu'une personne obtient le mutex ils disent, vous décrémenter qu'ils sont en attente, puis vous relâchez le mutex. Pensez à la dernière étape un peu plus profondément. Si vous libérez le mutex avant gauche, ce qui est possible ici?

Edit2 (en réponse à vos commentaires) : A quoi ressemble votre nouveau code (modifier votre message original)?

cela nous aidera à abstraire le code loin à la logique et puis nous pouvons essayer de structurer votre logique correctement et comparer ce que nous pensons est juste à ce que votre code fait.

Edit 3: OK, on dirait que vous vous approchez. Voici quelques choses à penser (Je ne suis pas poster une solution complète parce que c'est un devoir et je veux que vous appreniez!)

• Qu'est-ce que mutex protège?
• Quel est l'homme/la femme protéger?
• qu'est-ce que restroomCount protecting?
• qu'est-ce que maxCapacity protège?
• dans quel ordre une personne doit-elle obtenir ces sémaphores?
• ...c'est à dire Qui les sémaphores protègent d'autres sémaphores et comment?

pensez surtout au sémaphore des toilettes... (Indice: cela peut être plus important que de simplement protéger la variable count. Il peut être nécessaire de protéger la libération des autres sémaphores...)

Edit 4: donc j'ai finalement réalisé que vous essayez d'éviter la famine dans ce problème (comme indiqué par les commentaires ci-dessous). Bien que vos devoirs soient très comme pour le problème des lecteurs / écrivains, la contrainte supplémentaire pour éviter la famine par l'un ou l'autre type de thread le rend difficile à mettre en œuvre. Personnellement, je ne sais pas comment faire cela sans utiliser les événements pour définir la préférence ( http://msdn.microsoft.com/en-us/library/dd492846.aspx ), et même alors il n'y a aucune garantie que la famine ne pourrait jamais se produire, ce qui si je comprends la Wikipédia ( http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem ) article sur ce sujet correctement, est la seule façon de le faire.

Êtes-vous autorisé à utiliser events?

je dois m'excuser de ne pas avoir complètement grogné cette contrainte supplémentaire de lecteurs/écrivains de ne pas mourir de faim. Espérons que quelqu'un d'autre peut vous aider à mieux.

des Problèmes avec la question

Le code original n'est pas très OO.

le traitement de la file d'attente de la salle de bain doit être séparé de la génération des gens dans la file d'attente - si pas un fil séparé au moins après que la file d'attente est remplie.

faisant l'hypothèse qu'il y a fondamentalement des files d'attente séparées des hommes et des femmes - pas mélangé dans un ordre fixe, sinon le problème n'a pas de sens d'utiliser un sémaphore.

le problème ne décrit pas combien de personnes arrivent à entrer quand la condition est bonne, toilettes hommes avec plus d'hommes, vous remplissez à 4 ou seulement jusqu'à ce que la file d'attente des hommes est moins que les femmes à nouveau?

même si le problème tel que décrit (et basé sur le code échantillon sans filetage) ne fonctionne pas bien avec un sémaphore à mon avis, le problème principal est que le sémaphore ne donne pas le compte facilement et un une attente réussie change le compte.

la chose intéressante que je vois dans le problème est l'inefficacité dans une longueur de file d'attente presque égale et le commerce entre le rejet d'un autre du même sexe dans les toilettes et la chance qu'avant que les personnes restantes dans les toilettes quittent le nombre du même sexe devient plus grand encore. Admettons-le, Il est unisexe et donc il devrait permettre 4 personnes dans indépendamment du sexe;)

solution proposée

Donc, vous devez utiliser un sémaphore, les choses intéressantes à propos d'un sémaphore est l'enregistrement de plusieurs utilisations (contrairement à mutex) et s'il n'y a pas d'espace libre alors il sera peut-être attendre. Il ne fait cependant pas de distinction entre ceux qui attendent, il dira seulement qu'il y a de l'espace libre.

ont 1 sémaphore et pensent que vous devriez vérifier le sémaphore quand une personne entre dans la file d'attente ou quand quelqu'un sort de la salle de bains.

vous pourriez alors avoir 1 'file' chacun pour les hommes et les femmes (d'où ceci est essentiellement un compte). Ces Files d'attente ne sont pas vraiment liées ou limitatives les unes aux autres en termes d'entrée et n'ont donc rien à voir avec les sémaphores. Chacun pourrait suivre un modèle de fournisseur libre de verrouillage, mais vous pourriez trouver plus facile d'utiliser un mutex pour synchroniser de sorte que vous pouvez examiner la taille des files d'attente et de les manipuler. Dans ce qui suit, je viens d'utiliser le compte directement, à la place, il devrait être en utilisant une certaine forme de L'augmentation et de la diminution imbriquées pour se protéger contre l'ajout et le retrait de personnes de la même file d'attente.

dans la salle de bains rugueuse.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;
};

salle de bains.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();
    }
}

programme.cpp

Bathroom b1;

addPeople() {
  while(true) {
  // randomly add people
    Delay();
    b1.AddMen();
    b1.AddWomen();
  }
}

int main(){

  thread( addPeople );

  b1.run();
}