Лекционные материалы (1162669), страница 8
Текст из файла (страница 8)
Он возвращает данные клиентампо их запросам на чтение, по запросам на запись он корректирует данные и посылаетклиентам в ответ квитанции. Клиенты могут использовать тайм-аут для посылки повторныхзапросов при отсутствии ответа сервера. Дубликаты запросов на запись могут распознаватьсяпутем нумерации запросов. Если несколько повторных обращений к серверу остались безответа, приложение получит отрицательный код ответа (это обеспечит клиент).Алгоритм прост в реализации, но сервер будет узким местом.Можно разделяемые данные распределить между несколькими серверами. В этом случаеклиент должен уметь определять, к какому серверу надо обращаться при каждом доступе кразделяемой переменной.
Можно, например, распределить между серверами данные взависимости от их адресов и использовать функцию отображения для определения нужногосервера.Независимо от числа серверов,катастрофически замедлится.работа с памятью будет требовать коммуникаций и6.2.2 Миграционный алгоритм.В отличие от предыдущего алгоритма, когда запрос к данным направлялся в место ихрасположения, в этом алгоритме меняется расположение данных - они перемещаются в томесто, где потребовались. Это позволяет последовательные обращения к даннымосуществлять локально.
Миграционный алгоритм позволяет обращаться к одному элементуданных в любой момент времени только одному узлу.Обычно мигрирует целиком страницы или блоки данных, а не запрашиваемые единицыданных. Это позволяет воспользоваться присущей приложениям локальностью доступа кданным для снижения стоимости миграции. Однако, такой подход приводит к трэшингу,когда страницы очень часто мигрируют между узлами при малом количестве обслуживаемыхзапросов. Причиной этого может быть так называемое “ложное разделение”, когда разнымпроцессорам нужны разные данные, но эти данные расположены в одном блоке или странице.Некоторые системы позволяют задать время, в течение которого страница насильноудерживается в узле для того, чтобы успеть выполнить несколько обращений к ней до еемиграции в другой узел.Миграционный алгоритм позволяет интегрировать DSM с виртуальной памятью,обеспечивающейся операционной системой в отдельных узлах.
Если размер страницы DSMсовпадает с размером страницы виртуальной памяти (или кратен ей), то можно обращаться кразделяемой памяти обычными машинными командами, воспользовавшись аппаратнымисредствами проверки наличия в оперативной памяти требуемой страницы и заменывиртуального адреса на физический. Конечно, для этого виртуальное адресное пространствопроцессоров должно быть достаточно, чтобы адресовать всю разделяемую память.
При этом,несколько процессов в одном узле могут разделять одну и ту же страницу.Для определения места расположения блоков данных миграционный алгоритм можетиспользовать сервер, отслеживающий перемещения блоков, либо воспользоватьсямеханизмом подсказок в каждом узле. Возможна и широковещательная рассылка запросов.6.2.3 Алгоритм размножения для чтения.Предыдущий алгоритм позволял обращаться к разделяемым данным в любой момент временитолько процессам в одном узле (в котором эти данные находятся). Данный алгоритмрасширяет миграционный алгоритм механизмом размножения блоков данных, позволяя либомногим узлам иметь возможность одновременного доступа по чтению, либо одному узлуиметь возможность читать и писать данные (протокол многих читателей и одного писателя).33При использовании такого алгоритма требуется отслеживать расположение всех блоковданных и их копий.
Например, каждый собственник блока может отслеживать расположениеего копий.Безусловно, производительность повышается за счет возможности одновременного доступа почтению, но запись требует серьезных затрат для уничтожения всех устаревших копий блокаданных или их коррекции. Да и модель многих читателей и одного писателя мало подходитдля параллельных программ.6.2.4 Алгоритм размножения для чтения и записи.Этот алгоритм является расширением предыдущего алгоритма.
Он позволяет многим узламиметь одновременный доступ к разделяемым данным на чтение и запись (протокол многихчитателей и многих писателей). Поскольку много узлов могут писать данные параллельно,требуется для поддержания согласованности данных контролировать доступ к ним.Одним из способов обеспечения согласованности данных является использованиеспециального процесса для упорядочивания модификаций памяти. Все узлы, желающиемодифицировать разделяемые данные должны посылать свои модификации этомупроцессу.
Он будет присваивать каждой модификации очередной номер и рассылать егошироковещательно вместе с модификацией всем узлам, имеющим копиюмодифицируемого блока данных. Каждый узел будет осуществлять модификации в порядкевозрастания их номеров. Разрыв в номерах полученных модификаций будет означатьпотерю одной или нескольких модификаций. В этом случае узел может запроситьнедостающие модификации.Данный алгоритм может существенно снизить среднюю стоимость доступа к данным толькотогда, когда количество чтений значительно превышает количество записей.В общем случае, все перечисленные выше алгоритмы являются слишком неэффективными,чтобы их можно было использовать для преодоления архитектурных ограничениймультипроцессоров и сокращения усилий, необходимых для написания программ дляраспределенных систем.Добиться эффективности можно только изменив семантику обращений к памяти.Для упрощения понимания основных идей алгоритмов реализации 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.Описанный ранее миграционный алгоритм реализует последовательную консистентность.Последовательная консистентность может быть реализована гораздо более эффективноследующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
