Параллельное программирование

Распараллеливание в МВК. Семафоры


Распараллеливание для полного использования ресурсов МВК осуществляется двумя путями:

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

Синхронизация информационно взаимосвязанных процессов производится с помощью механизма семафоров.

Пусть существует множество величин - примитивов синхронизации, имеющих тип "семафор" и принимающих в простейшем случае два значения: "открыт" и "закрыт". (В другой версии семафор — счетчик; закрытию соответствует его увеличение на единицу, а открытию — уменьшение на единицу.)

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

ОБЪЯВИТЬ (С) — объявляется список семафоров C, выделяется память и задается тип переменной при трансляции.

ЗАКРЫТЬ (С) — присваивает семафорам, перечисленным в списке C, значение "закрыт".

ЖДАТЬ (С) — в случае, если в C указаны семафоры со значением "закрыт", прерывает выполняемый процесс. Стек процесса условно дополняет очереди к закрытым семафорам, перечисленным в списке C. Таким образом, если с данной процедуры начинается выполнение некоторой работы, то оно будет поставлено в зависимость от условий выполнения каких-то других работ. Концом выполнения процедуры является переход к анализу очереди процессов для последующей загрузки процессора.

ОТКРЫТЬ (С) — семафорам, указанным в списке C, присваивается значение "открыт" и процессоры из очередей к данным семафорам переводятся в очередь для продолжения их выполнения.

Очередь процессов, конечно, одна, но в ней процессы, "зависшие" на семафорах, соответствующим образом помечаются.

Пусть параллельная программа имеет структуру, представленную на рис. 8.11

информационно-логическим графом (тонкие стрелки — связи по информации, толстые — по управлению).
Обозначение процедуры выше вершины с номером процесса означает, что процесс начинается с нее. Если процедура изображена ниже вершины, значит, процесс заканчивается ее выполнением. Штриховой линией отмечен возможный переход на повторное решение задачи.


Рис. 8.11.  Синхронизация распараллеливания с помощью семафоров

Выше рассмотрен механизм семафоров для информационно взаимосвязанных или взаимодействующих процессов. Однако семафоры применяются и для синхронизации обращений к общим данным и другим общим ресурсам. Рассмотрим вариант, применяемый в МВК "Эльбрус-2".

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

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

Процесс, который должен модифицировать общие данные — этот же массив, — "закрывает семафор по записи", засылая в него соответствующий признак. Попытка закрыть по записи уже закрытый семафор приводит к прерыванию, конфликт разрешает ОС. После модификации общих данных процесс "открывает" семафор.

Таким образом, семафор состоит из двух частей. В одной части содержится счетчик для закрытия по считыванию, в другой — признак (двоичная переменная) для закрытия по записи.

Указанных операций достаточно для решения различных задач синхронизации при использовании общих ресурсов.


Содержание раздела