| Предыдущий раздел | Оглавление | Следующий раздел |
3.3.4. Семафоры
Ситуация изменилась в 1965 году, когда Дейкстра предложил использовать целочисленную переменную для подсчета количества активизаций, отложенных на будущее. Он предложил учредить новый тип переменной — семафор (semaphore). Значение семафора может быть равно 0, что будет свидетельствовать об отсутствии сохраненных активизаций, или иметь какое-нибудь положительное значение, если ожидается не менее одной активизации.
Дейкстра предложил использовать две операции с семафорами, которые сейчас обычно называют down и up. Операция down выясняет, отличается ли значение семафора от 0. Если отличается, она уменьшает это значение на 1 (то есть использует одну сохраненную активизацию) и продолжает свою работу. Если значение равно 0, процесс приостанавливается, не завершая в этот раз операцию down. И проверка значения, и его изменение, и, возможно, приостановка процесса осуществляются как единое и неделимое атомарное действие. Тем самым гарантируется, что с началом семафорной операции никакой другой процесс не может получить доступ к семафору до тех пор, пока операция не будет завершена или заблокирована. Атомарность является абсолютно необходимым условием для решения проблем синхронизации и исключения состязательных ситуаций. Атомарные действия, в которых группа взаи¬мосвязанных операций либо выполняется без каких-либо прерываний, либо вообще не выполняется, приобрели особую важность и во многих других областях информатики.
Операция up увеличивает значение, адресуемое семафором, на 1. Если с этим семафором связаны один или более приостановленных процессов, способных завершить ранее начатые операции down, система выбирает один из них (к примеру, произвольным образом) и позволяет ему завершить его операцию down. Таким образом, после применения операции up в отношении семафора, с которым были связаны приостановленные процессы, значение семафора так и останется нулевым, но количество приостановленных процессов уменьшится на 1. Операция увеличения значения семафора на 1 и активизации одного из процессов также является неделимой. Ни один из процессов не может быть заблокирован при выполнении операции up.
В качестве примера применения семафоров рассмотрим задачу производителя и потребителя (также известную как задача ограниченного буфера). Два процесса используют общий буфер фиксированного размера. Один из них, производитель, помещает информацию в буфер, а другой, потребитель, извлекает ее оттуда.
Проблемы возникают в тот момент, когда производителю требуется поместить новую запись в уже заполненный буфер. Решение заключается в блокировании производителя до тех пор, пока потребитель не извлечет как минимум одну запись. Также, если потребителю нужно извлечь запись из буфера и он видит, что буфер пуст, он блокируется до тех пор, пока производитель не поместит что-нибудь в буфер и не активизирует этого потребителя.
В примере, приведенном в листинге 3.2, семафоры используются двумя различными способами. Различия этих способов настолько важны, что требуют дополнительного разъяснения. Семафор mutex используется для организации взаимного исключения. Его предназначение — гарантировать, что в каждый отдельно взятый момент времени к буферу и соответствующим переменным имеет доступ по чтению или записи только один процесс.
Листинг 3.2. Задача производителя и потребителя, решаемая с помощью семафоров
#define N 100 /* Количество мест в буфере */
typedef int semaphore; /* Семафоры - это специальная разновидность целочисленной переменной */
semaphore mutex = 1; /* управляет доступом к критической области */
semaphore empty = N; /* подсчитывает пустые места в буфере */
semaphore full = 0; /* подсчитывает занятые места в буфере */
void producer(void)
{
int item;
while (TRUE) { /* TRUE - константа, равная 1 */
item = produce_item( ); /* генерация чего-нибудь для помещения в буфер */
down(&empty); /* уменьшение счетчика пустых мест */
down(&mutex); /* вход в критическую область */
insert_item(item); /* помещение новой записи в буфер */
up(&mutex); /* покинуть критическую область */
up(&full); /* инкремент счетчика занятых мест */
}
}
void consumer(void)
{
int item;
while (TRUE) { /* бесконечный цикл */
down(&full); /* уменьшение счетчика занятых мест */
down(&mutex); /* вход в критическую область */
item = remove_item( ); /* извлечение записи из буфера */
up(&mutex); /* выход из критической области */
up(&empty); /* увеличение счетчика пустых мест */
consume_item(item); /* работа с записью */
}
}
Другие семафоры используются для синхронизации. Семафоры full и empty нужны для гарантии наступления или ненаступления тех или иных конкретных последовательностей событий. В данном случае они гарантируют, что производитель приостановит свою работу при заполненном буфере, а потребитель приостановит свою работу, если этот буфер опустеет.
| Предыдущий раздел | Оглавление | Следующий раздел |