6-DSM (1158856), страница 2
Текст из файла (страница 2)
Последовательная консистентность не гарантирует, что операция чтения возвратит значение, записанное другим процессом наносекундой или даже минутой раньше, в этой модели только точно гарантируется, что все процессы должны «видеть» одну и ту же последовательность записей в память.
Результат повторного выполнения параллельной программы в системе с последовательной консистентностью (как, впрочем, и при строгой консистентности) может не совпадать с результатом предыдущего выполнения этой же программы, если в программе нет регулирования операций доступа к памяти с помощью механизмов синхронизации.
Два примера правильного выполнения одной программы. В примерах используются следующие обозначения:
W(x)1 - запись значения 1 в переменную x;
R(x)0 - чтение значения 0 из переменной x.
| P1: | W(x)1 | W(y)1 | ||||
| P2: | W(z)1 | |||||
| P3: | R(x)0 | R(y)0 | R(z)1 | R(y)0 | ||
| P4: | R(x)0 | R(y)1 | R(z)1 | R(x)1 |
В этом примере процессы «видят» записи в порядке W(z)1, W(x)1,W(y)1 или W(x)1, W(z)1,W(y)1.
| P1: | W(x)1 | W(y)1 | ||||
| P2: | W(z)1 | |||||
| P3: | R(x)0 | R(y)1 | R(z)0 | R(y)1 | ||
| P4: | R(x)1 | R(y)1 | R(z)0 | R(x)1 |
В этом примере процессы «видят» записи в порядке W(x)1, W(y)1,W(z)1.
Два примера неправильного выполнения той же программы.
| P1: | W(x)1 | W(y)1 | ||||
| P2: | W(z)1 | |||||
| P3: | R(x)0 | R(y)0 | R(z)1 | R(y)0 | ||
| P4: | R(x)0 | R(y)1 | R(z)0 | R(x)1 |
Процессы Р3 и Р4 «видят» записи W(y)1 и W(z)1 в разном порядке.
| P1: | W(x)1 | W(y)1 | ||||
| P2: | W(z)1 | |||||
| P3: | R(x)1 | R(y)0 | R(z)1 | R(y)1 | ||
| P4: | R(x)0 | R(y)1 | R(z)1 | R(x)0 |
Процесс Р4 «видит» записи W(x)1 и W(y)1 не в том порядке, как они выполнялись в процессе Р1.
Описанный ранее миграционный алгоритм реализует последовательную консистентность.
Последовательная консистентность может быть реализована гораздо более эффективно следующим образом. Страницы, доступные на запись, размножаются, но операции с разделяемой памятью (и чтение, и запись) не должны начинаться на каждом процессоре до тех пор, пока не завершится выполнение предыдущей операции записи, выданной этим процессором, т.е. будут скорректированы все копии соответствующей страницы.
Централизованный алгоритм. Процесс посылает координатору запрос на модификацию переменной и ждет от него указания о проведении этой модификации. Такое указание координатор рассылает сразу всем владельцам копий этой переменной. Каждый процесс выполняет эти указания по мере их получения. Поскольку сообщения от координатора приходят каждому процессу в том порядке, в котором они были им посланы, то все процессы корректируют свои копии переменных в этом едином порядке.
Децентрализованный алгоритм. Процесс посылает посредством механизма упорядоченного широковещания (неделимые широковещательные рассылки) указание о модификации переменной всем владельцам копий соответствующей страницы (включая и себя) и ждет получения этого своего собственного указания.
6.3.3 Причинная консистентность.
Причинная модель консистентности памяти представляет собой более «слабую» модель по сравнению с последовательной моделью, поскольку в ней не всегда требуется, чтобы все процессы «видели» одну и ту же последовательность записей в память, а проводится различие между потенциально зависимыми операциями записи, и независимыми.
Рассмотрим пример. Предположим, что процесс P1 модифицировал переменную x, затем процесс P2 прочитал x и модифицировал y. В этом случае модификация x и модификация y потенциально причинно зависимы, так как новое значение y могло зависеть от прочитанного значения переменной x. С другой стороны, если два процесса одновременно изменяют значения одной и той же или различных переменных, то между этими событиями нет причинной связи. Операции записи, которые причинно не зависят друг от друга, называются параллельными.
Причинная модель консистентности памяти определяется следующим условием: «Последовательность операций записи, которые потенциально причинно зависимы, должна наблюдаться всеми процессами системы одинаково, параллельные операции записи могут наблюдаться разными узлами в разном порядке».
Пример.
(а) Нарушение модели причинной консистентности
| P1: | W(x)1 | ||||
| P2: | R(x)1 | W(x)2 | |||
| P3: | R(x)2 | R(x)1 | |||
| P4: | R(x)1 | R(x)2 |
(б) корректная последовательность для модели причинной консистентности.
| P1: | W(x)1 | W(x)3 | ||||
| P2: | R(x)1 | W(x)2 | ||||
| P3: | R(x)1 | R(x)3 | R(x)2 | |||
| P4: | R(x)1 | R(x)2 | R(х)3 |
При реализации причинной консистентности в случае размножения страниц выполнение записи в общую память требует ожидания выполнения только тех предыдущих операций записи, от которых эта запись потенциально причинно зависит. Параллельные операции записи не задерживают выполнение друг друга (и не требуют неделимости широковещательных рассылок всем владельцам копий страницы).
Реализация причинной консистентности может осуществляться следующим образом:
-
все модификации переменных на каждом процессоре нумеруются;
-
всем процессорам вместе со значением модифицируемой переменной рассылается номер этой модификации на данном процессоре, а также номера модификаций всех процессоров, известных данному процессору к этому моменту;
-
выполнение любой модификации на каждом процессоре задерживается до тех пор, пока он не получит и не выполнит все те модификации других процессоров, о которых было известно процессору - автору задерживаемой модификации.
6.3.4 PRAM консистентность и процессорная консистентность.
PRAM (Pipelined RAM) консистентность определяется следующим образом: «Операции записи, выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, но операции записи, выполняемые разными процессорами, могут быть видны в произвольном порядке».
Пример допустимой последовательности событий в системе с PRAM консистентностью.
| P1: | W(x)1 | ||||
| P2: | R(x)1 | W(x)2 | |||
| P3: | R(x)1 | R(x)2 | |||
| P4: | R(x)2 | R(x)1 |
Преимущество модели PRAM консистентности заключается в простоте ее реализации, поскольку операции записи на одном процессоре могут быть конвейеризованы: можно продолжать выполнение процесса и выполнять другие операции с общей памятью не дожидаясь завершения предыдущих операций записи (модификации всех копий страниц, например), необходимо только быть уверенным, что все процессоры увидят эти записи в одном и том же порядке.
PRAM консистентность может приводить к результатам, противоречащим интуитивному представлению. Пример:
| Процесс P1 | Процесс P2 |
| .......... | .......... |
| a = 1; | b = 1; |
| if (b==0) kill (P2); | if (a==0) kill (P1); |
| .......... | .......... |
Оба процесса могут быть убиты, что невозможно при последовательной консистентности.
Модель процессорной консистентности отличается от модели PRAM консистентности тем, что в ней дополнительно требуется когерентность памяти: «Для каждой переменной x есть общее согласие относительно порядка, в котором процессоры модифицируют эту переменную, операции записи в разные переменные - параллельны». Таким образом, к упорядочиванию записей каждого процессора добавляется упорядочивание записей в переменные или группы переменных (например, находящихся в независимых блоках памяти).
Децентрализованный алгоритм. За каждую группу переменных отвечает свой координатор, который получает от процессов запросы на модификацию и рассылает всем указания о проведении модификации. Чтобы не нарушить порядок получения процессами указаний о модификациях различных переменных, запрошенных одним процессом у разных координаторов, надо каждому процессу нумеровать свои модификации, и эти номера должны рассылаться всем вместе с указаниями о проведении модификаций. Тогда любой процесс, получающий указание о проведении модификации, может задержать его выполнение до получения недостающих указаний о предшествующих модификациях соответствующего процесса.
6.3.5. Слабая консистентность.
Модель PRAM консистентности производительнее и эффективнее моделей с более строгой консистентностью, но и ее ограничения для многих приложений не всегда являются необходимыми, так как требуют получение всеми процессорами информации о каждой операции записи, выполняемой на некотором процессоре.
Рассмотрим, для примера, процесс, который в критической секции циклически читает и записывает значение некоторых переменных. Даже, если остальные процессоры и не пытаются обращаться к этим переменным до выхода первого процесса из критической секции, для удовлетворения требований описанных выше моделей консистентности они должны «видеть» все записи первого процессора в порядке их выполнения, что, естественно, совершенно не нужно. Наилучшее решение в такой ситуации - это позволить первому процессу завершить выполнение критической секции и, только после этого, переслать остальным процессам значения модифицированных переменных, не заботясь о пересылке промежуточных результатов, и порядка их вычисления внутри критической секции.
Предложенная в 1986 г. (Dubois et al.) модель слабой консистентности, основана на выделении среди переменных специальных синхронизационных переменных (доступ к которым производится специальной операцией синхронизации памяти) и описывается следующими правилами:
1. Доступ к синхронизационным переменным определяется моделью последовательной консистентности;
-
Доступ к синхронизационным переменным запрещен (задерживается), пока не выполнены все предыдущие операции записи;
-
Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущие обращения к синхронизационным переменным.
Первое правило определяет, что все процессы «видят» обращения к синхронизационным переменным в определенном (одном и том же) порядке (а “видеть” они могут только посредством чтения обычных переменных!).
Второе правило гарантирует, что выполнение процессором операции обращения к синхронизационной переменной возможно только после «выталкивания» конвейера (полного завершения выполнения всех предыдущих операций записи переменных, выданных данным процессором). При этом, все выполненные процессом записи станут гарантированно видны остальным процессам только после выполнения ими синхронизации. Третье правило определяет, что при обращении к обычным (не синхронизационным) переменным на чтение или запись, все предыдущие обращения к синхронизационным переменным должны быть выполнены полностью. Выполнив синхронизацию памяти (эта операция обозначена ниже буквой S) перед обращением к общей переменной, процесс может быть уверен, что получит правильное значение этой переменной (то, которое записал какой-то процесс, успевший сообщить об этом всем посредством синхронизации памяти).
-
Пример допустимой последовательности событий.
| P1: | W(x)1 | W(x)2 | S | ||
| P2: | R(x)1, R(x)2 | S | |||
| P3: | R(x)2, R(x)1 | S |
б) Пример недопустимой последовательности событий.
| P1: | W(x)1 | W(x)2 | S | ||
| P2: | S | R(x)1 |
6.3.6 Консистентность по выходу.
В системе со слабой консистентностью возникает проблема при обращении к синхронизационной переменной: система не имеет информации о цели этого обращения - или процесс завершил модификацию общей переменной, или готовится прочитать значение общей переменной. Для более эффективной реализации модели консистентности система должна различать две ситуации: вход в критическую секцию и выход из нее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
