1 Операционные системы и оболочки Одинцов Игорь Олегович ст. преподаватель кафедры информатики весна 2006 Слайды можно взять на сайтах: и

2 Лекция 7 Процессы и алгоритмы работы с ними в сетевых и распределенных ОС (продолжение)

3 Что надо знать о процессах? Средства коммуникации Средства синхронизации Проблема тупиков Планирование ИзучилиИзучаем Изучаем сетевые и распределенные ОС

4 Протоколы TCP/IP Уровень приложений (эквивалентен 5, 6 и 7-му уровням в модели ВОС) FTP, SMTP, TELNET, NFS (перечень файлов, электронная почта, терминал) Транспортный уровень (эквивалентен 4-му уровню в модели ВОС) ТСР, UDP Уровень Интернета (эквивалентен 3-му уровню в модели ВОС) IP Уровень сетевого протокола (эквивалентен 1 и 2 уровням в модели ВОС) Ethernet, Token ring Было на предыдущей лекции

5 План лекции Коммуникация процессов: низкоуровневые средства (роль уровневых протоколов и семиуровневой модели, стек TCP/IP, адресация и маршрутизация) Коммуникация процессов: высокоуровневые средства (удаленный вызов процедуры, коммуникации в группах) Синхронизация процессов: низкоуровневые средства (роль координатора, централизованный алгоритм, алгоритм с круговым маркером) Синхронизация процессов: высокоуровневые средства (атомарные транзакции и двухфазный протокол утверждения) Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Сетевые и распределенные ОС

6 Механизмы обеспечения коммуникации Средства коммуникации Низкоуровневые Создание коммуникационных узлов Высокоуровневые Удаленный вызов процедуры Коммуникации в группах Сетевые и распределенные ОС

7 Удаленный вызов процедур Удаленный вызов процедур (Remote Procedure Call RPC) основан на том, что процесс, исполняющийся на одном компьютере, запускает процесс на удаленном компьютере. Фактически осуществляется вызов процедуры, которая реально находится и поддерживается на другом компьютере. Удаленный вызов внешне очень похож на локальный вызов, но в нем существенно отличаются действия по передаче параметров и получению результата.

8 Действия могут быть описаны следующим образом Программа-клиент производит локальный вызов процедуры, называемой "заглушкой", при этом клиенту кажется, что, вызывая "заглушку", он на самом деле вызывает процедуру сервера. В действительности, задача "заглушки" принять аргументы, адресуемые вызываемой процедуре, преобразовать их в некоторый формат и сформировать сетевой запрос. Сетевой запрос пересылается по сети на удаленную систему, при этом, например, используется стек протоколов TCP/IP. На сервере все происходит в обратном порядке: "заглушка" сервера ожидает запрос и при его получении извлекает из него параметры. "Заглушка" сервера выполняет вызов настоящей процедуры (которой адресован запрос клиента), передавая ей нужные параметры. После выполнения процедуры при передаче результатов ее работы управление опять возвращается в "заглушку" сервера, которая формирует сообщение-отклик. Отклик передается клиенту. Отклик принимается "заглушкой" клиента, которая извлекает необходимые данные и передает их программе. Процесс завершен.

9 RPC как далекий предок грид Grid computing (распределенные вычисления) Суть: объединить вычислительные ресурсы серверов, память, сети в одну большую систему с целью предоставить всю мощь этих ресурсов пользователю для решения вычислительных задач. Цель: виртуализация ресурсов для решения проблем. Важная характеристика: эффективность и оптимальное использование ресурсов. Технический базис: Grid Services базируются на Web Services /* а Web Services == RPC посредством XML */

10 Дополнительные возможности грид Grid – это новая инфраструктура, которая обеспечивает потребности индустрии в высокопроизводительных вычислениях и хранении данных. Безопас ность Использование распределенных ресурсов Аппаратура и ПО Надежность Открытые стандарты Равномерная загрузка Однократная регистрация

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

12 Коммуникации в группах

13 План лекции Коммуникация процессов: низкоуровневые средства (роль уровневых протоколов и семиуровневой модели, стек TCP/IP, адресация и маршрутизация) Коммуникация процессов: высокоуровневые средства (удаленный вызов процедуры, коммуникации в группах) Синхронизация процессов: низкоуровневые средства (роль координатора, централизованный алгоритм, алгоритм с круговым маркером) Синхронизация процессов: высокоуровневые средства (атомарные транзакции и двухфазный протокол утверждения) Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Сетевые и распределенные ОС

14 Основные подходы к синхронизации В традиционных архитектурах синхронизация выполнялась через общий для всех процессов участок. Синхронизация в распределенных системах использует децентрализованные алгоритмы и становится гораздо более сложной, чем в централизованных. Такие алгоритмы обладают, как правило, следующими свойствами: относящаяся к делу информация распределена между множеством компьютеров; процессы принимают решения только на основе локальной информации; не должно быть единой критической точки, выход из которой приводил бы к краху алгоритма; не существует общих часов или другого источника точного глобального времени. Первые три свойства говорят о том, что недопустимо собирать всю необходимую информацию для принятия решения в одном месте.

