OS49-11 (В.А. Крюков - Электронные лекции), страница 3

В модели консистентности по выходу введены специальные функции обращения к синхронизационным переменным:

(1) ACQUIRE - захват синхронизационной переменной, информирует систему о входе в критическую секцию;

(2) RELEASE - освобождение синхронизационной переменной, определяет завершение критической секции.

Захват и освобождение используется для организации доступа не ко всем общим переменным, а только к тем, которые защищаются данной синхронизационной переменной. Такие общие переменные называют защищенными переменными.

Пример допустимой последовательности событий для модели с консистентностью по выходу. (Acq(L) - захват синхронизационной переменной L; Rel(L) - освобождение синхронизационной переменной).

Следующие правила определяют требования к модели консистентности по выходу:

(1) До выполнения обращения к общей переменной, должны быть полностью выполнены все предыдущие захваты синхронизационных переменных данным процессором.

(2) Перед освобождением синхронизационной переменной должны быть закончены все операции чтения/записи, выполнявшиеся процессором прежде.

(3) Реализация операций захвата и освобождения синхронизационной переменной должны удовлетворять требованиям процессорной консистентности (последовательная консистентность не требуется).

При выполнении всех этих требований и использовании методов захвата и освобождения, результат выполнения программы будет таким же, как при выполнении этой программы в системе с последовательной моделью консистентности.

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

6.3.7 Консистентность по входу.

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

Кроме того, критические секции, охраняемые одной синхронизационной переменной могут быть двух типов:

1. секция с монопольным доступом (для модификации переменных);

1. секция с немонопольным доступом (для чтения переменных).

Рассмотрим использование синхронизационных переменных.

Каждая синхронизационная переменная имеет временного владельца - последний процесс, захвативший доступ к этой переменной. Этот владелец может в цикле выполнять критическую секцию не посылая при этом сообщений другим процессорам. Процесс, который в данный момент не является владельцем синхронизационной переменной, но требующий ее захвата, должен послать запрос текущему владельцу этой переменной для получения значения этой переменной и права собственности на синхронизационную переменную. Разрешена ситуация, когда синхронизационная переменная имеет несколько владельцев, но только в том случае, если связанные с этой переменной общие данные используются только для чтения.

Ниже приведены формальные правила, определяющие модель консистентности по входу:

(1) Процесс не может захватить синхронизационную переменную до того, пока не обновлены все переменные этого процесса, охраняемые захватываемой синхронизационной переменной;

1. Процесс не может захватить синхронизационную переменную в монопольном режиме (для модификации охраняемых данных), пока другой процесс, владеющий этой переменной (даже в немонопольном режиме), не освободит ее;

1. Если какой-то процесс захватил синхронизационную переменную в монопольном режиме, то ни один процесс не сможет ее захватить даже в немонопольном режиме до тех пор, пока первый процесс не освободит эту переменную и будут обновлены текущие значения охраняемых переменных в процессе, запрашивающем синхронизационную переменную.

6.3.8 Сравнение моделей консистентности.

Различия между описанными моделями консистентности памяти определяются ограничениями моделей, простотой реализации и способами программирования. В приведенной ниже таблице определены отличительные характеристики описанных моделей консистентности памяти.

(а) Модели консистентности, не использующие операции синхронизации.

(б) Модели консистентности с операциями синхронизации.

6.4 Протоколы когерентности.

WRITE-INVALIDATE - всем владельцам копий сообщается о их недействительности.

WRITE-UPDATE - организуется обновление копий у всех владельцов.

Выбор определяется частотами чтений и записей, а также временами оповещения и обновления.

1. Конструкторские решения.

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 на всех процессорах при выходе из цикла должно быть присвоено то значение, которое было получено на витке цикла с максимальным номером (требуется фиксировать на каждом процессоре максимальный номер витка, на котором переменной присваивается значение. При распределении витков последовательными блоками между процессорами достаточно фиксировать сам факт изменения переменной каждым процессором).

Вне цикла приведение в консистентное состояние переменной A[0] не требуется, поскольку на каждом процессоре выполняется один и тот же оператор, который присваивает одно и то же значение всем копиям переменной.

6.5.3 DSM на базе объектов.

Последнюю группу образуют многопроцессорные системы с объектной организацией распределенной общей памятью. В отличие от всех остальных рассмотренных систем, программы для объектно-ориентированной DSM системы не могут напрямую использовать общие переменные, а только через специальные функции-методы. Система поддержки выполнения параллельных программ, получив запрос на использование некоторой общей переменной, обрабатывает его, поддерживая при этом консистентное состояние разделяемых данных. Весь контроль осуществляется только программными средствами.

В тех случаях, когда для балансировки загрузки процессоров применяется миграция данных, воспользоваться соседством расположения данных в локальной памяти процессора затруднительно. В таких случаях потери эффективности из-за доступа к данным через функции могут быть вполне приемлемыми, поскольку они могут сполна компенсироваться тем выигрышем, который достигается балансировкой загрузки.

14