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

Существует два типа распределенных операционных систем. Мультипроцессорная операционная система (multiprocessor operating system) управляет ресурсами мультипроцессора. Мулътикомпьютерная операционная система (multicomputer operating system) разрабатывается для гомогенных мультикомпыотеров. Функциональность распределенных операционных систем в основном не отличается от функциональности традиционных операционных систем, предназначенных для компьютеров с одним процессором за исключением того, что она поддерживает функционирование нескольких процессоров. Поэтому давайте кратко обсудим операционные системы, предназначенные для обыкновенных компьютеров с одним процессором.

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

Операционные системы традиционно строились для управления компьютерами с одним процессором. Основной задачей этих систем была организация легкого доступа пользователей и приложений к разделяемым устройствам, таким как процессор, память, диски и периферийные устройства. Говоря о разделении ресурсов, мы имеем в виду возможность использования одного и того же аппаратного обеспечения различными приложениями изолированно друг от друга. Для приложения это выглядит так, словно эти ресурсы находятся в его полном распоряжении, при этом в одной системе может выполняться одновременно несколько приложений, каждое со своим собственным набором ресурсов. В этом смысле говорят, что операционная система реализует виртуальную машину (virtual machine), предоставляя приложениям средства мультизадачности. Важным аспектом совместного использования ресурсов в такой виртуальной машине является то, что приложения отделены друг от друга. Так, невозможна ситуация, когда при одновременном исполнении двух приложений,A и B, приложение A может изменить данные приложения B, просто работая с той частью общей памяти, где эти данные хранятся. Также требуется гарантировать, что приложения смогут использовать предоставленные им средства только так, как предписано операционной системой. Например, приложениям обычно запрещено копировать сообщения прямо в сетевой интерфейс. Взамен операционная система предоставляет первичные операции связи, которые можно использовать для пересылки сообщений между приложениями на различных машинах. Следовательно, операционная система должна полностью контролировать использование и распределение аппаратных ресурсов. Поэтому большинство процессоров поддерживают как минимум два режима работы. В режиме ядра (kernel

mode) выполняются все разрешенные инструкции, а в ходе выполнения доступна вся имеющаяся память и любые регистры. Напротив, в пользовательском режиме (user mode) доступ к регистрам и памяти ограничен. Так, приложению не будет позволено работать с памятью за пределами набора адресов, установленного для него операционной системой, или обращаться напрямую к регистрам устройств. На время выполнения кода операционной системы процессор переключается в режим ядра. Однако единственный способ перейти из пользовательского режима в режим ядра — это сделать системный вызов, реализуемый через операционную систему. Поскольку системные вызовы — это лишь базовые службы, предоставляемые операционной системой, и поскольку ограничение доступа к памяти и регистрам нередко реализуется аппаратно, операционная система в состоянии полностью их контролировать. Существование двух режимов работы привело к такой организации операционных систем, при которой практически весь их код выполняется в режиме ядра. Результатом часто становятся гигантские монолитные программы, работающие в едином адресном пространстве. Оборотная сторона такого подхода состоит в том, что перенастроить систему часто бывает нелегко. Другими словами, заменить или адаптировать компоненты операционной системы без полной перезагрузки, а возможно и полной перекомпиляции и новой установки очень трудно. С точки зрения открытости, проектирования программ, надежности или легкости обслуживания монолитные операционные системы — это не самая лучшая из идей. Более удобен вариант с организацией операционной системы в виде двух частей. Одна часть содержит набор модулей для управления аппаратным обеспечением, которые прекрасно могут выполняться в пользовательском режиме. Например, управление памятью состоит в основном из отслеживания, какие блоки памяти выделены под процессы, а какие свободны. Единственный момент, когда мы нуждаемся в работе в режиме ядра, — это установка регистров блока управления памятью.

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

Рис. 1.8. Разделение приложений в операционной системе посредством микроядра

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

У микроядер имеется два существенных недостатка. Во-первых, они работают иначе, чем существующие операционные системы, а попытки поменять сложившееся «статус-кво» всегда встречают активное сопротивление («если эта операционная система подходила для моего деда — она подойдет и для меня»). Во-вторых, микроядро требует дополнительного обмена, что слегка снижает производительность. Однако, зная как быстры современные процессоры, снижение производительности в 20 % вряд ли можно считать фатальным.

Мультипроцессорные операционные системы

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

