6-DSM (В.А. Крюков, В.А. Бахтин - Распределенные системы)

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

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

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

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

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

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

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

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

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

По существу, DSM-системы преодолевают архитектурные ограничения мультипроцессоров и сокращают усилия, необходимые для написания программ для распределенных систем. Обычно они реализуются программно-аппаратными средствами, но в 90-х годах появилось несколько коммерческих MPP с DSM, реализованной аппаратно (Convex SPP, KSR1, Origin 2000). В конце 2004 года второй в списке TOP-500 являлась система, состоящая из 20 DSM-кластеров SGI ALTIX 3000, каждый по 512 процессоров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 г.

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