Взаимодействие параллельных процессов

Размещено на http://www.allbest.ru/

Лекция

Взаимодействие параллельных процессов

1. Задачи синхронизации

синхронизация программный очередность

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

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

Часто механизм синхронизации выполняет 2 функции: упорядочивают развитие процессов, обеспечивают информационное взаимодействие.

Число задач синхронизации не ограничено, но сущ. некоторые типичные случаи:

1) Задача взаимного исключения (необходимо согласовать работу не более 2 параллельных процессов), при использовании некоторого критического ресурса (КО - критической области) с выполнение следующих требований:

одновременно внутри критической области не может находиться более 1 процесса.

критические области не должны иметь приоритет в отношении друг друга.

остановка процесса вне КО никак не влияет на работу других процессов по использованию КО

для одновременно поступивших запросов от равно приоритетных процессов, решение о вхождении в КО конечного времени.

скорости развития процессов неизвестны и произвольны.

любой процесс переходит в любое неактивное состояние только за пределами КО.

процесс использует КО конечное время.

2. Задача «Производитель-потребитель»

Наиболее простой случай -- взаимодействие двух процессов. Первый вырабатывает сообщения, второй -- принимает (потребитель). Взаимодействие идет через общую область памяти: которая и является критическим ресурсом. Она позволяет хранить только одно сообщение, все сообщения фиксированной длины.

Для согласования работы двух процессов необходимо:

выполнение задачи взаимного исключения для общей памяти.

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

Производитель не может поместить следующее сообщение в занятую область, из которой не считано предыдущее. Процесс - производитель либо получает предупреждение о невозможности размещения, либо переводится в состояние ожидания (блокировка) очистки памяти. Потребитель не может читать пустую область. Возможно 2 варианта:

Для варианта с ожиданием необходимо реализовать механизм поддержки очереди. При изменении состояния области изменение состояния процесса.

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

Эта задача реализована - используется при реализации конвейерных команд (dir | sort).

«Читатель и писатель».

Существует 2 типа процессов: читатели -- могут одновременно читать информацию из области; писатели могут писать информацию, исключая как друг друга, так и читателей (т.е. запись идет с условиями задачи взаимного исключения).

Может быть вариант, когда читатели имеют больший приоритет по сравнению с любым писателем (чтобы 1 писатель не заставлял ждать всех читателей).

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

«Обедающие философы»

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

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

Здесь вилки изображают парно используемый ресурс. Если 1 то ничего.

Возможны 2 ситуации:

тупиковая: все одновременно проголодались, взяли правую вилку, есть нельзя - нет левой вилки, и каждый философ ждет, когда сосед положит вилку.

голодание отдельного философа в случае заговора его соседей. Каждый раз, когда он собирается поесть, то слева, то справа забирают вилку.

Используется при построении системы использования ресурсов.

3. Основные вопросы построения механизмов синхронизации

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

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

На промежутке t_ко КО имеет свойство неделимости, что необходимо для задачи взаимного исключения.

Достоинства: простота.

Недостатки:

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

2) во время t_ко машина никак не реагирует на внутренние и внешние события, другие процессы не могут развиваться, а текущий процесс становится монопольным хозяином не только КР но и ЦП.

При длительном и частом использовании КО многозадачность может быть сведена на нет, нужно применение состояния КО, которая должна быть доступна всем процессам. Они должны ее не только читать, но и изменять. В этом случае эта переменна тоже становится критическим ресурсом, но вспомогательным.

При помощи блокировки прерывания устанавливается захват вспомогательной КО, изменяется его состояние, потом прерывания снова разрешаются, после чего можно приступать к работе с основным КР. На выходе аналогично вспомогательному КР переводится в «Свободно».

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

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

Действия при занятости основного ресурса могут быть:

режим «занято»: процесс сам должен периодически проверять освобождение ресурса

режим пассивного ожидания -- активный процесс переводится в состояние Blocked.

Требуется организовать очередь к ресурсу со всеми ее атрибутами (формирование, обслуживание и т.д.)

4. Использование семафоров

Понятие семафор введено в 75 г. {Дейлстром}.

