Семафорский тупик

Question

У меня проблема с использованием семафора. Написание кода, где 4 комнаты и некоторые посетители. В каждом номере есть определенная кепка для количества посетителей, которые они могут держать. Таким образом, вход в полную комнату вызовет ожидание(). Посетители не должны покидать комнату, прежде чем они смогут войти в другую, поэтому они всегда находятся в комнате.

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

Тупик появляется, когда 2 человека пытаются войти в комнаты друг друга. Также по какой-то причине счет placesLeft не подходит.

Итак, что мне делать?

EDIT:

были заняты чем-то другим, возрождая вопрос. Проблема не возникает из-за того, что комнаты заполняются, замок возникает, когда человек1 из комнаты 1 хочет войти в комнату2 и то же время человек2 из комнаты2 хочет войти в комнату1. Как я понимаю, что-то делать с синхронизацией? Они застревают до выпуска, поэтому релиз не вызывается. Поскольку я понимаю, что одна комната обвиняет и освобождает, нельзя назвать то же самое время. Так что основной выпуск семафора номер1 нельзя назвать cuz, в то же время вызывается accuire, то же самое для room2? Я новичок-кодер и синхронизация еще не совсем понятны. Удаление синхронизаций с того или другого не работает (также неверно).

Answer 1

Добавить список текущих посетителей в Room, чтобы вы могли зарегистрироваться в acquire при условии, что входящий посетитель прибывает из комнаты, в которой находится один из пассажиров этой комнаты. Вам также нужно будет добавить комнату, которую посетитель ждет, чтобы войти в 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(); 
} 

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

Answer 2

Вместо того чтобы реализовать свои собственные, как насчет использования java.util.concurrent.Semaphore, который встроен в стандартную библиотеку Java?

В пакете java.util.concurrent имеется большое tutorial покрытие Семафоров и множество других полезных механизмов синхронизации, которые он предоставляет.

Answer 3

Чтобы ответить на ваш вопрос: «Что делать?», Если вы обнаружите тупик, переместите одного из запертых посетителей в любую комнату с пространством. Затем переместите его в комнату, которую он действительно хочет. Это в основном позволяет обменять, не нарушая ни одно из приведенных ниже правил.

1. Номера никогда не должны содержать более посетителей X
2. Посетитель всегда ровно в одной комнате
3. только один посетитель может изменить номера в то время, (которые на самом деле суть проблемы)

Имейте в виду, что существует около миллиона стратегий блокировки семафоров ...

Answer 4

Тупик возникает, когда на графике зависимостей существует цикл. Когда 2 человека пытаются войти в комнаты друг друга, это, очевидно, цикл, и взаимоблокировка является естественным следствием.

Однако вы хотите относиться к циклам по-другому: когда цикл происходит, люди все перемещаются по циклу (может быть более двух человек, обменивающихся комнатами).

Итак, вы должны сначала определить, сформирован ли цикл, а затем изменить местоположение посетителей.

Answer 5

Попробуйте это:

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

старого код синхронизированного на отдельных экземплярах Семафора. Очень сложно предотвратить взаимоблокировки, потому что метод acquire() одного экземпляра вызывает release() другого экземпляра. Затем вызов release() блокирует, если другой поток в настоящее время выполняет метод acquire() в этом другом экземпляре. Если этот второй поток наконец вызовет release() в первом случае, у вас есть тупик.

Я заменил синхронизацию на отдельных экземплярах Semaphore синхронизацией на одном объекте с именем LOCK. Нить, которая выполняет acquire(), заблокировала монитор LOCK. Поэтому этот поток не блокируется, когда он вызывает метод release(). Таким образом, метод release() всегда заканчивается. Это решает тупик.

Answer 6

Тупиковые замки обычно разрешаются иерархической системой семафоров. Типичная мертвая блокировка выглядит

процесс А

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

Процесс B

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

Просто для всех процессов, чтобы выбрать, прежде чем B. Это может быть достигнуто путем написания getSemaphore функции для обеспечения иерархии с утверждениями.

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

Создайте очередь миграции. Когда пользователь хочет изменить номера ваша функция может выглядеть следующим образом:

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

«3200» является семафор тайм-аут. Если процесс прерывается после склеивания семафора, он все равно затормозит систему. Это дает 1 час таймаута. Вы можете установить его на логическое значение 1 мин, 5 секунд на основе стабильности вашей системы. Затем есть процессор очереди, что позволяет только одну передачи одновременно с неблокирующим семафором

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

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

Это приводит к переходу для получения семафора очереди, прежде чем они смогут получить семафор в комнате. Настройка безударной иерархии. Пользователь никогда не покинет очередь, если комната заполнена, но она не будет блокировать систему.