Отрывок из книги Никола Санторо
Design And Analysis Of Distributed Algorithms
Перевод с английского Заняла Д.Г.
В распределенной вычислительной среде, возникает масса случаев и ситуаций, в которых необходимо предоставить единственному объекту (или отдельной группе объектов) право эксклюзивного контроля.
Это происходит, например, всякий раз, когда вычисления требуют присутствия центрального управляющего устройства (например, из-за того что таким способом координация будет выполнена эффективнее). В течение всего жизненного цикла системы, такая потребность будет периодически возникать; следовательно, это - постоянная проблема. Типичное решение, используемое в этих ситуациях - это выбор нового координатора каждый раз, когда он необходим. Мы детально обсудили и исследовали эту задачу в главе 3. Однако подход с повторяющимся выбором лидера имеет некоторые недостатки. Первый и основной – это то, что обычно такой выбор является несправедливым. Заметим, что нет никакого ограничения на то, какой объект станет лидером; таким образом, возможно, что некоторые объекты никогда не будут выполнять эту роль, в то время как другие (например, с маленьким порядковым номером) будут всегда выбираться. Это означает, что нагрузка не сбалансирована в пределах системы; также это может создать дополнительные узкие места. Побочный (но важный) недостаток повторяющегося выбора лидера - это его стоимость. Даже если он выполняется на изначально заданном связующем дереве, каждый раз требуется не менее Ω(n) сообщений.
Другая ситуация, когда необходимо эксклюзивное управление – это доступ к критическому ресурсу системы. Это, например, тот случай, когда только ресурс какого-то типа (например, принтер, шина) существует в системе в единственном экземпляре, и этот ресурс не может быть использован одновременно несколькими объектами. В этом случае, любой объект, требующий использования такого ресурса должен быть уверен, что он единственный, кто использует этот ресурс. Важным является не характер ресурса, а тот факт, что доступ должен быть проведен в ситуации взаимного исключения: то есть только один объект в одно время. Это означает, что, когда больше чем один объект пытается обратиться к критическому ресурсу, то обращение будет позволено только одному из них. Механизм предоставления должен также гарантировать, что любой запрос, в конечном счете, будет удовлетворён, то есть ни один объект не будет ждать бесконечно. Подход, использующий голосование для выбора объекта, которому предоставляют доступ, является, к сожалению, не рациональным. Это так - не только из-за стоимости, но и и из-за несправедливости подхода. Он не гарантирует, что каждый объект, желающий обратиться к ресурсу, обратится к нему (то есть, станет лидером) в конечный промежуток времени.
Это подводит нас к такой интересной непрерывной задаче, как распределенное взаимное исключение. Более точно это можно описать, используя понятие критических операций в непрерывном вычислении C. В этом понятии,
где операция может являться действием или даже целым ce,протоколом. Механизмом распределенного взаимного исключения может быть любой протокол, который гарантирует следующие два свойства:
• взаимное исключение: если объект выполняет критическую операцию, никакой другой объект не может её выполнить.
• справедливость: если объект хочет исполнить критическую операцию, он сможет это сделать в пределах конечного промежутка времени.
Далее в этом разделе мы рассмотрим проектирование эффективных протоколов с такими свойствами. В процессе проектирования, мы увидим, что есть интересная связь между проблемой распределенного взаимного исключения и проблемой управления распределенной очередью (другим непрерывным вычислением). В частности, мы увидим как любой протокол для справедливого управления распределенной очередью может использоваться, чтобы решить проблему распределенных взаимных исключений. Во всех случаях, мы будем принимать ограничения IR.
Проблема распределенного взаимного исключения имеет очень простое и эффективное централизованное решение:
"Центральный" протокол:
Первоначально, объект избран как лидер; этот объект тогда координирует предоставление разрешения следующим образом:
Последний пункт выполняется, например, при наличии лидера, хранящего ожидающие запросы в списке, упорядоченном по принципу FIFO.
Этот очень простой централизованный протокол не только корректен, но также и весьма эффективен. Фактически, для каждой критической операции, имеют место запрос от объекта лидеру; разрешение (через какое-то время), данное лидером объекту; и уведомление о завершении операции, посланное объектом обратно лидеру. Таким образом, будет 3d(x, r) сообщения для каждой операции x, которую необходимо исполнить, где r – лидер. Итак, эксплуатационные расходы "центрального" протокола будут не более, чем
3 диаметра (G)
сообщений за одну критическую операцию. Это означает, что в полном графе стоимость будет только три сообщения на критическую операцию.
Недостатки этого решения такие же, как у всех централизованных решений: не сбалансированная нагрузка; возможная необходимость хранения лидером большого количества информации; лидер является критическим параметром отказоустойчивости. Поскольку мы предполагаем абсолютную надежность, мы не будем сейчас заботиться о проблеме отказоустойчивости. Другие две проблемы, однако, являются достаточно актуальными, чтобы начать поиск децентрализованных решений.
Для создания эффективного децентрализованного протокола взаимного исключения сначала опишем механизм централизованного протокола ещё раз: в системе есть единственный "разрешающий" маркер, первоначально принадлежащий лидеру, и объект может исполнить критическую операцию, только если получают в распоряжение такой маркер. Этот факт гарантирует свойство взаимного исключения в пределах "центрального" протокола. Свойство справедливости обеспечивается "центральным" протоколом, потому что (1) решение, согласно которому объект должен получить маркер, принимается лидером, к которому маркер возвращается после того как была выполнена критическая операция, и (2), лидер применяет справедливый механизм принятия решений (например, список FIFO).
Мы можем продолжить описание взаимного исключения, используя идею маркера разрешения, и в то же время, мы выполним свойство справедливости, даже не имея лидера, а просто используя децентрализованный способ. Например, мы можем допустить, что маркер циркулирует среди всех объектов:
Протокол "непрерывного обхода":
• единственный маркер непрерывно выполняет обход сети.
• когда объект x получает маркер, то, если ему нужно исполнить критическую операцию, сделает это и после завершения операции передаст маркер дальше; иначе, он немедленно передаст маркер далее.
• если объект должен исполнить критическую операцию, он будет ждать, пока не получит маркер.
Мы подробно обсудили, как эффективно исполнить отдельный обход сети. Отметим, что полный обход может быть сделан, используя связующее дерево сети, ценой 2(n-1) сообщения за обход. Если сеть является гамильтоновой, то имеет связующий цикл, мы можем использовать этот цикл, чтобы исполнить обход, передающий только n сообщений для полного обхода.
Это используется во многих практических системах.
Какова стоимость осуществления такого протокола на одну критическую операцию? Отвечая этот вопрос, рассмотрим период времени, когда все объекты непрерывно требуют маркер; в этом случае, почти после каждого перемещения, маркер будет позволять объекту исполнять критическую операцию. Это означает,что в этой ситуации тяжелой загрузки, стоимость непрерывного обхода - только O(1) сообщение на критическую операцию. Если запросы являются немногими и нечастым, то есть имеет место легкая загрузка, количество сообщений на запрос является непредсказуемым, поскольку это зависит от времени между последовательными запросами и скоростью маркера. С практической точки зрения, это означает, что управление редко используемым ресурсом может привести к переполнению сети сообщениями.
Рассмотрим теперь период времени, когда объекты не имеют никакой потребности в выполнении критических операций; в течение всего этого времени, маркер продолжит обходить сеть, в поиске объектов, нуждающихся в нем, и не находя ни одного. Так как эта ситуация нулевой загрузки может продолжаться неопределённое время, из этого следует, что, в протоколе непрерывного обхода, количество сообщений на критическую операцию, является неограниченным!
Посмотрим, как можно исправить эту ситуацию. Рассмотрим виртуальный вызов R связанный с первоначальным обходом сети; в случае, если имеем гамильтонову сеть. Будем использовать гамильтонов цикл в качестве кольца.
В обходе, маркер двигается к R в одном направлении, назовём это направление - "вправо". Если маркер достигает объекта, который не должен выполнять критическую операцию (или только закончил её выполнение), то с целью сокращения количества передач сообщения, объект отправляет маркер по кольцу не автоматически, а только в том случае, если имеются запросы маркера, то есть если есть объекты, желающие выполнить критическую операцию.
Проблема состоит в том, как известить объект, имеющий маркер, о том, что есть объекты требующие получения маркера. Эта проблема, к счастью, решается просто: объект, который должен выполнить критическую операцию, но не владеет маркером, посылает в сеть запрос маркера; запрос проходит по кольцу в направлении противоположном движению маркера, пока не достигает объекта, владеющего маркером или объект, который также послал запрос маркера. Есть много нюансов, которые должны быть приняты во внимание, чтобы преобразовать настолько нестрогое описание в протокол, так что уточним его.
В нашем описании, каждая связь будет иметь цвет, и цвета будут меняться в зависимости от типа сообщения, согласно следующим двум правилам:
• связи могут быть или белыми, или черными; первоначально, все связи белые.
• всякий раз, когда по связи посылается запрос, эта связь становится черной; всякий раз, когда маркер посылают по связи, эта связь становится белой.
Окончательный механизм тогда определен следующим образом:
Механизм "обхода по требованию":
Таким способом, вместо простого "непрерывного обхода", мы имеем такой обход, который провоцируется запросами о маркере. Не трудно проверить, что приведенный протокол "обхода по требованию" действительно правильный, гарантирующий и взаимное исключение, и справедливость. В отличие от "непрерывного обхода", стоимость протокола "обхода по требованию" всегда ограничена. Фактически, если в системе нет никаких запросов, маркер не будет циркулировать. Другими словами, каждый обход маркера удовлетворяет как минимум запрос, возможно не один. Это означает, что в самом плохом случае, обход точно удовлетворяет один запрос; другими словами, количество движений маркера за запрос – не более n'-1, где n' - количество узлов в R. В дополнение к маркеру, протокол также использует сообщения запроса. Сообщение запроса, двигающееся в направлении противоположном движению маркера, перемещается вдоль кольца, пока не находит маркер или другой объект, ожидающий маркера. (ПРИМЕЧАНИЕ: маркер и запрос никогда не пересекаются на связи). Это значит, что запрос вызовет не более n-1 передач. Поэтому, общее количество сообщений на критическую операцию в протоколе "обход по требованию" в худшем случае
2(n' - 1) ≤ 4(n - 2).
Обратите внимание, что хоть стоимость и ограничена, она всегда больше, чем стоимость, полученная при использовании "центрального" протокола. В частности, в полном графе стоимость в наихудшем случае протокола "обхода по требованию" будет 2(n-1), в то время как в 'центральном" протоколе, как мы видели, стоимость составляет всего три сообщения.
Худший случай, фактически, не даёт оснований судить обо всём механизме. На самом деле, фактическая стоимость будет зависеть от частоты и распространенности запросов. В частности, подобно протоколу 'непрерывного обхода", чем чаще запросы и шире их распространенность, тем ближе протокол "обхода по требованию" будет к стоимости O(1) сообщения на критическую операцию. Это будет так, независимо от диаметра топологии, даже в сетях, где "центральный" протокол при тех же самых условиях мог требовать O(n) сообщения в запрос.
Мы увидели, что маркер двигается только, если в сети имеются запросы. Движения маркера, провоцируемые запросами, соответствовали непрерывному обходу по R, циклу содержащему все объекты. Если сеть - гамильтонова, мы, конечно, выбираем R как гамильтонов цикл; мы стремимся создать самый короткий такой цикл. Мы действительно знаем, что для любой сети мы можем всегда создать связующий цикл R с 2(n-1) узлами: это цикл, полученный в первый обход связующего дерева сети.