OS49-11 (В.А. Крюков - Электронные лекции)

6 Распределенная общая память (DSM - Distributed Shared Memory).

Традиционно распределенные вычисления базируются на модели передачи сообщений, в которой данные передаются от процессора к процессору в виде сообщений. Удаленный вызов процедур фактически является той же самой моделью (или очень близкой).

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

6.1 Достоинства DSM.

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

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

(3) Объем суммарной физической памяти всех узлов может быть огромным. Эта огромная память становится доступна приложению без издержек, связанных в традиционных системах с дисковыми обменами. Это достоинство становится все весомее в связи с тем, что скорости процессоров растут быстрее скоростей памяти и в то же время появляются очень быстрые коммуникации.

(4) DSM-системы могут наращиваться практически беспредельно в отличие от систем с разделяемой памятью, т.е. являются масштабируемыми.

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

По существу, DSM-системы преодолевают архитектурные ограничения мультипроцессоров и сокращают усилия, необходимые для написания программ для распределенных систем. Обычно они реализуются программно-аппаратными средствами, но в последние годы появилось несколько коммерческих MPP с DSM, реализованной аппаратно (Convex SPP, KSR1).

6.2 Алгоритмы реализации DSM.

При реализации DSM центральными являются следующие вопросы.

1. как поддерживать информацию о расположении удаленных данных.

2. как снизить при доступе к удаленным данным коммуникационные задержки и большие накладные расходы, связанные с выполнением коммуникационных протоколов.

3. как сделать разделяемые данные доступными одновременно на нескольких узлах для того, чтобы повысить производительность системы.

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

6.2.1 Алгоритм с центральным сервером.

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

Алгоритм прост в реализации, но сервер может стать узким местом.

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

6.2.2 Миграционный алгоритм.

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

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

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

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

6.2.3 Алгоритм размножения для чтения.

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

При использовании такого алгоритма требуется отслеживать расположение всех блоков данных и их копий. Например, каждый собственник блока может отслеживать расположение его копий.

Данный алгоритм может снизить среднюю стоимость доступа по чтению тогда, когда количество чтений значительно превышает количество записей.

6.2.4 Алгоритм полного размножения.

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

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

Все перечисленные алгоритмы являются неэффективными. Добиться эффективности можно только изменив семантику обращений к памяти.

6.3 Модели консистентности.

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

6.3.1 Строгая консистентность.

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

Все однопроцессорные системы обеспечивают строгую консистентность, но в распределенных многопроцессорных системах ситуация намного сложнее. Предположим, что переменная X расположена в памяти машины B, и процесс, который выполняется на машине A, пытается прочитать значение этой переменной в момент времени T1. Для этого машине B посылается запрос переменной X. Немного позже, в момент времени T2, процесс, выполняющийся на машине B, производит операцию записи нового значения в переменную X. Для обеспечения строгой консистентности операция чтения должна возвратить в машину А старое значение переменной вне зависимости от того, где расположена машина A и насколько близки между собой два момента времени T1 и T2. Однако, если T1-T2 равно 1 нсек, и машины расположены друг от друга на расстоянии 3-х метров, то сигнал о запросе значения переменной должен быть передан на машину B со скоростью в 10 раз превышающей скорость света, что невозможно.

а) Строго консистентная память

б) Память без строгой консистентности

6.3.2 Последовательная консистентность.

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

Последовательную консистентность впервые определил Lamport в 1979 г.

По его определению, модель последовательной консистентности памяти должна удовлетворять следующему условию: «Результат выполнения должен быть тот-же, как если бы операторы всех процессоров выполнялись бы в некоторой последовательности, в которой операторы каждого индивидуального процессора расположены в порядке, определяемом программой этого процессора»

Это определение означает, что при параллельном выполнении, все процессы должны «видеть» одну и ту же последовательность записей в память.

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

Два примера правильного выполнения одной программы. В примерах используются следующие обозначения:

W(x)1 - запись значения 1 в переменную x;