Глава_1 (1085730), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Представьте, что каталог спулера состоит из большого числа сегментов, прону­мерованных 0, 1,2,..., в каждом их которых может храниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент. Эти две переменные можно хранить в одном файле (состоящем из двух слов), доступном всем процессам. Пусть в данный момент сегменты с 0 по 3 пусты (эти файлы уже напечатаны), а сегменты с 4 по 6 заняты (эти файлы ждут своей очереди на печать). Более или менее одновременно процессы А и В решают поставить файл в очередь на печать. Описанная ситуация схематически изображена на рис. 2.14.

Директория

спулера

abc

prog.c

prog.n

Рис. 2.14. Два процесса хотят одновременно получить доступ к совместно используемой памяти

В соответствии с законом Мерфи (он звучит примерно так: «Если что-то плохое может случиться, оно непременно случится») возможна следующая ситуация.

Процесс А считывает значение (7) переменной in и сохраняет его в локальной пере­менной next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс В. Процесс B в свою очередь, считывает значение пере­менной in и сохраняет его (опять 7) в своей локальной переменной next_free_slot. В данный момент оба процесса считают, что следующий свободный сегмент- седьмой.

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

Наконец управление переходит к процессу А, и он продолжает с того места, на котором остановился. Он обращается к переменной next_free_slot, считыва­ет ее значение и записывает в седьмой сегмент имя файла (разумеется, удаляя при этом имя файла, записанное туда процессом В). Затем он заменяет значение in на 8 (next_free_slot + 1 = 8). Структура каталога спулера не нарушена, так что демон печати не заподозрит ничего плохого, но файл процесса В не будет напе­чатан. Пользователь, связанный с процессом В, может в этой ситуации полдня описывать круги вокруг принтера, ожидая требуемой распечатки. Ситуации, в ко­торых два (и более) процесса считывают или записывают данные одновременно и конечный результат зависит от того, какой из них был первым, называются состояниями состязания. Отладка программы, в которой возможно состояние состязания, вряд ли может доставить удовольствие. Результаты большинства тестовых прогонов будут хорошими, но изредка будет происходить нечто стран­ное и необъяснимое.

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

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

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

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

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

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

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

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

В абстрактном виде требуемое поведение процессов представлено на рис. 2.15. Процесс А попадает в критическую область в момент времени Т₁. Чуть позже, в мо­мент времени Т₂, процесс В пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс А, а два процесса не должны одновременно находиться в критических областях. Поэто­му процесс В временно приостанавливается, до наступления момента времени Т₃, когда процесс А выходит из критической области. В момент времени Т₄ процесс В также покидает критическую область, и мы возвращаемся в исходное состояние, когда ни одного процесса в критической области не было.

П роцесс А попадает в критическую область

Процесс А покидает критическую область

Процесс А

Процесс Б пытается Процесс Б

попасть в критическую попадает в

область критическую

область

П роцесс Б

Т₁ Т₂ Т₃ Т₄

Время Процесс Б покидает критическую

область

Рис. 2.15. Взаимное исключение с использованием критических областей

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

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

Запрещение прерываний

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

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

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

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

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

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

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

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

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

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

Язык С обладает всеми необходимыми свойствами для написания операционных систем: это мощный, эффективный и предсказуемый язык программирования. Язык Java, например, не является предсказуемым, поскольку у программы, написанной на нем, может в критический момент закончиться свободная память и она вызовет «сборщика мусора» в исключительно неподходящее время. В случае С это невоз­можно, поскольку в С процедура «сбора мусора» в принципе отсутствует. Срав­нительный анализ С, C++, Java и еще четырех языков представлен в [268].

Характеристики

Список файлов книги