Семафор

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

Для того чтобы управлять доступом к принтеру, операционная система долж­на отслеживать, свободен ли принтер. Это можно сделать в помощью флага, ко­торый в данном случае представляет собой бит в памяти, о котором говорят, что он либо установлен, либо сброшен, а не имеет значение 0 или 1. Сброшенный флаг обозначает, что принтер доступен, а установленный флаг — что принтер занят. На первый взгляд может показаться, что при таком подходе не возникает никаких непредвиденных сложностей. Операционная система просто проверяет флаг каждый раз, когда требуется доступ к принтеру. Если он пуст, то требование процесса удовлетворяется и операционная система устанавливает флаг. Если же флаг уже установлен, операционная система просит процесс подождать. Каждый раз, когда процесс заканчивает работу с принтером, операционная система или отдает принтер ждущему процессу, или, если ждущих процессов нет, оставляет флаг пустым.

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

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

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

Другая возможность разрешения этой проблемы — использовать команду «проверить-и-установить» (test-and-set), которая доступна во многих машинных язы­ках. Эта команда предписывает центральному процессору извлечь значение фла­га, проанализировать его, а затем установить флаг, все в пределах одной команды. Преимущество такой команды состоит в том, что центральный процессор всегда завершает проверку и установку флага, поскольку эти действия выполняются за одну команду.

Описанный выше метод используется для установки флагов, называемых се­мафорами (semaphore), по аналогии с железнодорожным сигналом, который ис­пользуется для управления доступом к частям дороги. Использование семафо­ров в системах программного обеспечения очень похоже на их использование в железнодорожных системах. Части дороги, которая может вмещать только один поезд, соответствует набор команд, который в данный момент времени может выполняться только одним процессом. Такая последовательность команд назы­вается критической областью (critical region). Требование того, чтобы в данный момент времени только один процесс мог выполнять команды из критической области, называется взаимным исключением доступа (mutual exclusion). Обычно для обеспечения взаимного исключения доступа к критической области исполь­зуется семафор. Для того чтобы процесс мог войти в критическую область, сема­фор должен быть пустым. Перед тем как войти, процесс устанавливает семафор, а при выходе из критической области он очищает семафор. Если семафор уста­новлен, процесс, пытающийся войти в критическую область, должен подождать, пока он станет пустым.