Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

161

классу принтеров, так и по классу лент, но в комплексе она является

тупиковой. Алгоритм "проигрывания ситуации" требует значительного

объема вычислений, но обеспечивает комплексный анализ безопасности.

Отметим, что алгоритм банкира, хотя и является значительно более

либеральным, чем все рассмотренные выше, тоже не обеспечивает

оптимального уровня мультипрограммирования. Опасная ситуация еще не

является тупиковой. Так, ситуация, представленная на рисунке 5.3.б, еще

может разрядиться, если процесс P1 освободит хотя бы один из

удерживаемых им ресурсов. ОС же в оценке ситуации исходит из прогноза

о наихудшем развитии ситуации – предположения о том, что процессы

будут только запрашивать ресурсы, а не освобождать их.

Возможны и стратегии, обеспечивающие еще более либеральную

политику, но они требуют большей предварительной информации о

процессе и, как правило, – большего объема вычислений при реализации

стратегии. Например, нетрудно представить себе, что если ОС заранее

знает, в какой последовательности процесс будет

запрашивать/освобождать ресурсы, то она может обеспечить более

эффективное управление ими. Но часто ли такая последовательность

может быть известна заранее? Среди авторов [12, 26, 30 и др.] нет даже

единодушного мнения о том, реально ли требовать от процесса

предварительной заявки. На наш взгляд, однако, такое требование в

большинстве случаев реально выполнимо: для пакетных процессов

потребность в ресурсах бывает известна заранее, интерактивные же

процессы в многопользовательских системах запускаются только

зарегистрированными пользователями, указанный при регистрации

пользователя доступный ему объем ресурсов может считаться такой

заявкой.

Двигаясь дальше в сторону либерализации, мы пересекаем ту

границу, до которой можно было предотвратить тупики. Теперь тупики

162

возможны. И теперь ведущее значение приобретают методы обнаружения

тупиков.

Методы обнаружения тупиков

Определение нетупиковой ситуации очень похоже на определение

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

потенциальные запросы – заявки, а текущие – уже сделанные, но еще не

удовлетворенные запросы. Ситуация называется нетупиковой, если

процессы можно выстроить в такую последовательность, при которой:

• первый процесс может получить ресурсы по всем своим текущим

запросам;

• второй процесс может получить ресурсы по всем своим текущим

запросам при условии, что первый процесс закончился и

освободил все выделенные ему ресурсы;

• i-й процесс может получить ресурсы по всем своим текущим

запросам при условии, что i-1-й процесс закончился и освободил

все выделенные ему ресурсы.

В противном случае ситуация является тупиковой.

Если анализ опасной ситуации исходит из предположения о худшем

развитии событий, то анализ тупиковой – из предположения о лучшем их

развитии – что процессы больше не будут запрашивать ресурсы, а будут

только их освобождать.

Пусть в системе имеется 11 ресурсов одного класса, как

представлено на Рисунке 5.5. Процесс P1 уже имеет 2 ресурса и

запрашивает еще 2, процесс P2 уже имеет 3 и запрашивает еще 5, процесс

P3 имеет 4 и запрашивает еще 4. Системный резерв – 2 ресурса. В

зависимости от того, какие у процессов максимальные заявки (нам это

неизвестно), ситуация может быть расценена как опасная или безопасная,

163

но она определенно не является тупиковой. Процесс P1 может получить

требуемые ресурсы, если он после этого закончится, то может быть

удовлетворен запрос процесса P3, а после его завершения – запрос

процесса P2. Но если мы выделим еще хотя бы один ресурс процессу P3,

ситуация станет тупиковой.

a) нетупиковая

б) тупиковая

Рисунок 5.5 Анализ ситуации

При исследовании проблемы тупиков удобно представлять систему в

виде графа. Пример такого графа показан на рисунке 5.6.

Рисунок 5.6 Граф ресурсов и процессов

164

Графы такого рода содержат вершины двух типов: процессы

(показаны окружностями) и классы ресурсов (показаны

прямоугольниками), в последних указывается число ресурсов в классе.

Дуги графа могут соединять только разнотипные вершины.

Направленность дуг означает: от ресурса к процессу – ресурс выделен

данному процессу, от процесса к ресурсу – процесс запрашивает ресурс.

Признаком тупика является наличие в графе петли – такого пути, который

начинается и заканчивается в одной вершине, и из которого нет выхода.

Так, на рисунке 5.5 представлена тупиковая ситуация: следование по графу

любыми возможными путями заставит нас проходить одни и те же

вершины. Если же мы уберем дугу, ведущую от процесса P3 к ресурсу R2,

то появится выход из петли в вершину P3. Обнаружение тупика сводится к

попытке редукции (сокращения) графа. Из графа удаляются те вершины-

процессы, которые не имеют запросов или запросы которых могут быть

удовлетворены. При этом сокращаются также и все дуги, связанные с

этими вершинами. За счет освободившихся ресурсов появляется

