[29.09.11] Лекция №5 (1061259)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №5 [29.09.11]

Организация взаимного исключения в распределённых системах

Три основных алгоритма реализации взаимного исключения:

1) централизованный – основан на управлении доступом к критическому ресурсу посредством координирующего сервера. Есть процесс-координатор.

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

Алгоритм прост в реализации, экономичен в количестве сообщений, но если система масштабная, то координатор становится узким местом.

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

Если ресурс не нужен никому, то маркер будет мотаться по кольцу бесконечно. А ещё маркер можно потерять.

3) распределённый алгоритм – FIFO. Когда процесс желает войти в критический интервал, он отправляет всем процессам, включая себя, сообщение с запросом ресурса. Сообщение упорядочивается по отметкам времени (потому что одновременно может быть несколько запросов). Получив сообщение с запросом, процесс может либо немедленно ответить на него, либо отложить отправку ответа: если он находится в критическом интервале, то он не отвечает, задерживает ответ до освобождения, а если не находится, то отправляет сразу.

Если он намерен войти в критический интервал, но не вошёл ещё, то он сравнивает временные отметки. И если обнаруживает, что есть метки раньше его, то он немедленно отвечает, а если нет – занимает ресурс. Процесс, получивший ответы от всех остальных процессов, может войти в интервал. А после выхода из него он отвечает на те запросы, отправка которых была задержана.

Здесь узкими местами могут быть все узлы системы.

Взаимоблокировка в распределённых системах

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

Два типа взаимоблокировки:

1) в связи с распределением ресурсов – когда процесс пытается получить доступ к ресурсам, которые находятся на другом узле сети. При этом образуется группа процессов, располагающихся на различных узлах сети, которые пытаются получить доступ к ресурсу на сервере, например.

2) возникающая при обмене сообщениями.

Условия возникновения блокировки:

1) взаимоисключение – когда одновременно использовать критический ресурс может только один процесс;

2) удержание и ожидание – когда процесс удерживает все выданные ему ресурсы и не освобождает;

3) отсутствие перераспределения – ресурс не может быть принудительно отнят у процесса;

4) образуется замкнутая цепь запросов (процессов), каждый из которых удерживает как минимум один ресурс, необходимый следующему процессу в сети;

Также есть фиктивная (фантомная, ложная) блокировка:

(1) три процесса, у каждого по ресурсу.

(2) P3 освобождает ресурс r3 и запрашивает ресурс r1. Замкнутой цепочки нет.

(3) P3 сначала запрашивает r1, но r3 ещё не освободил – тогда блокировка, замкнутая цепь запросов. Однако, это не будет являться взаимоблокировкой, потому что P3 всё-таки освободит ресурс r3. Как-то так.

Методы избежания взаимоблокировок:

1) метод иерархического (линейного) упорядочивания ресурсов – освобождение ресурсов предыдущего уровня или разрешение получения ресурса процессом только после того, как он использовал предыдущий. Не всегда можно использовать ресурсы только в линейном порядке;

2) использование временных меток. Ликвидируется условие кругового ожидания.

Выявление взаимоблокировок:

1) если централизованное управление, то выявление реализуется на одном узле;

2) иерархическое управление – узлы организованы в древовидную структуру: один корень, остальные подчинены.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций