Добавлен: 29.10.2018
Просмотров: 48024
Скачиваний: 190
156
Глава 2. Процессы и потоки
области, H входит в состояние готовности (к примеру, после завершения операции
ввода-вывода). Теперь H входит в режим активного ожидания, но поскольку, пока вы-
полняется процесс H, выполнение L не планируется, у L не остается шансов вый ти из
своей критической области, поэтому H пребывает в бесконечном цикле. На подобную
ситуацию иногда ссылаются как на проблему инверсии приоритета.
Теперь рассмотрим некоторые примитивы взаимодействия процессов, которые блоки-
руют работу, пока им не разрешается входить в критическую область, вместо напрасной
траты времени центрального процессора. Представителями простейшей пары таких
примитивов являются sleep и wakeup. Системный вызов sleep блокирует вызывающий
его процесс, который приостанавливается до тех пор, пока его не активизирует другой
процесс. Активизирующий вызов wakeup использует один аргумент — активизируемый
процесс. Дополнительно и sleep и wakeup используют еще один аргумент — адрес памяти,
используемой для соотнесения вызовов sleep с вызовами wakeup.
Задача производителя и потребителя
В качестве примера применения этих примитивов рассмотрим задачу производителя
и потребителя
(также известную как задача ограниченного буфера). Два процесса
используют общий буфер фиксированного размера. Один из них, производитель,
помещает информацию в буфер, а другой, потребитель, извлекает ее оттуда. (Можно
также расширить проблему до m производителей и n потребителей, но мы будем рас-
сматривать только случай с одним производителем и одним потребителем, поскольку
такое допущение упрощает решение.)
Проблемы возникают в тот момент, когда производителю требуется поместить новую
запись в уже заполненный буфер. Решение заключается в блокировании производителя
до тех пор, пока потребитель не извлечет как минимум одну запись. Также, если по-
требителю нужно извлечь запись из буфера и он видит, что буфер пуст, он блокируется
до тех пор, пока производитель не поместит что-нибудь в буфер и не активизирует
этого потребителя.
На первый взгляд этот подход выглядит довольно простым, но он приводит к той же
разновидности состязательной ситуации, которая нам уже встречалась в примере
с каталогом спулера. Для отслеживания количества записей в буфере нам потребуется
переменная count. Если максимальное количество записей, которое может содержаться
в буфере, равно N, то программа производителя должна сначала проверить, не имеет
ли count значение N. Если переменная имеет такое значение, производитель должен за-
блокировать свое выполнение, а если не имеет, производитель должен добавить запись
и увеличить показание счетчика count.
Программа потребителя работает схожим образом: сначала проверяет, не является ли
значение count нулевым. Если оно равно нулю, процесс блокирует свое выполнение,
а если не равно нулю, он извлекает запись и уменьшает значение счетчика. Каждый
из процессов также проверяет, не нужно ли активизировать другой процесс, и если
нужно, проводит эту активизацию. Программы производителя и потребителя показаны
в листинге 2.5.
Чтобы выразить вызовы sleep и wakeup на языке C, мы покажем их в виде вызо-
вов библиотечных процедур. Они не являются частью стандартной библиотеки C,
но, по-видимому, были бы доступны на любой системе, имеющей эти системные
вызовы.
2.3. Взаимодействие процессов
157
Листинг 2.5. Задача производителя и потребителя с фатальной состязательной
ситуацией
#define N 100 /* количество мест для записей в буфере */
int count = 0; /* количество записей в буфере */
void producer(void)
{
int item;
while (TRUE) { /* бесконечное повторение */
item = produce_item( ); /* генерация новой записи */
if (count == N) sleep( ); /* если буфер полон, заблокироваться */
insert_item(item); /* помещение записи в буфер */
count = count + 1; /* увеличение счетчика записей в буфере */
if (count == 1) wakeup(consumer); /* был ли буфер пуст? */
}
}
void consumer(void)
{
int item;
while (TRUE) { /* бесконечное повторение */
if (count == 0) sleep(); /* если буфер пуст, заблокироваться */
item = remove_item( ); /* извлечь запись из буфера */
count = count− 1; /* уменьшение счетчика записей в буфере */
if (count == N − 1) wakeup(producer); /* был ли буфер полон? */
consume_item(item); /* распечатка записи */
}
}
Не показанные в листинге процедуры insert_item и remove_item занимаются помеще-
нием записей в буфер и извлечением их оттуда.
Вернемся теперь к состязательной ситуации. Причиной ее появления может стать сво-
бодный доступ к счетчику count. Как следствие может сложиться следующая ситуация.
Буфер пуст, и потребитель только что считал показания count, чтобы увидеть, что его
значение равно 0. В этот самый момент планировщик решает временно приостановить
выполнение процесса потребителя и возобновить выполнение процесса производи-
теля. Производитель помещает запись в буфер, увеличивает значение счетчика count
и замечает, что теперь оно равно 1. Приняв во внимание, что только что счетчик имел
нулевое значение, при котором потребитель должен находиться в заблокированном
состоянии, производитель вызывает процедуру wakeup, чтобы активизировать вы-
полнение процесса потребителя.
К сожалению, с точки зрения логики программы потребитель не находился в бездей-
ствующем состоянии, поэтому сигнал на активизацию будет утрачен. Когда подойдет
очередь возобновить выполнение процесса потребителя, он проверит ранее считанное
значение счетчика, определит, что оно было равно 0, и снова перейдет в заблокиро-
ванное состояние. Рано или поздно производитель заполнит буфер и тоже перейдет
в заблокированное состояние. И оба процесса впадут в вечную спячку.
Суть возникшей проблемы заключается в утрате вызова wakeup в отношении процесса,
который не находится в состоянии блокировки по собственной воле. Если бы этот вы-
158
Глава 2. Процессы и потоки
зов не утрачивался, то все бы работало должным образом. Быстро устранить проблему
позволит изменение правил за счет добавления к картине событий бита ожидания
активизации
. Этот бит устанавливается, когда в отношении процесса, который не на-
ходится в состоянии бездействия, вызывается процедура wakeup. Затем, когда процесс
попытается заблокироваться при установленном бите ожидания активизации, этот
бит снимается, но процесс не блокируется. Бит ожидания активизации становится
своеобразной копилкой, хранящей сигналы активизации. Потребитель снимает бит
ожидания активизации в каждой итерации цикла.
Хотя в нашем простом примере бит ожидания активизации спасает положение, не-
трудно создать такие примеры, где фигурируют три и более процесса, для которых
одного бита ожидания активизации явно недостаточно. Можно внести другие правки
и добавить второй бит ожидания активизации, а может быть, 8 или 32 таких бита, но,
в принципе, проблема останется нерешенной.
2.3.5. Семафоры
Ситуация изменилась в 1965 году, когда Дейкстра предложил использовать целочис-
ленную переменную для подсчета количества активизаций, отложенных на будущее.
Он предложил учредить новый тип переменной — семафор (semaphore). Значение
семафора может быть равно 0, что будет свидетельствовать об отсутствии сохраненных
активизаций, или иметь какое-нибудь положительное значение, если ожидается не
менее одной активизации.
Дейкстра предложил использовать две операции с семафорами, которые сейчас обычно
называют down и up (обобщения sleep и wakeup соответственно). Операция down выясня-
ет, отличается ли значение семафора от 0. Если отличается, она уменьшает это значение
на 1 (то есть использует одну сохраненную активизацию) и продолжает свою работу.
Если значение равно 0, процесс приостанавливается, не завершая в этот раз операцию
down. И проверка значения, и его изменение, и, возможно, приостановка процесса осу-
ществляются как единое и неделимое атомарное действие. Тем самым гарантируется,
что с началом семафорной операции никакой другой процесс не может получить доступ
к семафору до тех пор, пока операция не будет завершена или заблокирована. Атомар-
ность является абсолютно необходимым условием для решения проблем синхронизации
и исключения состязательных ситуаций. Атомарные действия, в которых группа взаи-
мосвязанных операций либо выполняется без каких-либо прерываний, либо вообще не
выполняется, приобрели особую важность и во многих других областях информатики.
Операция up увеличивает значение, адресуемое семафором, на 1. Если с этим сема-
фором связаны один или более приостановленных процессов, способных завершить
ранее начатые операции down, система выбирает один из них (к примеру, произвольным
образом) и позволяет ему завершить его операцию down. Таким образом, после приме-
нения операции up в отношении семафора, с которым были связаны приостановленные
процессы, значение семафора так и останется нулевым, но количество приостанов-
ленных процессов уменьшится на 1. Операция увеличения значения семафора на 1
и активизации одного из процессов также является неделимой. Ни один из процессов
не может быть заблокирован при выполнении операции up, равно как ни один из про-
цессов не может быть заблокирован при выполнении wakeup в предыдущей модели.
Между прочим, в первоначальном варианте своей работы Дейкстра вместо down и up
использовал имена P и V соответственно. Но в них не было никакого мнемонического
2.3. Взаимодействие процессов
159
смысла для тех, кто не говорит по-голландски, да и для тех, кто говорит, смысл был
едва уловим — Proberen (пытаться) и Verhogen (поднимать выше), поэтому вместо них
мы будет употреблять down и up. Впервые они были представлены в языке програм-
мирования Algol 68.
Решение задачи производителя-потребителя
с помощью семафоров
В листинге 2.6 показано, как с помощью семафоров решается проблема утраченных ак-
тивизаций. Чтобы заставить их корректно работать, очень важно, чтобы их реализация
предусматривала неделимый режим работы. Вполне естественно было бы реализовать
операции up и down в виде системных вызовов, чтобы операционная система на время
тестирования семафора, обновления его значения и приостановки процесса при не-
обходимости кратковременно запрещала все прерывания. Поскольку все эти действия
занимают только несколько команд, запрет на прерывания не причинит никакого вреда.
Если используются несколько центральных процессоров, каждый семафор должен
быть защищен переменной lock, а для гарантии того, что семафор в отдельно взятый
момент времени задействуется только одним центральным процессором, используется
команда TSL или XCHG.
Нужно усвоить, что использование TSL или XCHG для предупреждения одновремен-
ного доступа к семафору нескольких центральных процессоров в корне отличается от
режима активного ожидания производителем или потребителем момента опустошения
или наполнения буфера. Операция работы с семафором займет лишь несколько микро-
секунд, а ожидание производителя или потребителя может быть сколь угодно долгим.
В этом решении используются три семафора: один из них называется full и предна-
значен для подсчета количества заполненных мест в буфере, другой называется empty
и предназначен для подсчета количества пустых мест в буфере, третий называется
mutex, он предотвращает одновременный доступ к буферу производителя и потреби-
теля. Семафор full изначально равен 0, семафор empty изначально равен количеству
мест в буфере, семафор mutex изначально равен 1. Семафоры, инициализированные
значением 1 и используемые двумя или более процессами для исключения их одно-
временного нахождения в своих критических областях, называются двоичными се-
мафорами
. Взаимное исключение гарантируется в том случае, если каждый процесс
совершает операцию down непосредственно перед входом в свою критическую область
и операцию up сразу же после выхода из нее.
Теперь, когда в нашем распоряжении имеется хороший примитив взаимодействия
процессов, давайте вернемся назад и заново рассмотрим последовательность пре-
рываний, показанную в табл. 2.2. В системе, использующей семафоры, естественным
способом скрыть прерывания станет использование семафора с исходным нулевым
значением, связанным с каждым устройством ввода-вывода. Сразу же после запуска
устройства ввода-вывода управляющий процесс выполняет операцию down в от-
ношении связанного с этим устройством семафора, при этом немедленно переходя
в состояние заблокированности. Затем при поступлении прерывания его обработчик
выполняет операцию up в отношении связанного с устройством семафора, которая
переводит соответствующий процесс в состояние готовности к продолжению вы-
полнения. В этой модели шаг 5 из табл. 2.2 состоит из выполнения операции up
над семафором устройства, с тем чтобы на шаге 6 планировщик мог запустить про-
грамму, управляющую устройством. Разумеется, если к этому моменту будут готовы
160
Глава 2. Процессы и потоки
к выполнению сразу несколько процессов, планировщик может выбрать следующим
для выполнения более важный процесс. Позже в этой главе мы еще рассмотрим не-
которые алгоритмы, используемые для работы планировщика.
В примере, приведенном в листинге 2.6, семафоры используются двумя различными
способами. Различия этих способов настолько важны, что требуют дополнительного
разъяснения. Семафор mutex используется для организации взаимного исключения.
Его предназначение — гарантировать, что в каждый отдельно взятый момент времени
к буферу и соответствующим переменным имеет доступ по чтению или записи толь-
ко один процесс. Организуемое взаимное исключение призвано предотвратить хаос.
В следующем разделе мы изучим взаимное исключение и способы его достижения.
Листинг 2.6. Задача производителя и потребителя, решаемая с помощью
семафоров
#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 нужны для
гарантии наступления или ненаступления тех или иных конкретных последователь-
ностей событий. В данном случае они гарантируют, что производитель приостановит
свою работу при заполненном буфере, а потребитель приостановит свою работу, если