В.А. Крюков - Операционные системы распределенных вычислительных систем, страница 10

Даже, если остальные процессоры и непытаются обращаться к этим переменным до выхода первого процесса из критическойсекции, для удовлетворения требований описанных выше моделей консистентности они38должны «видеть» все записи первого процессора в порядке их выполнения, что,естественно, совершенно не нужно.

Наилучшее решение в такой ситуации - это позволитьпервому процессу завершить выполнение критической секции и, только после этого,переслать остальным процессам значения модифицированных переменных, не заботясь опересылке промежуточных результатов, и порядка их вычисления внутри критическойсекции.Предложенная в 1986 г. (Dubois et al.) модель слабой консистентности, основана навыделении среди переменных специальных синхронизационных переменных (доступ ккоторым производится специальной операцией синхронизации памяти) и описываетсяследующими правилами:1. Доступ к синхронизационным переменным определяется моделью последовательнойконсистентности;2.

Доступ к синхронизационным переменным запрещен (задерживается), пока не выполненывсе предыдущие операции записи;3. Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущиеобращения к синхронизационным переменным.Первое правило определяет, что все процессы «видят» обращения к синхронизационнымпеременным в определенном (одном и том же) порядке (а “видеть” они могут толькопосредством чтения обычных переменных!).Второе правило гарантирует, что выполнение процессором операции обращения ксинхронизационной переменной возможно только после «выталкивания» конвейера (полногозавершения выполнения всех предыдущих операций записи переменных, выданных даннымпроцессором).

При этом, все выполненные процессом записи станут гарантированно видныостальным процессам только после выполнения ими синхронизации. Третье правилоопределяет, что при обращении к обычным (не синхронизационным) переменным на чтениеили запись, все предыдущие обращения к синхронизационным переменным должны бытьвыполнены полностью. Выполнив синхронизацию памяти (эта операция обозначена нижебуквой S) перед обращением к общей переменной, процесс может быть уверен, что получитправильное значение этой переменной (то, которое записал какой-то процесс, успевшийсообщить об этом всем посредством синхронизации памяти).a) Пример допустимой последовательности событий.P1:W(x)1W(x)2SP2:R(x)1, R(x)2P3:R(x)2, R(x)1б) Пример недопустимой последовательности событий.P1:P2:W(x)1W(x)2SSSSR(x)16.3.6 Консистентность по выходу.В системе со слабой консистентностью возникает проблема при обращении ксинхронизационной переменной: система не имеет информации о цели этого обращения - илипроцесс завершил модификацию общей переменной, или готовится прочитать значение общейпеременной.

Для более эффективной реализации модели консистентности система должнаразличать две ситуации: вход в критическую секцию и выход из нее.39В модели консистентности по выходу введены специальные функции обращения ксинхронизационным переменным:(1)ACQUIRE - захват синхронизационной переменной, информирует систему о входе вкритическую секцию;(2)RELEASE - освобождение синхронизационной переменной, определяет завершениекритической секции.Захват и освобождение используется для организации доступа не ко всем общим переменным,а только к тем, которые защищаются данной синхронизационной переменной.

Такие общиепеременные называют защищенными переменными.Пример допустимой последовательности событий для модели с консистентностью по выходу.(Acq(L) - захват синхронизационной переменной L; Rel(L) - освобождениесинхронизационной переменной).P1:Acq(L) W(x)1 W(x)2 Rel(L)P2:Acq(L) R(x)2Rel(L)P3:R(x)1Следующие правила определяют требования к модели консистентности по выходу:(1) До выполнения обращения к общей переменной, должны быть полностью выполненывсе предыдущие захваты синхронизационных переменных данным процессором.(2) Перед освобождением синхронизационной переменной должны быть закончены всеоперации чтения/записи, выполнявшиеся процессором прежде.(3) Реализация операций захвата и освобождения синхронизационной переменной должныудовлетворять требованиям процессорной консистентности (последовательнаяконсистентность не требуется, захваты разных переменных осуществляютсяпараллельно).При выполнении всех этих требований и использовании методов захвата и освобождения,результат выполнения программы будет таким же, как при выполнении этой программы всистеме с последовательной моделью консистентности.Существует модификация консистентности по выходу - «ленивая».

