Хороший пример livelock?
Я понимаю, что такое livelock, но мне было интересно, есть ли у кого-нибудь хороший пример на основе кода? И под кодовой базой я не подразумеваю "двух людей, пытающихся пройти друг друга в коридоре". Если я прочитаю это снова, я потеряю свой обед.
12 ответов
Вот очень простой пример Java Livelock, где муж и жена пытаются съесть суп, но между ними только одна ложка. Каждый из супругов слишком вежлив, и передаст ложку, если другой еще не ел.
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();
}
}
Если оставить в стороне комментарии Flippant, один известный пример - это код, который пытается обнаружить и обработать тупиковые ситуации. Если два потока обнаружат взаимоблокировку и попытаются "отойти в сторону" друг от друга, они будут беззаботно зацикливаться на петле, всегда "отстраняясь" и никогда не смогут продвинуться вперед.
Под "шагом в сторону" я подразумеваю, что они освободят замок и попытаются позволить другому получить его. Мы можем представить себе ситуацию с двумя потоками, которые делают это (псевдокод):
// thread 1
getLocks12(lock1, lock2)
{
lock1.lock();
while (lock2.locked())
{
// attempt to step aside for the other thread
lock1.unlock();
wait();
lock1.lock();
}
lock2.lock();
}
// thread 2
getLocks21(lock1, lock2)
{
lock2.lock();
while (lock1.locked())
{
// attempt to step aside for the other thread
lock2.unlock();
wait();
lock2.lock();
}
lock1.lock();
}
Если не принимать во внимание условия гонки, то здесь мы имеем ситуацию, когда оба потока, если они вступят в одно и то же время, в конечном итоге будут работать во внутреннем цикле без продолжения. Очевидно, это упрощенный пример. Наивным решением было бы поместить некоторую случайность в количество времени, которое ожидают потоки.
Правильное решение - всегда соблюдать иерархию блокировки. Выберите заказ, в котором вы приобретаете замки и придерживайтесь этого. Например, если оба потока всегда получают lock1 до lock2, то нет возможности взаимоблокировки.
Поскольку нет ответа, помеченного как принятый, я попытался создать пример блокировки в реальном времени;
Оригинальная программа была написана мной в апреле 2012 года для изучения различных концепций многопоточности. На этот раз я изменил его, чтобы создать тупик, состояние гонки, live lock и т. Д.
Итак, давайте сначала разберемся с постановкой задачи;
Проблема Создателя Печенья
Есть несколько контейнеров с ингредиентами: ChocoPowederContainer, WheatPowderContainer. Cookie Maker берет некоторое количество порошка из контейнеров с ингредиентами, чтобы испечь Cookie. Если производитель печенья находит контейнер пустым, он проверяет другой контейнер, чтобы сэкономить время. И ждет, пока заполнитель не заполнит необходимый контейнер. Есть Наполнитель, который проверяет контейнер на регулярной основе и заполняет некоторое количество, если контейнер нуждается в этом.
Пожалуйста, проверьте полный код на GitHub;
Позвольте мне объяснить вам реализацию вкратце.
- Я запускаю Filler как поток демона. Таким образом, он будет продолжать заполнять контейнеры на регулярной основе. Чтобы сначала наполнить контейнер, он запирает контейнер -> проверяет, нужен ли ему порошок -> заполняет его -> сигнализирует всем производителям, которые его ждут -> разблокировать контейнер.
- Я создаю Cookie Maker и устанавливаю, что он может одновременно выпекать до 8 файлов cookie. И я начинаю 8 потоков, чтобы испечь печенье.
- Каждая производственная нить создает 2 вызываемые вспомогательные нити для извлечения порошка из контейнеров.
- дополнительная нить захватывает контейнер и проверяет, достаточно ли порошка. Если нет, подождите некоторое время. Как только наполнитель заполнит контейнер, он заберет порошок и разблокирует контейнер.
- Теперь он выполняет другие действия, такие как: приготовление смеси, выпечка и т. Д.
Давайте посмотрим на код:
Cookie Maker.java
private Integer getMaterial(final Ingredient ingredient) throws Exception{
:
container.lock();
while (!container.getIngredient(quantity)) {
container.empty.await(1000, TimeUnit.MILLISECONDS);
//Thread.sleep(500); //For deadlock
}
container.unlock();
:
}
IngredientContainer.java
public boolean getIngredient(int n) throws Exception {
:
lock();
if (quantityHeld >= n) {
TimeUnit.SECONDS.sleep(2);
quantityHeld -= n;
unlock();
return true;
}
unlock();
return false;
}
Все работает нормально, пока наполнитель не заполнит контейнеры. Но если я забываю запустить наполнитель или наполнитель неожиданно уходит, дочерние потоки продолжают изменять свои состояния, чтобы позволить другому производителю пойти и проверить контейнер.
Я также создал демон ThreadTracer, который следит за состоянием потоков и взаимными блокировками. Это вывод из консоли;
2016-09-12 21:31:45.065 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:RUNNABLE, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]
2016-09-12 21:31:45.065 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]
WheatPowder Container has 0 only.
2016-09-12 21:31:45.082 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:RUNNABLE]
2016-09-12 21:31:45.082 :: [Maker_0:WAITING, Maker_1:WAITING, Maker_2:WAITING, Maker_3:WAITING, Maker_4:WAITING, Maker_5:WAITING, Maker_6:WAITING, Maker_7:WAITING, pool-7-thread-1:TIMED_WAITING, pool-7-thread-2:TIMED_WAITING, pool-8-thread-1:TIMED_WAITING, pool-8-thread-2:TIMED_WAITING, pool-6-thread-1:TIMED_WAITING, pool-6-thread-2:TIMED_WAITING, pool-5-thread-1:TIMED_WAITING, pool-5-thread-2:TIMED_WAITING, pool-1-thread-1:TIMED_WAITING, pool-3-thread-1:TIMED_WAITING, pool-2-thread-1:TIMED_WAITING, pool-1-thread-2:TIMED_WAITING, pool-4-thread-1:TIMED_WAITING, pool-4-thread-2:TIMED_WAITING, pool-3-thread-2:TIMED_WAITING, pool-2-thread-2:TIMED_WAITING]
Вы заметите, что субпотоки меняют свои состояния и ждут.
Реальный (хотя и без точного кода) пример - это две конкурирующие живые блокировки процессов в попытке исправить тупик SQL-сервера, причем каждый процесс использует один и тот же алгоритм ожидания-повтора для повторных попыток. Хотя это удача времени, я видел, как это происходило на отдельных машинах с похожими характеристиками производительности в ответ на сообщение, добавленное в тему EMS (например, сохранение обновления одного графа объектов более одного раза) и отсутствие возможности контролировать порядок блокировки.
Хорошим решением в этом случае было бы иметь конкурирующих потребителей (не допускать повторной обработки как можно выше в цепочке, разделяя работу на несвязанные объекты).
Менее желательное (хорошо, грязное) решение состоит в том, чтобы заранее сломать неудачу во времени (вид различий в силе при обработке) или сломать ее после тупика, используя различные алгоритмы или некоторый элемент случайности. Это может по-прежнему иметь проблемы, поскольку возможно, что порядок получения блокировок "залипает" для каждого процесса, и это занимает определенный минимум времени, не учитываемый при повторной попытке ожидания.
Еще одно решение (по крайней мере, для SQL Server) состоит в том, чтобы попробовать другой уровень изоляции (например, снимок).
C# версия кода Джелборна:
using System;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;
namespace LiveLockExample
{
static class Program
{
public static void Main(string[] args)
{
var husband = new Diner("Bob");
var wife = new Diner("Alice");
var s = new Spoon(husband);
Task.WaitAll(
Task.Run(() => husband.EatWith(s, wife)),
Task.Run(() => wife.EatWith(s, husband))
);
}
public class Spoon
{
public Spoon(Diner diner)
{
Owner = diner;
}
public Diner Owner { get; private set; }
[MethodImpl(MethodImplOptions.Synchronized)]
public void SetOwner(Diner d) { Owner = d; }
[MethodImpl(MethodImplOptions.Synchronized)]
public void Use()
{
Console.WriteLine("{0} has eaten!", Owner.Name);
}
}
public class Diner
{
public Diner(string n)
{
Name = n;
IsHungry = true;
}
public string Name { get; private set; }
private bool IsHungry { get; set; }
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 (ThreadInterruptedException e)
{
}
continue;
}
// If spouse is hungry, insist upon passing the spoon.
if (spouse.IsHungry)
{
Console.WriteLine("{0}: You eat first my darling {1}!", Name, spouse.Name);
spoon.SetOwner(spouse);
continue;
}
// Spouse wasn't hungry, so finally eat
spoon.Use();
IsHungry = false;
Console.WriteLine("{0}: I am stuffed, my darling {1}!", Name, spouse.Name);
spoon.SetOwner(spouse);
}
}
}
}
}
Рассмотрим систему UNIX, имеющую 50 слотов процессов.
Выполняется десять программ, каждая из которых должна создать 6 (под) процессов.
После того, как каждый процесс создал 4 процесса, 10 исходных процессов и 40 новых процессов исчерпали таблицу. Каждый из 10 исходных процессов теперь находится в бесконечном цикле, разветвляющемся и завершающемся неудачей, что вполне соответствует ситуации livelock. Вероятность того, что это произойдет, очень мала, но это может случиться.
Я кодировал пример 2 человек, проходящих по коридору. Две нити будут избегать друг друга, как только они поймут, что их направления совпадают.
public class LiveLock {
public static void main(String[] args) throws InterruptedException {
Object left = new Object();
Object right = new Object();
Pedestrian one = new Pedestrian(left, right, 0); //one's left is one's left
Pedestrian two = new Pedestrian(right, left, 1); //one's left is two's right, so have to swap order
one.setOther(two);
two.setOther(one);
one.start();
two.start();
}
}
class Pedestrian extends Thread {
private Object l;
private Object r;
private Pedestrian other;
private Object current;
Pedestrian (Object left, Object right, int firstDirection) {
l = left;
r = right;
if (firstDirection==0) {
current = l;
}
else {
current = r;
}
}
void setOther(Pedestrian otherP) {
other = otherP;
}
Object getDirection() {
return current;
}
Object getOppositeDirection() {
if (current.equals(l)) {
return r;
}
else {
return l;
}
}
void switchDirection() throws InterruptedException {
Thread.sleep(100);
current = getOppositeDirection();
System.out.println(Thread.currentThread().getName() + " is stepping aside.");
}
public void run() {
while (getDirection().equals(other.getDirection())) {
try {
switchDirection();
Thread.sleep(100);
} catch (InterruptedException e) {}
}
}
}
Python-версия кода Джелборна:
import threading
import time
lock = threading.Lock()
class Spoon:
def __init__(self, diner):
self.owner = diner
def setOwner(self, diner):
with lock:
self.owner = diner
def use(self):
with lock:
"{0} has eaten".format(self.owner)
class Diner:
def __init__(self, name):
self.name = name
self.hungry = True
def eatsWith(self, spoon, spouse):
while(self.hungry):
if self != spoon.owner:
time.sleep(1) # blocks thread, not process
continue
if spouse.hungry:
print "{0}: you eat first, {1}".format(self.name, spouse.name)
spoon.setOwner(spouse)
continue
# Spouse was not hungry, eat
spoon.use()
print "{0}: I'm stuffed, {1}".format(self.name, spouse.name)
spoon.setOwner(spouse)
def main():
husband = Diner("Bob")
wife = Diner("Alice")
spoon = Spoon(husband)
t0 = threading.Thread(target=husband.eatsWith, args=(spoon, wife))
t1 = threading.Thread(target=wife.eatsWith, args=(spoon, husband))
t0.start()
t1.start()
t0.join()
t1.join()
if __name__ == "__main__":
main()
Одним из примеров здесь может быть использование синхронизированного tryLock для получения более чем одной блокировки, и если вы не можете получить их все, откатитесь и попробуйте снова.
boolean tryLockAll(Collection<Lock> locks) {
boolean grabbedAllLocks = false;
for(int i=0; i<locks.size(); i++) {
Lock lock = locks.get(i);
if(!lock.tryLock(5, TimeUnit.SECONDS)) {
grabbedAllLocks = false;
// undo the locks I already took in reverse order
for(int j=i-1; j >= 0; j--) {
lock.unlock();
}
}
}
}
Я мог предположить, что такой код будет проблематичным, поскольку у вас много потоков, сталкивающихся и ожидающих получения набора блокировок. Но я не уверен, что это очень убедительный пример для меня.
Я изменяю ответ @jelbourn. Когда один из них замечает, что другой голоден, он (она) должен освободить ложку и дождаться другого уведомления, чтобы произошла блокировка.
public class LiveLock {
static class Spoon {
Diner owner;
public String getOwnerName() {
return owner.getName();
}
public void setOwner(Diner diner) {
this.owner = diner;
}
public Spoon(Diner diner) {
this.owner = diner;
}
public void use() {
System.out.println(owner.getName() + " use this spoon and finish eat.");
}
}
static class Diner {
public Diner(boolean isHungry, String name) {
this.isHungry = isHungry;
this.name = name;
}
private boolean isHungry;
private String name;
public String getName() {
return name;
}
public void eatWith(Diner spouse, Spoon sharedSpoon) {
try {
synchronized (sharedSpoon) {
while (isHungry) {
while (!sharedSpoon.getOwnerName().equals(name)) {
sharedSpoon.wait();
//System.out.println("sharedSpoon belongs to" + sharedSpoon.getOwnerName())
}
if (spouse.isHungry) {
System.out.println(spouse.getName() + "is hungry,I should give it to him(her).");
sharedSpoon.setOwner(spouse);
sharedSpoon.notifyAll();
} else {
sharedSpoon.use();
sharedSpoon.setOwner(spouse);
isHungry = false;
}
Thread.sleep(500);
}
}
} catch (InterruptedException e) {
System.out.println(name + " is interrupted.");
}
}
}
public static void main(String[] args) {
final Diner husband = new Diner(true, "husband");
final Diner wife = new Diner(true, "wife");
final Spoon sharedSpoon = new Spoon(wife);
Thread h = new Thread() {
@Override
public void run() {
husband.eatWith(wife, sharedSpoon);
}
};
h.start();
Thread w = new Thread() {
@Override
public void run() {
wife.eatWith(husband, sharedSpoon);
}
};
w.start();
try {
Thread.sleep(10000);
} catch (InterruptedException e) {
e.printStackTrace();
}
h.interrupt();
w.interrupt();
try {
h.join();
w.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Пример:
Тема 1
top:
lock(L1);
if (try_lock(L2) != 0) {
unlock(L1);
goto top;
Тема 2
top:
lock(L2);
if (try_lock(L1) != 0) {
unlock(L2);
goto top;
Единственная разница в том, что поток 1 и поток 2 пытаются получить блокировки в другом порядке. Livelock может происходить следующим образом:
Поток 1 запускается, получает L1, затем происходит переключение контекста. Поток 2 запускается, получает L2, затем происходит еще одно переключение контекста. Поток 1 работает и не может получить L2, но перед освобождением L1 происходит переключение контекста. Поток 2 работает и не может получить L1, освобождает L2, и происходит переключение контекста. Поток 1 выпускает L1, и теперь мы практически вернулись в начальное состояние, и теоретически эти шаги могут повторяться вечно.
package concurrently.deadlock;
import static java.lang.System.out;
/* This is an example of livelock */
public class Dinner {
public static void main(String[] args) {
Spoon spoon = new Spoon();
Dish dish = new Dish();
new Thread(new Husband(spoon, dish)).start();
new Thread(new Wife(spoon, dish)).start();
}
}
class Spoon {
boolean isLocked;
}
class Dish {
boolean isLocked;
}
class Husband implements Runnable {
Spoon spoon;
Dish dish;
Husband(Spoon spoon, Dish dish) {
this.spoon = spoon;
this.dish = dish;
}
@Override
public void run() {
while (true) {
synchronized (spoon) {
spoon.isLocked = true;
out.println("husband get spoon");
try { Thread.sleep(2000); } catch (InterruptedException e) {}
if (dish.isLocked == true) {
spoon.isLocked = false; // give away spoon
out.println("husband pass away spoon");
continue;
}
synchronized (dish) {
dish.isLocked = true;
out.println("Husband is eating!");
}
dish.isLocked = false;
}
spoon.isLocked = false;
}
}
}
class Wife implements Runnable {
Spoon spoon;
Dish dish;
Wife(Spoon spoon, Dish dish) {
this.spoon = spoon;
this.dish = dish;
}
@Override
public void run() {
while (true) {
synchronized (dish) {
dish.isLocked = true;
out.println("wife get dish");
try { Thread.sleep(2000); } catch (InterruptedException e) {}
if (spoon.isLocked == true) {
dish.isLocked = false; // give away dish
out.println("wife pass away dish");
continue;
}
synchronized (spoon) {
spoon.isLocked = true;
out.println("Wife is eating!");
}
spoon.isLocked = false;
}
dish.isLocked = false;
}
}
}