Однако многие операционные системы, особенно предназначенные для персональных компьютеров и рабочих станций, не могут с легкостью поддерживать несколько процессоров. Основная причина такого поведения состоит в том, что они были разработаны как монолитные программы, которые могут выполняться только в одном потоке управления. Адаптация таких операционных систем под мультипроцессорные означает повторное проектирование и новую реализацию всего ядра. Современные операционные системы изначально разрабатываются с учетом возможности работы в мультипроцессорных системах. Многопроцессорные операционные системы нацелены на поддержание высокой производительности конфигураций с несколькими процессорами. Основная их задача — обеспечить прозрачность числа процессоров для приложения. Сделать это достаточно легко, поскольку сообщение между различными приложениями или их частями требует тех же примитивов, что и в многозадачных однопроцессорных операционных системах. Идея состоит в том, что все сообщение происходит путем работы с данными в специальной совместно используемой области данных, и все что нам нужно — это защитить данные от одновременного доступа к ним. Защита осуществляется посредством примитивов синхронизации. Два наиболее важных (и эквивалентных) примитива — это семафоры и мониторы. Семафор (semaphore) может быть представлен в виде целого числа, поддерживающего две операции: up (увеличить) и down (уменьшить). При уменьшении сначала проверяется, превышает ли значение семафора 0. Если это так, его значение уменьшается и выполнение процесса продолжается. Если же значение семафора нулевое, вызывающий процесс блокируется. Оператор увеличения совершает противоположное действие. Сначала он проверяет все заблокированные в настоящее время процессы, которые были неспособны завершиться в ходе предыдущей операции уменьшения. Если таковые существуют, он разблокирует один из них и продолжает работу. В противном случае он просто увеличивает счетчик семафора. Разблокированный процесс выполняется до вызова операции уменьшения. Важным свойством операций с семафорами является то, что они атомарны {atomic), то есть в случае запуска операции уменьшения или увеличения до момента ее завершения (или до момента блокировки процесса) никакой другой процесс не может получить доступ к семафору.

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

Формально монитор (monitor) представляет собой конструкцию языка программирования, такую же, как объект в объектно-ориентированном программировании. Монитор может рассматриваться как модуль, содержащий переменные и процедуры. Доступ к переменным можно получить только путем вызова одной из процедур монитора. В этом смысле монитор очень похож на объект. Объект также имеет свои защищенные данные, доступ к которым можно получить только через методы, реализованные в этом объекте. Разница между мониторами и объектами состоит в том, что монитор разрешает выполнение процедуры только одному процессу в каждый момент времени. Другими словами, если процедура, содержащаяся в мониторе, выполняется процессом A (мы говорим, что A вошел в монитор) и процесс B также вызывает одну из процедур монитора, B будет блокирован до завершения выполнения A (то есть до тех пор, пока A не покинет монитор). В качестве примера рассмотрим простой монитор для защиты целой переменной (листинг 1.1). Монитор содержит одну закрытую (private) переменную count, доступ к которой можно получить только через три открытых (public) процедуры — чтения текущего значения, увеличения на единицу и уменьшения. Конструкция монитора гарантирует, что любой процесс, который вызывает одну из этих процедур, получит атомарный доступ к внутренним данным монитора.

Листинг 1.1. Монитор, предохраняющий целое число от параллельного доступа

monitor Counter {

private:

int count = 0;

public:

int value() { return count; }

void incr() { count = count + 1;}

void decr() { count = count - 1;}

}

Итак, мониторы пригодны для простой защиты совместно используемых данных. Однако для условной блокировки процесса необходимо большее. Например, предположим, нам нужно заблокировать процесс при вызове операции уменьшения, если обнаруживается, что значение count равно нулю. Для этой цели в мониторах используются условные переменные (condition variables). Это специальные переменные с двумя доступными операциями: wait (ждать) и signal (сигнализировать). Когда процесс A находится в мониторе и вызывает для условной переменной, хранящейся в мониторе, операцию wait, процесс A будет заблокирован и откажется от своего исключительного доступа к монитору. Соответственно, процесс B, ожидавший получения исключительного доступа к монитору, сможет продолжить свою работу. В определенный момент времени B может разблокировать процесс A вызовом операции signal для условной переменной, которого ожидает A. Чтобы предотвратить наличие двух активных процессов внутри монитора, мы доработаем схему так, чтобы процесс, подавший сигнал, покидал монитор. Теперь мы можем переделать наш предыдущий пример. Монитор из листинга 1.2 — это новая реализация обсуждавшегося ранее семафора.

