Координирование действий машины

Одним из главных принципов, лежащих в основе современных операционных систем, является разделение понятий программы и деятельности по ее исполне­нию. Программа — это просто статический набор указаний, а выполнение про­граммы — динамическая деятельность, свойства которой меняются во времени. Эта деятельность называется процессом (process). Текущее состояние деятельно­сти называется состоянием процесса (process state). Это состояние включает уча­сток программы, который в данный момент выполняется (значение в счетчике команд), а также значения других регистров центрального процессора и соответ­ствующих ячеек памяти. Грубо говоря, состояние процесса — это моментальный снимок ресурсов машины в данное время. В разные моменты выполнения про­граммы имеют место разные состояния процесса.

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

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

Управление процессами

Задачи, связанные с координацией процессов, выполняются планировщиком и диспетчером, которые входят в ядро операционной системы. Планировщик ведет учет процессов, которые протекают в данный момент, записывает новые и удаля­ет уже законченные. Для того чтобы следить за всеми процессами, планировщик помещает информацию о них в область оперативной памяти, которая называется таблицей процессов (process table). Каждый раз, когда машине назначается зада­ча, планировщик создает для нее процесс, помещая новые данные в таблицу. Эти данные содержат информацию об области памяти, приписанной процессу (эта информация получена от программы распределения памяти), о приоритете процесса и о том, находится ли он в состоянии готовности или ожидания. Процесс находится в состоянии готовности (ready), если его выполнение можно продол­жить, а в состоянии ожидания (waiting) — когда выполнение приостановлено до появления какого-либо внешнего события, такого как получение доступа к диску или получение сообщения от другого процесса.

Диспетчер — компонент ядра операционной системы, который управляет вы­полнением запланированных процессов. В системах с разделением времени эта задача осуществляет разделение времени на короткие интервалы, которые назы­ваются квантами (не более 50 миллисекунд), и переключение центрального про­цессора с одного процесса на другой, поскольку длительность непрерывного вы­полнения одного процесса не может превышать одного кванта (рис. 3.6). Процедура смены процессов называется переключением процессов (process switch).

Каждый раз, когда начинается квант времени процесса, диспетчер запускает таймер, который измеряет, сколько времени прошло от начала кванта. Когда вре­мя, отведенное данному процессу, заканчивается, таймер генерирует сигнал, который называется сигналом прерывания (interrupt). Центральный процессор реа­гирует на этот сигнал почти так же, как реагируете вы, когда вас отрывают от какого-либо дела. Вы останавливаетесь, записываете, на каком этапе выполнения задачи вы находитесь. Когда центральный процессор получает сигнал прерыва­ния, он завершает выполнение текущего машинного цикла, сохраняет позицию в текущем процессе и начинает выполнение программы, которая называется об­работчиком прерывания (interrupt handler) и хранится в определенной области оперативной памяти.

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

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

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

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

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

Семафор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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