Лекционные материалы (1162669), страница 9
Текст из файла (страница 9)
Страницы, доступные на запись, размножаются, но операции сразделяемой памятью (и чтение, и запись) не должны начинаться на каждом процессоре дотех пор, пока не завершится выполнение предыдущей операции записи, выданной этимпроцессором, т.е. будут скорректированы все копии соответствующей страницы.Централизованный алгоритм. Процесс посылает координатору запрос на модификациюпеременной и ждет от него указания о проведении этой модификации. Такое указаниекоординатор рассылает сразу всем владельцам копий этой переменной.
Каждый процессвыполняет эти указания по мере их получения. Поскольку сообщения от координатораприходят каждому процессу в том порядке, в котором они были им посланы, то всепроцессы корректируют свои копии переменных в этом едином порядке.Децентрализованный алгоритм. Процесс посылает посредством механизма упорядоченногошироковещания (неделимые широковещательные рассылки) указание о модификациипеременной всем владельцам копий соответствующей страницы (включая и себя) и ждетполучения этого своего собственного указания.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 консистентности производительнее и эффективнее моделей с более строгойконсистентностью, но и ее ограничения для многих приложений не всегда являютсянеобходимыми, так как требуют получение всеми процессорами информации о каждойоперации записи, выполняемой на некотором процессоре.Рассмотрим, для примера, процесс, который в критической секции циклически читает изаписывает значение некоторых переменных.
Даже, если остальные процессоры и непытаются обращаться к этим переменным до выхода первого процесса из критическойсекции, для удовлетворения требований описанных выше моделей консистентности они38должны «видеть» все записи первого процессора в порядке их выполнения, что,естественно, совершенно не нужно. Наилучшее решение в такой ситуации - это позволитьпервому процессу завершить выполнение критической секции и, только после этого,переслать остальным процессам значения модифицированных переменных, не заботясь опересылке промежуточных результатов, и порядка их вычисления внутри критическойсекции.Предложенная в 1986 г. (Dubois et al.) модель слабой консистентности, основана навыделении среди переменных специальных синхронизационных переменных (доступ ккоторым производится специальной операцией синхронизации памяти) и описываетсяследующими правилами:1.
Доступ к синхронизационным переменным определяется моделью последовательнойконсистентности;2. Доступ к синхронизационным переменным запрещен (задерживается), пока не выполненывсе предыдущие операции записи;3. Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущиеобращения к синхронизационным переменным.Первое правило определяет, что все процессы «видят» обращения к синхронизационнымпеременным в определенном (одном и том же) порядке (а “видеть” они могут толькопосредством чтения обычных переменных!).Второе правило гарантирует, что выполнение процессором операции обращения ксинхронизационной переменной возможно только после «выталкивания» конвейера (полногозавершения выполнения всех предыдущих операций записи переменных, выданных даннымпроцессором).
При этом, все выполненные процессом записи станут гарантированно видныостальным процессам только после выполнения ими синхронизации. Третье правилоопределяет, что при обращении к обычным (не синхронизационным) переменным на чтениеили запись, все предыдущие обращения к синхронизационным переменным должны бытьвыполнены полностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
