Rozumiem, co to jest livelock, ale zastanawiałem się, czy ktoś ma dobry przykład oparty na kodzie? I kodem oparte, ja nie znaczy „dwie osoby próbują ominąć siebie w korytarzu”. Jeśli jeszcze raz to przeczytam, stracę lunch.
Rozumiem, co to jest livelock, ale zastanawiałem się, czy ktoś ma dobry przykład oparty na kodzie? I kodem oparte, ja nie znaczy „dwie osoby próbują ominąć siebie w korytarzu”. Jeśli jeszcze raz to przeczytam, stracę lunch.
Odpowiedzi:
Oto bardzo prosty przykład livelocka w Javie, w którym mąż i żona próbują zjeść zupę, ale mają między sobą tylko jedną łyżkę. Każdy z małżonków jest zbyt uprzejmy i podaje łyżkę, jeśli drugi jeszcze nie jadł.
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
metoda również nie musi być synchronizowana? Z efektywnej Java „ synchronizacja nie ma żadnego efektu, chyba że zarówno odczyt, jak i zapis ”.
Thread.join()
raczej używać niż Thread.sleep()
, ponieważ chce poczekać, aż małżonek zacznie jeść?
getOwner
Metoda musi być zsynchronizowane, ponieważ nawet jeśli setOwner
jest zsynchronizowany, to nie gwarantuje nić korzystania getOwner
(lub uzyskiwania dostępu do pola owner
bezpośrednio) będzie zobaczyć zmiany dokonane przez innego wątku wykonującego setOwner
. Ten film wyjaśnia to bardzo dokładnie: youtube.com/watch?v=WTVooKLLVT8
synchronized
słowa kluczowego dla setOwner
metody, ponieważ czytanie i pisanie jest niepodzielną akcją dla zmiennej referencyjnej.
Odkładając na bok niepoważne komentarze, jednym z przykładów, o którym wiadomo, że pojawia się, jest kod, który próbuje wykryć i poradzić sobie z sytuacjami zakleszczenia. Jeśli dwa wątki wykryją zakleszczenie i spróbują „odsunąć się” dla siebie nawzajem, bez ostrzeżenia skończą z utknięciem w pętli, zawsze „odsuwając się na bok” i nigdy nie udając się ruszyć do przodu.
Przez „odsunięcie się” mam na myśli, że zwolniliby blokadę i spróbowaliby pozwolić drugiemu go zdobyć. Możemy sobie wyobrazić sytuację z dwoma wątkami robiącymi to (pseudokod):
// 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();
}
Pomijając warunki wyścigu, mamy tutaj sytuację, w której oba wątki, jeśli wejdą w tym samym czasie, zakończą bieg w wewnętrznej pętli bez kontynuowania. Oczywiście jest to uproszczony przykład. Naiwnym rozwiązaniem byłoby wprowadzenie pewnego rodzaju przypadkowości w czasie oczekiwania wątków.
Właściwym rozwiązaniem jest zawsze przestrzeganie hierarchii blokad . Wybierz kolejność, w której zdobędziesz zamki i trzymaj się tego. Na przykład, jeśli oba wątki zawsze uzyskują lock1 przed lock2, nie ma możliwości zakleszczenia.
Ponieważ nie ma odpowiedzi oznaczonej jako zaakceptowana, próbowałem utworzyć przykład blokady na żywo;
Oryginalny program został napisany przeze mnie w kwietniu 2012 roku, aby nauczyć się różnych koncepcji wielowątkowości. Tym razem zmodyfikowałem go, aby utworzyć zakleszczenie, stan wyścigu, blokadę żywą itp.
Więc najpierw zrozummy stwierdzenie problemu;
Problem z twórcą plików cookie
Jest kilka pojemników na składniki: ChocoPowederContainer , WheatPowderContainer . CookieMaker wymaga pewnej ilości proszku z pojemników składników upiec Cookie . Jeśli producent ciasteczek stwierdzi, że pojemnik jest pusty, szuka innego pojemnika, aby zaoszczędzić czas. I czeka, aż Filler wypełni wymagany pojemnik. Jest wypełniacz który regularnie sprawdza pojemnik i uzupełnia pewną ilość, jeśli pojemnik tego potrzebuje.
Sprawdź cały kod na github ;
Pozwólcie, że krótko wyjaśnię wdrożenie.
Spójrzmy na kod:
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;
}
Wszystko działa dobrze do Fillera nie napełni pojemników. Ale jeśli zapomnę uruchomić wypełniacz lub wypełniacz nieoczekiwanie opuścił, wątki podrzędne zmieniają swoje stany, aby umożliwić innemu producentowi przejście i sprawdzenie pojemnika.
Stworzyłem również demona ThreadTracer, który śledzi stany wątków i zakleszczenia. To jest wyjście z konsoli;
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]
Zauważysz, że pod-wątki i zmieniają się ich stany i czekają.
Rzeczywisty (aczkolwiek bez dokładnego kodu) przykład to dwa konkurujące ze sobą procesy blokujące na żywo w celu skorygowania zakleszczenia serwera SQL, przy czym każdy proces używa tego samego algorytmu oczekiwania na ponowienie podczas ponawiania. Chociaż jest to szczęście związane z synchronizacją, widziałem, że dzieje się to na oddzielnych maszynach o podobnej charakterystyce wydajności w odpowiedzi na wiadomość dodaną do tematu EMS (np. Zapisywanie aktualizacji pojedynczego wykresu obiektu więcej niż raz) i brak możliwości sterowania kolejność zamka.
Dobrym rozwiązaniem w tym przypadku byłoby posiadanie konkurujących konsumentów (zapobieganie zduplikowanemu przetwarzaniu jak najwyżej w łańcuchu poprzez podzielenie pracy na niepowiązane ze sobą obiekty).
Mniej pożądanym rozwiązaniem (ok, brudny hack) jest przełamanie pecha czasowego (rodzaj różnic sił w przetwarzaniu) z wyprzedzeniem lub przełamanie go po impasie za pomocą różnych algorytmów lub elementu losowości. Może to nadal powodować problemy, ponieważ jest możliwe, że kolejność przyjmowania blokad jest „lepka” dla każdego procesu, a to zajmuje pewien minimalny czas, który nie jest uwzględniany w ponownej próbie oczekiwania.
Jeszcze innym rozwiązaniem (przynajmniej dla SQL Server) jest wypróbowanie innego poziomu izolacji (np. Migawki).
Zakodowałem przykład 2 osób przechodzących na korytarzu. Dwie nici będą się unikać, gdy tylko zorientują się, że ich kierunki są takie same.
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) {}
}
}
}
Wersja C # kodu jelbourn:
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);
}
}
}
}
}
Jednym z przykładów może być użycie czasowego tryLock, aby uzyskać więcej niż jedną blokadę, a jeśli nie możesz uzyskać ich wszystkich, wycofaj się i spróbuj ponownie.
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();
}
}
}
}
Mogę sobie wyobrazić, że taki kod byłby problematyczny, ponieważ wiele wątków koliduje i czeka na uzyskanie zestawu blokad. Ale nie jestem pewien, czy jest to dla mnie bardzo przekonujące jako prosty przykład.
tryLockAll()
z zamkami locks
w tej samej kolejności, nie ma żywej blokady.
Wersja kodu jelbourn w Pythonie:
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()
Modyfikuję odpowiedź @jelbourn. Kiedy jeden z nich zauważy, że drugi jest głodny, powinien puścić łyżkę i poczekać, aż inny powiadomi, aby zdarzyło się bydło.
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();
}
}
}
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;
}
}
}