Листинг 1.2. Монитор, предохраняющий целое число от параллельного доступа и блокирующий процесс

monitor Counter {

private:

int count = 0;

int blockecl_procs = 0;

condition unblocked;

public:

int value() { return count;}

void incr() {

if (blockecl_procs == 0)

count = count + 1;

else

signal(unblocked);

}

void decr() {

if (count == 0) {

blocked_procs = blocked_procs + 1;

wait(unblocked);

blocked_procs = blocked_procs - 1;

}

else

count = count – 1;

}

}

Оборотная сторона мониторов состоит в том, что они являются конструкциями языка программирования. Так, Java поддерживает мониторы, просто разрешая каждому объекту предохранять себя от параллельного доступа путем использования в нем инструкции synchronized и операций wait и notify. Библиотечная поддержка мониторов обычно реализуется на базе простых семафоров, которые могут принимать только значения 0 и 1. Такие семафоры часто называются переменными - мъютексами (mutex variables), или просто мьютексами. С мьютексами ассоциируются операции lock (блокировать) и unlock (разблокировать). Захват мьютекса возможен только в том случае, если его значение равно единице, в противном случае вызывающий процесс будет блокирован. Соответственно, освобождение мьютекса означает установку его значения в 1, если нет необходимости разблокировать какой-нибудь из ожидающих процессов. Условные переменные и соответствующие им операции также поставляются в виде библиотечных процедур

Мультикомпьютерные операционные системы

Мультикомпьютерные операционные системы обладают гораздо более разнообразной структурой и значительно сложнее, чем мультипроцессорные. Эта разница проистекает из того факта, что структуры данных, необходимые для управления системными ресурсами, не должны больше отвечать условию легкости совместного использования, поскольку их не нужно помещать в физически общую память. Единственно возможным видом связи является передача сообщений (message passing). Мультикомпьютерные операционные системы в основном организованы так, как показано на рис. 1.9. Каждый узел имеет свое ядро, которое содержит модули для управления локальными ресурсами — памятью, локальным процессором, локальными дисками и т. д. Кроме того, каждый узел имеет отдельный модуль для межпроцессорного взаимодействия, то есть посылки сообщений на другие узлы и приема сообщений от них.

Рис. 1.9. Общая структура мультикомпьютерных операционных систем

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

Рис. 1.10. Возможности блокировки и буферизации при пересылке сообщений

Существует всего два возможных места буферизации сообщений — на стороне отправителя или на стороне получателя. Это приводит к четырем возможным точкам синхронизации, то есть точкам возможной блокировки отправителя или получателя. Если буферизация происходит на стороне отправителя, это дает возможность заблокировать отправителя, только если его буфер полон, что показано точкой синхронизации S1 на рисунке. С другой стороны, процедура помещения сообщения в буфер может возвращать состояние, показывающее, что операция успешно выполнена. Это позволяет отправителю избежать блокировки по причине переполнения буфера. Если же отправитель ие имеет буфера, существует три альтернативных точки блокировки отправителя: отправление сообщения (точка S2), поступление сообщения к получателю (точка S3 ), принятие сообщения получателем (точка S4). Отметим, что если блокировка происходит в точке S2, S3 или S4, наличие или отсутствие буфера на стороне отправителя не имеет никакого значения.

Блокировка получателя имеет смысл только в точке синхронизации S3 и может производиться, только если у получателя нет буфера или если буфер пуст. Альтернативой может быть опрос получателем наличия входящих сообщений. Однако эти действия часто ведут к пустой трате процессорного времени или слишком запоздалой реакции на пришедшее сообщение, что, в свою очередь, приводит к переполнению буфера входящими сообщениями и их потере. Другой момент, важный для понимания семантики обмена сообщениями, — надежность связи. Отличительной чертой надежной связи является получение отправителем гарантии приема сообщения. На рис. 1.10 надежность связи означает, что все сообщения гарантированно достигают точки синхронизации S3. При ненадежной связи всякие гарантии отсутствуют. Если буферизация производится на стороне отправителя, о надежности связи ничего определенного сказать нельзя. Также операционная система не нуждается в гарантированно надежной связи в случае блокировки отправителя в точке S2. С другой стороны, если операционная система блокирует отправителя до достижения сообщением точки S3 или S4, она должна иметь гарантированно надежную связь. В противном случае мы можем оказаться в ситуации, когда отправитель ждет подтверждения получения, а сообщение было потеряно при передаче. Отношение между блокировкой, буферизацией и гарантиями относительно надежности связи суммированы в табл. 1.4.

