Реализация распределенных файловых систем.

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

5.2.1 Использование файлов.

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

большинство файлов имеют размер менее 10К. (Следует перекачивать целиком).

b) чтение встречается гораздо чаще записи. (Кэширование).

c) чтение и запись последовательны, произвольный доступ редок.

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

d) большинство файлов имеют короткое время жизни. (Создавать файл в клиенте и держать его там до уничтожения).

e) мало файлов разделяются (кэширование в клиенте и семантика сессий).

f) существуют различные классы файлов с разными свойствами.

(Следует иметь в системе разные механизмы для разных классов).

5.2.2 Структура системы.

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

Второй вопрос - должны ли быть файловый сервер и сервер директорий отдельными серверами или быть объединенными в один сервер. Разделение позволяет иметь разные серверы директорий (UNIX, MS-DOS) и один файловый сервер. Объединение позволяет сократить коммуникационные издержки.

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

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

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

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

Серверы с состоянием. Достоинства.

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

b)   выше эффективность (информация об открытых файлах может храниться в оперативной памяти).

c)    блоки информации могут читаться с упреждением.

d)   убедиться в достоверности запроса легче, если есть состояние (например, хранить номер последнего запроса).

e)    возможна операция захвата файла.

Серверы без состояния. Достоинства.

a) устойчивость к ошибкам.

b) не требуется операций ОТКРЫТЬ/ЗАКРЫТЬ.

c) не требуется память для таблиц.

d) нет ограничений на число открытых файлов.

e) нет проблем при крахе клиента.

5.2.3           Кэширование.

В системе клиент-сервер с памятью и дисками есть четыре потенциальных места для хранения файлов или их частей.

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

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

Коммуникационные издержки остаются.

Избавиться от коммуникаций позволяет кэширование в машине клиента.

В третьих, кэширование на диске клиента.

Оно может не дать преимуществ перед кэшированием в памяти сервера, а сложность повышается значительно.

Поэтому рассмотрим подробнее четвертый вариант - организацию кэширования в памяти клиента. При этом имеется три различных способа:

a)    кэширование в каждом процессе. (Хорошо, если c файлом активно работает один процесс - многократно открывает и закрывает файл, читает и пишет, например в случае процесса базы данных).

b)   кэширование в ядре. (Накладные расходы на обращение к ядру).

c)    кэш-менеджер в виде отдельного процесса. (Ядро освобождается от функций файловой системы, но на пользовательском уровне трудно эффективно использовать память, особенно в случае виртуальной памяти. Возможна фиксация страниц, чтобы избежать обменов с диском).

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

Консистентность кэшей.

Кэширование в клиенте создает серьезную проблему - сложность поддержания кэшей в согласованном состоянии.

Алгоритм со сквозной записью.

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

Алгоритм с отложенной записью. Через регулярные промежутки времени все модифицированные блоки пишутся в файл (так на традиционных ЭВМ работает OC UNIX). Эффективность выше, но семантика непонятна пользователю.

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

Однако, аналогичная картина происходит и на традиционной ЭВМ, когда два процесса на одной ЭВМ открывают файл, читают его, модифицируют в своей памяти и пишут назад в файл.

Алгоритм централизованного управления. Можно выдержать семантику UNIX, но не эффективно, ненадежно, и плохо масштабируется.

5.2.4           Размножение.

Система может предоставлять такой сервис, как поддержание для указанных файлов нескольких копий на различных серверах. Главные цели:

1)   Повысить надежность.

2)   Повысить доступность (крах одного сервера не вызывает недоступность размноженных файлов.

3)   Распределить нагрузку на несколько серверов.

Имеются три схемы реализации размножения:

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

b)   «Ленивое» размножение. Сначала копия создается на одном сервере, а затем он сам автоматически создает (в свободное время) дополнительные копии и обеспечивает их поддержание.

c)    Симметричное размножение. Все операции одновременно вызываются в нескольких серверах и одновременно выполняются.

Протоколы коррекции.

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

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

Слабость - выход из строя главного сервера не позволяет выполнять коррекции.

(2)   Метод голосования. Идея - запрашивать чтение и запись файла у многих серверов (запись - у всех!). Запрос может получить одобрение у половины серверов плюс один. При этом должно быть согласие относительно номера текущей версии файла. Этот номер увеличивается на единицу с каждой коррекцией файла. Можно использовать различные значения для кворума чтения (Nr) и кворума записи (Nw). При этом должно выполняться соотношение Nr+Nw>N. Поскольку чтение является более частой операцией, то естественно взять Nr=1. Однако в этом случае для кворума записи потребуются все серверы.

5.2.5      Пример: Sun Microsystem’s Network File System (NFS).

Изначально реализована Sun Microsystem в 1985 году для использования на своих рабочих станций на базе UNIX. В настоящее время поддерживается также другими фирмами для UNIX и других ОС (включая MS-DOS). Интересны следующие аспекты NFS - архитектура, протоколы и реализация.

Архитектура NFS.

Позволяет иметь произвольное множество клиентов и серверов на произвольных ЭВМ локальной или широкомасштабной сети.

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

Клиент получает доступ к экспортированным директориям путем их монтирования. Если клиент не имеет дисков, то может монтировать директории в свою корневую директорию.

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

Протоколы NFS.

Поскольку одна из целей NFS - поддержка гетерогенных систем, клиенты и серверы могут работать на разных ЭВМ с различной архитектурой и различными ОС.

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

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

   Многие клиенты монтируют требуемые удаленные директории автоматически при запуске (используя   командную   процедуру shell-интерпретатора ОС UNIX).

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