В отличие от описанной(«энергичной») консистентности по выходу, она не требует выталкивания всехмодифицированных данных при выходе из критической секции. Вместо этого, при запросевхода в критическую секцию процессу передаются текущие значения защищенныхразделяемых переменных (например, от процесса, который последним находился вкритической секции, охраняемой этой синхронизационной переменной). При повторныхвходах в критическую секцию того же самого процесса не требуется никаких обменовсообщениями. Для того, чтобы узнать, какие переменные защищаются конкретнойсинхронизационной переменной, нужно фиксировать все переменные, изменяемые внутрисоответствующих критических секций.6.3.7 Консистентность по входу.Эта консистентность представляет собой еще один пример модели консистентности, котораяориентирована на использование критических секций.

Так же, как и в предыдущей модели,эта модель консистентности требует от программистов (или компиляторов) использованиемеханизма захвата/освобождения для выполнения критических секций. Однако в этой моделитребуется, чтобы каждая общая переменная была явна связана с некоторойсинхронизационной переменной (или с несколькими синхронизационными переменными),при этом, если доступ к элементам массива, или различным отдельным переменным, можетпроизводиться независимо (параллельно), то эти элементы массива (общие переменные)должны быть связаны с разными синхронизационными переменными. Таким образом,40вводится явная связь между синхронизационными переменными и общими переменными,которые они охраняют.Кроме того, критические секции, охраняемые одной синхронизационной переменной, могутбыть двух типов:секция с монопольным доступом (для модификации переменных);секция с немонопольным доступом (для чтения переменных).Рассмотрим использование синхронизационных переменных.Каждая синхронизационная переменная имеет временного владельца - последний процесс,захвативший доступ к этой переменной.

Этот владелец может в цикле выполнятькритическую секцию, не посылая при этом сообщений другим процессорам. Процесс,который в данный момент не является владельцем синхронизационной переменной, нотребующий ее захвата, должен послать запрос текущему владельцу этой переменной дляполучения права собственности на синхронизационную переменную и значенийохраняемых ею общих переменных. Разрешена ситуация, когда синхронизационнаяпеременная имеет несколько владельцев, но только в том случае, если связанные с этойпеременной общие данные используются только для чтения.Ниже приведены формальные правила, определяющие модель консистентности по входу:(1) Процесс не может захватить синхронизационную переменную до того, пока необновленывсепеременныеэтогопроцесса,охраняемыезахватываемойсинхронизационной переменной;(2) Процесс не может захватить синхронизационную переменную в монопольном режиме(для модификации охраняемых данных), пока другой процесс, владеющий этойпеременной (даже в немонопольном режиме), не освободит ее;(3) Если какой-то процесс захватил синхронизационную переменную в монопольномрежиме, то ни один процесс не сможет ее захватить даже в немонопольном режиме дотех пор, пока первый процесс не освободит эту переменную, и будут обновлены текущиезначения охраняемых переменных в процессе, запрашивающем синхронизационнуюпеременную.6.3.8Сравнение моделей консистентности.В приведенной ниже таблице определены отличительные характеристики описанных моделейконсистентности памяти.(а) Модели консистентности, не использующие операции синхронизации.КонсистентностьОписаниеСтрогаяУпорядочение всех доступов к разделяемым данным поабсолютному времениПоследовательнаяВсе процессы видят все записи разделяемых данных водном и том же порядкеПричиннаяВсе процессы видят все причинно-связанные записиданных в одном и том же порядкеПроцессорнаяPRAM-консистентность + когерентность памятиPRAMВсе процессоры видят записи любого процессора водном и том же порядке41(б) Модели консистентности с операциями синхронизации.КонсистентностьОписаниеСлабаяРазделяемые данные можно считать консистентнымитолько после выполнения синхронизацииПо выходуРазделяемые данные, изменяемые в критическойсекции, становятся консистентными после выхода изнее.По входуРазделяемые данные, связанные с монопольной илинемонопольной критической секцией, становятсяконсистентными при входе в нее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;42s = 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 на всех процессорах при выходе из цикла должно быть присвоено тозначение, которое было получено на витке цикла с максимальным номером.