Семафор - переменная специального типа, которая доступна параллельным процессам для 2-х операций - закрытие и открытие (P и V). Они неделимы при выполнении и взаимоисключающие, т. е. являются примитивными по отношению к семафору.

Поэтому существует средство формирования и обслуживания очередей.

Семафорных механизмов существует много. Они отличаются значениями С, набором примитивов и т, д.

Примеры:

Для простых семафоров возможны следующие варианты значений:

любые целые значения С

любые целые неотрицательные значения С

Особый случай - двоичный семафор.

Обобщенный алгоритм Р примитива:

Проверить значение S, если оно >0, перейти к выполнению следующей команды, если <=0 (S закрыт) перевести процесс в состояние пассивного ожидания, уменьшив S на 1. Процесс “засыпает” по С.

V-примитив

S увеличиваем на 1 и “будим” одного или несколько спящих процессов по С - перевод в очередь готовых процессов из блокировки.

Пример Р примитива:

S:=S-1;

If S<0 then

Перевести процесс в очередь к S (блокировка)

Else

Работа с КР

V - примитив

If S<0 then

Перевести один или несколько процессов в состояние READY;

S:=S+1;

Пример использования семафора:

Begin

S:=1;

StartParallelProcess ;

1: ... P(S); KO; V'(S); ...

2: ... P(S); KO; V'(S); ...

:

StopParallelProcess;

End.

Возможны 2 варианта поведения процесса после побудки.

Вариант первый.

Процесс снова пытается выполнить P примитив, считая предыдущую попытку неудачной.

В этом случае возможен тупик.

S=1

P1 - S=0;

P2 - S= -1; “заснул”

V1 - S=0

P2 - S= -1; ”заснул”

P1 - S= -2; “заснул”

В случае использования другого алгоритма - этого нет.

При S<0 (когда семафор закрыт); ABS(S) определяет длину очереди к семафору из заснувших процессов.

Еще нужно из М процессов одновременно использовать КР N процессами.

Алгоритм может быть таким:

Begin

S:=N;

StartParallelProcess;

1: ... P(S); KO; V'(S); ...

2: ... P(S); KO; V'(S); ...

:

:

M: ... P(S); KO; V(S); ...

StopParallelProcess;

END.

Второй вариант.

Рассмотрим, когда S не может быть больше 0.

Для определения длины очереди ожидающих процессов вводим дополнительную переменную L, тогда изменятся примитивы.

Примитив P'(S)

IF S=0 THEN BEGIN

Остановить процесс и перевести его в очередь к S;

L:=L+1 END

ELSE S:=S-1;

Примитив V'(S)

IF L<>0 THEN BEGIN

Пометить 1 процесс из очереди к S в Ready

L:=L-1 END

ELSE S:=S+1

Для приведенного V'(S) в готовности переводится только один процесс.

При этом процессы, стоящие в очереди к семафору имеют как бы более высокий приоритет, т. к. после V' один из них переводится в готовность, а затем входит в КО. При выполнении P' процесс всегда попадет в очередь к семафору при L<>0, и должен будет пройти 2 очереди - к семафору и к готовности.

Для выравнивания приоритетов всех процессов можно при выполнении V' все процессы из очереди перевести в готовность. В этом случае используется первый вариант реактивации.

Недостаток способа: увеличение системных издержек.

Рассмотрим такой пример.

BEGIN

S:=1; Q=0; КО: 1,2,2,2,1,1,1

StartParallelProcess;

1: ... P(S); KO; V'(S); ...

2: ... P(S); KO; V'(S); ...

:

StopParallelProcess;

END.

Var S,Q: Semaphore

BEGIN

S:=1; Q:=1;

S:=1;

StartParallelProcess; {1,2,1,2,1}

1: ... P(S); KO; V'(S); ...

2: ... P(S); KO; V'(S); ...

:

StopParallelProcess

END.

В этом случае порядок работы с КО жестко задан.

Эта схема может использоваться при реактивации задачи производитель-потребитель (1-произв., 2-потреб.). Если область может хранить N сообщений, в этом случае S инициализируется числом и (S=N).

Размещено на Allbest.ru