Взаимная блокировка
Взаи́мная блокиро́вка (англ. deadlock), класс ошибок в параллельных вычислительных системах. Она возникает в случае, если несколько параллельно работающих активностей (программных сущностей) ожидают ресурсов, захваченных друг другом. Возникновение взаимной блокировки может приводить, например, к отказу в обслуживании (зависанию), т. е. к нарушению т. н. свойства живучести. Примерами ресурсов могут быть различные средства для обеспечения синхронизации потоков (т. н. примитивы синхронизации). Здесь и далее будет использован термин «поток» для обозначения параллельно работающей активности, тем не менее всё дальнейшее верно и для других активностей (например, процессов).
Классическим примером ситуации, приводящей к взаимной блокировке, является захват двух примитивов синхронизации в двух потоках в различном порядке. Возможно такое выполнение программы, что ни один из потоков не сможет продолжить своё выполнение, т. к. каждый ожидает освобождения соответствующего примитива другим потоком. Следует отметить, что данная ошибка проявляется лишь на некоторых выполнениях программы, а если поток успевает захватить оба примитива, то программа завершится корректно.
Ситуация взаимной блокировки не ограничивается проблемами с порядком захватов ресурсов. К ситуации взаимной блокировки может привести потерянный из-за некорректной синхронизации сигнал. В этом случае один поток будет находиться в бесконечном ожидании сигнала, а второй поток, пославший сигнал, будет ожидать результата.
Взаимная блокировка имеет те же особенности, что и другие ошибки, связанные с параллельным исполнением кода. Она имеет случайный характер, т. к. для её возникновения необходимо воспроизвести определённую последовательность действий в нескольких параллельных потоках. Взаимную блокировку достаточно сложно обнаружить и локализовать в первую очередь из-за её случайного характера. Именно поэтому помимо традиционного тестирования для проверки сложных программных систем применяются различные техники как динамического, так и статического анализа. Ошибки, связанные с взаимной блокировкой, зачастую непросто исправить, т. к. не всегда проблема решается именно порядком захвата ресурсов.
Некоторые программные системы, такие как виртуальные машины, операционные системы, системы управления базами данных, могут реализовывать внутри себя алгоритмы разрешения взаимных блокировок в динамике на основе алгоритмов поиска циклов.
См. также Состояние гонки.