Exclusion mutuelle et sémaphores

J’écris un programme (pour les devoirs) qui simule une salle de bain unisexe. 4 personnes seulement sont autorisées à la fois et les hommes et les femmes ne peuvent pas entrer si l’autre sexe utilise déjà les canvasttes. Mon problème est de permettre un maximum de 4 personnes dans la salle de bain. Comme vous pouvez le constater à la sortie, une seule personne entre dans les canvasttes à la fois. Voici mon code:

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

Cela génère la sortie suivante:

Un homme est entré dans les canvasttes
Personnes dans les canvasttes: 1

Un homme est sorti des canvasttes
Personnes dans les canvasttes: 0

Un homme est entré dans les canvasttes
Personnes dans les canvasttes: 1

Un homme est sorti des canvasttes
Personnes dans les canvasttes: 0

Une femme est entrée dans les canvasttes
Personnes dans les canvasttes: 1

Une femme a quitté les canvasttes
Personnes dans les canvasttes: 0

Une femme est entrée dans les canvasttes
Personnes dans les canvasttes: 1

Une femme a quitté les canvasttes
Personnes dans les canvasttes: 0

Et ainsi de suite, pour toujours.

Je pense que vous avez trop de sémaphores. Vos sémaphores homme / femme s’adressent à une personne à la fois. Pensez à utiliser certaines variables d’état protégées par des mutex (sexe actuel de la salle de bain, nombre de personnes dans la salle de bain) plutôt que par autant de sémaphores différents.

Maintenez-vous une ligne de commande ou les gens peuvent-ils sauter en fonction du sexe actuel aux canvasttes? Par exemple, si vous avez une femme, une femme, une femme, un homme, une femme, est la 4ème femme autorisée à sauter l’homme et à aller aux canvasttes, ou les 3 femmes sortent, puis l’homme entre / sort, puis la femme peut entrer ? C’est un problème plus facile que d’autoriser un saut.

l’utilisation de sémaphores est-elle une exigence? Par exemple, dans le pseudo-code “c ++”, une implémentation ressemblerait à ceci:

Commençons par créer un object 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 permettant de mettre à jour l’état actuel en fonction de l’état souhaité

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

puis nous créons un vecteur global pour tenir les états, et une fonction représentant un fil de femmes essayant d’aller aux canvasttes

 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 un peu sortingché parce que je ne supprime aucun des états provisoires créés, donc chaque état persiste jusqu’à la fin du processus. le ramassage correct des ordures nécessiterait une technique appelée gestion du pointeur de risque .

Notez que je n’utilise pas de sémaphores ni de verrou mutex, la seule primitive de locking que j’utilise est le CAS (adresse, ancienne valeur, nouvelle valeur) (comparer et échanger). Cette primitive compare atomiquement un pointeur (adresse) et si elle contient toujours (ancienne_valeur), elle lui atsortingbue nouvelle_valeur et réussit, sinon elle échoue. En outre, vous avez toujours besoin d’un verrou global pour std :: vector stockant les états que je n’ai pas inclus dans le code (vous pouvez également les divulguer, mais je les stocke quelque part pour que vous puissiez penser qu’ils doivent être supprimés une fois que vous savez comment faire fonctionner le GC dans ces cas)

