3. Асинхронные параллельные процессы. Проблема «производитель-потребитель».

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

Асинхронные параллельные процессы, реализующие единый алгоритм решения некоторой задачи, неизбежно вступают во взаимодействие при разделении общих ресурсов. (реализ. как правило на многопроцессорных ВС с автономным управление для каждого процессорного элемента). Такие ресурсы: различные устройства; общая память; общие структуры данных и процедуры.

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

1. Синхронизация 2-х и более процессов; 2. Проблема «производитель - потребитель»;

3. Проблема взаимных блокировок

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

• SR – повторно используемые (все аппаратный ресурсы (устройства, каналы сязи, память), преоперабельные процедуры, неизменяемые ресурсы структуры данных - после освобождения процессом возвращаются в систему в неизменном виде для дальнейшего использования).

• CR – потребляемые (изменяемые структуры данных и процедуры, а также все сообщения и сигналы, информационные ресурсы, программные, т.е. не могут возвратиться с систему в неизменном виде).

Некоторые процессы в системе генерируют потребляемые ресурсы определенного типа, другие их потребляют. Необходима синхронизация процессов производителя и потребителя по каждому из ресурсов CR-типа. Данная проблема решается с помощью общих семафоров. Общий семафор – целочисленная переменная, принимающая значения 0 ≤ x ≤ n. Операции определенные над семафорами.

P(x)	x-1, если x > 0
	0, если x = 0 – перевод процесса в режим ожидания (уменьш. на 1)
V(x)	x+1, если x < n (увелич. на 1)
	x, если x = n

Процесс-производитель перед генерацией CR-ресурса выполняет над общим семафором V операцию, а процесс-потребитель – P операцию. Т.о. осуществляется их синхронизация. Если семафор закрыт, то процесс производитель приходит в состояние ожидания. Общий семафор имеет физический смысл:

4. Асинхронные параллельные процессы. Проблемы синхронизации параллельных процессов.

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

Асинхронные параллельные процессы, реализующие единый алгоритм решения некоторой задачи, неизбежно вступают во взаимодействие при разделении общих ресурсов. (реализ. как правило на многопроцессорных ВС с автономным управление для каждого процессорного элемента). Такие ресурсы: различные устройства; общая память; общие структуры данных и процедуры. Взаимодействие параллельных процессов основано на решении 3х проблем: 1. Синхронизация 2-х и более процессов; 2. Проблема «производитель - потребитель»; 3. Проблема взаимных блокировок.

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

Проблема синхронизации возникает при использовании параллельными процессами общих ресурсов: аппаратные ресурсы; программные ресурсы (структуры данных и процедуры); информационные ресурсы. Режимы использования: монопольное (ресурсом владеет 1 процесс); разделяемое (любое число процессов)

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

Задача синхронизации – обеспечить вхождение в свою критическую секцию только одного процесса. Могут использоваться как программные, так и аппаратные средства. Средства синхронизации: 1) высокого уровня; 2) низкого уровня.

Нижний уровень: «двоичный семафор» (частный случай общего семафора)

Двоичный семафор: это переменная, связанная с некоторым критическим ресурсом и может принимать значения 0 –семафор закрыт/1-семафор открыт

P(x)	x, если x = 0; x-1, если x = 1
	Если семафор открыт, то его значении становиться равным 0, а процесс входит в критическую секцию. Если перед операцией семафор =0, то оно не изменяется, а сам процесс становится в очередь ожидания.
V(x)	x, если x = 1; x+1, если x = 0
	Если семафор открыт → значение не меняется и ничего не происходит. Если закрыт → первый процесс выходит из крит.секции, а на его место выбирается процесс из очереди ожидания, который входит в свою крит.секцию.

Каждый процесс перед входов в крит.секцию выполняет P операцию, а перед выходом – V операцию. P и V операции неделимы. Начавшись, они не могут быть прерваны.

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