Взаимная блокировка: когда замок перестаёт быть лечением

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

/* transfer.c */
void transfer(account *from, account *to, long cents) {
  mutex_lock(&from->lock);
  mutex_lock(&to->lock);
  from->balance -= cents;
  to->balance += cents;
  mutex_unlock(&to->lock);
  mutex_unlock(&from->lock);
}

transfer(&alice, &bob, 500);    /* thread 1 */
transfer(&bob, &alice, 700);    /* thread 2 */У каждого счёта свой замок. Два вызова ниже выполняются в двух разных потоках одновременно.

Посмотрите, у кого что. Поток 1 захватил замок alice и теперь хочет замок bob. Поток 2 захватил замок bob и теперь хочет замок alice. Ни один никогда не отпустит, потому что ни один не завершился. Оба спят вечно. Чтобы это случилось, должны были одновременно выполняться четыре условия, все четыре сформулированы ещё в 1971 году, и они до сих пор остаются чек-листом.

mutual exclusion      request()
hold and wait         hold(A); request(B)
no preemption         request(B); loop
circular wait         T1 -> B, T2 -> A

all four hold   ->   deadlock
break any one   ->   no deadlockЧетыре условия Коффмана. Разорвите любое одно — и взаимная блокировка станет невозможной, как бы ни использовались замки.

Дешевле всего разорвать здесь циклическое ожидание, и лекарство — одна строка: задайте всем блокируемым объектам глобальный порядок и всегда захватывайте замки в этом порядке. Классический приём — сравнивать адреса: тот, что лежит ниже в памяти, берётся первым. Тогда два потока не могут держать замки, нужные друг другу, потому что оба первым делом тянутся за одним и тем же.

mutex_lock(&from->lock);   /* wrong: order depends on arguments */
mutex_lock(&to->lock);

mutex_lock(&lo->lock);     /* right: one global order, by address */
mutex_lock(&hi->lock);Теперь оба вызова берут сначала младший адрес, поэтому один просто ждёт другого, а не борется с ним.

Второе условие, которое можно разорвать, — удержание с ожиданием. Сделайте каждый захват «всё или ничего»: если второй замок сейчас не свободен, отпустите первый и начните заново. Никто не ждёт, держа что-то, поэтому цикл держателей образоваться не может. Это работает только если состояние не остаётся наполовину изменённым: функция обязана либо сделать всё, либо ничего. Это настоящее ограничение, и именно поэтому в банковском коде есть транзакции.

while (!mutex_trylock(&from->lock)) { /* backoff */ }
if (!mutex_trylock(&to->lock)) {
  mutex_unlock(&from->lock);
  return RETRY;                /* held nothing while waiting */
}

/* $ timeout 30 ./bank && echo ok || echo 'still stuck' */

Взаимная блокировка — не единственный способ остановить работу. Два потока могут продолжать работать и продолжать отменять друг друга: каждый замечает конфликт, вежливо отпускает замок и повторяет попытку — и оба повторяют в один и тот же момент, вечно. Это livelock. Процессор загружен на 100%, логи полны активности, и ни одна транзакция не завершается. Это, пожалуй, хуже взаимной блокировки: заблокированный процесс стоит на нулевом CPU и виден в дампе стеков, а живой-livelock выглядит занятым и здоровым. Лечится внесением случайности: экспоненциальная задержка со случайной составляющей, чтобы потоки перестали повторять синхронно.

deadlock    blocked,  cpu 0%
livelock    running,  cpu 100%
starvation  running,  cpu 100%

F1 holds B forever
F2 and F3 retry
F1 is frozenТри способа остановить работу, различающиеся только тем, что делает процессор и кто именно застрял.

Голодание — третий сбой и самый безобидный на вид. Ничего не циклично и ничто не заблокировано: система в целом продвигается, но один конкретный поток так и не получает свой ход. Обычная причина — блокировка «читатели-писатели», которая всегда отдаёт предпочтение приходящим читателям: при непрерывном потоке читателей писатель ждёт вечно. Другой пример — поток самого низкого приоритета на загруженной машине. Голодание — это ошибка справедливости, а не структуры, и заметить её можно через дни, потому что графики пропускной способности выглядят идеально.

А теперь почему очевидный совет неверен. Добавить замок — значит добавить не безопасность, а ресурс, а каждый новый ресурс — это новое ребро ожидания в графе. Два замка дают один возможный цикл; десять замков дают 45 упорядоченных пар, и любая из них может оказаться неправильным порядком где-то в кодовой базе. Функция, которая берёт три отдельных замка и вызывает код, берущий ещё два, сделала взаимную блокировку возможной в месте, где никто не догадается искать. Замки к тому же не композируются: два независимых модуля, каждый из которых корректен, могут заблокироваться в тот момент, когда один вызовет другой, держа свой замок.

На практике не только замки могут войти во взаимную блокировку. Поток, держащий соединение с базой и ждущий соединение из того же пула, опустошает пул; два сервиса, каждый из которых ждёт синхронного вызова от другого, — это распределённая взаимная блокировка, которую не покажет ни один дамп одного процесса. В продакшене такое обычно ловят таймаутами и сторожевыми потоками: если транзакция не продвинулась за N секунд, снимают стеки всех потоков и ищут цикл. В живом процессе это видно напрямую: в стеках заблокированных потоков назван замок, которого каждый из них ждёт, и замок, которым каждый владеет.