Алгоритмы взаимного исключения

Алгоритмы взаимного исключения в сетевых системах.

Взаимное исключение в сетевых системах.

Именование в сетевых системах.

Алгоритмы синхронизации часов в сетевых системах.

Вопросы согласование времени в сетевых системах.

Существует земное время (по общему соглашению). Для сетей используют всеобщее скоординированное время (UTC – universal time coordinated). Для получения UTC существуют специальные приемники, которые подсоединяются к компьютеру.

Способы получения времени:

- спутник

- радтостанция

Точность зависит от многих факторов. Для спутников существует 2службы:

1) GPS (точность 1 мкс)

2) GEOS (точность 0,1 мкс)

Радиовещание 10 мкс

К спутникам и радиостанциям подключаются серверы времени, а к ним все остальные.

Алгоритмы синхронизации часов:

Существует 2 алгоритма согласования:

- с использованием приемника UTC (сеть в идеальном случае имеет 1 UTC приемник на сервере, а остальные компьютеры подключаются к нему и опрашивают его для корректировки своих часов. Клиент корректирует свое время с учетом коммуникационной задержки).

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

Алгоритм крупномасштабной координации (пригоден для глобальных сетей). Для него существуют специальные протоколы. Для интернета это NTP (network time protocol) точность до 1—ков мс. NTP имеет трех уровневую иерархию:

1) несколько серверов с приемниками UTC каждый из них отвечает за передачу времени 2-му уровню

2) серверы путем широковещательных запросов обеспечивают доставку всем остальным

3) все остальные узлы.

Локальная ОС поддерживает имена в пределах заданного узла. Это пространство используется разными объектами.

При рассмотрении РС пространство имен должно быть расширено. Имена должны быть использованы в различных контекстах. Для каждого объекта имя должно быть уникально в том контексте, в котором оно используется.

Способы задания уникальных имен:

1) Использование уникальных идентификаторов (простой, но сложно реализовать эффективный поиск)

2) Иерархический способ наименования (уникальность имени достигается путем построения их иерархии для доменной структуры например DNS)

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

Централизованный алгоритм

Наиболее очевидный и простой путь реализации взаимного исключения в распределенных системах - это применение тех же методов, которые используются в однопроцессорных системах. Один из процессов выбирается в качестве координатора (например, процесс, выполняющийся на машине, имеющей наибольшее значение сетевого адреса). Когда какой-либо процесс хочет войти в критическую секцию, он посылает сообщение с запросом к координатору, оповещая его о том, в какую критическую секцию он хочет войти, и ждет от координатора разрешение. Если в этот момент ни один из процессов не находится в критической секции, то координатор посылает ответ с разрешением. Если же некоторый процесс уже выполняет критическую секцию, связанную с данным ресурсом, то никакой ответ не посылается; запрашивавший процесс ставится в очередь, и после освобождения критической секции ему отправляется ответ-разрешение. Этот алгоритм гарантирует взаимное исключение, но вследствие своей централизованной природы обладает низкой отказоустойчивостью.

Распределенный алгоритм

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

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

2. Если получатель уже находится в критической секции, то он не отправляет никакого ответа, а ставит запрос в очередь.

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

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

Алгоритм Token Ring

Совершенно другой подход к достижению взаимного исключения в распределенных системах иллюстрируется рисунком 3.7. Все процессы системы образуют логическое кольцо, т.е. каждый процесс знает номер своей позиции в кольце, а также номер ближайшего к нему следующего процесса. Когда кольцо инициализируется, процессу 0 передается так называемый токен. Токен циркулирует по кольцу. Он переходит от процесса n к процессу n+1 путем передачи сообщения по типу "точка-точка". Когда процесс получает токен от своего соседа, он анализирует, не требуется ли ему самому войти в критическую секцию. Если да, то процесс входит в критическую секцию. После того, как процесс выйдет из критической секции, он передает токен дальше по кольцу. Если же процесс, принявший токен от своего соседа, не заинтересован во вхождении в критическую секцию, то он сразу отправляет токен в кольцо. Следовательно, если ни один из процессов не желает входить в критическую секцию, то в этом случае токен просто циркулирует по кольцу с высокой скоростью.

Сравним эти три алгоритма взаимного исключения. Централизованный алгоритм является наиболее простым и наиболее эффективным. При его использовании требуется только три сообщения для того, чтобы процесс вошел и покинул критическую секцию: запрос и сообщение-разрешение для входа и сообщение об освобождении ресурса при выходе. При использовании распределенного алгоритма для одного использования критической секции требуется послать (n-1) сообщений-запросов (где n - число процессов) - по одному на каждый процесс и получить (n-1) сообщений-разрешений, то есть всего необходимо 2(n-1) сообщений. В алгоритме Token Ring число сообщений переменно: от 1 в случае, если каждый процесс входил в критическую секцию, до бесконечно большого числа, при циркуляции токена по кольцу, в котором ни один процесс не входил в критическую секцию.

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

Дата добавления: 2014-01-20