возможность сократить новые вершины-процессы и т.д. Если в графе нет

петель, то после многократных сокращений нам удастся сократить все

вершины-процессы.

Как часто следует выполнять проверку тупика? Обратим внимание

на то, что если конструктор ОС отказывается от предупреждения тупиков,

то он делает это в значительной степени из нежелания загружать систему

значительным объемом вычислений по анализу безопасности при каждом

запросе. Обнаружение тупика выполняется сходным образом с анализом

безопасной ситуации и требует такого же объема вычислений,

следовательно, желательно выполнять его как можно реже. Единственным

событием, которое может перевести систему из нетупикового состояния в

тупиковое, является поступление запроса, который не может быть

удовлетворен. Следовательно, попытку обнаружения тупика надо

165

производить только по этому событию, никак не чаще. В некоторых

реализациях ОС применяет еще более ленивую политику.

Неудовлетворенный запрос может привести к тупику, но может и не

привести. "Ленивая" ОС не спешит выполнять проверку даже при

поступлении такого запроса, а выжидает некоторое время: может быть "все

само собой уладится" – и в большинстве случаев именно так и случается. И

только если запрос остается неудовлетворенным в течение определенного

времени, ОС принимается за поиск тупика. Размер временной выдержки

может определяться скоростными характеристиками запрашиваемого

ресурса.

Если тупик обнаружен, то как его ликвидировать? К сожалению,

развязка тупика практически всегда связана с потерями. Единственным

реальным способом развязки является принудительное прекращение

одного или нескольких процессов и освобождение удерживаемых ими

ресурсов. Как выбрать жертву для прекращения? Во-первых, ОС, конечно,

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

освободится объем ресурсов, достаточный для развязки тупика. Во-

вторых, оценивается объем потерь, связанных с прекращением того или

иного процесса. Прекращенный процесс, скорее всего, будет запущен

повторно, таким образом, ресурсы, использованные им при его

незаконченном выполнении, составляют прямые потери. Поэтому

естественным решением представляется прекращение того процесса,

который к этому моменту использовал меньше всего ресурсов (не только

монопольных, но любых ресурсов вообще). Поскольку самым

дорогостоящим ресурсом обычно является процессорное время, выбор

жертвы по критерию минимального использованного времени

производится наиболее часто.

Желательно, чтобы "пострадавший" процесс был снова запущен,

причем, возможно даже, с повышенным приоритетом. Но всякий ли

166

процесс можно прервать на середине, а потом запустить сначала?

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

на 10 банковских счетов. Эта программа принудительно завершается в тот

момент, когда она успела обработать только 5 счетов. Если при

перезапуске программа начнет выполняться с начала, она повторно

начислит взносы на первые 5 счетов. ОС не может знать, приведет ли

перезапуск процесса к нежелательным последствиям, поэтому решение о

повторном запуске обычно перекладывается на пользователя.

5.4. Бесконечное откладывание

Процессы, ожидающие ресурсов, встают в очереди к этим ресурсам.

Такая очередь может обслуживаться любой невытесняющей стратегией

планирования. Моментом, когда менеджер ресурса принимает решение об

обслуживании, является освобождение ресурса.

Единственной дисциплиной, которая гарантирует, что все процессы в

очереди будут в конце концов обслужены, является FCFS. Другие методы

базируются на приоритетах – внешних или вычисляемых на основании

размера запроса или/и безопасности ситуации. Очередь может быть

упорядочена по возрастанию размера запроса и при освобождении

ресурсов последние могут отдаваться по запросу "самого подходящего"

размера. Очередь может быть упорядочена в порядке возрастания

опасности выделения ресурсов, и освободившийся ресурс может

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

упорядочении очереди процесс, выдавший самый большой или самый

опасный запрос, может надолго в ней застрять, то есть попасть в ситуацию

бесконечного откладывания. С другой стороны, применение FCFS в

чистом виде может привести к снижению уровня

мультипрограммирования, к опасному состоянию и даже к тупику – если

167

процесс со слишком большим запросом окажется первым в очереди.

Отчасти это противоречие может быть сглажено, если мы допустим

частичное выделение ресурсов: запрос, стоящий в очереди первым

получает столько ресурсов, сколько ему можно выделить, сохраняя

ситуацию безопасной, остальные – отдаются следующему в очереди

процессу.

Поскольку тупиковая ситуация более опасна, чем бесконечное

откладывание, ОС все же отдает предпочтение критериям безопасности,

следовательно, заведомо предотвратить бесконечное откладывание

невозможно. Бесконечное откладывание процесса устанавливается по

времени его пребывания в очереди: если процесс пребывает в очереди

дольше некоторого установленного времени, то считается, что он ожидает

бесконечно. В зависимости от политики ОС в отношении справедливости

обслуживания и от характеристик процесса (если они известны)

допустимое время ожидания может устанавливаться большим или

меньшим. Если же бесконечное откладывание установлено, то для его

ликвидации ОС приостанавливает выдачу ресурсов новым процессам, пока

