exclusión mutua y semáforos

Question

Estoy escribiendo un programa (para la tarea) que simula un baño unisex. Solo se permiten 4 personas a la vez y los hombres y las mujeres no pueden ingresar si el otro sexo ya está usando el baño. Mi problema es permitir un máximo de 4 personas en el baño. Como puede ver en la salida, solo 1 persona ingresa al baño a la vez. Aquí está mi código:

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

} 

Esto genera el siguiente resultado:

Un hombre ha entrado en el lavabo
Personas en el baño: 1

Un hombre ha salido del lavabo
Personas en el baño: 0

Un hombre ha entrado en el baño
La gente en el baño: 1

Un hombre ha salido del lavabo
Personas en el baño: 0

una mujer ha entrado Baño
Personas en el baño: 1

Una mujer ha salido baño
la gente en el baño: 0

una mujer ha entrado en el baño
la gente en el baño: 1

Una mujer ha salido de baños
Personas en el baño: 0

Y así sucesivamente, para siempre.

Answer 1

Editar 5 (Me doy cuenta de esto puede ser demasiado poco y demasiado tarde, ya que era probable una tarea, pero me acaba de ocurrir una manera de hacer esto utilizando sólo los semáforos.)

bien aquí es mi pseudocódigo :

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

El subproceso "Hombre" debe comportarse de manera similar. Tenga en cuenta que los semáforos de espera y mutex protegen las variables de hombres y mujeres.

---

Estás señalando el mutex antes de que un hombre/mujer haya "salido" del baño. Si entiendo correctamente, el mutex es para que solo haya un sexo en el baño en cualquier momento. Como lo está señalizando antes de dar salida a "Un hombre ha salido del baño", una mujer puede obtener el mutex y entrar.

Dado que los hombres y las mujeres esperan inicialmente en dos semáforos diferentes Es comprensible que algunos entren en eso semáforo inicial. A partir de ahí, parece que está obteniendo el mutex (compartido entre hombres y mujeres) y luego de entrar, lo suelta antes de salir. ¿Tal vez quiere decir que está señalando el semáforo "hombre" o "mujer" aquí en su lugar?

Editar: Supongo que la esencia de mi respuesta es esta: el mutex se comparte entre hombres y mujeres.En tu código, cuando una persona obtiene el mutex, dicen que están dentro, decreces que están esperando, y luego liberas el mutex. Piensa en ese último paso un poco más profundamente. Si liberas el mutex antes de que se hayan ido, ¿qué hay aquí?

Edit2 (en respuesta a sus comentarios): ¿Cómo se ve su nuevo código (Edite su publicación original)?

Esto nos ayudará a abstraer el código de la lógica y luego podemos tratar de estructurar su lógica correctamente y comparar lo que creemos que es correcto con lo que está haciendo su código.

Edit3: De acuerdo, parece que te estás acercando. Aquí hay algunas cosas en que pensar (¡No estoy publicando una solución completa porque es una tarea y quiero que aprenda!)

• ¿Qué es mutex protectivo?
• ¿Qué está protegiendo el hombre/la mujer?
• ¿Qué es restroomCount?
• ¿Qué es la protección maxCapacity?
• ¿En qué orden debe una persona obtener estos semáforos?
• ... i.e. ¿Qué semáforos protegen qué otros semáforos y cómo?

Piense especialmente duro sobre el baño recuento de semáforos ... (PISTA: Puede ser más importante que la simple protección de la variable de recuento Es posible que sea necesario proteger la liberación de otros semáforos ....)

