OS49-11 (1156239), страница 2
Текст из файла (страница 2)
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(X)3 |
При реализации причинной консистентности для случая размножения страниц выполнение операций с общей памятью требует ожидания выполнения только тех предыдущих операций записи, которые являются потенциально причинно зависимыми. Параллельные операции записи не задерживают выполнение операций с общей памятью, а также не требуют неделимости широковещательных рассылок.
Определение потенциальной причинной зависимости может осуществляться компилятором посредством анализа зависимости операторов программы по данным.
Система DSM может это осуществить посредством нумерации всех записей на каждом процессоре, распространения этих номеров по всем процессорам вместе с модифицируемыми данными, и задержке любой модификации на любом процессоре до тех пор, пока он не получит все те модификации, о которых известно процессору - автору задерживаемой модификации.
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. Доступ к синхронизационным переменным определяется моделью последовательной консистентности;
-
Доступ к синхронизационным переменным запрещен (задерживается), пока не выполнены все предыдущие операции записи;
-
Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущие обращения к синхронизационным переменным.
Первое правило определяет, что все процессы «видят» обращения к синхронизационным переменным в определенном (одном и том же) порядке .
Второе правило гарантирует, что выполнение процессором операции обращения к синхронизационной переменной возможно только после «выталкивания» конвейера (полного завершения выполнения на всех процессорах всех предыдущих операций записи переменных, выданных данным процессором). Третье правило определяет, что при обращении к обычным (не синхронизационным) переменным на чтение или запись, все предыдущие обращения к синхронизационным переменным должны быть выполнены полностью. Выполнив синхронизацию перед обращением к общей переменной, процесс может быть уверен, что получит правильное значение этой переменной.
-
Пример допустимой последовательности событий.
| 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}
