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