Edit 4: Así que finalmente me di cuenta de que está tratando de evitar la inanición en este problema (como lo indican los comentarios a continuación). Aunque su tarea es muy similar al problema de lectores/escritores, la restricción adicional para evitar la inanición por cualquiera de los tipos de subprocesos hace que sea difícil implementarla. Personalmente, no sé cómo hacer esto sin utilizar Events para establecer la preferencia (http://msdn.microsoft.com/en-us/library/dd492846.aspx), y aun así no hay garantía de que la inanición nunca podría suceder, lo que si entiendo correctamente el artículo de Wikipedia (http://en.wikipedia.org/wiki/Readers-writers_problem#The_third_readers-writers_problem) sobre este tema, es el único forma de hacerlo

¿Está permitido el uso de eventos?

Debo disculparme por no haber asimilado por completo esta restricción adicional de lectores/escritores de no morir de hambre. Con suerte, alguien más puede ayudarlo mejor.

Answer 2

Creo que tiene demasiados semáforos. Sus semáforos de hombre/mujer se dirigen a 1 persona a la vez. Considere usar algunas variables de estado protegidas por mutexes (sexo actual del baño, número de personas en el baño) en lugar de tantos semáforos diferentes.

¿Mantiene un pedido en línea o puede la gente saltear según el sexo del baño actual? Por ejemplo, si tiene mujer, mujer, mujer, hombre, mujer, se le permite a la 4ª mujer saltarse al hombre e ir al baño, o las 3 mujeres salen, entonces el hombre entra/sale, entonces la mujer puede ingresar ? Este es un problema más fácil que permitir un salto.

Answer 3

es el uso de semáforos como requisito?por ejemplo, en "C++" pseudo-código, una aplicación se vería así:

En primer lugar permite crear un objeto de estado y una función que valida las transiciones entre los estados

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

Permite también crear una referencia global a la estado actual y una función para actualizar el estado actual basado en alguna próxima estado deseado

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

entonces se crea un vector global para mantener los estados, y una función que representa una mujer hilo tratando de ir al baño

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 

y la función principal de la lógica de bucle proceso y la inicialización

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

este código debe trabajar (i no lo he probado). He engañado un poco porque no estoy eliminando ninguno de los estados provisionales creados, por lo que cada estado persiste hasta que el proceso muere. la recogida de basura adecuada requeriría una técnica llamada gestión de punteros de peligro.

Tenga en cuenta que no utilizo ningún semáforo mute o bloqueo, la única primitiva de bloqueo que estoy usando es la CAS (dirección, valor_antiguo, valor_nuevo) (comparar y cambiar). Esta primitiva compara atómicamente un puntero (dirección) y si aún contiene (valor_antiguo), entonces le asigna valor_nuevo y lo logra, de lo contrario, falla. Además, todavía necesita un bloqueo global para std :: vector que almacene los estados que no he incluido en el código (también puede filtrarlos, pero los guardo en algún lugar para que pueda pensar que deberían eliminarse una vez que sepa cómo se puede hacer que GC funcione en estos casos)

Dado que todos mis estados intermedios son inmutables (inmutabilidad de estilo lisp/clojure) la contención (y por lo tanto, la inanición) de los hilos mejora enormemente. En su ejemplo, el conjunto de estados es pequeño (solo un grupo de personas), no está mal que no eliminemos los estados usados.

Sin embargo, incluso con los problemas que he mencionado, creo que estaría de acuerdo en que la lógica de lo que está sucediendo es mucho más explícita y legible.

Answer 4

Problemas con la pregunta
El código original no es muy OO.

El procesamiento de la cola del baño debe separarse de la generación de las personas en la cola, si no se ejecuta un hilo por separado al menos después de que se llena la cola.

Suponiendo que hay básicamente colas separadas de hombres y mujeres, no entremezcladas en un orden fijo, de lo contrario el problema no tiene sentido usar un semáforo.

El problema no describe cuántas personas pueden ingresar cuando la condición es correcta, baño masculino con más hombres, ¿lo llena a 4 o solo hasta que la cola de hombres es menor que la de mujeres otra vez?

Aun así el problema descrito (y basado en código de muestra sin subprocesamiento) no funciona bien con un semáforo en mi opinión, el problema principal es que el semáforo no produce el conteo fácilmente y una espera exitosa cambia el conteo.

Lo interesante que veo en el problema es la ineficacia en una longitud de cola casi igual y el comercio entre no permitir a otro del mismo sexo en el inodoro y la posibilidad de que antes las personas restantes en el inodoro dejan el mismo número el sexo se vuelve más grande de nuevo. Deja la cara él, es unisex y por lo que debería permitir a 4 personas en independientemente de su sexo;)

Solución propuesta
Así que hay que utilizar un semáforo, las cosas interesantes acerca de un semáforo es la grabación de múltiples usos (a diferencia de mutex) y si no hay espacio libre, posiblemente esperará. Sin embargo, no discrimina entre los que esperan, solo indicará que hay espacio libre.

Tenga 1 semáforo y piense que debe verificar el semáforo cuando una persona entra en la cola o cuando alguien sale del baño.

Usted podría tener 1 'cola' para hombres y mujeres (dado que esto es básicamente un conteo). Estas colas no están realmente relacionadas o limitadas entre sí en términos de entrada y, por lo tanto, no tienen nada que ver con semáforos. Cada uno de ellos puede seguir un patrón de proveedor libre de bloqueo, pero es posible que le resulte más fácil utilizar un mutex para sincronizar, de modo que pueda examinar el tamaño de las colas y manipularlas. A continuación, acabo de utilizar el recuento directamente, en su lugar, debe utilizar alguna forma de InterlockedIncrement y InterlockedDecrement para proteger contra la adición y eliminación de personas de la misma cola.

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