Таблица 1.4. Соотношение между блокировкой, буферизацией и надежностью связи

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

Системы с распределенной разделяемой памятью

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

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

Один из распространенных подходов — задействовать виртуальную память каждого отдельного узла для поддержки общего виртуального адресного пространства. Это приводит нас к распределенной разделяемой памяти (Distributed Shared Memory, DSM) со страничной организацией. Принцип работы этой памяти следующий. В системе с DSM адресное пространство разделено на страницы (обычно по 4 или по 8 Кбайт), распределенные по всем процессорам системы. Когда процессор адресуется к памяти, которая не является локальной, происходит внутреннее прерывание, операционная система считывает в локальную память страницу, содержащую указанный адрес, и перезапускает выполнение вызвавшей прерывание инструкции, которая теперь успешно выполняется. Этот подход продемонстрирован на рис. 1.11, а для адресного пространства из 16 страниц и четырех процессоров. Это вполне нормальная страничная организация, если не считать того, что в качестве временного хранилища информации используется не диск, а удаленная оперативная память. В этом примере при обращении процессора 1 к коду или данным со страницы 0, 2, 5 или 9 обращение происходит локально. Ссылки на другие страницы вызывают внутреннее прерывание. Так, например, ссылка на адрес со страницы 10 вызывает внутреннее прерывание операционной системы, и она перемещает страницу 10 с машины 2 на машину 1, как показано на рис. 1.11, б. Одно из улучшений базовой системы, часто позволяющее значительно повысить ее производительность, — это репликация страниц, которые объявляются закрытыми на запись, например, страниц, содержащих текст программы, константы «только для чтения» или другие закрытые на запись структуры. Например, если страница 10 — это секция текста программы, ее использование процессором 1 приведет к пересылке процессору 1 ее копии, а оригинал в памяти процессора 2 будет продолжать спокойно храниться, как показано на рис. 1.11, в. В этом случае процессоры 1 и 2 оба смогут обращаться к странице 10 так часто, как им понадобится, не вызывая при этом никаких внутренних прерываний для выборки памяти.

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

Другая возможность — это репликация также и не закрытых на запись страниц, то есть любых страниц. Пока производится только чтение, никакой разницы между репликацией закрытых и незакрытых на запись страниц нет. Однако если реплицированная страница внезапно изменяется, необходимо предпринимать специальные действия для предотвращения появления множества несовместимых копий. Обычно все копии, кроме одной, перед проведением записи объявляются неверными. Дополнительного увеличения производительности можно добиться путем ухода от строгого соответствия между реплицируемыми страницами. Другими словами, мы позволяем отдельной копии временно отличаться от других. Практика показывает, что этот подход действительно может помочь, но, к сожалению, может также сильно осложнить жизнь программиста, вынужденного в этом случае отслеживать возможную несовместимость. Поскольку основной причиной разработки DSM была простота программирования, ослабление соответствия не находит реального применения.

Другой проблемой при разработке эффективных систем DSM является вопрос о размере страниц. Мы сталкивались с подобным выбором, когда рассматривали вопрос размера страниц в однопроцессорной системе с виртуальной памятью. Так, затраты на передачу страницы по сети в первую очередь определяются затратами на подготовку к передаче, а не объемом передаваемых данных. Соответственно, большой размер страниц может снизить общее число сеансов передачи при необходимости доступа к большому количеству последовательных элементов данных. С другой стороны, если страница содержит данные двух независимых процессов, выполняющихся на разных процессорах, операционная система будет вынуждена постоянно пересылать эту страницу от одного процессора к другому, как показано на рис. 1.12. Размещению данных двух независимых процессов на одной странице называется ошибочным разделением (false sharing).

Рис. 1.12. Ошибочное разделение страницы двумя независимыми процессами

После почти 15 лет исследований распределенной памяти совместного использования разработчики DSM продолжают добиваться сочетания эффективности и легкости программирования. Для достижения высокой производительности крупномасштабных мультикомпьютерных систем программисты прибегают к пересылке сообщений, невзирая на ее высокую, по сравнению с программированием систем (виртуальной) памяти совместного использования, сложность. Это позволяет нам сделать вывод о том, что DSM не оправдывает наших ожиданий для высокопроизводительного параллельного программирования.

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