Я понимаю, что такое livelock, но мне было интересно, есть ли у кого-нибудь хороший пример этого кода? И под «основанным на коде» я не имею в виду «двух людей, пытающихся обойти друг друга в коридоре». Если я прочитаю это снова, то потеряю обед.
concurrency
livelock
Алекс Миллер
источник
источник
Ответы:
Вот очень простой пример livelock на Java, когда муж и жена пытаются съесть суп, но между ними остается только одна ложка. Каждый из супругов слишком вежлив и передаст ложку, если другой еще не ел.
public class Livelock { static class Spoon { private Diner owner; public Spoon(Diner d) { owner = d; } public Diner getOwner() { return owner; } public synchronized void setOwner(Diner d) { owner = d; } public synchronized void use() { System.out.printf("%s has eaten!", owner.name); } } static class Diner { private String name; private boolean isHungry; public Diner(String n) { name = n; isHungry = true; } public String getName() { return name; } public boolean isHungry() { return isHungry; } public void eatWith(Spoon spoon, Diner spouse) { while (isHungry) { // Don't have the spoon, so wait patiently for spouse. if (spoon.owner != this) { try { Thread.sleep(1); } catch(InterruptedException e) { continue; } continue; } // If spouse is hungry, insist upon passing the spoon. if (spouse.isHungry()) { System.out.printf( "%s: You eat first my darling %s!%n", name, spouse.getName()); spoon.setOwner(spouse); continue; } // Spouse wasn't hungry, so finally eat spoon.use(); isHungry = false; System.out.printf( "%s: I am stuffed, my darling %s!%n", name, spouse.getName()); spoon.setOwner(spouse); } } } public static void main(String[] args) { final Diner husband = new Diner("Bob"); final Diner wife = new Diner("Alice"); final Spoon s = new Spoon(husband); new Thread(new Runnable() { public void run() { husband.eatWith(s, wife); } }).start(); new Thread(new Runnable() { public void run() { wife.eatWith(s, husband); } }).start(); } }
источник
getOwner
метод тоже не нужно синхронизировать? Начиная с Effective Java, « синхронизация не имеет эффекта, если и чтение, и запись ».Thread.join()
вместоThread.sleep()
, потому что он хочет дождаться, пока супруга поест?getOwner
Метод должен быть синхронизированы , поскольку даже еслиsetOwner
синхронизируется, это не гарантирует нить с помощьюgetOwner
(или доступ полеowner
непосредственно) будут видеть изменения , сделанные другим потоком , выполняющегоsetOwner
. В этом видео это очень подробно объясняется: youtube.com/watch?v=WTVooKLLVT8synchronized
ключевое слово дляsetOwner
метода, потому что чтение и запись являются атомарными действиями для ссылочной переменной.Если оставить в стороне ошибочные комментарии, известно, что один из примеров - это код, который пытается обнаруживать и обрабатывать ситуации взаимоблокировки. Если два потока обнаруживают взаимоблокировку и пытаются «отойти в сторону» друг для друга, они без особой осторожности застрянут в цикле, который всегда «отступает в сторону» и никогда не сможет двигаться вперед.
Под «отойти в сторону» я имею в виду, что они снимут блокировку и попытаются позволить другому заполучить ее. Мы можем представить себе ситуацию, когда это делают два потока (псевдокод):
Помимо условий гонки, здесь мы имеем ситуацию, когда оба потока, если они входят одновременно, в конечном итоге будут работать во внутреннем цикле без продолжения. Очевидно, это упрощенный пример. Наивным решением было бы внести некоторую случайность в количество времени, в течение которого потоки будут ждать.
Правильное решение - всегда соблюдать иерархию блокировок . Выберите порядок, в котором вы приобретаете замки, и придерживайтесь его. Например, если оба потока всегда получают lock1 перед lock2, то нет возможности взаимоблокировки.
источник
Поскольку нет ответа, помеченного как принятый, я попытался создать пример живой блокировки;
Оригинальная программа была написана мной в апреле 2012 года для изучения различных концепций многопоточности. На этот раз я изменил его, чтобы создать тупик, состояние гонки, живую блокировку и т. Д.
Итак, давайте сначала разберемся с постановкой проблемы;
Проблема с создателем файлов cookie
Есть несколько контейнеров для ингредиентов: ChocoPowederContainer , WheatPowderContainer . CookieMaker берет некоторое количество порошка из контейнеров для ингредиентов, чтобы испечь печенье . Если производитель файлов cookie обнаруживает, что контейнер пуст, он проверяет наличие другого контейнера, чтобы сэкономить время. И ждет, пока Filler заполнит необходимый контейнер. Есть наполнитель, который регулярно проверяет контейнер и наполняет некоторое количество, если это необходимо контейнеру.
Пожалуйста, проверьте полный код на github ;
Позвольте мне вкратце объяснить вам реализацию.
Заглянем в код:
CookieMaker.java
IngredientContainer.java
Все идет нормально, пока Filler не заполнит контейнеры. Но если я забываю запустить наполнитель или наполнитель неожиданно уходит в отпуск, подпотоки продолжают менять свое состояние, позволяя другому производителю пойти и проверить контейнер.
Я также создал демон ThreadTracer, который следит за состояниями потоков и взаимоблокировками. Это вывод из консоли;
Вы заметите, что подпотоки меняют свое состояние и ожидают.
источник
Реальный (хотя и без точного кода) пример - это два конкурирующих процесса с динамической блокировкой в попытке исправить тупик SQL-сервера, причем каждый процесс использует один и тот же алгоритм ожидания-повтора для повторной попытки. Хотя это удача по времени, я видел, что это происходило на разных машинах с аналогичными характеристиками производительности в ответ на сообщение, добавленное в тему EMS (например, сохранение обновления одного графа объекта более одного раза), и невозможность управления порядок блокировки.
Хорошим решением в этом случае было бы наличие конкурирующих потребителей (предотвращение дублирования обработки как можно выше в цепочке путем разделения работы на несвязанные объекты).
Менее желательное (хорошо, грязный хак) решение - заранее избавиться от временных неудач (разницы сил в обработке) или сломать их после тупика, используя другие алгоритмы или какой-то элемент случайности. Это все еще может иметь проблемы, потому что возможно, что порядок снятия блокировки является «липким» для каждого процесса, и это занимает определенный минимум времени, не учтенный в ожидании-повторении.
Еще одно решение (по крайней мере, для SQL Server) - попробовать другой уровень изоляции (например, моментальный снимок).
источник
Я закодировал пример прохождения 2 человек по коридору. Две нити будут избегать друг друга, как только поймут, что их направления совпадают.
источник
C # версия кода jelbourn:
источник
Одним из примеров здесь может быть использование временной блокировки tryLock для получения нескольких блокировок, и если вы не можете получить их все, отступите и повторите попытку.
Я могу представить, что такой код будет проблематичным, поскольку у вас много потоков, которые сталкиваются и ожидают получения набора блокировок. Но я не уверен, что этот простой пример мне подходит.
источник
tryLockAll()
блокировки вlocks
одном и том же порядке, живой блокировки нет.Версия кода jelbourn для Python:
источник
Я изменяю ответ @jelbourn. Когда один из них замечает, что другой голоден, он (она) должен отпустить ложку и дождаться другого уведомления, чтобы произошла блокировка.
источник
источник