24. Понятие семафоров. Виды семафоров. Операции над семафорами. Пример обеспечения взаимоисключения с помощью семафоров.

Под семафором S понимается переменная особого типа, значение которой может опрашиваться и изменяться только при помощи специальных операций P(S) и V(S), реализуемых в соответствии со следующими алгоритмами:

операция P(S)

если S > 0

то S = S – 1

иначе < ожидать S >

операция V(S)

если < один или несколько потоков ожидают S >

то < снять ожидание у одного из ожидающих потоков >

иначе S = S + 1

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

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

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

Semaphore Sem=1; // семафор взаимоисключения потоков

Thread_1() {

while (1) {

// проверить семафор и ждать, если ресурс занят

P(Sem);

< Использование общего ресурса >

// освободить один из ожидающих ресурса потоков

// увеличить семафор, если нет ожидающих потоков

V(Sem);

}

______________________________________________________________________________________

25. Синхронизация процессов с помощью семафоров. Задача о производителе и потребителе.

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

Producer:	while(1) { produce_item;  put_item; }
Consumer:	while(1) { get_item;  consume_item; }

Если буфер забит, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация. Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex - для организации взаимоисключения на критических участках, которыми являются действия put_item и get_item (операции положить информацию и взять информацию не могут пересекаться, так как тогда возникнет опасность искажения информации). Тогда решение задачи выглядит так:

Semaphore mutex = 1; Semaphore empty = N, где N – емкость буфера; Semaphore full = 0; 

Producer: 

while(1) { 

produce_item;  P(empty);  P(mutex);  put_item;  V(mutex);  V(full); 

} 

Consumer: 

while(1) { 

P(full);  P(mutex);  put_item;  V(mutex);  V(empty);  consume_item; 

}

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

______________________________________________________________________________________