Электронный коспект лекций (1162752), страница 8
Текст из файла (страница 8)
Если размер страницы 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 разпревышающей скорость света, что невозможно.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)1В этом примере процессы «видят» записи в порядке W(z)1, W(x)1,W(y)1или W(x)1, W(z)1,W(y)1.P1:W(x)1W(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Причинная консистентность.Причинная модель консистентности памяти представляет собойболее «слабую» модель по сравнению с последовательноймоделью, поскольку в ней не всегда требуется, чтобы все процессы«видели» одну и ту же последовательность записей в память, апроводитсяразличиемеждупотенциальнозависимымиоперациями записи, и независимыми.Рассмотримпример.Предположим,чтопроцесс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) консистентность определяется следующимобразом: «Операции записи, выполняемые одним процессором,видны всем остальным процессорам в том порядке, в каком онивыполнялись, но операции записи, выполняемые разнымипроцессорами, могут быть видны в произвольном порядке».Пример допустимой последовательности событий в системе сPRAM консистентностью.P1:P2:W(x)1R(x)1W(x)2P3:R(x)1R(x)2P4:R(x)2R(x)1Преимущество модели PRAM консистентности заключается впростоте ее реализации, поскольку операции записи на одномпроцессоре могут быть конвейеризованы: можно продолжатьвыполнение процесса и выполнять другие операции с общейпамятью не дожидаясь завершения предыдущих операций записи(модификации всех копий страниц, например), необходимо толькобыть уверенным, что все процессоры увидят эти записи в одном итом же порядке.PRAM консистентность может приводить к результатам,противоречащим интуитивному представлению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
