Можно рассмотреть тот пример с банковскими счетами, которые рандомно пересылают деньги друг другу и ждут, пока им кто-нибудь не докинет денег, если на счету не хватает денег, чтобы провести транзакцию. Там на каждый банковский счёт есть ровно один поток. Если у всех по умолчанию, скажем, 1000 денег, и максимальная величина транзакции — тоже 1000, то ничего не сможет дедлокнуться, потому что в любой момент времени хотя бы у кого-нибудь будет достаточно денег, чтобы перечислить их кому-нибудь другому.
Но, если увеличить максимальную величину транзакции, то уже могут возникуть ситуации, при которых никто не сможет никому перечислить деньги. Например:
И никто ничего не может сделать.
Ещё дедлок тут может случиться из-за того, что на condition’е вызывается signal(), а не signalAll():
signal() выбирает рандомно только один спящий поток. Второй поток получает деньги, но всё ещё спит, третий просыпается, но сразу же засыпает, потому что у него нет денег.Кстати, вроде как можно посмотреть дамп тредов, если нажать Ctrl + \ при выполнении прог раммы, но у меня почему-то там не отобразился ни один из созданных мною потоков. Но получилось посмотреть на это через jconsole.
Вообще в общем случае дедлок возникает, когда каждый поток ждёт выполнения какого-то условия, и в итоге никто не может продолжить своё выполнение.
Ignoring deadlock. Можно игнорировать возможное состояние дедлока, исходя из предположения о том, что дедлок либо невозможен, либо вероятность его возникновения крайне мала и в целом расходы на то, чтобы избежать это потенциальное плохое состояние нерелевантны, учитывая вероятность его возникновения. В общем случае это называется Ostrich algorithm — a strategy of ignoring potencial problems on the basis that they may be exceedingly rare (ostrich effect — to stick one’s head in the sand and pretend there is no problem).
Deadlock detection and correction. Другой способ — разрешить системе дедлокнуться, выявить состояние дедлока и разрешить его (намеренно нарушив одно из условий дедлока, обычно то, которое про circluar wait, то есть разбить цикл).
Можно прервать все процессы, которые вместе находятся в состоянии дедлока. Это гарантированно его уберёт, но при этом можно потерять результаты вычислений. Другой способ — последовательно прерывать процессы (в каком-то особом порядке, может, там эвристика какая-то, или просто выбирается в соответствии с приоритетами и временем выполнения), пока дедлок не пропадёт. Это, очевидно, более долгий способ, потому что нужно итеративно убирать процесс — проверять условия дедлока, но зато итоге можно будет обойтись меньшими потерями. Как я понимаю, это не самый предпочтительный метод, потому что впустую тратится ЦПУ-время.
Или можно отобрать ресурсы от одних потоков и дать их другим (resource preemption), делать так, пока дедлок не разрешится. В идеале хорошо было бы вернуть при этом соответствующий поток в последнее безопасное состояние и запустить его заново, когда дедлок разрешится, однако часто это невозможно, так что он просто запускается заново. Тут тоже есть проблема с тем, как выбирать victim‘ов для resource preemption.
Ещё одна проблема с этим всем — это голодование процесса (starvation). Это просто, когда процессу постоянно не дают ресурсов (не важно, ЦПУ-время, или что-то ещё). Тут это может произойти из-за того, что в качестве жертвы постоянно будет выбираться один и тот же поток.
…
потом полистать, там они, наверное, пересекаются, но можно будет достать бол ьше ссылок
Critical section — это кусок программы, который защищён от того, чтобы он выполнялся одновременно более, чем одним потоком, для того, чтобы избежать race condition. Race condition — это состояние системы, в котором на её поведение очень сильно влияют тайминги или последовательность выполнения процессов/потоков.
Частный случай — data race (когда два потока одновременно что-то делают с одним местом в памяти таким образом, что это может привести к неопределённым результатам и к повреждению памяти из-за не-атомарности операций). Обычно, помимо обычных, небезопасных операций работы с данными, имплементированы синхронизированные или atomic операции, которые не могут быть прерваны во время своего выполнения. При этом в терминах программы, которая использует атомик операции всё ещё может иметь место race condition, но с использованием атомиков по крайней мере не будет повреждений памяти, но всё будет неопределённым.
Критическую секцию можно реализовать, например, с помощью алгоритма Петерсона. В оригинале он был сделан только для двух потоков, но он расширяется до произвольного количества потоков. Потоки коммуницируют друг с другом через один общий интеджер (int turn) и массив из boolean значений по одному на каждый поток (bool[] flag). Это может работать корректно только при условии того, что значения этих переменных и ячеек массива видны одинаково из всех потоков. В джаве достаточно объявить их как volatile (вернее нет, для массива как раз недостаточно, нужно использовать, например AtomicIntegerArray).
Volatile массивы в джавве. А ещё можно после каждой записи в массив делать arr = arr, тогда вроде как это будет массив из volatile значений, хоть он и будет неэффективным (на каждую запись (по смыслу) тратится две записи по сути):
volatile int[] arr = new int[...];
...
arr[4] = 100;
arr = arr;
...
Но, начиная с Java 9, можно использовать VarHandle, который умеет ссылаться на что угодно и для которого можно явно вызвать get/setVolatile при необходимости. Этот же способ используется при реализации AtomicIntegerArray, кстати:
public class AtomicIntegerArray {
private static final VarHandle AA = MethodHandles.arrayElementVarHandle(int[].class);
private final int[] array;
public final int get(int i) {
return (int) AA.getVolatile(array, i);
}
public final void set(int i, int newValue) {
AA.setVolatile(array, i, newValue);
}
}