Punto muerto del semáforo

Question

Tengo un problema con el semáforo. Escribiendo un código donde hay 4 habitaciones y algunos visitantes. Cada habitación tiene un cierto límite para la cantidad de visitantes que pueden albergar. Por lo tanto, ingresar a una sala llena provocaría una espera(). Los visitantes no deben salir de una habitación antes de poder ingresar a otra, por lo que siempre están en una habitación.

public class Semaphore { 

    private int placesLeft; 

    public Semaphore(int placesInRoom) { 
    this.placesLeft = placesInRoom; 
    } 

    public synchronized void acquire(Visitor visitor) { 
    Semaphore sem = visitor.getRoom().getSemaphore(); 

    try { 
     while (placesLeft <= 0) { 
     this.wait(); 
    } 

    } catch (InterruptedException e) {} 

    sem.release(); 
    placesLeft--; 
} 

public synchronized void release() { 
    placesLeft++; 
    this.notifyAll(); 
} 

Deadlock aparece cuando 2 personas intentan entrar en las habitaciones de los demás. También por alguna razón, el conteo placesLeft no está saliendo bien.

¿Qué debo hacer?

EDIT:

estado ocupado con otra cosa, la reactivación de la cuestión. El problema no ocurre porque las salas se llenan, se bloquea cuando la persona1 de la habitación1 quiere entrar en la habitación2 y al mismo tiempo la persona2 de la habitación2 quiere entrar en la habitación1. Como entiendo, ¿tiene algo que ver con la sincronización? Se atascan antes del lanzamiento, por lo que no se llama a la liberación. Como yo entiendo, una habitación no se puede llamar y liberar a la misma hora. Así que, básicamente, la liberación del semáforo Room1 no se puede llamar primo al mismo tiempo que se llama el accuire, ¿lo mismo para room2? Soy un codificador novato y la sincronización no es tan clara todavía. La eliminación de sincronizaciones de una u otra no parece funcionar (también está mal).

Answer 1

Agregue una lista de visitantes actuales al Room para que pueda verificar en acquire la condición de que el visitante entrante proviene de una habitación que uno de los ocupantes de esta habitación está esperando ingresar. También deberá agregar la habitación que un visitante está esperando ingresar al Visitor.

Room comingFrom = visitor.getRoom(); 
while (placesLeft <= 0) { 
    for (Visitor waiter : room.getVisitors()) { 
     if (waiter.getWaitingForRoom().equals(comingFrom) { 
      // swap the visitors without releasing/acquiring any semaphores and return 
     } 
    } 
    this.wait(); 
} 

estoy un poco inseguro de la lógica para comprobar si un usuario está esperando para entrar en la misma habitación que el visitante actual se va. No puedo decir qué habitación representa room dado el código.

Answer 2

En lugar de implementar la suya propia, ¿qué le parece usar java.util.concurrent.Semaphore que está integrado en la Biblioteca Estándar de Java?

El paquete java.util.concurrent tiene un gran tutorial que cubre semáforos y los muchos otros mecanismos de sincronización útiles que proporciona.

Answer 3

Para responder a su pregunta, "¿Qué debo hacer?", Si detecta un interbloqueo, mueva uno de los Visitantes interbloqueados a cualquier habitación con espacio. Luego muévelo a la habitación que realmente quiere. Esto básicamente permite un intercambio sin violar ninguna de las reglas a continuación.

1. habitaciones no deben contener más de X visitantes
2. un visitante es siempre exactamente en una sala de
3. Sólo un visitante puede cambiar de habitación a la vez (que realmente es el quid de la cuestión)

Tenga en cuenta que hay un millón de estrategias de bloqueo de semáforos por ahí ...

Answer 4

El bloqueo se produce cuando hay un ciclo en el gráfico de dependencia. Cuando 2 personas intentan entrar en las habitaciones de los demás, esto es evidentemente un ciclo, y el punto muerto es una consecuencia natural.

Sin embargo, desea tratar los ciclos de otra manera: cuando se produce el ciclo, las personas se mueven a lo largo del ciclo (puede haber más de 2 personas intercambiando habitaciones).

Por lo tanto, primero debe determinar si se forma un ciclo y luego cambiar las ubicaciones de los visitantes.

Answer 5

Prueba esto:

public class Semaphore { 
    private final static Object LOCK = new Object(); 
    private int placesLeft; 

    public Semaphore(int placesInRoom) { 
    this.placesLeft = placesInRoom; 
    } 

    public void acquire(Visitor visitor) { 
     synchronized (LOCK) { 
      Semaphore sem = visitor.getRoom().getSemaphore(); 

      try { 
       while (placesLeft <= 0) { 
        LOCK.wait(); 
       } 
      } catch (InterruptedException e) {} 

     sem.release(); 
     placesLeft--; 
    } 
} 

public void release() { 
    synchronized(LOCK) { 
     placesLeft++; 
     LOCK.notifyAll(); 
    } 
} 

El código antiguo sincronizada en los casos individuales del semáforo. Es muy difícil evitar interbloqueos, porque el método acquire() de una instancia llama al release() de otra instancia. La llamada al release() luego bloquea si otro hilo está ejecutando actualmente el método acquire() en esa otra instancia. Si ese segundo hilo finalmente llama al release() en la primera instancia, tiene un interbloqueo.

He sustituido la sincronización en las instancias de semáforo individuales por sincronización en un solo objeto llamado LOCK. El hilo que ejecuta acquire() ha bloqueado el monitor de LOCK. Por lo tanto, este subproceso no se bloquea cuando llama al método release(). El método release() siempre terminará. Esto resuelve el punto muerto.

Answer 6

Los bloqueos suelen resolverse mediante un sistema de semáforo jerárquico. bloqueo de la muerte típica se parece a

Proceso A

getSemaphore('A'); 
getSemaphore('B'); 

Proceso B

getSemaphore('B'); 
getSemaphore('A'); 

Sólo por todos los procesos para seleccionar A antes de B. Esto se puede lograr mediante la escritura de su función getSemaphore para hacer cumplir la jerarquía con afirmaciones.

Para su caso específico, esto no resuelve el problema muy obviamente, pero puede extrapolar de esta idea.

Cree una cola de migración. Cuando un usuario quiere cambiar de habitación de su función podría ser:

ChangeRoom(person, from, to) 
{ 
    getSemaphore('room_queue', 3200); 
    enqueue(room_queue, Object(person, from, to)); 
    releaseSemaphore('room_queue'); 
} 

El "3200" es un descanso del semáforo. Si un proceso se interrumpe después de consultar con el semáforo, aún se bloqueará el sistema. Esto da un tiempo de espera de 1 hora. Puede establecerlo en un valor lógico de 1 minuto, 5 segundos según la estabilidad de su sistema. Entonces tienen un procesador de cola que sólo permite una transferencia a la vez con un semáforo no bloqueante

QueueProcessor() 
{ 
    getSemaphore('room_queue', 3200); 
    for (transition = dequeue(room_queue)) 
    { 
     if (getNonBlockingSemaphore(transition.to) 
     { 
      releaseSemaphore(transition.from); 
      getSemaphore(transition.to); 
     } 
     continue; 
    } 
    releaseSemaphore('room_queue'); 
    sleep(10); 
} 

El sueño mantiene la forma abrumadora proceso de cola de procesador. Ponlo en un control apropiado. También puede configurar interrupciones para extraer elementos de la cola solo cuando una sala tiene un espacio abierto o se agrega una transición. De esta forma, si una habitación está llena, no perderá tiempo tratando de entrar, pero todos tendrán al menos una oportunidad para entrar inmediatamente.

Esto fuerza una transición para obtener el semáforo de cola antes de que puedan obtener un semáforo de sala. Configuración de una jerarquía sin interbloqueo. Un usuario nunca abandonará la cola si una sala está llena, pero no bloqueará el sistema.