В чем разница между тупиком и livelock?

Может кто-нибудь объяснить с примерами (кода), в чем разница между взаимоблокировками и livelock ?

Взято с http://en.wikipedia.org/wiki/Deadlock :

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

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

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

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

динамический тупик

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

Как и в случае взаимоблокировки, потоки с блокировкой в ​​реальном времени не могут добиться дальнейшего прогресса . Однако потоки не блокируются - они просто слишком заняты, отвечая друг другу, чтобы возобновить работу . Это сравнимо с двумя людьми, пытающимися обойти друг друга в коридоре: Альфонс движется налево, чтобы пропустить Гастона, а Гастон движется вправо, чтобы пропустить Альфонса. Видя, что они все еще блокируют друг друга, Альфонс движется вправо, а Гастон - слева. Они все еще блокируют друг друга и так далее ...

Основное различие между livelock и deadlock состоит в том, что потоки не будут блокироваться, вместо этого они будут пытаться отвечать друг другу непрерывно.

На этом изображении оба круга (нити или процессы) будут пытаться освободить место для другого, перемещаясь влево и вправо. Но они не могут двигаться дальше.

Все содержание и примеры здесь взяты из

Операционные системы: внутреннее устройство и принципы проектирования
William Stallings
8º Edition

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

Например, рассмотрим два процесса, P1 и P2, и два ресурса, R1 и R2. Предположим, что каждому процессу необходим доступ к обоим ресурсам для выполнения части его функций. Тогда возможна следующая ситуация: ОС назначает R1 для P2 и R2 для P1. Каждый процесс ожидает один из двух ресурсов. Ни один из них не освободит ресурс, которым он уже владеет, до тех пор, пока он не получит другой ресурс и не выполнит функцию, требующую обоих ресурсов. Два процесса заблокированы

Живая блокировка : ситуация, в которой два или более процессов непрерывно изменяют свои состояния в ответ на изменения в других процессах без какой-либо полезной работы:

Голодание : Ситуация, когда планировщик игнорирует запущенный процесс на неопределенный срок; хотя он может продолжать, он никогда не выбирается.

Предположим, что каждому из трех процессов (P1, P2, P3) требуется периодический доступ к ресурсу R. Рассмотрим ситуацию, когда P1 владеет ресурсом, и P2 и P3 задерживаются, ожидая этого ресурса. Когда P1 выходит из своей критической секции, P2 или P3 должен быть разрешен доступ к R. Предположим, что ОС предоставляет доступ к P3 и что P1 снова требует доступ до того, как P3 завершит свою критическую секцию. Если ОС предоставляет доступ к P1 после завершения P3 и впоследствии поочередно предоставляет доступ к P1 и P3, то P2 может быть неограниченно запрещен доступ к ресурсу, даже если нет ситуации взаимоблокировки.

ПРИЛОЖЕНИЕ А - ТЕМЫ В ВАЛЮТЕ

Пример тупика

Если оба процесса устанавливают свои флаги в true до того, как один из них выполнит оператор while, то каждый из них будет думать, что другой вошел в критическую секцию, вызывая взаимоблокировку.

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

Пример живой блокировки

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...] рассмотрим следующую последовательность событий:

• P0 устанавливает флаг [0] в true.
• P1 устанавливает флаг [1] в true.
• P0 проверяет флаг [1].
• P1 проверяет флаг [0].
• P0 устанавливает флаг [0] в ложь.
• P1 устанавливает флаг [1] в ложь.
• P0 устанавливает флаг [0] в true.
• P1 устанавливает флаг [1] в true.

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

Не содержание из книги больше.

А как насчет спинлок?

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

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

Проблема начинает появляться, когда beginLock()стоит намного больше, чем doSomething(). В очень преувеличенном виде представьте, что происходит, когда beginLockстоит 1 секунда, а doSomethingстоит всего 1 миллисекунда.

В этом случае, если вы подождали 1 миллисекунду, вам бы не мешали в течение 1 секунды.

Почему это beginLockбудет стоить так дорого? Если блокировка свободна, это не стоит больших затрат (см. Https://stackoverflow.com/a/49712993/5397116 ), но если блокировка не свободна, ОС «заморозит» ваш поток, настройте механизм, чтобы разбудить вас когда замок будет освобожден, а затем снова разбудить вас в будущем.

Все это намного дороже, чем некоторые петли, проверяющие блокировку. Вот почему иногда лучше сделать «спинлок».

Например:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

Если ваша реализация не является осторожной, вы можете упасть на livelock, потратив все ресурсы процессора на механизм блокировки.

Также см:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Является ли моя реализация спин-блокировки правильной и оптимальной?

Резюме :

Тупик : ситуация, когда никто не прогрессирует, ничего не делает (спит, ждет и т. Д.). Загрузка процессора будет низкой;

Livelock : ситуация, когда никто не прогрессирует, но процессор расходуется на механизм блокировки, а не на ваш расчет;

Голодание: ситуация, когда один прогресс никогда не получает шанс бежать; по чистой случайности или по какой-либо причине (например, с низким приоритетом);

Спинлок : метод избежания затрат, ожидающих освобождения блокировки.

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

LIVELOCK Условия Livelock могут возникать, когда две или более задач зависят от некоторого ресурса и используют его, вызывая состояние циклической зависимости, при котором эти задачи продолжают выполняться вечно, таким образом блокируя выполнение всех задач с более низким приоритетом (эти задачи с более низким приоритетом испытывают состояние, называемое голоданием)

Возможно, эти два примера иллюстрируют разницу между тупиком и livelock:

Java-пример для тупика:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

Образец вывода:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

Java-пример для livelock:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

Образец вывода:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

Оба примера заставляют нити приобретать замки в разных порядках. В то время как тупик ожидает другую блокировку, livelock на самом деле не ждет - он отчаянно пытается захватить блокировку без возможности ее получить. Каждая попытка потребляет циклы процессора.

Представьте, что у вас поток A и поток B. Они оба находятся synchronisedв одном объекте, и внутри этого блока есть глобальная переменная, которую они оба обновляют;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

Таким образом, когда поток А входит в whileпетлю и удерживает блокировку, он делает то , что он должен делать , и установить commonVarвtrue . Затем нить B входит, входит в whileпетлю и , так как commonVarэто trueсейчас, это быть в состоянии удерживать замок. Это делает, выполняет synchronisedблок и устанавливает commonVarобратно false. Теперь поток А снова получает это новое окно CPU, он был собирается выйти из whileцикла , но поток B только установить его обратно false, так что цикл повторяется снова. Потоки что-то делают (поэтому они не блокируются в традиционном смысле), но практически ничего.

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