В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 8

Кроме того, онобеспечивает отображение имен машин на их сетевые адреса, и другие отображения. NISсерверы используют схему главный -подчиненные для реализации размножения («ленивое»размножение).Реализация NFS.(XDR - External Data Represantation)Задача уровня виртуальной файловой системы - поддерживать для каждого открытого файластроку в таблице (v-вершину), аналогичную i-вершине UNIX. Эта строка позволяет различатьлокальные файлы от удаленных. Для удаленных файлов вся необходимая информацияхранится в специальной r-вершине в NFS-клиенте, на которую ссылается v-вершина. Усервера нет никаких таблиц.Передачи информации между клиентом и сервером NFS производятся блоками размером 8К(для эффективности).Два кэша - кэш данных и кэш атрибутов файлов (обращения к ним очень часты, разработчикиNFS исходили из оценки 90%).

Реализована семантика отложенной записи - предмет критикиNFS.Имеется также кэш подсказок для ускорения получения v-вершины по символическому имени.При использовании устаревшей подсказки NFS-клиент будет обращаться к NFS-серверу икорректировать свой кэш (пользователь об этом ничего не должен знать).316 Распределенная общая память (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, Origin2000).

В конце 2004 года второй в списке TOP-500 являлась система, состоящая из 20 DSMкластеров SGI ALTIX 3000, каждый по 512 процессоров.6.2Алгоритмы реализации DSM.При реализации DSM центральными являются следующие вопросы.1) как поддерживать информацию о расположении удаленных данных.2) как снизить при доступе к удаленным данным коммуникационные задержки и большиенакладные расходы, связанные с выполнением коммуникационных протоколов.3) как сделать разделяемые данные доступными одновременно на нескольких узлах длятого, чтобы повысить производительность системы.Рассмотрим четыре возможных алгоритма реализации DSM.326.2.1Алгоритм с центральным сервером.Все разделяемые данные поддерживает центральный сервер. Он возвращает данные клиентампо их запросам на чтение, по запросам на запись он корректирует данные и посылаетклиентам в ответ квитанции.

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

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

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

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

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

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

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

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

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