как гарантировать отсутствие тупика

Question

Я застрял на одном вопросе в интервью.

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

Я знаю, что избежать тупика нелегко, поэтому я застрял. Кто-нибудь может дать подсказку.

Спасибо!

Answer 1

В описании немного не хватает, но если вы наложите порядок блокировки (например, если блокировки A и B, никогда не блокируйте B, если вы уже не заблокировали A, и никогда не отпускаете A, пока B заблокирован), тогда тупик выиграл не происходит.

Answer 2

Известны алгоритмы предотвращения тупиковых ситуаций , которые могут обнаружить, что может возникнуть тупик, и избежать попадания системы в это состояние. Например, Алгоритм банкира .

Answer 3

Ответ, который искали ваши интервьюеры, - это, вероятно, WaitForMultipleObjects (). Это Windows API, который блокирует оба (или более) ресурса одновременно.

Answer 4

Порядок блокировки предпочтительнее тайм-аутов / обнаружения взаимоблокировок, но иногда необходимы тайм-ауты, особенно если вы не контролируете все компоненты в системе: отсюда время ожидания / обнаружение взаимоблокировок в базах данных Если бы все вызывающие абоненты были достаточно умны, взаимоблокировки никогда бы не возникли, но обычно не все вызывающие абоненты достаточно умны.

Answer 5

С одной блокировкой невозможно заблокироваться, если только один не откажется снять блокировку - в этом случае ожидающий поток называется голодным. Для нескольких блокировок они должны быть разблокированы в обратном порядке, в котором они были получены, и оба потока должны согласовать порядок.

Чего вы пытаетесь избежать, так это ситуации:

A имеет блокировку 1, ожидающую блокировки 2

B имеет блокировку 2, ожидающую блокировки 1

Answer 6

Это две стандартные причины тупика:

1. Блокировка блокировки заказов:
   Это происходит, когда два потока пытаются получить одинаковые блокировки в разном порядке. Последовательность будет примерно такой:
   я) Нить получает блокировку влево
   ii) Нить B получает блокировку ВПРАВО
   iii) Поток A пытается заблокировать ПРАВО
   iv) Поток B пытается заблокировать ВЛЕВО
   ---> Оба будут ждать вечно

   РЕШЕНИЕ: проверьте код и убедитесь, что нет зависимости циклической блокировки. Если потоки будут запрашивать блокировки в том же порядке, тупиковая ситуация никогда не произойдет.

2. Блокировка динамического блокировки: Когда блокировки определены во время выполнения и у вас нет контроля, сценарий, подобный описанному выше, может все еще вызывать взаимные блокировки. Например -

   void transferFund( Account A, Account B, Amount x)
   {
       synchronized(A)
       { 
           synchronized(B)
           {
             // do transfer update balance
           }
       }
   }                                                                                  
   

   Последовательность для тупика будет: Поток 1 - трансфертный фонд (А1, В1, 10); Тема 2 - трансфертный фонд (B1, A1, 20);

   Решение: чтобы избежать этих взаимных блокировок, нужно использовать логику, чтобы потоки всегда использовали одинаковый порядок получения блокировок. Например -

   if( A1.hashCode()  < B1.hashCode())
     { Lock A1 then Lock B1 }
   else
     { Lock B1 then Lock A1 }
   

ПРИМЕЧАНИЕ: Вы не можете избежать взаимоблокировок, когда вы вызываете инопланетные методы, и вы не можете контролировать, как эти инопланетные методы вызывают блокировки: (

Answer 7

Большая часть работы по параллельному / параллельному программированию сосредоточена на конструкциях без блокировок. Не точный ответ на ваш вопрос, но, как уже упоминал Эндрю в этой теме, лучший способ избежать взаимоблокировок - вообще не блокировать. Такого мнения придерживаются многие очень умные люди, работающие над вопросами параллелизма.