15 Алгоритм Лампорта Абсолютной синхронизации не требуется, т. е. если два процесса не взаимодействуют, то единого времени и не требуется. Процессам достаточно иметь согласованное (логическое) время. Лампорт вводит специальный предикат "произошло до": А>В означает, что "событие А произошло до события В". Это соотношение очевидно в двух случаях: если оба события произошли в одном процессе; если событие А есть операция посылки сообщения одним процессом, а событие В прием этого сообщения другим процессом. Если два события случились в разных процессах, которые не обмениваются сообщениями, то соотношения А>В, В>А являются неверными, а события А и В одновременными. Введем логическое время C, которое будем определять таким образом: если А>В, то С(А) < С(В). Часы Сi увеличивают свое значение с каждым событием в процессе Pi следующим образом: Ci = Ci + d, где d > 0 и обычно d = 1. Если событие a есть посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm = Ci(a), и в момент получения этого сообщения процессом Pj его время корректируется таким образом: Cj = max(Cj, tm + d).

16 Выборы координатора Очень многие алгоритмы в распределенных системах требуют наличия координатора одного из процессов, который должен выполнять специальные функции по инициации, координации или решению других задач. Широковещательный алгоритм выбора Один из процессов, обнаруживший отсутствие координатора, инициирует алгоритм выбора: процесс посылает свое сообщение всем процессам с номером, бОльшим чем у него "а не избрать ли нам координатора?"; процессы с большими номерами отвечают инициатору, и его участие в выборах заканчивается. Эти процессы посылают сообщения "а не избрать ли нам координатора?" процессам с еще бОльшими номерами; в конце алгоритма останется один процесс, который не дождется ответа. Он и объявляет себя координатором. Круговой алгоритм выбора Круговой алгоритм использует физическое или логическое кольцо без маркера. При этом каждый процесс знает следующего за ним в круговом списке. Когда какой-либо из процессов обнаруживает отсутствие координатора, он посылает следующему за ним сообщение "а не избрать ли нам координатора?" и указывает свой номер. Если следующий не отвечает, то сообщение посылается процессу, идущему за ним. Каждый процесс добавляет в список свой номер. Рано или поздно список вернется процессу, инициировавшему выборы. Он посылает новое сообщение, в котором извещает о том, что он стал новым координатором, и указывает свой номер.

17 Механизмы обеспечения синхронизации Средства синхронизации Низкоуровневые Централизованный алгоритм Алгоритм с круговым маркером Высокоуровневые Атомарные транзакции Двухфазный протокол утверждения Сетевые и распределенные ОС

18 Низкоуровневые средства синхронизации Централизованный алгоритм Все процессы запрашивают у координатора разрешения на вход в критическую секцию и ждут разрешения. Координатор обслуживает запросы в порядке их поступления. Получив разрешение координатора, процесс входит в критическую секцию. Завершив работу, процесс докладывает об этом координатору. Алгоритм с круговым маркером Все процессы образуют логическое кольцо, при этом каждый знает, кто следует за ним. По кольцу циркулирует маркер, дающий право на критическую секцию. Получив маркер, процесс либо входит в критическую секцию, держа маркер у себя, либо перенаправляет маркер дальше, если ему не нужна критическая секция. Дважды подряд входить в критическую секцию, не отдавая маркер, нельзя.

19 План лекции Коммуникация процессов: низкоуровневые средства (роль уровневых протоколов и семиуровневой модели, стек TCP/IP, адресация и маршрутизация) Коммуникация процессов: высокоуровневые средства (удаленный вызов процедуры, коммуникации в группах) Синхронизация процессов: низкоуровневые средства (роль координатора, централизованный алгоритм, алгоритм с круговым маркером) Синхронизация процессов: высокоуровневые средства (атомарные транзакции и двухфазный протокол утверждения) Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Сетевые и распределенные ОС

20 Атомарные транзакции Атомарные транзакции это высокоуровневые средства синхронизации, представляющие логические единицы работы. Логическая единица работы, как правило, является согласованием ряда операций. Система, поддерживающая процесс транзакции, гарантирует, что если во время выполнения некоторых операций произошла ошибка, то все обновления будут аннулированы. В результате транзакция либо полностью выполняется, либо полностью отменяется. Транзакции пришли в программирование из области деловых отношений, когда переговоры могут вернуться к своему начальному состоянию в любой момент до заключения соглашения. Транзакции обеспечиваются администратором транзакций с помощью следующих операторов: BEGIN_TRANSACTION объявляет начало транзакций; END_TRANSACTION объявляет успешное завершение транзакции и утверждает ее; ABORT_TRANSACTION указывает на неудачное завершение транзакции, в результате чего все изменения должны быть отменены, и восстанавливает начальные значения; READ служит для чтения данных; WRITE служит для записи данных.

