В чем разница между тупиком и живым замком?
Может кто-нибудь объяснить с примерами (кода), в чем разница между взаимоблокировками и livelock?
6 ответов
Взято с http://en.wikipedia.org/wiki/Deadlock:
В параллельных вычислениях тупик - это состояние, в котором каждый член группы действий ожидает, пока какой-либо другой участник не снимет блокировку.
Живая блокировка похожа на тупиковую, за исключением того, что состояния процессов, вовлеченных в живую блокировку, постоянно меняются относительно друг друга, и ни один из них не прогрессирует. Livelock - это особый случай истощения ресурсов; общее определение только утверждает, что конкретный процесс не прогрессирует.
Реальный пример живой блокировки происходит, когда два человека встречаются в узком коридоре, и каждый пытается быть вежливым, отодвигаясь в сторону, чтобы пропустить другого, но в итоге они раскачиваются из стороны в сторону, не делая никакого прогресса, потому что они оба неоднократно перемещаются так же, в то же время.
Livelock - это риск, связанный с некоторыми алгоритмами, которые обнаруживают и восстанавливаются после тупика. Если действие выполняется более чем одним процессом, алгоритм обнаружения взаимоблокировки может запускаться повторно. Этого можно избежать, гарантируя, что только один процесс (выбранный случайным образом или по приоритету) выполняет действие.
Поток часто действует в ответ на действие другого потока. Если действие другого потока также является ответом на действие другого потока, то может возникнуть прямая блокировка.
Как и в случае взаимоблокировки, потоки с блокировкой в реальном времени не могут добиться дальнейшего прогресса. Однако потоки не блокируются - они просто слишком заняты, отвечая друг другу, чтобы возобновить работу. Это сравнимо с двумя людьми, пытающимися обойти друг друга в коридоре: Альфонс движется налево, чтобы пропустить Гастона, а Гастон движется вправо, чтобы пропустить Альфонса. Видя, что они все еще блокируют друг друга, Альфонс движется вправо, а Гастон - слева. Они все еще блокируют друг друга и так далее...
Основное различие между livelock и deadlock состоит в том, что потоки не будут блокироваться, вместо этого они будут пытаться отвечать друг другу непрерывно.
На этом изображении оба круга (нити или процессы) будут пытаться освободить место для другого, перемещаясь влево и вправо. Но они не могут двигаться дальше.
Все содержание и примеры здесь взяты из
Операционные системы: внутреннее устройство и принципы проектирования
Уильям Сталлингс
8º издание
Тупик: ситуация, в которой два или более процессов не могут продолжаться, потому что каждый ждет, пока один из них что-то сделает.
Например, рассмотрим два процесса, 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;
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] в true.
- P0 проверяет флаг [1].
- P1 проверяет флаг [0].
- P0 устанавливает флаг [0] в ложь.
- P1 устанавливает флаг [1] в ложь.
- P0 устанавливает флаг [0] в true.
- P1 устанавливает флаг [1] в true.
Эта последовательность может быть расширена до бесконечности, и ни один из процессов не сможет войти в ее критическую секцию. Строго говоря, это не тупик, потому что любое изменение относительной скорости двух процессов нарушит этот цикл и позволит войти в критическую секцию. Это условие называется livelock. Напомним, что тупик возникает, когда набор процессов хочет войти в свои критические секции, но ни один процесс не может быть успешным. При использовании 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
}
}
}
Итак, когда поток A входит в while цикл и удерживает блокировку, он делает то, что должен, и устанавливает commonVar к true. Затем входит поток B, входит вwhile петля и так commonVar является trueтеперь он может удерживать замок. Он делает это, выполняетsynchronised блок и устанавливает commonVar вернуться к false. Теперь поток А снова получает это новое окно CPU, он был собирается выйти изwhile цикл, но поток B только что вернул его к false, поэтому цикл повторяется снова. Потоки что-то делают (поэтому они не блокируются в традиционном смысле), но почти ничего.
Также неплохо было бы упомянуть, что здесь не обязательно появляться livelock. Я предполагаю, что планировщик отдает предпочтение другому потоку, как толькоsynchronisedблок закончить выполнение. В большинстве случаев я думаю, что это трудноосуществимое ожидание, и оно зависит от многих вещей, происходящих под капотом.
Я просто планировал поделиться некоторыми знаниями.
Взаимоблокировки Набор потоков / процессов находится в состоянии взаимоблокировки, если каждый поток / процесс в наборе ожидает события, которое может вызвать только другой процесс в наборе.
Здесь важно то, что другой процесс также находится в том же наборе. это означает, что другой процесс также заблокирован, и никто не может продолжить.
Взаимоблокировки возникают, когда процессам предоставляется монопольный доступ к ресурсам.
Чтобы зайти в тупик, необходимо выполнить эти четыре условия.
- Условие взаимного исключения (каждый ресурс закреплен за 1 процессом)
- Условие удержания и ожидания (процесс удержания ресурсов и в то же время может запрашивать другие ресурсы).
- Нет условия вытеснения (ранее предоставленные ресурсы не могут быть отобраны принудительно) # Это условие зависит от приложения
- Условие циклического ожидания (Должна быть циклическая цепочка из 2 или более процессов, каждый из которых ожидает ресурса, удерживаемого следующим членом цепочки) # Это будет происходить динамически
Если мы нашли эти условия, то можем сказать, что может возникнуть ситуация вроде тупика.
LiveLock
Каждый поток / процесс повторяет одно и то же состояние снова и снова, но не продвигается дальше. Что-то похожее на тупик, так как процесс не может войти в критическую секцию. Однако в тупике процессы ждут, ничего не делая, но в режиме livelock процессы пытаются продолжить, но процессы повторяются в одном и том же состоянии снова и снова.
(В вычислении с тупиковой блокировкой нет возможной последовательности выполнения, которая будет успешной. Но в вычислении с динамической блокировкой есть успешные вычисления, но есть одна или несколько последовательностей выполнения, в которых ни один процесс не входит в его критическую секцию.)
Отличие от deadlock и livelock
Когда происходит взаимоблокировка, выполнение не происходит. но в livelock некоторые исполнения будут происходить, но этих исполнений недостаточно для входа в критическую секцию.
С http://operatingsystemgeeks.blogspot.in/
Пример тупика:
Действует условие взаимного исключения, поскольку на участке улицы одновременно может находиться только одно транспортное средство.
Применяется условие удержания и ожидания, поскольку каждое транспортное средство занимает участок улицы и ожидает перехода к следующему участку улицы.
Применяется условие без вытеснения, поскольку часть улицы, которая является частью улицы, занятой транспортным средством, не может быть отнята у него.
Применяется условие кругового ожидания, поскольку каждое транспортное средство ожидает движения следующего транспортного средства. Таким образом, каждое транспортное средство в движении ожидает участок улицы, на котором находится следующее транспортное средство в движении.