Электронный коспект лекций (1162752), страница 9
Текст из файла (страница 9)
Пример:Процесс P1..........a = 1;if (b==0) kill (P2);..........Процесс P2..........b = 1;if (a==0) kill (P1);..........Оба процесса могут быть убиты, что невозможно припоследовательной консистентности.Модель процессорной консистентности отличается от моделиPRAM консистентности тем, что в ней дополнительно требуетсякогерентность памяти: «Для каждой переменной x есть общеесогласие относительно порядка, в котором процессорымодифицируют эту переменную, операции записи в разныепеременные - параллельны».
Таким образом, к упорядочиваниюзаписей каждого процессора добавляется упорядочивание записейв переменные или группы переменных (например, находящихся внезависимых блоках памяти).Децентрализованный алгоритм. За каждую группу переменныхотвечает свой координатор, который получает от процессовзапросы на модификацию и рассылает всем указания о проведениимодификации. Чтобы не нарушить порядок получения процессамиуказаний о модификациях различных переменных, запрошенныходним процессом у разных координаторов, надо каждому процессунумеровать свои модификации, и эти номера должны рассылатьсявсем вместе с указаниями о проведении модификаций. Тогдалюбой процесс, получающий указание о проведении модификации,может задержать его выполнение до получения недостающихуказаний о предшествующих модификациях соответствующегопроцесса.6.3.5.
Слабая консистентность.Модель PRAM консистентности производительнее и эффективнеемоделей с более строгой консистентностью, но и ее ограничениядля многих приложений не всегда являются необходимыми, таккак требуют получение всеми процессорами информации о каждойоперации записи, выполняемой на некотором процессоре.Рассмотрим, для примера, процесс, который в критическойсекции циклически читает и записывает значение некоторыхпеременных. Даже, если остальные процессоры и не пытаютсяобращаться к этим переменным до выхода первого процесса изкритической секции, для удовлетворения требованийописанных выше моделей консистентности они должны«видеть» все записи первого процессора в порядке ихвыполнения, что, естественно, совершенно не нужно.Наилучшее решение в такой ситуации - это позволить первомупроцессу завершить выполнение критической секции и, толькопосле этого, переслать остальным процессам значениямодифицированных переменных, не заботясь о пересылкепромежуточных результатов, и порядка их вычисления внутрикритической секции.Предложенная в 1986 г.
(Dubois et al.) модель слабойконсистентности, основана на выделении среди переменныхспециальных синхронизационных переменных (доступ к которымпроизводится специальной операцией синхронизации памяти) иописывается следующими правилами:1. Доступ к синхронизационным переменным определяетсямоделью последовательной консистентности;2. Доступксинхронизационнымпеременнымзапрещен(задерживается), пока не выполнены все предыдущие операциизаписи;3. Доступ к данным (запись, чтение) запрещен, пока не выполненывсе предыдущие обращения к синхронизационным переменным.Первое правило определяет, что все процессы «видят» обращенияк синхронизационным переменным в определенном (одном и томже) порядке (а “видеть” они могут только посредством чтенияобычных переменных!).Второе правило гарантирует, что выполнение процессоромоперации обращения к синхронизационной переменной возможнотолько после «выталкивания» конвейера (полного завершениявыполнения всех предыдущих операций записи переменных,выданных данным процессором).
При этом, все выполненныепроцессом записи станут гарантированно видны остальнымпроцессам только после выполнения ими синхронизации. Третьеправило определяет, что при обращении к обычным (несинхронизационным) переменным на чтение или запись, всепредыдущие обращения к синхронизационным переменнымдолжны быть выполнены полностью. Выполнив синхронизациюпамяти (эта операция обозначена ниже буквой S) передобращением к общей переменной, процесс может быть уверен, чтополучит правильное значение этой переменной (то, котороезаписал какой-то процесс, успевший сообщить об этом всемпосредством синхронизации памяти).a) Пример допустимой последовательности событий.P1:P2:P3:W(x)1W(x)2SR(x)1, R(x)2R(x)2, R(x)1б) Пример недопустимой последовательности событий.SSP1:P2:W(x)1W(x)2SSR(x)16.3.6 Консистентность по выходу.В системе со слабой консистентностью возникает проблема приобращении к синхронизационной переменной: система не имеетинформации о цели этого обращения - или процесс завершилмодификацию общей переменной, или готовится прочитатьзначение общей переменной.
Для более эффективной реализациимодели консистентности система должна различать две ситуации:вход в критическую секцию и выход из нее.В модели консистентности по выходу введены специальныефункции обращения к синхронизационным переменным:(1)ACQUIRE - захват синхронизационной переменной,информирует систему о входе в критическую секцию;(2)RELEASE - освобождение синхронизационной переменной,определяет завершение критической секции.Захват и освобождение используется для организации доступа неко всем общим переменным, а только к тем, которые защищаютсяданной синхронизационной переменной. Такие общие переменныеназывают защищенными переменными.Пример допустимой последовательности событий для модели сконсистентностью по выходу.
(Acq(L) - захват синхронизационнойпеременной L; Rel(L) - освобождение синхронизационнойпеременной).P1:P2:P3:Acq(L)W(x)1W(x)2Rel(L)Следующие правила определяютконсистентности по выходу:Acq(L)R(x)2Rel(L)Rтребованиякмодели(1) До выполнения обращения к общей переменной, должныбыть полностью выполнены все предыдущие захватысинхронизационных переменных данным процессором.(2) Перед освобождением синхронизационной переменнойдолжны быть закончены все операции чтения/записи,выполнявшиеся процессором прежде.(3) Реализацияоперацийзахватаиосвобождениясинхронизационной переменной должны удовлетворятьтребованиямпроцессорнойконсистентности(последовательная консистентность не требуется, захватыразных переменных осуществляются параллельно).При выполнении всех этих требований и использовании методовзахвата и освобождения, результат выполнения программы будеттаким же, как при выполнении этой программы в системе споследовательной моделью консистентности.Существует модификация консистентности по выходу - «ленивая».В отличие от описанной («энергичной») консистентности повыходу, она не требует выталкивания всех модифицированныхданных при выходе из критической секции.
Вместо этого, призапросе входа в критическую секцию процессу передаютсятекущие значения защищенных разделяемых переменных(например, от процесса, который последним находился вкритической секции, охраняемой этой синхронизационнойпеременной). При повторных входах в критическую секцию тогоже самого процесса не требуется никаких обменов сообщениями.Для того, чтобы узнать, какие переменные защищаютсяконкретной синхронизационной переменной, нужно фиксироватьвсепеременные,изменяемыевнутрисоответствующихкритических секций.6.3.7 Консистентность по входу.Эта консистентность представляет собой еще один пример моделиконсистентности, которая ориентирована на использованиекритических секций.
Так же, как и в предыдущей модели, этамодель консистентности требует от программистов (иликомпиляторов) использование механизма захвата/освобождениядля выполнения критических секций. Однако в этой моделитребуется, чтобы каждая общая переменная была явна связана снекоторой синхронизационной переменной (или с несколькимисинхронизационными переменными), при этом, если доступ кэлементам массива, или различным отдельным переменным, можетпроизводиться независимо (параллельно), то эти элементы массива(общие переменные) должны быть связаны с разнымисинхронизационными переменными. Таким образом, вводитсяявная связь между синхронизационными переменными и общимипеременными, которые они охраняют.Крометого,критическиесекции,охраняемыесинхронизационной переменной, могут быть двух типов: секция с монопольнымпеременных);доступом(дляодноймодификации секция с немонопольным доступом (для чтения переменных).Рассмотрим использование синхронизационных переменных.Каждая синхронизационная переменная имеет временноговладельца - последний процесс, захвативший доступ к этойпеременной.
Этот владелец может в цикле выполнятькритическую секцию, не посылая при этом сообщений другимпроцессорам. Процесс, который в данный момент не являетсявладельцем синхронизационной переменной, но требующий еезахвата, должен послать запрос текущему владельцу этойпеременной для получения права собственности насинхронизационную переменную и значений охраняемых еюобщихпеременных.Разрешенаситуация,когдасинхронизационная переменная имеет несколько владельцев, нотолько в том случае, если связанные с этой переменной общиеданные используются только для чтения.Ниже приведены формальные правила, определяющие модельконсистентности по входу:(1) Процесснеможетзахватитьсинхронизационнуюпеременную до того, пока не обновлены все переменныеэтогопроцесса,охраняемыезахватываемойсинхронизационной переменной;(2) Процесснеможетзахватитьсинхронизационнуюпеременную в монопольном режиме (для модификацииохраняемых данных), пока другой процесс, владеющий этойпеременной (даже в немонопольном режиме), не освободитее;(3) Если какой-то процесс захватил синхронизационнуюпеременную в монопольном режиме, то ни один процесс несможет ее захватить даже в немонопольном режиме до техпор, пока первый процесс не освободит эту переменную, ибудут обновлены текущие значения охраняемых переменныхвпроцессе,запрашивающемсинхронизационнуюпеременную.6.3.8Сравнение моделей консистентности.В приведенной ниже таблице определены отличительныехарактеристики описанных моделей консистентности памяти.(а) Модели консистентности,синхронизации.КонсистентностьнеиспользующиеоперацииОписаниеСтрогаяУпорядочение всех доступов к разделяемым данным поабсолютному времениПоследовательнаяВсе процессы видят все записи разделяемыходном и том же порядкеПричиннаяВсе процессы видят все причинно-связанныеданных в одном и том же порядкеПроцессорнаяPRAM-консистентность + когерентность памятиPRAMВсе процессоры видят записи любого процессора в одном итом же порядкеданных взаписи(б) Модели консистентности с операциями синхронизации.КонсистентностьОписаниеСлабаяРазделяемые данные можно считать консистентными толькопосле выполнения синхронизацииПо выходуРазделяемые данные, изменяемые в критической секции,становятся консистентными после выхода из нее.По входуРазделяемые данные, связанные с монопольной илинемонопольнойкритическойсекцией,становятсяконсистентными при входе в нее6.4 Протоколы когерентности.WRITE-INVALIDATE - всем владельцам копий сообщается о ихнедействительности.WRITE-UPDATE - организуется обновление копий у всехвладельцов.Выбор определяется частотами чтений и записей, а такжевременами оповещения и обновления.6.5 Конструкторские решения.6.5.1Страничная DSM.Общая память разбивается на порции одинаковой длины страницы или блоки.
Если выбрать длину совпадающей (иликратной) длине страницы оперативной памяти процессоров (еслиих память страничная), то можно будет воспользоватьсямеханизмом защиты памяти для обнаружения отсутствующихстраниц DSM и аппаратным механизмом замены виртуальногоадреса на физический.К этому же типу DSM (не знающих заранее ничего о содержимомпамяти) можно отнести и аппаратные реализации на базе кэшей(Convex SPP).6.5.2 DSM на базе разделяемых переменных.В DSM системах с разделяемыми переменными только отдельныеструктурыданныхразделяютсямеждупроцессорами.Программист должен точно определить, какие переменные впрограмме должны разделяться, а какие не должны.Знание информации о режиме использования разделяемыхпеременных позволяет воспользоваться более эффективнымипротоколами когерентности.Рассмотрим следующую программу, которая автоматическираспараллеливается посредством размножения всех переменных навсе процессоры и распределения между ними витков цикла.s = 0;last_A = 0;for (i = 1; i < L2-1; i++){r = A[i-1]*A[i+1];C[i] = r;s = s + r*r;if (A[i]!=0) { last_A = A[i};}A[0] = last_A;Переменные внутри цикла используются в следующих режимах:А - только на чтение;r - приватно (фактически не является разделяемой);C - раздельно используется (любой элемент массива изменяется неболее, чем одним процессом, и никакой процесс не читает элемент,изменяемый другими);s - редукционная переменная, используемая для суммирования;last_A - переменная, хранящая значение последнего ненулевогоэлемента массива А.Приведения в консистентное состояние переменных A и r - нетребуется.Для приведения в консистентное состояние массива С необходимопри завершении цикла каждому процессу послать остальным всесвои изменения в массиве С.Для переменной s в конце цикла надо довыполнить операциюредукции - сложить все частичные суммы, полученные разнымипроцессорами в своих копиях переменной s и разослать результатвсем процессорам (если бы начальное значение переменной sбыло отлично от нуля, то это надо было бы учесть).Переменной last_A на всех процессорах при выходе из цикладолжно быть присвоено то значение, которое было получено навитке цикла с максимальным номером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
