В чем разница между тупиком и живым замком? - PullRequest
Новая
       100

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

302 голосов
/ 27 мая 2011

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

Ответы [ 5 ]

355 голосов
/ 27 мая 2011

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

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

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

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

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

71 голосов
/ 17 января 2015

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

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

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

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

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

enter image description here

56 голосов
/ 01 февраля 2016

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

Операционные системы: внутреннее оборудование и принципы проектирования
Уильям Сталлингс
8º Edition

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

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

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

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

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

ПРИЛОЖЕНИЕ A - ТЕМЫ В СОВРЕМЕННОСТИ

Пример взаимоблокировки

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

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

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

Пример Livelock 

/* PROCESS 0 */
flag[0] = true; 
while (flag[1]){
    flag[0] = false; 
    /*delay */;
    flag[0] = true;
}
/*critical section*/;
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] в значение false.
  • P1 устанавливает флаг [1] в значение false.
  • P0 устанавливает флаг [0]в true.
  • P1 устанавливает флаг [1] в true.

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

13 голосов
/ 27 января 2012

ТУПИК Тупик - это состояние, в котором задача ждет на неопределенный срок для условий, которые никогда не могут быть довольный - задача требует эксклюзивного контроля над общим Ресурсы - задача удерживает ресурсы в ожидании других ресурсы, которые будут выпущены - задачи нельзя заставить перераспределить ресурсы - существует круговое ожидание

* 1006 динамический тупик * Условия прямой блокировки могут возникнуть, когда два или больше задач зависит от и использовать некоторые ресурс, вызывающий круговую зависимость состояние, в котором эти задачи продолжаются работает вечно, таким образом блокируя все ниже задачи уровня приоритета от запуска (эти задачи с более низким приоритетом испытывают условие называется голодом)

5 голосов
/ 22 сентября 2017

Возможно, эти два примера иллюстрируют разницу между взаимоблокировкой и 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 действительно не ждет - он отчаянно пытается захватить замок без возможности его получить. Каждая попытка потребляет циклы процессора.

...