Конспект по распределённым ОС (Крюков) (1162768), страница 9
Текст из файла (страница 9)
Он будет присваивать каждой модификации очередной номер и рассылать егошироковещательно вместе с модификацией всем узлам, имеющим копиюмодифицируемого блока данных. Каждый узел будет осуществлять модификации в порядкевозрастания их номеров. Разрыв в номерах полученных модификаций будет означатьпотерю одной или нескольких модификаций. В этом случае узел может запроситьнедостающие модификации.Данный алгоритм может существенно снизить среднюю стоимость доступа к данным толькотогда, когда количество чтений значительно превышает количество записей.В общем случае, все перечисленные выше алгоритмы являются слишком неэффективными,чтобы их можно было использовать для преодоления архитектурных ограничениймультипроцессоров и сокращения усилий, необходимых для написания программ дляраспределенных систем.Добиться эффективности можно только изменив семантику обращений к памяти.Для упрощения понимания основных идей алгоритмов реализации DSM мы в дальнейшембудем исходить из того, что все работает надежно (например, все сообщения доходят доадресатов) и никаких мер для обеспечения надежности предпринимать не нужно.6.3 Модели консистентности.Модель консистентности представляет собой некоторый договор между программами ипамятью, в котором указывается, что при соблюдении программами определенных правилработы с памятью будет обеспечена определенная семантика операций чтения/записи, если жеэти правила будут нарушены, то память не гарантирует правильность выполнения операцийчтения/записи.
В этой главе рассматриваются основные модели консистентностииспользуемые в системах с распределенной памятью.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 естьобщее согласие относительно порядка, в котором процессоры модифицируют эту переменную,операции записи в разные переменные - параллельны». Таким образом, к упорядочиваниюзаписей каждого процессора добавляется упорядочивание записей в переменные или группыпеременных (например, находящихся в независимых блоках памяти).Децентрализованный алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
