Вопрос по concurrency – Хороший пример livelock?

127

Я понимаю, что такое livelock, но мне было интересно, есть ли у кого-нибудь хороший пример на основе кода? И на основе кода, я делаюnot означают "два человека, пытающиеся пройти друг друга в коридоре". Если я прочитаю это снова, я потеряю свой обед.

Как насчет программной симуляции двух людей, пытающихся обойти друг друга в коридоре? 1800 INFORMATION
Связанная шутка для любопытных парней:codingarchitect.wordpress.com/2006/01/18/… Jorjon
Два человека пытаются пройти друг друга в коридоре:gist.github.com/deepankarb/d2dd6f21bc49902376e614d3746b8965 :п iceman
Странно уместно:seuss.wikia.com/wiki/The_Zax NotMe
Проклинаю тебя! Я потерял свой обед! Alex Miller

Ваш Ответ

10   ответов
1

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

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

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

для того чтобы это была живая блокировка, вам понадобится другой поток, чтобы получить эти блокировки в другом порядке. Если все темы используютtryLockAll() с замками вlocks в том же порядке нет живой блокировки.
0

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()
Ошибки: в use () печать не используется и, что более важно, флаг голодного не установлен в False.
2

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

когда муж и жена пытаются съесть суп, но между ними только одна ложка. Каждый из супругов слишком вежлив, и передаст ложку, если другой еще не ел.

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();
    }
}
Не должен ли он использоватьThread.join() скорее, чемThread.sleep()потому что он хочет подождать, пока супруг покушает?
Вам не нужно использоватьsynchronized  ключевое слово дляsetOwner метод, потому что чтение и запись являются атомарным действием для ссылочной переменной.
что мы должны сделать, чтобы преодолеть проблему livelock в этом конкретном примере?
getOwner метод должен быть синхронизирован, так как даже еслиsetOwner синхронизируется, это не гарантирует использование потокаgetOwner (или доступ к полюowner непосредственно) увидит изменения, сделанные другим потоком, выполняющимsetOwner, Это видео объясняет это очень тщательно:youtube.com/watch?v=WTVooKLLVT8
Doesn & APOS; тgetOwner метод должен быть синхронизирован? Из эффективной Java & quot;synchronization has no effect unless both read and write& Quot ;.
71

один известный пример - это код, который пытается обнаружить и обработать тупиковые ситуации. Если два потока обнаруживают взаимоблокировку и пытаются «отойти в сторону» друг для друга, не обращая внимания, они в конечном итоге застрянут в петле, всегда «отступая»; и никогда не удается двигаться вперед.

«Отойди в сторону» Я имею в виду, что они откроют замок и попытаются позволить другому получить его. Мы можем представить себе ситуацию с двумя потоками, которые делают это (псевдокод):

// 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, то нет возможности взаимоблокировки.

Отличный и содержательный пример.
Да, я понимаю это. Я ищу пример такого кода. Вопрос в том, что означает «отойти в сторону». значит и как получается такой сценарий. Alex Miller
Хотя это и не является стабильным живым замком, потому что они со временем, очевидно, вырвутся из него, я думаю, что он достаточно хорошо подходит под описание
Я понял, что это надуманный пример, но возможно ли, что это может привести к блокировке? Не было бы намного более вероятным, что в конечном итоге откроется окно, в котором одна функция может получить обе функции из-за несоответствий во времени, когда потоки могут запускаться вслух, и когда они запланированы.
4

е блокировки процессов в попытке исправить тупик SQL-сервера, при этом каждый процесс использует один и тот же алгоритм ожидания-повтора для повторной попытки. Несмотря на то, что мне повезло с выбором времени, я видел, как это происходило на отдельных машинах с похожими характеристиками производительности в ответ на сообщение, добавленное в тему EMS (например, сохранение обновления одного графа объектов более одного раза), и я не смог контролировать порядок блокировки.

Хорошее решение вthis В этом случае конкурирующие потребители должны были бы (не допускать повторной обработки как можно выше в цепочке, разбивая работу на несвязанные объекты).

Менее желательное (хорошо, грязное) решение состоит в том, чтобы заранее сломать неудачу во времени (вид различий в силе при обработке) или сломать ее после тупика, используя различные алгоритмы или некоторый элемент случайности. Это может по-прежнему иметь проблемы, поскольку возможно, что запрос на блокировку является «липким». для каждого процесса, и это занимает определенный минимум времени, не учитываемый при повторной попытке ожидания.

Еще одно решение (по крайней мере для SQL Server) состоит в том, чтобы попробовать другой уровень изоляции (например, снимок).

6

помеченного как принятый ответ, я попытался создать пример блокировки в реальном времени;

Оригинальная программа был написан мной в апреле 2012 года для изучения различных концепций многопоточности. На этот раз я изменил его, чтобы создать тупик, условия гонки, livelock и т. Д.

Итак, давайте сначала поймем формулировку проблемы;

Cookie Maker Problem

Есть несколько контейнеров для ингредиентов:ChocoPowederContainer, WheatPowderContainer. CookieMaker берет некоторое количество порошка из контейнеров для ингредиентов, чтобы испечьCookie, Если производитель печенья находит контейнер пустым, он проверяет другой контейнер, чтобы сэкономить время. И ждет покаFiller заполняет необходимый контейнер. EстьFiller который проверяет контейнер на регулярной основе и заполняет некоторое количество, если контейнер нуждается в этом.

Пожалуйста, проверьте полный код наGitHub;

Позвольте мне объяснить вам реализацию вкратце.

I start Filler as daemon thread. So it'll keep filling containers on regular interval. To fill a container first it locks the container -> check if it needs some powder -> fills it -> signal all makers who are waiting for it -> unlock container. I create CookieMaker and set that it can bake up to 8 cookies in parallel. And I start 8 threads to bake cookies. Each maker thread creates 2 callable sub-thread to take powder from containers. sub-thread takes a lock on a container and check if it has enough powder. If not, wait for some time. Once Filler fills the container, it takes the powder, and unlock the container. Now it completes other activities like: making mixture and baking etc.

Давайте посмотрим на код:

CookieMaker.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;
}

Все работает нормально, покаFiller заполняет контейнеры. Но если я забываю запустить наполнитель или наполнитель неожиданно уходит, дочерние потоки продолжают изменять свои состояния, чтобы позволить другому производителю пойти и проверить контейнер.

Я также создал демона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]

Вы заметите, что вложенные потоки изменяют свои состояния и ждут.

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

Когда один из них замечает, что другой голоден, он (она) должен освободить ложку и дождаться другого уведомления, чтобы произошла блокировка.

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

Похожие вопросы