Сегодня я хотел бы рассказать про замечательную статью, котора | Of Code & Men

Сегодня я хотел бы рассказать про замечательную статью, которая стала вехой в науке о распределенных вычислениях. Статья была написана Эдсгером Дейкстрой в дремучем 1965-ом году. В том же году появились Pink Floyd и Velvet Underground, а в это время Дейкстра ввел в компьютерную науку понятие мьютекса. 

Мьютекс (mutex) - это mutual exclusion, взаимное исключение, механизм, который разрешает только одному участнику распределенного процесса войти в критическую секцию. Что-то уже запутанно, да? Рассмотрим всё по порядку.

Есть набор машин, которые в бесконечном цикле вместе молотят какую-то задачу. Ключевое слово "вместе", значит, им надо иногда синхронизировать свои результаты, например, увеличивать на 1 общий счётчик. Существует вероятность того, что если два компьютера одновременно начнут увеличивать общий счётчик, то часть работы может потеряться. Как это возможно? Операции чтения и записи не атомарны. Сперва необходимо прочитать значение счётчика, потом увеличить значение на 1 у себя в памяти, а затем записать заново. Возможна ситуация, когда два компьютера одновременно читают значение счётчика (допустим, это 5), увеличивают на 1 (у обоих станет 6) и по очереди записывают число 6 обратно. В итоге вместо ожидаемых 7, счётчик будет равен 6.

Как избежать этой ситуации? Создать ту самую критическую секцию, которая включает в себя и чтение, и запись. То есть, сделать так, чтобы пока один компьютер читает и записывает данные, другие этого сделать бы не смогли.

Это весьма нетривиальная задача и с момента её постановки прошло три года, прежде чем Дейкстра нашёл решение.  При этом он наложил ряд дополнительных условий:
• решение не зависит от числа компьютеров N и у них нет никакого приоритета в зависимости от порядкового номера;
• решение не завязано на скорости выполнения задач каждым из компьютеров;
• если один из компьютеров зависнет вне критической секции, то это не приведёт к остановке всего процесса;
• должна соблюдаться живучесть системы, то есть прогресс не должен останавливаться из-за того, что все компьютеры только и делают, что говорят друг другу “После вас!“, “Нет, после вас!”

Так вот, в чём примечательность статьи. Мало того, что Дейкстра решил задачу, всё условие, решение и доказательство поместились на одной странице! Правда, даже чтение этой страницы может вызвать определённые трудности. Поэтому в следующем посте я немного осовременю код и попробую на интуитивном уровне объяснить решение.

#distributedcomputing