Обработка конкуренции между процессами

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

Семафор

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

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

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

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

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

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

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

Взаимная блокировка

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

Взаимная блокировка возникает, когда выполняются все три приведенные ниже условия.

1. Существует конкуренция за ресурс, который не может использоваться совместно.

2. Ресурсы запрашиваются по частя!«, то есть, получив некоторые ресурсы, процесс позже возвращается, чтобы получить больше.

3. Если ресурс распределен, то его уже нельзя принудительно извлечь.

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

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

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

Сети

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