не будет обслужен отложенный процесс.

Проблема тупиков до некоторой степени теряет актуальность в

современных ОС, так как они имеют тенденцию к уменьшению количества

неразделяемых ресурсов. Одним из способов сделать неразделяемое

устройство разделяемым является буферизация, которую мы рассмотрим в

следующей главе. Системные структуры данных разделяются с

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

посвящена глава 8. Эта проблема, однако, становится все более актуальной

для современных СУБД, которые обеспечивают одновременный доступ к

ресурсам-данным для тысяч и десятков тысяч пользователей.

168

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Приведите примеры ресурсов: разделяемых и монопольно

используемых, непрерывных и дискретных, потребляемых и повторно

используемых.

2. Какую информацию о ресурсах должна хранить ОС?

3. Почему иерархическое выделение ресурсов является весьма

популярным во многих ОС?

4. В чем состоят ограничения на возможность применения

алгоритма банкира?

5. В чем сходство безопасной и беступиковой ситуаций? В чем их

различия?

6. В какие моменты ОС должна проводить действия по

обнаружению тупика?

7. Какие соображения могут влиять на выбор процесса-жертвы

при ликвидации тупика?

8. В чем достоинство дисциплины обслуживания FCFS для

очередей к монопольно используемым ресурсам?

Глава 6. Управление вводом-выводом

6.1. Виртуализация устройств и структура драйвера

Управление вводом-выводом в полной мере воплощает в себе

определение "ОС снаружи": ОС конструирует ресурсы высокого уровня –

виртуальные устройства – и предоставляет пользователю интерфейс для

работы с ними. Программисты, начинавшие работу в среде MS DOS,

привыкли к доступности средств прямого управления вводом-выводом для

любой программы, но в многозадачных ОС о такой доступности для

169

прикладной программы может идти речь только в исключительных

случаях, а в многопользовательских ОС она исключается вообще.

Можно в общем случае определить четыре метода, которые могут

использоваться ОС для конструирования виртуальных устройств

(виртуализации):

• метод закрепления или выделения (allocation);

• метод разделения (sharing);

• метод накопления или спулинга (spooling);

• метод моделирования (simulation).

Одна и та же ОС может использовать разные методы виртуализации

для разных устройств.

Метод закрепления однозначно отображает виртуальное устройство

на реальное устройство. Метод закрепления наименее эффективен, так как

закрепляемое устройство является монопольно используемым ресурсом, и

применение этого метода порождает все проблемы, связанные с

использованием таких ресурсов.

Метод разделения применим к устройством, ресурс которых является

делимым. В этом случае ресурс устройства разбивается на части, каждая из

которых закрепляется за одним процессом. Примером применения метода

могут служить минидиски в ОС VM/370 [28]: все пространство диска

разбивается на участки, каждый из которых выглядит для процесса как

отдельный том. Можно, например, разделять между процессами и экран

видеотерминала. Зафиксированная часть устройства является также

монопольным ресурсом и разделение лишь частично снимает остроту

проблем управления таким ресурсом. Возможность дробления устройства

предполагает внутреннюю адресацию в устройстве (адрес на диске, адрес в

видеопамяти). По аналогии с адресацией в памяти процесс и здесь

работает с виртуальными адресами в виртуальном устройстве, а ОС

транслирует их в реальные адреса в реальном устройстве.

170

Метод спулинга заставляет процесс обмениваться данными не с

реальным устройством, а с некоторой буферной областью в памяти

(оперативной или внешней). Обмен же данными между буфером и

реальным устройством организует сама ОС, причем, как правило, с

упреждением (при вводе) или с запаздыванием (при выводе). Буферизация

прозрачна для процессов и может создавать у них иллюзию

одновременного использования устройства, если каждому процессу

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

применяемый во всех современных ОС.

Метод моделирования не связан с реальными устройствами вообще.

Устройство моделируется ОС чисто программными методами.

Естественным применением этого метода является отработка приемов

работы с устройствами, отсутствующими в конфигурации данной

вычислительной системы. Часто ОС удобно представлять некоторые свои

ресурсы как метафоры (подобия) устройств – это также моделируемые

устройства. Так, в VM/ESA обмен данными между виртуальными

машинами ведется через виртуальный адаптер, метафорой устройства

можно также считать межпрограммный канал (pipe), реализованный во

многих современных ОС.

При любом методе виртуализации ОС является "прослойкой" между

процессами и реальными устройствами. Эту функцию выполняют

входящие в состав ОС драйверы устройств. К драйверам обращаются и

другие модули ОС, и процессы пользователя, причем последние, как

правило, не непосредственно, а через библиотеки вызовов,

предоставляющие более удобный API. В некоторых случаях ОС может

предоставить пользователю интерфейс, обладающий высокой степенью

подобия с интерфейсом реального устройства, но и в этом случае ОС, даже

применяя метод выделения, производит обработку управляющих

воздействий, сформированных процессом: проверку правильности команд,