Процессы называются параллельными, если они существуют одновременно. Параллельные процессы могут работать совершенно независимо
друг от друга или они могут быть асинхронными – это значит им необходимо периодически синхронизироваться и взаимодействовать. Для иллюстрации параллельных асинхронных
процессов применяется нотация аналогичная той, которая применяется
в языках параллельного программирования Модула, Ада и т. п.
Параллельная обработка
Параллельное выполнение нескольких программ заманчиво,
как один из вариантов повышения быстродействия, и как следствие – производительности
ОС. Многопроцессорные вычислительные комплексы (суперкомпьютеры)
дают основание надеяться на внедрение мультипроцессорных систем в персональные
компьютеры, и в результате – на развитие основных концепций параллельного
программирования и создание соответствующего программного обеспечения. Здесь
встречаются принципиальные трудности:
- сложность определения фрагментов будущих программ, возможных
быть
распараллеленными;
- трудность отладки таких программ. Т.к. после предположительного
исправления ошибки трудно восстановить последовательность событий,
на которых эта ошибка проявилась впервые. Поэтому нельзя утверждать с
уверенностью, что данная ошибка устранена.
- трудность доказательства корректности параллельных программ
по сравнению с последовательными программами.
Взаимоисключение
Пусть имеется многотерминальная система разделения времени,
в которой пользователи вводят текстовые данные. Каждый пользователь
использует один терминал. Ввод очередной строки заканчивается нажатие на клавишу
Enter. Необходимо вести постоянный учет общего количества строк, введенных пользователями
с начала работы системы. Предполагается, что контроль каждого терминала
ведется при помощи отдельного процесса. Сигналом к увеличению на 1 глобальной
переменной STROKWWEDENYH – служит ввод сигнала Enter с соответствующего
терминала. Пусть каждый процесс имеет в своем составе копию кода:
mov ax, STROKWWEDENYH
inc ax
mov STROKWWEDENYH, ax
Пусть в данный момент глобальная переменная
STROKWWEDENYH имеет значение 21687. Пусть один процесс успевает выполнить только
первые две команды mov ax, STROKWWEDENYH inc ax
После чего в регистре ax (аккумуляторе) будет 21688. Затем
этот процесс ввиду истечения отведенного ему кванта времени уступает процессор
другому процессу. Второй процесс выполняет теперь все три команды, устанавливая
значение
STROKWWEDENYH=21688. Далее 2-й процесс возвращает управление
1-ому процессу, который возобновляет свое выполнение с команды mov STROKWWEDENYH, ax и также помещает значение 21688 в STROKWWEDENYH. Т.о.,
из-за не координированного доступа к разделяемой переменной
STROKWWEDENYH – потеряли одну строку.
Эту задачу можно решить, если каждому процессу предоставить
монопольное исключительное право доступа к переменной
STROKWWEDENYH. Когда один процесс увеличивает эту разделяемую переменную, всем остальным
процессам, которым нужно было бы также, нарастить значение STROKWWEDENYH в то же
самое время – придется ждать. А когда данный процесс закончит свое использование
переменной, будет разрешено продолжать работу одному из процессов, находящихся
в состоянии ожидания. Т. о. каждый процесс, обращающийся к разделяемым данным,
исключает
для других процессов возможность одновременного с ним обращения к
данным. Это называется взаимоисключением. Когда процесс производит обращение
к разделяемым данным, то говорят, что он находится на своем критическом участке.
Применение примитивов взаимоисключения
для управления взимодействием процессами
program взаимоисключение;
var строквведенных: целое;
procedure
процессодин;
while истина do
begin
взятиеследующейстрокитерминала;
входвзаимоисключения;
строквведенных:=строквведенных + 1;
выходвзаимоисключения;
обработкастроки
end;
procedure процессдва;
while истина do
begin
взятиеследующейстрокитерминала;
входвзаимоисключения;
строквведенных:=строквведенных + 1;
выходвзаимоисключения;
обработкастроки
end;
begin
строквведенных:=0;
parbegin
процессодин;
процессдва
parend
end.
Для простоты полагаем, что взаимодействуют два параллельных
процесса. Управлять n процессами – значительно сложнее. Две конструкции входвзаимоисключения и выходвзаимоисключения обрамляют критические участки в каждом из процессов. Эти операторы
называются примитивы взаимоисключения. Внутри этого участка обеспечен монопольный
доступ к переменной
СТРОКВВЕДЕННЫХ.
Если один из процессов находится внутри своего критического
участка, а другой процесс пытается войти в этот же участок, то он переводится
в состояние ожидания, пока первый процесс не выполнит выходвзаимоисключения. Только после этого первый процесс сможет войти в свой критический участок.
Операторные скобки parbegin
оператор 1;
оператор 2;
…………..
оператор n
parend
служат для синтаксического оформления параллельно выполняющихся
процессов в рамках программы, где они употреблены. Оператор parbegin указывает, что последовательное течение программы должно быть разделено на несколько параллельно выполняемых последовательностей
(цепочек управления). В данном случае на n отдельных самостоятельных цепочек - по
одной для каждого внутреннего оператора для данной конструкции.
Оператор parend указывает, что вышеперечисленные параллельно выполняемые цепочки должны слиться воедино и должно возобновиться последовательное
выполнение программы.
Если процессодин и процессдва выполняют входвзаимоисключения одновременно, то одному из них случайным образом будет разрешено продолжать
работу, а другому – остается ждать.
Реализация примитивов взаимоисключения
(общие замечания).
Для реализации примитивов взаимоисключения «входвзаимоисключения»
(код входа взаимоисключения) и «выходвзаимоисключения» (код
выхода взаимоисключения) необходимо, чтобы соблюдались следующие четыре правила:
1. Задача д. б. решена чисто программным способом на ЭВМ
(компьютере), не имеющей специальных команд взаимоисключения. Каждая команда машинного языка выполняется, как неделимая операция, т. е. каждая ______8начатая команда завершается без прерывания ее. Будем считать, что в случае одновременных попыток нескольких процессоров обратиться
к одному и тому же элементу данных возможные конфликты разрешаются
аппаратно при помощи схемы защитной блокировки памяти. Эта схема распараллеливает конфликтующие обращения к памяти со стороны отдельных процессоров, выстраивая их в очередь, т. е.,
разрешая производить только одно обращение в каждый конкретный момент
времени. Предполагается, что эти отдельные обращения обслуживаются
в случайном порядке.
2. Не должно быть никаких предположений об относительных
скоростях выполнения асинхронных параллельных процессов.
3. Процессы, находящиеся вне своих критических участков,
не могут препятствовать другим процессам входить в их собственные
критические участки.
4. Не должно быть бесконечного откладывания момента входа
процессов в их критические участки. Неплохие реализации программных механизмов взаимоисключения
предложил голландский математик Деккер. Существенно улучшил этот
алгоритм Э. Дейкстра.
| 
