Задача взаимного исключения
Традиционные и широко используемые механизмы синхронизации, которые относятся к группе методов, предотвращающих конфликты, предполагают взаимное исключение по доступу к общим данным для одновременно выполняемых потоков, а различные реализации моделей параллельного программирования предоставляют необходимые средства для решения данной задачи.
Задача взаимного исключения в классическом виде впервые была сформулирована и решена (приведено решение математика Деккера) в работе голландского математика Дейкстры [dijkstra]. Формальная постановка задачи выглядит следующим образом [taubenfeld].
Предположим, что в ВС более двух процессов, выполняющих некоторую последовательность программных инструкций в бесконечном цикле. Выполняемые инструкции разделяются на четыре непрерывных блока кода: код, не требующий синхронизации, КС, вход в КС, выход из КС. Каждый процесс начинает свое выполнение с блока кода, не требующего синхронизации. В некоторый момент времени процессу может потребоваться выполнить инструкции из блока критической секции. Перед этим ему необходимо войти в КС, выполнив инструкции блока входа в КС, тем самым обеспечив себе эксклюзивное право выполнения инструкций КС. По завершении КС процесс выполняет инструкции выхода из нее, тем самым оповещая другие процессы о возможности получения доступа к КС. После выхода из КС процесс продолжает выполнять код, не требующий синхронизации.
Задача взаимного исключения состоит в разработке кода для блоков входа в КС и выхода из КС таким образом, чтобы были удовлетворены два основных требования:
1. взаимное исключение (англ. mutual exclusion) — свойство безопасности, которое гарантирует, что никакие два процесса не могут одновременно находиться внутри КС;
2. отсутствие мертвой блокировки или свобода от взаимоблокировок (англ. deadlock freedom) — свойство живости, подразумевающее, что если один процесс пытается войти в КС, то некоторый процесс, не обязательно тот же самый, рано или поздно войдет в свою КС.
Условие отсутствия мертвой блокировки предоставляет гарантию прогресса (живость) всей системы в целом, однако оно допускает ситуацию “голодания” отдельных процессов, которые периодически и безуспешно пытаются войти в КС. Более строгое условие гарантии прогресса — условие отсутствия “голодания” процессов (англ. starvation freedom) — если один процесс пытается войти в КС, то этот процесс рано или поздно обязательно войдет в свою КС. Для перечисленных условий решение задачи взаимного исключения может гарантировать определенную справедливость порядка выполнения КС процессами. Примером справедливого условия может служить условие “первый зашел-первым обслужен” или FIFO-справедливость (англ. first-in-first-out) — ни один процесс не может войти в КС до процесса, уже ожидающего своей очереди на вход в КС.
Изначально проблема взаимного исключения ставилась для систем с общей памятью, в которых есть возможность применения атомарных на аппаратном уровне операций чтения/записи. В настоящее время существует большое количество методов и средств решения данной задачи как для мультипроцессорных, так и для мультикомпьютерных систем.
Методы бесконфликтного доступа к памяти, которые решают задачу взаимного исключения, основаны на понятии блокировки или исключающего права. Попытка захвата блокировки осуществляется при входе в КС, а освобождение — при выходе из КС. При безуспешной попытке захвата процесс останавливается и помещается операционной системой в очередь ожидания блокировки.
Обладание таким исключающим правом означает для процесса возможность исполнения КС. Популярность данного подхода обосновывается относительной простотой использования средств синхронизации на основе блокировок при программировании и наличием достаточно эффективных реализаций блокировок.
1.3.1. Решение задачи взаимного исключения для мультипроцессоров
Ранние решения задачи взаимного исключения для систем с общей памятью были алгоритмическими (на аппаратном уровне необходима была лишь поддержка неделимости операций чтения/записи регистров памяти) и использовали схему активного ожидания. При данной схеме процесс постоянно считывает значение одной или нескольких переменных-флагов. Значение такой переменной или набора переменных говорит о возможности доступа к разделяемому ресурсу, т.е. о возможности выполнения КС. Алгоритм Деккера — первый корректный алгоритм (фактически изложенный в работе Дейкстры [dijkstra]), решающий задачу взаимного исключения и использующий активное ожидание. Алгоритм Деккера разработан для двух процессов и основан на строгом чередовании: выполнение КС разрешается только одному из двух процессов в зависимости от того, чья сейчас очередь. Реализуется алгоритм с помощью трех общих переменных-флагов, две из которых указывают на намерение одного из двух процессов войти в КС, а третья показывает, чья сейчас очередь. Очень похожий на решение Деккера, но более изящный алгоритм был предложен Петерсоном [peterson]. Оба оригинальных алгоритма (Деккера и Петерсона) разрабатывались для двух процессов. Решение для большего и заранее неопределенного количества процессов было впервые предложено Лэмпортом. В его алгоритме, который называется алгоритмом булочной [lamport], по аналогии с различными системами обслуживания, процесс является клиентом. Каждый клиент обслуживается (процессу предоставляется доступ к КС) на основании полученного им ранее “талончика”, т.е. некоторого уникального числового идентификатора. Однако в силу особенностей традиционной аппаратной архитектуры ВС (невозможности атомарно выполнять несколько операций чтения/записи подряд) несколько процессов могут получить талончики с одинаковыми номерами. Для разрешения данного конфликта используется приоритет процесса, его номер: чем меньше номер процесса, тем выше его приоритет.
Недостатком описанных алгоритмов является использование активного ожидания, что влечет за собой бесполезное использование процессорных ресурсов и пропускной способности шины памяти. Избежать недостатков программных решений задачи взаимного исключения, позволяет аппаратная поддержка со стороны вычислительной системы. В первую очередь, это использование запрета/разрешения прерываний и специальные атомарные операции. При использовании запрета/разрешения прерываний процесс при входе в КС специальной инструкцией запрещает прерывания, а при выходе из КС — вновь разрешает прерывания. Взаимное исключение достигается за счет того, что в КС никто не сможет прервать процесс, соответственно диспетчер операционной системы не может назначить на выполнение другой конкурентный процесс. У данного метода несколько недостатков; основной — его можно использовать только на однопроцессорной системе.
Кроме атомарных операций чтения/записи архитектура ПЭ ВС также может поддерживать специальные атомарные операции — RMW-операции (англ. read-modify-write), упрощающие реализацию описанных выше чисто программных решений задачи взаимного исключения.
Использование напрямую только описанных выше средств для решения задачи синхронизации с точки зрения прикладного программирования сложно и трудоемко. Как правило, реализации модели параллельного программирования включают в себя более удобные высокоуровневые средства бесконфликтного доступа к памяти — примитивы синхронизации, зачастую построенные на базе атомарных инструкций процессора и/или запрете/разрешении прерываний. Среди наиболее часто используемых на практике примитивов можно выделить: семафоры, мьютексы (или блокировки), спин-блокировки и условные переменные. В настоящее время наиболее эффективные реализации таких примитивов разрабатываются с применением алгоритмов, основанных на активном ожидании с экспоненциальной задержкой установления значения локального флага и выстраивании в очередь ожидающих процессов: прежде всего, это использующие списки ожидающих процессов алгоритм MCS (англ. Mellor-Crummey and Scott) [mcs] и алгоритм CLH (англ. Craig, Landin and Hagersten) [clh]. За разработку алгоритма MCS в 2006 году авторы были удостоены престижной награды ACM имени Дейкстры в области параллельных и распределенных вычислений. Данный алгоритм признан наиболее эффективным и масштабируемым и с небольшими модификациями используется в различных программных системах, в том числе ядре Linux [boyd] и виртуальной машине Java.
1.3.2. Решение задачи взаимного исключения для мультикомпьютеров
Решение задачи взаимного исключения чаще требуется и более подробно описано в литературе для мультипроцессоров, однако необходимость ее решения возникает и для слабосвязанных распределенных систем. Ресурсом, к которому необходимо разграничить доступ вычислительных процессов, в таких системах может выступать как память — при использовании парадигмы PGAS или DSM, так и любой другой сетевой ресурс или устройство. Ограничения и особенности мультикомпьютерных систем, в частности, использование механизма передачи сообщений или механизма RDMA между ПЭ и отсутствие глобальных синхронизируемых часов, делают решение рассматриваемой задачи более сложным. В алгоритмах взаимного исключения для таких систем вместо понятия блокировки используются сходные понятия, обозначающие владение исключительным правом на исполнение КС: токен и разрешение. Существующие алгоритмы распределенного взаимного исключения принято разделять [fu, bertier] на две группы:
1. алгоритмы на основе разрешений (англ. permission-based) — процессы получают право на вход в КС в результате опроса и набора достаточного количества разрешений/голосов от других процессов;
2. алгоритмы, использующие токены или маркеры (англ. Token-based), — доступ к КС получает только процесс, владеющий токеном.
Один из первых опубликованных алгоритмов распределенного взаимного исключения был предложен Лэмпортом [lamport2] и принадлежит к первому классу. Для этого класса алгоритмов особенно важным является определение порядка поступления запросов на вход в КС. Сложность здесь заключается в одном из основных ограничений распределенных систем: отсутствии нативного понятия глобального времени. Данное ограничение возникает из-за трудности эффективной реализации единых глобальных и синхронизированных для всех ПЭ системы часов. Есть два возможных подхода к такой реализации, однако оба они неэффективны и редко применяются на практике. При использовании первого подхода в системе доступны единые общие часы, к которым обращается каждый ПЭ с целью получения значения текущего времени. Однако в распределенной системе возможен случай, когда два различных ПЭ могут прочитать одинаковое значение часов в физически различные моменты времени в силу задержек при передаче сообщений, что приводит к неправильному представлению процессоров о текущем времени в системе. Второй подход предполагает наличие у каждого процессора собственных локальных часов, к которым он обращается за отметкой времени. В силу сложности обеспечения как программной, так и аппаратной корректной синхронизации всех распределенных локальных часов такое решение может привести к проблеме дрейфа часов относительно их общесистемного значения. Кроме того, величина дрейфа разных часов может варьироваться, что еще более усложняет использование данного подхода.
Использование отметок глобальных часов — наиболее простой способ упорядочения возникающих в системе событий, и их отсутствие приводит к усложнению решения задачи распределенного взаимного исключения. Оригинальный подход к решению проблемы предложил в своей знаменитой статье [lamport2] Лэмпорт, который ввел понятие причинно-следственного отношения частичного порядка между событиями и представил способ упорядочения событий в распределенной системе на основе отметок логического времени.