Распараллеливание в МВК. Семафоры
Распараллеливание для полного использования ресурсов МВК осуществляется двумя путями:
- на основе естественного существования независимых задач пользователей;
- на основе существования сложных программных систем, которые состоят из взаимосвязанных процессов, допускающих параллельное выполнение.
Синхронизация информационно взаимосвязанных процессов производится с помощью механизма семафоров.
Пусть существует множество величин - примитивов синхронизации, имеющих тип "семафор" и принимающих в простейшем случае два значения: "открыт" и "закрыт". (В другой версии семафор — счетчик; закрытию соответствует его увеличение на единицу, а открытию — уменьшение на единицу.)
В состав ОС входит ряд процедур, которые обеспечиваются аппаратными средствами и отражаются на входном языке, т.е. доступны пользователю. Минимально необходимый набор таких процедур:
ОБЪЯВИТЬ (С) — объявляется список семафоров C, выделяется память и задается тип переменной при трансляции.
ЗАКРЫТЬ (С) — присваивает семафорам, перечисленным в списке C, значение "закрыт".
ЖДАТЬ (С) — в случае, если в C указаны семафоры со значением "закрыт", прерывает выполняемый процесс. Стек процесса условно дополняет очереди к закрытым семафорам, перечисленным в списке C. Таким образом, если с данной процедуры начинается выполнение некоторой работы, то оно будет поставлено в зависимость от условий выполнения каких-то других работ. Концом выполнения процедуры является переход к анализу очереди процессов для последующей загрузки процессора.
ОТКРЫТЬ (С) — семафорам, указанным в списке C, присваивается значение "открыт" и процессоры из очередей к данным семафорам переводятся в очередь для продолжения их выполнения.
Очередь процессов, конечно, одна, но в ней процессы, "зависшие" на семафорах, соответствующим образом помечаются.
Пусть параллельная программа имеет структуру, представленную на рис. 8.11
информационно-логическим графом (тонкие стрелки — связи по информации, толстые — по управлению).
Обозначение процедуры выше вершины с номером процесса означает, что процесс начинается с нее. Если процедура изображена ниже вершины, значит, процесс заканчивается ее выполнением. Штриховой линией отмечен возможный переход на повторное решение задачи.
Рис. 8.11. Синхронизация распараллеливания с помощью семафоров
Выше рассмотрен механизм семафоров для информационно взаимосвязанных или взаимодействующих процессов. Однако семафоры применяются и для синхронизации обращений к общим данным и другим общим ресурсам. Рассмотрим вариант, применяемый в МВК "Эльбрус-2".
Участок программы, использующий (считывающий или модифицирующий) общие для нескольких процессов данные, называется критическим блоком(иногда — критической секцией).
Для синхронизации (соблюдения последовательности) обращения к общим данным семафоры сопровождают массивы данных и указываются в их дескрипторах. В семафоре предусмотрено поле, в котором указано, сколько процессов пользуются в данный момент этим массивом. Очередной процесс перед считыванием из массива увеличивает на единицу значение этого поля, а при выходе из критического блока уменьшает его на единицу. Ненулевое значение поля означает, что семафор "закрыт по считыванию".
Процесс, который должен модифицировать общие данные — этот же массив, — "закрывает семафор по записи", засылая в него соответствующий признак. Попытка закрыть по записи уже закрытый семафор приводит к прерыванию, конфликт разрешает ОС. После модификации общих данных процесс "открывает" семафор.
Таким образом, семафор состоит из двух частей. В одной части содержится счетчик для закрытия по считыванию, в другой — признак (двоичная переменная) для закрытия по записи.
Указанных операций достаточно для решения различных задач синхронизации при использовании общих ресурсов.
