шинства тестов будут хорошими, но изредка будет происходить нечто странное и необъяснимое.

2.2.2. Критические области

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

Проблему исключения состояний состязания можно сформулировать на абстрактном уровне. Некоторый промежуток времени процесс занят внутренними расчетами и другими задачами, не приводящими к состояниям состязания. В другие моменты времени процесс обращается к совместно используемым данным или выполняет какое-то иное действие, чреватое состязанием. Часть программы, в которой происходит обращение к совместно используемым данным, называется критической областью или критической секи/лей. Если нам удастся избежать одновременного нахождения двух процессов в критических областях, мы сможем избежать состязаний.

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

1. Два процесса не должны одновременно находиться в критических областях.

2. В программе не должно быть предположений о скорости или количестве процессоров.

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

4. Недопустима ситуация, в которой процесс вечно ждет попадания в критическую секцию.

2.2.3. Взаимное исключение с активным ожиданием

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

Запрет на прерывания

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

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

С другой стороны, для ядра характерна блокировка прерываний для некоторых команд при работе с переменными или списками. Возникновение прерывания в момент, когда, например, список готовых процессов находится в неопределенном состоянии, могло бы привести к состоянию состязания. Итак, запрет прерываний бывает полезным в самой операционной системе, но это решение неприемлемо в качестве механизма взаимного исключения для пользовательских процессов.

Переменные блокировки

Теперь попробуем найти программное решение. Рассмотрим одну совместно используемую переменную блокировки, изначально равную 0. Если процесс хочет попасть в критическую область, он предварительно считывает значение переменной блокировки. Если переменная равна О, процесс изменяет ее на 1 и входит в критическую область. Если же переменная равна 1, то процесс ждет, пока ее значение сменится на 0. Таким образом, О означает, что ни одного процесса в критической области нет, а 1 свидетельствует, что какой-либо процесс уже находится в этом состоянии.

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

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

Строгое чередование

Третий метод реализации взаимного исключения иллюстрирован на рис. 2.6. Этот фрагмент программного кода, как и многие другие в данной книге, написан на С. Язык С был выбран, поскольку практически все существующие операционные системы написаны на С (или С++), а не на Java, Modula 3, Pascal и т. п. Язык С обладает всеми необходимыми свойствами для написания операционных систем: это мощный, эффективный и предсказуемый язык программирования. А язык Java, например, не является предсказуемым, поскольку у программы, написанной на нем, может в критический момент закончиться свободная память, и она вызовет сборщика мусора в исключительно неподходящее время. В случае С это невозможно, поскольку в С процедура сбора мусора в принципе отсутствует.

while(TRUE) {

while(turn!=0) /*wait*/;

critical region();

turn=l;

noncritical region();

while(TRUE) {

while(turn!=l) /*wait*/;

critical region();

turn=0;

noncriticalregion0;

Рис. 2.6. Предлагаемое решение проблемы критической области: а - процесс 0; б - процесс 1. В обоих случаях необходимо удостовериться в наличии точки с запятой, ограничивающей цикл while

На рис. 2.6 целая переменная turn, изначально равная О, фиксирует, чья очередь входить в критическую область. Вначале процесс О проверяет значение turn, считывает О и входит в критическую область. Процесс 1 также проверяет значение turn, считывает О и после этого крутится в цикле, непрерывно проверяя, когда же значение turn будет равно 1. Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. Подобного способа следует избегать, поскольку он является бесцельной тратой времени процессора. Активное ожидание используется только в случае, когда есть уверенность в незначительности времени ожидания.

Когда процесс О покидает критическую область, он изменяет значение turn на 1, позволяя процессу 1 завершить цикл. Предположим, что процесс 1 быстро покидает свою критическую область, так что оба процесса теперь находятся в обычном состоянии, и значение turn равно 0. Теперь процесс О выполняет весь цикл быстро, выходит из критической области и устанавливает значение turn равным 1. В итоге в этот момент значение turn равно 1, и оба процесса находятся вне критической области.

Неожиданно процесс О завершает работу вне критической области и возвращается к началу цикла. Но на большее он не способен, поскольку значение turn равно 1, и процесс 1 находится вне критической области. Процесс О зависнет в своем цикле while, ожидая, пока процесс 1 изменит значение turn на 0. Получа-