Проектирование взаимодействующих вычислительных процессов

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

Различные ОС имеют разные средства синхронизации.

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

 

Параллельными называются процессы, которые одновременно находятся в каком-либо активном состоянии.

Два параллельных процесса могут быть независимыми.

 

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

Независимые процессы не влияют на работу друг друга (с точки зрения логики исполнения), они могут только задерживать работу друг друга.

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

 

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

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

 

Взаимодействовать могут 2 разновидности процессов: конкурирующие и совместно исполняющие некоторую работу. Конкурирующие действуют в некотором плане независимо, но имеют доступ к некоторым переменным.

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

 

Пример:

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

 

№ оператора	Р1	№ оператора	Р2
	R1:=x		R2:=x
	R1: R1+1		R2: R2+1
	X:= R1		X:= R2

 

Оба процесса могут исполняться с разной скоростью, поэтому время исполнения 1-6 не предсказуемо. Рассмотрим 2 случая:

Первый случай – когда используются операторы 1,2,3, а затем 4,5,6.

 

P1 R1:=x R1:=R1+1 x:=R1

 

P2 R2:=x R2:=R2+1 x:=R2

X

 

 

2 случай – когда в исполнение 1,2,3 вмешиваются 4,5,6

 

P1 R1:=x R1:=R1+1 x:=R1

 

P2 R2: =x R2: =R2+1 x: =R2

X

 

 

Лекция 4.

 

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

Таким образом, говоря о синхронизации процессов, имеется в виду синхронизация критических секций.

К синхронизации критических секций выдвигаются следующие требования:

 

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

 

ПР1 ПР2

 

 

 

Простейшим способом синхронизации может быть использование общего типа переменной, служащей указателем свободен критический ресурс или нет. Каждый раз, когда какой-то процесс первым занимает критический ресурс, он устанавливает указатель в состояние «занято». В результате никакой другой процесс не может обратиться к этому ресурсу.

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

+ Простота

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

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

Более широко используется механизм светофоров.

 

Светофоры (семафоры)

 

Светофор - переменная специального типа, которая доступна параллельным

процессам для проведения над ней только двух операций: открытия и закрытия (P и V).

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

Смысл операции P., закрытия светофора, заключается в том, чтобы проверить текущее значение светофора. Если оно неотрицательное, то осуществляется переход к следующей операции, стоящей за операцией Р и при этом значение семафора уменьшается на 1 (-1).

Операция V заключается в том, что значение семафора увеличивается на 1 (+1) при этом один или несколько процессов претендующих на ресурс устанавливается в состояние готовности.

InitSem (S,0) тогда структура:

ПР1: begin ПР2: begin

P(S) P(S)

CS1 CS2

V(S) V(S)

End End

 

 

Семафоры получили очень широкое распространение в ОС нашего времени.

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

Даже для одного критического ресурса можно устанавливать несколько семафоров.

Характерная особенность: при задании семафоров фактически не определяется критический ресурс.

 

Лекция 5.

 

Почтовые ящики

 

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

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

 

Размер и количество буферов определяется при создании почтового ящика.

Головной элемент обычно содержит информацию о количестве буферов и их размерах.

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

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

Почтовые ящики могут использоваться отправителями и получателями по-разному. Может быть обеспечена связь между 1 отправителем и одним получателем – это простейший случай.

Правило работы с почтовыми ящиками могут различаться у ОС.

Некоторый процесс Р1 может передать, а Р2 может читать. При этом Р2 может читать, а может не читать.

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

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

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

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

 

Реализация почтовых ящиков требует использования специальных операторов. Наиболее типовые операторы:

 

1. SEND_MESSADGE (получатель, сообщение, буфер)

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

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

 

2. WAIT_MESSADGE ([отправитель], [ сообщение ], [ буфер ])

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

 

3. SEND_ANSWER (ответ, [буфер])

Ответ помещается в буфер в котором находилось сообщение. Если отправитель ждал ответ, то он разблокируется.

 

4. WAIT_ANSWER (ответ, буфер)

Процесс блокируется до тех пор, пока ответ не поступает.

 

Основные достоинства использования почтовых ящиков:

+ простота, привычный механизм обмена сообщениями.

+ почтовые ящики могут служить синхронизаторами.

+ получатель и отправитель достаточно независимы друг от друга (т. е могут ждать, а могут и не ждать)