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

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

Предположим, чтопеременная X расположена в памяти машины B, и процесс, который выполняется на машинеA, пытается прочитать значение этой переменной в момент времени T1. Для этого машине Bпосылается запрос переменной X. Немного позже, в момент времени T2, процесс,выполняющийся на машине B, производит операцию записи нового значения в переменнуюX. Для обеспечения строгой консистентности операция чтения должна возвратить в машину Астарое значение переменной вне зависимости от того, где расположена машина A и насколькоблизки между собой два момента времени T1 и T2. Однако, если T1-T2 равно 1 нсек, имашины расположены друг от друга на расстоянии 3-х метров, то сигнал о запросе значенияпеременной должен быть передан на машину B со скоростью в 10 раз превышающей скоростьсвета, что невозможно.P1: W(x)1P1: W(x)1--------------------------------> t-----------------------------------> tP2:R(x)1P2:R(x)0 R(x)1а)б)а) Строго консистентная памятьб) Память без строгой консистентности6.3.2Последовательная консистентность.Строгая консистентность представляет собой идеальную модель для программирования, ноее, к сожалению программистов, невозможно реализовать для распределенных систем.Однако, практический опыт показывает, что в некоторых случаях можно обходиться и более«слабыми» моделями.

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

В примерах используютсяследующие обозначения:W(x)1 - запись значения 1 в переменную x;R(x)0 - чтение значения 0 из переменной x.P1:W(x)1W(y)1P2:W(z)1P3:R(x)0R(y)0R(z)1R(y)0P4:R(x)0R(y)1R(z)1R(x)135В этом примере процессы «видят» записи в порядке W(z)1, W(x)1,W(y)1W(z)1,W(y)1.P1:W(x)1или W(x)1,W(y)1P2:W(z)1P3:R(x)0R(y)1R(z)0R(y)1P4:R(x)1R(y)1R(z)0R(x)1В этом примере процессы «видят» записи в порядке W(x)1, W(y)1,W(z)1.Два примера неправильного выполнения той же программы.P1:W(x)1W(y)1P2:W(z)1P3:R(x)0R(y)0R(z)1R(y)0P4:R(x)0R(y)1R(z)0R(x)1Процессы Р3 и Р4 «видят» записи W(y)1 и W(z)1 в разном порядке.P1:W(x)1W(y)1P2:W(z)1P3:R(x)1R(y)0R(z)1R(y)1P4:R(x)0R(y)1R(z)1R(x)0Процесс Р4 «видит» записи W(x)1 и W(y)1 не в том порядке, как они выполнялись впроцессе Р1.Описанный ранее миграционный алгоритм реализует последовательную консистентность.Последовательная консистентность может быть реализована гораздо более эффективноследующим образом. Страницы, доступные на запись, размножаются, но операции сразделяемой памятью (и чтение, и запись) не должны начинаться на каждом процессоре дотех пор, пока не завершится выполнение предыдущей операции записи, выданной этимпроцессором, т.е.

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

Процесс посылает посредством механизма упорядоченногошироковещания (неделимые широковещательные рассылки) указание о модификациипеременной всем владельцам копий соответствующей страницы (включая и себя) и ждетполучения этого своего собственного указания.6.3.3Причинная консистентность.Причинная модель консистентности памяти представляет собой более «слабую» модель посравнению с последовательной моделью, поскольку в ней не всегда требуется, чтобы всепроцессы «видели» одну и ту же последовательность записей в память, а проводится различиемежду потенциально зависимыми операциями записи, и независимыми.36Рассмотрим пример. Предположим, что процесс P1 модифицировал переменную x, затемпроцесс P2 прочитал x и модифицировал y.

В этом случае модификация x и модификация yпотенциально причинно зависимы, так как новое значение y могло зависеть от прочитанногозначения переменной x. С другой стороны, если два процесса одновременно изменяютзначения одной и той же или различных переменных, то между этими событиями нетпричинной связи. Операции записи, которые причинно не зависят друг от друга, называютсяпараллельными.Причинная модель консистентности памяти определяется следующим условием:«Последовательность операций записи, которые потенциально причинно зависимы, должнанаблюдаться всеми процессами системы одинаково, параллельные операции записи могутнаблюдаться разными узлами в разном порядке».Пример.(а) Нарушение модели причинной консистентностиP1:P2:W(x)1R(x)1W(x)2P3:R(x)2R(x)1P4:R(x)1R(x)2(б) корректная последовательность для модели причинной консистентности.P1:W(x)1W(x)3P2:R(x)1W(x)2P3:R(x)1R(x)3R(x)2P4:R(x)1R(x)2R(X)3При реализации причинной консистентности в случае размножения страниц выполнениезаписи в общую память требует ожидания выполнения только тех предыдущих операцийзаписи, от которых эта запись потенциально причинно зависит.

Параллельные операциизаписи не задерживают выполнение друг друга (и не требуют неделимостишироковещательных рассылок всем владельцам копий страницы).Реализация причинной консистентности может осуществляться следующим образом:все модификации переменных на каждом процессоре нумеруются;всем процессорам вместе со значением модифицируемой переменной рассылаетсяномер этой модификации на данном процессоре, а также номера модификаций всехпроцессоров, известных данному процессору к этому моменту;выполнение любой модификации на каждом процессоре задерживается до тех пор,пока он не получит и не выполнит все те модификации других процессоров, окоторых было известно процессору - автору задерживаемой модификации.6.3.4 PRAM консистентность и процессорная консистентность.PRAM (Pipelined RAM) консистентность определяется следующим образом: «Операциизаписи, выполняемые одним процессором, видны всем остальным процессорам в том порядке,37в каком они выполнялись, но операции записи, выполняемые разными процессорами, могутбыть видны в произвольном порядке».Пример допустимой последовательности событий в системе с PRAM консистентностью.P1:P2:W(x)1R(x)1W(x)2P3:R(x)1R(x)2P4:R(x)2R(x)1Преимущество модели PRAM консистентности заключается в простоте ее реализации,поскольку операции записи на одном процессоре могут быть конвейеризованы: можнопродолжать выполнение процесса и выполнять другие операции с общей памятью недожидаясь завершения предыдущих операций записи (модификации всех копий страниц,например), необходимо только быть уверенным, что все процессоры увидят эти записи водном и том же порядке.PRAM консистентность может приводить к результатам, противоречащим интуитивномупредставлению.

Пример:Процесс P1..........a = 1;if (b==0) kill (P2);..........Процесс P2..........b = 1;if (a==0) kill (P1);..........Оба процесса могут быть убиты, что невозможно при последовательной консистентности.Модель процессорной консистентности отличается от модели PRAM консистентности тем,что в ней дополнительно требуется когерентность памяти: «Для каждой переменной x естьобщее согласие относительно порядка, в котором процессоры модифицируют эту переменную,операции записи в разные переменные - параллельны». Таким образом, к упорядочиваниюзаписей каждого процессора добавляется упорядочивание записей в переменные или группыпеременных (например, находящихся в независимых блоках памяти).Децентрализованный алгоритм. За каждую группу переменных отвечает свой координатор,который получает от процессов запросы на модификацию и рассылает всем указания опроведении модификации.

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