Puisque tous mes états intermédiaires sont immuables (inmutabilité du style lisp / clojure), la contention (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 si mal que nous ne supprimions pas les états utilisés.

Cependant, même avec les problèmes que j’ai mentionnés, je pense que vous conviendrez avec moi que la logique de ce qui se passe est beaucoup plus explicite et lisible.

Edit 5 (je réalise que cela est peut-être trop peu et trop tard, car c’était probablement un devoir, mais j’ai juste pensé à une façon de le faire en utilisant uniquement des sémaphores.)

ok voici mon pseudocode:

 //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 "Man" devrait se comporter de la même manière. Gardez à l'esprit que l'attente et les sémaphores mutex protègent les variables hommes et femmes.


Vous signalez le mutex avant qu'un homme / une femme ne soit "sorti" de la salle de bain. Si je comprends bien, le mutex est tel que seul un sexe est présent dans la salle de bain. Comme vous le signalez avant de sortir "Un homme est sorti de la salle de bain", une femme peut obtenir le mutex et entrer.

Puisque les hommes et les femmes attendent initialement deux sémaphores différents, il est compréhensible que certains s’intègrent à ce sémaphore initial. À partir de là, il semble que vous obteniez le mutex (partagé entre hommes et femmes) puis, une fois entré, relâchez-le avant de le quitter. Vous voulez peut-être signaler ici le sémaphore "homme" ou "femme"?

Edit : Je suppose que le sens de ma réponse est le suivant: le mutex est partagé entre hommes et femmes. Dans votre code, lorsqu'une personne obtient le mutex qu'elle dit, vous décrémentez son attente, puis vous libérez le mutex. Pensez à cette dernière étape un peu plus profondément. Si vous publiez le mutex avant son départ, qu'est-ce qui est possible ici?

Edit2 (en réponse à vos commentaires) : À quoi ressemble votre nouveau code (Éditez votre message original)?

Cela nous aidera à extraire le code de la logique et nous pourrons ensuite essayer de structurer votre logique correctement et de comparer ce que nous pensons être juste à ce que votre code fait.

Edit3: D'accord, on dirait que vous vous approchez . Voici quelques éléments à prendre en compte (je ne publie pas de solution complète car il s'agit d'un devoir et je veux que vous appreniez!)

  • Qu'est-ce que le mutex protège?
  • Qu'est-ce que l'homme / la femme protège?
  • Qu'est-ce que RestroomCount protège?
  • Que protège maxCapacity?
  • Dans quel ordre une personne devrait-elle obtenir ces sémaphores?
  • ... c.-à-d. quels sémaphores protègent quels autres sémaphores et comment?

Pensez particulièrement au sémaphore du nombre de canvasttes ... (CONSEIL: cela peut être plus important que de simplement protéger la variable de comptage. Il peut être nécessaire de protéger la libération d'autres sémaphores ...)

Edit 4: J'ai donc finalement réalisé que vous tentiez d'éviter la famine dans ce problème (comme indiqué par les commentaires ci-dessous). Bien que votre travail soit très similaire au problème des lecteurs / rédacteurs, la contrainte supplémentaire pour éviter la famine par l’un ou l’autre type de fil le rend difficile à mettre en œuvre. Personnellement, je ne sais pas comment faire cela sans utiliser Events pour définir les préférences ( http://msdn.microsoft.com/en-us/library/dd492846.aspx ), et même dans ce cas, rien ne garantit que la famine ne pourrait jamais se produire, Si je comprends bien l'article Wikipedia ( http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem ) sur ce sujet, c'est le seul moyen de le faire.

Êtes-vous autorisé à utiliser des événements?

Je dois m'excuser de ne pas complètement critiquer cette contrainte supplémentaire de non-famine des lecteurs / écrivains. Espérons que quelqu'un d'autre puisse vous aider mieux.

Problèmes avec la question
Le code d’origine n’est pas très OO.

Le traitement de la queue de la salle de bain doit être distinct de celui de la génération des personnes dans la queue – si vous n’exécutez pas de thread séparé au moins après le remplissage de la queue.

Faire l’hypothèse qu’il existe essentiellement des files d’attente distinctes d’hommes et de femmes – non pas mélangées dans un ordre déterminé, sinon le problème n’a aucun sens d’utiliser un sémaphore.

Le problème ne décrit pas le nombre de personnes qui entrent quand la condition est bonne, canvasttes pour hommes avec plus d’hommes, est-ce que vous remplissez à 4 ou seulement jusqu’à ce que la file des hommes soit à nouveau inférieure à celle des femmes?

Même si le problème décrit (et basé sur un exemple de code sans thread) ne fonctionne pas bien avec un sémaphore à mon avis, le problème principal est que le sémaphore ne génère pas facilement le nombre et qu’une attente réussie le modifie.

La chose intéressante que je vois dans le problème est l’inefficacité d’une queue presque égale et l’échange entre le refus d’un autre sexe du même sexe dans les canvasttes et la possibilité qu’avant que les personnes restantes dans les canvasttes ne partent, le nombre de personnes du même sexe redevient plus grand. . Regardons les choses en face, il est unisexe et devrait donc permettre à 4 personnes quel que soit leur sexe;)

Solution proposée
Vous devez donc utiliser un sémaphore. Ce qui est intéressant à propos d’un sémaphore, c’est l’enregistrement de multiples utilisations (à la différence du mutex) et s’il n’ya pas d’espace libre, il attendra probablement. Il ne fait pas de distinction cependant entre ceux qui attendent, il dira seulement qu’il y a un espace libre.

Ayez 1 sémaphore et pensez que vous devriez vérifier le sémaphore quand une personne entre dans la queue ou quand quelqu’un sort de la salle de bain.

Vous pourriez alors avoir 1 “file” pour les hommes et les femmes (étant donné qu’il s’agit essentiellement d’un compte). Ces files d’attente ne sont pas vraiment liées ou ne se limitent pas mutuellement en termes d’entrée et n’ont donc rien à voir avec les sémaphores. Chacune peut suivre un modèle de fournisseur sans locking, mais vous pouvez trouver plus facile d’utiliser un mutex pour la synchronisation afin de pouvoir examiner la taille des files d’attente et les manipuler. Dans ce qui suit, je viens d’utiliser le décompte directement. Au lieu de cela, il devrait utiliser une forme quelconque d’InterlockedIncrement et d’InterlockedDecrement pour éviter l’ajout et la suppression de personnes de la même queue.

À l’état brut, 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; }; 

Salle de bain.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(); }