возможно наличие одного аргумента у обоих запросов (ожидания и запуска) - адреса ячейки памяти, предназначенной для их согласования.

Проблема производителя и потребителя

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

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

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

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

Листинг 2.3. Проблема производителя и потребителя с неустранимым состоянием соревнования

#define N 100 /* Максимальное количество элементов

/* в буфере */

int count = 0: /* Текущее количество элементов в буфере */

void producer(void) {

int item:

while (TRUE) { /* Повторять вечно */

item = produceJtemO; /* Сформировать следующий элемент */ if (count == N) sleepO: /* Если буфер полон, уйти в состояние /* ожидания */

insert item(item): /* Поместить элемент в буфер */

count = count +1: /* Увеличить количество элементов в буфере */

if (count == 1) wakeup(consumer): /* Был ли буфер пуст? */

void consumer(void) {

int item;

while (TRUE) { /* Повторять вечно */

if (count == 0) sleepO; /* Если буфер пуст, уйти в состояние

/* ожидания */

item = remove item( ); /* Забрать элемент из буфера */

count = count - 1; /* Уменьшить счетчик элементов в буфере */

if (count == N - 1) wakeup(producer): /* Был ли буфер полон? */ consume item(item); /* Отправить элемент на печать */

Для описания на языке С системных вызовов sleep и wakeup мы представили их в виде вызовов библиотечных процедур. В стандартной библиотеке С их нет, но они будут доступны в любой системе, в которой присутствуют такие системные вызовы. Процедуры insertjtem и removejtem помещают элементы в буфер и извлекают их оттуда.

Теперь давайте вернемся к состоянию состязания. Его возникновение вероятно, поскольку доступ к переменной count не ограничен. Может возникнуть следующая ситуация: буфер пуст, и потребитель только что считал значение переменной count, чтобы проверить, не равно ли оно нулю. В этот момент планировщик передал управление производителю, производитель поместил элемент в буфер и увеличил значение count, убедившись, что теперь оно стало равно 1. Зная, что ранее значение было равно О, а потребитель находился в состоянии ожидания, производитель активизирует потребителя с помощью вызова wakeup.

Но потребитель не был в состоянии ожидания, следовательно, сигнал активизации пропал впустую. Когда управление перейдет к потребителю, он вернется к считанному когда-то значению count, обнаружит, что оно равно О, и уйдет в состояние ожидания. Рано или поздно производитель наполнит буфер и также перейдет в состояние ожидания. Оба процесса так и останутся в состоянии простоя.

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

Несмотря на то что введение бита ожидания запуска спасло положение в нашем примере, легко представить ситуацию с несколькими процессами, в которой одного бита будет недостаточно. Мы можем добавить еще один бит, или 8, или 32, но это не решит проблему.

2.2.5. Семафоры

в 1965 году Дейкстра (Е. W. Dijkstra) предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее. Им был предложен новый тип переменных, так называемые семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активизации) или некоторым положительным числом, соответствующим количеству отложенных сигналов.

Дейкстра предложил две операции, down и up (обобщения sleep и wakeup). Операция down сравнивает значение семафора с нулем. Если значение семафора больше нуля, операция down уменьшает его (то есть расходует один из сохраненных сигналов активизации) и просто возвращает управление. Если значение семафора равно нулю, процедура down не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Атомарность операции чрезвычайно важна для разрешения проблемы синхронизации и предотвращения состояния состязания.

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

В оригинале Дейкстра употреблял вместо down и up обозначения Р и V соответственно. Мы не будем в дальнейшем использовать оригинальные обозначения, поскольку тем, кто не знает голландского языка, эти обозначения ничего не говорят (да и тем, кто знает язык, говорят немного). Впервые обозначения down и up появились в языке Алгол 68.

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

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