Реализация мониторов и передачи сообщений с помощью семафоров

Рассмотрим сначала, как реализовать мониторы с помощью семафоров. Для этого нам нужно уметь реализовывать взаимоисключения при входе в монитор и условные переменные. Возьмем семафор mutex с начальным значением 1 для реализации взаимоисключения при входе в монитор и по одному семафору c_i для каждой условной переменной. Когда процесс входит в монитор, компилятор будет генерировать вызов функции monitor_enter, которая выполняет операцию P над семафором mutex для данного монитора. При нормальном выходе из монитора (то есть при выходе без вызова операции signal для условной переменной) компилятор будет генерировать вызов функции monitor_exit, которая выполняет операцию V над этим семафором.

Для выполнения операции wait над условной переменной компилятор будет генерировать вызов функции wait, которая выполняет операцию V для семафора mutex, разрешая другим процессам входить в монитор, и выполняет операцию P над соответствующим семафором ci, блокируя вызвавший процесс. Для выполнения операции signal над условной переменной компилятор будет генерировать вызов функции signal_exit, которая выполняет операцию V над ассоциированным семафором ci, и выход из монитора, минуя функцию monitor_exit.

Semaphore mutex = 1;

void monitor_enter(){

P(mutex);

}

void monitor_exit(){

V(mutex);

}

void wait(){

V(mutex);
P(c_i );

}

void signal_exit(){

V(c_i);

}

Заметим, что при выполнении функции signal_exit, процесс покидает монитор без увеличения значения семафора mutex, не разрешая тем самым всем процессам, кроме разбуженного, войти в монитор. Это увеличение совершит разбуженный процесс, когда покинет монитор нормальным способом, либо когда выполнит новую операцию wait над какой-либо условной переменной.

Рассмотрим теперь, как реализовать передачу сообщений, используя семафоры. Для простоты опишем реализацию только одной очереди сообщений. Выделим в разделяемой памяти достаточно большую область под хранение сообщений, там же будем записывать, сколько пустых и заполненных ячеек находится в буфере, хранить ссылки на списки процессов, ожидающих чтения и памяти. Взаимоисключение при работе с разделяемой памятью будем обеспечивать семафором mutex. Также заведем по одному семафору c_i на взаимодействующий процесс для того, чтобы обеспечивать блокирование процесса при попытке чтения из пустого буфера или при попытке записи в переполненный буфер. Поглядим, как такой механизм будет работать. Начнем с процесса, желающего получить сообщение.

Процесс-получатель с номером i, прежде всего, выполняет операцию P(mutex), получая в монопольное владение разделяемую память.После чего он изучает наличие сообщений в буфере. Если сообщений нет, то он заносит себя в список процессов, ожидающих сообщения, выполняет V(mutex) и P(c_i ). Если сообщение в буфере есть, то он читает сообщение, изменяет счетчики буфера и проверяет, есть ли процессы в списке процессов, жаждущих записи. Если такой процесс есть (с номером j), то он удаляется из этого списка, выполняется V для его семафора cj, и мы выходим из критического района. Проснувшийся процесс начинает выполняться в критическом районе, так как mutex у нас имеет значение 0, и никто более не может попасть в критический район. При выходе из критического района именно разбуженный процесс произведет вызов V(mutex).

Как строится работа процесса-отправителя с номером i? Процесс, посылающий сообщение, тоже ждет, пока он не сможет иметь монополию на использование разделяемой памяти, выполнив операцию P(mutex). Далее он проверяет наличие места в буфере и, если оно есть, помещает сообщение в буфер, изменяет счетчики и смотрит, есть ли процессы, ожидающие сообщения. Если нет, выполняет V(mutex) и выходит из критической области, если есть (с номером j), будит один из них, вызывая V(cj), с одновременным удалением этого процесса из списка процессов, ожидающих сообщений, и выходит из критического региона без вызова V(mutex), предоставляя тем самым возможность разбуженному процессу прочитать сообщение. Если места в буфере нет, то процесс-отправитель заносит себя в очередь процессов, ждущих возможности записи, и вызывает V(mutex) и P(c_i ).