В чем разница между deadlock и livelock?

Question

В чем разница между deadlock и livelock?

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

6 262

pthreads multithreading deadlock livelock

6 ответов:

Livelock

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

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

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

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

61

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

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

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

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

ПРИЛОЖЕНИЕ А-ТЕМЫ В Параллелизм

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

Если оба процесса установили свои флаги в 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;
Пример Динамической Взаимоблокировки
/* 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] в истинный.

P0 проверяет флаг[1].

P1 проверяет флаг[0].

P0 устанавливает флаг[0] в значение false.

P1 устанавливает флаг [1] в значение false.

P0 устанавливает флаг[0] в true.

P1 устанавливает флаг[1] в true.

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

44

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

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

13

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

2

Со Ссылкой : http://operatingsystemgeeks.blogspot.in/ Пример взаимоблокировки : Применяется условие взаимного исключения, поскольку одновременно на одном участке улицы может находиться только одно транспортное средство. Условие удержания и ожидания применяется, так как каждое транспортное средство занимает участок улицы и ждет, чтобы перейти к следующему участку улицы. Нет-преимущественное условие применяется, так как участок улицы, который является участком улицы, который занят транспортным средством, не может быть забрали у него. Круговое условие ожидания применяется, так как каждое транспортное средство ждет следующего транспортного средства для перемещения. То есть, каждое транспортное средство в движении ждет участок улицы, удерживаемый следующим транспортным средством в движении.

-2

mah · Accepted Answer · 2017-01-23 01:41:06

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

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

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

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

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