21 Реализация и свойства транзакций Существуют два основных метода поддержки реализации транзакций: метод собственного пространства транзакции. Все действия ведутся в собственном "частном" пространстве транзакции. Изменения попадут в "реальное" пространство только в случае успешного завершения транзакции; метод протоколирования списка действий. Все действия протоколируются в специальном списке, называемом "лист намерений". При изменении значения каждой переменной в список заносится имя переменной, а также ее начальное и конечное значения. Транзакции обладают четырьмя важными свойствами: атомарность. С точки зрения окружающего мира транзакция выглядит единой и неделимой. Выполняется либо все, либо ничего; постоянство (согласованность). Если в системе есть некоторые инварианты и если они существовали до выполнения транзакции, то они должны остаться и после ее выполнения. Одно согласованное состояние переводится в другое. Обязательной поддержки согласованности в промежуточных точках нет; сериализация (изоляция). Транзакции отделены одна от другой и преобразуются в последовательную форму. Если существует несколько транзакций, выполняющихся параллельно, то они должны выглядеть так, как если бы они выполнялись последовательно; прочность (долговечность). Если транзакция завершена, то ее результаты надежно вписываются в состояние системы. Даже если в следующий момент произойдет сбой системы.

22 Двухфазный протокол утверждения Двухфазный протокол утверждения важен в тех случаях, когда транзакция может взаимодействовать с несколькими независимыми администраторами ресурсов. Каждый из них руководит своим собственным набором восстанавливаемых ресурсов и поддерживает собственный файл регистрации. Для транзакции не имеет смысла выполнять оператор завершения отдельно для каждого из администраторов ресурсов. Вместо этого должна быть выполнена единая общесистемная команда END_TRANSACTION или ABORT_TRANSACTION. Рассмотрим пример работы координатора. Пусть транзакция успешно завершена и ее нужно утвердить. Координатор осуществляет двухфазный процесс. Координатор записывает в протокол "транзакция готова к утверждению". Координируемые процессы, получив сообщение, записывают в свой протокол "готов к транзакции" и отсылают координатору сообщение "готов". Координатор в конце первой фазы собирает все сообщения о готовности. Когда все ответы собраны, координатор записывает в протокол "транзакция утверждена" и рассылает всем процессам сообщение "транзакция утверждена". Координируемые процессы, получив сообщение, записывают в свой протокол "транзакция утверждена" и отсылают координатору "готов". Если все ответы во время первой фазы собрать не удалось или хотя бы один из ответов содержит отказ от транзакции, то координатор дает команду ABORT_TRANSACTION.

23 План лекции Коммуникация процессов: низкоуровневые средства (роль уровневых протоколов и семиуровневой модели, стек TCP/IP, адресация и маршрутизация) Коммуникация процессов: высокоуровневые средства (удаленный вызов процедуры, коммуникации в группах) Синхронизация процессов: низкоуровневые средства (роль координатора, централизованный алгоритм, алгоритм с круговым маркером) Синхронизация процессов: высокоуровневые средства (атомарные транзакции и двухфазный протокол утверждения) Процессы и ресурсы: проблема тупиков Планирование и диспетчеризация процессов Сетевые и распределенные ОС

24 Тупики в распределенных системах Подобны тупикам в централизованных системах, только их еще сложнее обнаруживать и предотвращать. Стратегии, применяемые при борьбе с тупиками, таковы: Полное игнорирование проблемы ("алгоритм страуса"). Этот подход в распределенных системах так же популярен, как и в централизованных Обнаружение тупиков. Для этого существует два основных метода: централизованное обнаружение тупиков заключается в распространении идеи графа распределения ресурсов на распределенную систему. Координатор строит единый граф для всех узлов системы и на нем выполняет редукцию (приведение) распределенное обнаружение тупиков. В этом методе инициирование задачи обнаружения тупика начинает процесс, который подозревает, что система находится в тупике. Он посылает тем процессам, которые держат нужный ему ресурс, сообщение из трех информационных полей. Первое поле содержит номер процесса, инициировавшего поиск, и оно не меняется при дальнейшей пересылке. Второе и третье поля содержат соответственно номер процесса, который зависит от ресурса, и номер процесса, который держит этот ресурс. Если, в конце концов, сообщение вернется к тому процессу, который инициировал поиск, то он приходит к выводу, что система зациклена и он должен предпринять действия по ликвидации тупика Предотвращение тупиков в распределенных системах базируется на идее упорядочивания процессов по их временным меткам. Допустимой будет ситуация, когда "старший" процесс ждет ресурсы, которые захватил "младший" процесс. В обратном случае "младший" процесс должен отказаться от ожидания.

25 Спасибо! Вопросы?

26 P.S. Экзаменационные вопросы: Коммуникация процессов: высокоуровневые средства (удаленный вызов процедуры, коммуникации в группах) Синхронизация процессов: низкоуровневые средства (роль координатора, централизованный алгоритм, алгоритм с круговым маркером) Синхронизация процессов: алгоритм Лампорта; высокоуровневые средства (атомарные транзакции и двухфазный протокол утверждения) Процессы и ресурсы: проблема тупиков