Второй протокол - для доступа к директориям и файлам. Клиенты посылают сообщения, чтобы манипулировать директориями, читать и писать файлы. Можно получить атрибуты файла. Поддерживается большинство системных вызовов ОС UNIX, исключая OPEN и CLOSE. Для получения дескриптора файла по его символическому имени используется операция LOOKUP, отличающаяся от открытия файла тем, что никаких внутренних таблиц не создается.

Таким образом, серверы в NFS не имеют состояния (stateless). Поэтому для захвата файла используется специальный механизм.

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

Все ключи, используемые для контроля доступа, поддерживаются специальным сервисом (и серверами) - сетевым информационным сервисом (NIS). Храня пары (ключ, значение), сервис обеспечивает выдачу значения кода при правильном подтверждении ключей. Кроме того, он обеспечивает отображение имен машин на их сетевые адреса, и другие отображения. NIS-серверы используют схему главный -подчиненные для реализации размножения («ленивое» размножение).

Реализация NFS.

Клиент

Сервер

СЕТЬ

(XDR - External Data Represantation)

Задача уровня виртуальной файловой системы - поддерживать для каждого открытого файла строку в таблице (v-вершину), аналогичную i-вершине UNIX. Эта строка позволяет различать локальные файлы от удаленных. Для удаленных файлов вся необходимая информация хранится в специальной r-вершине в NFS-клиенте, на которую ссылается v-вершина. У сервера нет никаких таблиц.

Передачи информации между клиентом и сервером NFS производятся блоками размером 8К (для эффективности).

Два кэша - кэш данных и кэш атрибутов файлов (обращения к ним очень часты, разработчики NFS исходили из оценки 90%). Реализована семантика отложенной записи - предмет критики NFS.

Имеется также кэш подсказок для ускорения получения v-вершины по символическому имени. При использовании устаревшей подсказки NFS-клиент будет обращаться к NFS-серверу и корректировать свой кэш (пользователь об этом ничего не должен знать).

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.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 раз превышающей скорость света, что невозможно.

P1: W(x)1	P1: W(x)1
--------------------------------> t	-----------------------------------> t
P2: R(x)1	P2: R(x)0 R(x)1

а)	б)

<

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

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

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

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

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

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

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

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

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

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

R(x)0 - чтение значения 0 из переменной x.

P1:	W(x)1			W(y)1
P2:			W(z)1
P3:		R(x)0	R(y)0	R(z)1	R(y)0
P4:		R(x)0	R(y)1	R(z)1	R(x)1

<

/p> В этом примере процессы «видят» записи в порядке W(z)1, W(x)1,W(y)1 или W(x)1, W(z)1,W(y)1.

P1:	W(x)1			W(y)1
P2:			W(z)1
P3:		R(x)0	R(y)1	R(z)0	R(y)1
P4:		R(x)1	R(y)1	R(z)0	R(x)1

В этом примере процессы «видят» записи в порядке W(x)1, W(y)1,W(z)1.

Два примера неправильного выполнения той же программы.

P1:	W(x)1			W(y)1
P2:			W(z)1
P3:		R(x)0	R(y)0	R(z)1	R(y)0
P4:		R(x)0	R(y)1	R(z)0	R(x)1

Процессы Р3 и Р4 «видят» записи W(y)1 и W(z)1 в разном порядке.

P1:	W(x)1			W(y)1
P2:			W(z)1
P3:		R(x)1	R(y)0	R(z)1	R(y)1
P4:		R(x)0	R(y)1	R(z)1	R(x)0

Процесс Р4 «видит» записи W(x)1 и W(y)1 не в том порядке, как они выполнялись в процессе Р1.

Описанный выше миграционный алгоритм реализует последовательную консистентность.

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

6.3.3 Причинная консистентность.

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

Рассмотрим пример. Предположим, что процесс P1 модифицировал переменную x, затем процесс P2 прочитал x

и модифицировал y. В этом случае модификация x

и модификация y

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

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

Пример.

(а) Нарушение модели причинной консистентности

P1:	W(x)1
P2:		R(x)1	W(x)2
P3:				R(x)2	R(x)1
P4:				R(x)1	R(x)2

(б) корректная последовательность для модели причинной консистентности.

P1:	W(x)1			W(x)3
P2:		R(x)1	W(x)2
P3:		R(x)1			R(x)3	R(x)2
P4:		R(x)1			R(x)2	R(X)3

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

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

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

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

6.3.4 PRAM консистентность и процессорная консистентность.

PRAM (Pipelined RAM) консистентность определяется следующим образом: «Операции записи, выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, но операции записи, выполняемые разными процессорами, могут быть видны в произвольном порядке.»

Пример допустимой последовательности событий в системе с PRAM консистентностью.

P1:	W(x)1
P2:		R(x)1	W(x)2
P3:				R(x)1	R(x)2
P4:				R(x)2	R(x)1

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

PRAM консистентность может приводить к результатам, противоречащим интуитивному представлению. Пример:

Процесс P1	Процесс P2
..........	..........
a = 1;	b = 1;
if (b==0) kill (P2);	if (a==0) kill (P1);
..........	..........

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

Модель процессорной консистентности отличается от модели PRAM консистентности тем, что в ней дополнительно требуется когерентность памяти: «Для каждой переменной x есть общее согласие относительно порядка, в котором процессоры модифицируют эту переменную, операции записи в разные переменные - параллельны». Таким образом, к упорядочиванию записей каждого процессора добавляется упорядочивание записей в переменные или группы переменных (например, находящихся в независимых блоках памяти).

6.3.5. Слабая консистентность.

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

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

Предложенная в 1986 г. (Dubois et al.) модель слабой консистентности, основана на выделении среди переменных специальных синхронизационных переменных и описывается следующими правилами:

Содержание раздела