Решение проблемы в управлении конкурентными вычислениями

От переводчиков. Эту коротенькую статью Дейкстры, которой уже 57 лет, Лесли Лампорт назвал «работой, которая начала всю область конкурентных и распределенных алгоритмов». Но на Хабре её до сих пор вроде бы не переводили. Поскольку мы скоро проведём конференцию Hydra, которая посвящена именно этой области, решили восполнить этот пробел. Кстати, как думаете, как лучше переводить на русский слово concurrent? Мы выбрали вариант «конкурентный», но консенсуса тут вроде бы нет.

Эдсгер В. Дейкстра
Технический университет Эйндховена, Нидерланды

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

Введение

В данной работе приводится решение проблемы, вопрос о разрешимости которой, насколько известно автору, остается открытым по крайней мере с 1962 года. Работа состоит из трех частей: проблема, решение и доказательство. Хотя постановка задачи поначалу может показаться несколько академической, автор надеется, что любой, кто знаком с логическими проблемами, возникающими при взаимодействии компьютеров, оценит значимость того факта, что эта проблема в принципе может быть решена. 

Проблема

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

Решение должно удовлетворять следующим требованиям.

(a) Решение должно быть симметричным для N компьютеров; поэтому недопустимо вводить фиксированный приоритет.

(b) Не допускаются никакие предположения об относительных скоростях этих N компьютеров; мы даже не можем предполагать, что их скорости постоянны во времени.

(c) Если любой из компьютеров прекратил работу однозначно за пределами своей критической секции, недопустимо, чтобы это привело к потенциальной блокировке остальных.

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

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

Решение

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

Хранилище содержит:

Boolean array b, c[1:N]; integer k

Целое число k будет удовлетворять 1 ≤ k ≤ N, b[i] и c[i] могут быть изменены только i-тым компьютером; при этом они могут быть прочитаны другими. Предполагается, что все компьютеры начинают свою работу далеко за пределами своих критических секций, при том, что все упомянутые Булевы массивы установлены в значении истина. Начальное значение k не играет роли.

Программа для i-того компьютера (1 ≤ i ≤ N) приведена ниже:

Доказательство

Начнем с того, что решение является безопасным в том смысле, что никакие два компьютера не могут одновременно находиться в своей критической секции. Поскольку единственным способом попасть в критическую секцию является выполнение составного выражения Li4 без возврата к Li1, т.е. обнаружение истинности всех остальных c после того, как собственное c стало ложным.

Вторая часть доказательства должна показать, что никакой бесконечной блокировки типа "После тебя"-"После тебя" произойти не может; а именно, когда ни один из компьютеров не находится в своей критической секции, из зацикленных компьютеров (т.е. прыгающих назад в Li1)  хотя бы один — а значит, ровно один — будет допущен в свою критическую секцию в положенное время.

Если k-й компьютер не входит в число зацикленных, то b[k] будет истинным, а зацикленные компьютеры все будут обнаруживать k ≠ i. В результате один или несколько из них найдут в Li3 Булево b[k]истинным и, следовательно, один или несколько решат присвоить "k := i". После первого присваивания "k := i", b[k] становится ложным и никакие новые компьютеры не могут снова решить присвоить новое значение k. Когда все решенные присваивания k выполнены, k будет указывать на один из зацикленных компьютеров и не будет менять своего значения на время, а именно, пока b[k] не станет истинным, т.е. пока k-й компьютер не завершит свою критическую секцию. Как только значение k больше не будет меняться, k-й компьютер будет ждать (по составному высказыванию Li4), пока все остальные c станут истинными, но эта ситуация обязательно возникнет, если уже не возникла, поскольку все остальные зацикленные компьютеры будут вынуждены установить своё c истинным, так как найдут k ≠ i. И на этом, по мнению автора, доказательство завершается.