Гордеев А.В. Операционные системы

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

272 Глава 8, Проблема тупиков и методы борьбы с ними

процесса Р| и на любой стадии необходимо сначала попытаться сократить граф с

помощью процесса Р

(

. Если процесс Р

;

смог провести сокращение графа, то ника-

кие дальнейшие сокращения не являются необходимыми.

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

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

условиям для тупика.

Пучок, или узел, в ориентированном графе G = <Х, Е> — это подмножество вер-

шин Z I X, таких что V х I Z, Р(х) = Z, то есть потомством каждой вершины из Z

является само множество Z. Каждая вершина в узле достижима из каждой другой

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

Поясним сказанное рис. 8.10.

Рис. 8.10. Пример узла в модели Холта

Следует заметить, что наличие цикла — это необходимое, но не достаточное

условие для узла. Так, на рис. 8.11 изображены два подграфа. Подграф а пред-

ставляет собой пучок (узел), тогда как подграф б представляет собой цикл, но

узлом не является. В узел должны входить дуги, но они не должны из него вы-

ходить.

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

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

вания тупика. Эта ситуация возникает, если распределители ресурсов не от-

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

возможности немедленно (большинство распределителей следуют именно этой

дисциплине).

Состояние называется фиксированньш, если каждый процесс, выдавший запрос,

заблокирован.

Третья теорема: если состояние системы фиксированное (все процессы, имею-

щие запросы, удовлетворены), то наличие узла в соответствующем графе повтор

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

Методы борьбы с тупиками

ZYIS

y3enZ = {Z

}

Цикл Z = {Z

, Z

}, но не узел

Рис. 8.11. Узел и цикл в ориентированном графе

274

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

Для доказательства предположим, что граф содержит узел Z. Тогда все процессы в

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

так как никакие ребра не могут выходить из Z по определению. Аналогично, по той

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

Наконец, все процессы в Z должны быть заблокированы согласно условию фикси-

рованное™ и определению узла. Следовательно, все процессы в узле Z должны

быть в тупике.

Допустим, что каждый ресурс имеет единичную емкость (по одной единице ресур-

са), то есть IRJ = 1, (i = l, 2, ..., m). При этом ограничении наличие цикла также

становится достаточным условием тупика.

Четвертая теорема: граф повторно используемых ресурсов с единичной емкос-

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

Необходимость цикла доказывает первая теорема. Для доказательства достаточ-

ности допустим, что граф содержит цикл, и рассмотрим только лишь процессы и

ресурсы, принадлежащие циклу. Так как каждая вершина-процесс должна иметь

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

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

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

захвачен некоторым процессом. Следовательно, каждый процесс в цикле блоки-

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

из этого цикла; поэтому процессы в цикле находятся в тупике.

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

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

Алгоритм обнаружения тупика по наличию

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

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

ния ресурсов. Один из алгоритмов, основанный на методе обнаружения замкну-

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

ной из ОС этой компании. Он использует информацию о состоянии системы,

содержащуюся в двух таблицах: таблице текущего распределения (назначения)

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

ресурса может быть свой список заблокированных процессов). При каждом за-

просе на получение или освобождение ресурсов содержимое этих таблиц модифи-

цируется, а запрос анализируется в соответствии со следующим алгоритмом [22].

1. Начало алгоритма. Приходит запрос от процесса с номером J на занятый ресурс

с номером I.

2. Поместить номер ресурса I в таблицу PWTBL в строке с номером процесса J.

3. Использовать I в качестве смещения в таблице RATBL, чтобы найти номер про-

цесса К, который владеет ресурсом.

4. Использовать К в качестве смещения в таблице PWTBL.

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

номером Г. Если нет, то перейти к шагу 6, в противном случае — к шагу 7.

6 Перевести процесс с номером J в состояние ожидания и выйти из алгоритма.

7 Использовать Г в качестве смещения в таблице RATBL, чтобы найти помер К'

блокирующего его процесса.

8 Проверить, что К' = J. Если нет, перейти к шагу 9, в противном случае — к ша-

' гу П.

9. Проверить, вся ли таблица PWTBL просмотрена. Если да, то перейти к шагу

6, в противном случае — к шагу 10.

10. Присвоить К := К' и перейти к шагу 4.

П. Сделать вывод о наличии тупика с последующим восстановлением.

12. Конец алгоритма.

Для иллюстрации описанного алгоритма распознавания тупика рассмотрим сле-

дующую последовательность событий.

1. Процесс Р1 занимает ресурс R1.

2. Процесс Р2 занимает ресурс R3.

3. Процесс РЗ занимает ресурс R2.

4. Процесс Р2 занимает ресурс R4.

5. Процесс Р1 занимает ресурс R5.

В результате таблица распределения ресурсов (RATBL) принимает такой вид,

как показано в табл. 8.3.

Таблица 8.3. Таблица распределения ресурсов

Ресурсы Процессы

R1 Р1

R2 РЗ

R3 Р2

R4 Р2

R5 PJ

6. Пусть процесс Р1 пытается занять ресурс R3, поэтому в соответствии с описан-

ным алгоритмом J = 1,1 = 3, К = 2. Процесс К не ждет никакого ресурса, поэто-

му процесс Р1 блокируется по ресурсу R3.

7. Далее, пусть процесс Р2 пытается занять ресурс R2: J = 3,1 = 2, К = 3. Процесс

с номером К=3 не ждет никакого ресурса, поэтому процесс Р2 блокируется по

ресурсу R2.

о- И наконец, пусть процесс РЗ пытается обратиться к ресурсу R5: J = 3, I = 5,

К = 1, Г = 3, К' - 2, К' <> J, поэтомуберем К = 2, Г = 2, К" = 3.

& этом случае К' = J, то есть тупик определен. Таблица заблокированных процес-

сов (PWTBL) теперь будет выглядеть так, как показано в табл. 8.4.

Равенство J = К' означает, что существует замкнутая цепь взаимоисключающих

и 05к

идающих процессов, то есть выполняются все четыре условия существования

Упика.

276

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

Таблица 8.4. Таблица заблокированных ресурсов

Процесс Ресурс

Р1 R3 )

Р2 R2

РЗ R5

Для описанного нами примера можно построить модель Холта, как показано на

рис. 8.12. Здесь пронумерованы дуги запросов, которые процессы последователь-

но генерировали в соответствии с нашим примером. Из рисунка сразу видно, что

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

ка: (8, 5, 6, 2, 7, 3), что и говорит о существовании тупика.

Рис. 8.12. Граф распределения ресурсов

Распознавание тупика требует дальнейшего восстановления вычислений.

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

в опасном состоянии. Существуют следующие методы восстановления:

а принудительный перезапуск системы, характеризующийся потерей информа-

ции обо всех процессах, существовавших до перезапуска;

• принудительное завершение процессов, находящихся в тупике;

Q принудительное последовательное завершение процессов, находящихся в ту-

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

шения до исчезновения тупика;

• перезапуск процессов, находящихся в тупике, с некоторой контрольной точки,

то есть из состояния, предшествовавшего запросу на ресурс;

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

процессов, находящихся в тупике.

Контрольные вопросы и задачи 277

Основные издержки восстановления составляют потери времени на повторные

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

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

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

ния будут безвозвратно потеряны.

Контрольные вопросы и задачи

1. Что такое тупиковое состояние? Приведите несколько примеров возникнове-

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

2. Что является причиной возникновения тупиков на ресурсах типа SR? Пере-

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

3. Приведите пример графа повторно используемых ресурсов. Что позволяет сде-

лать эта модель Холта?

4. Приведите пример теоретико-множественного описания сети Петри.

5. Что такое маркировка сети Петри? Что представляет собой пространство воз-

можных состояний сети Петри?

6. Приведите пример графического представления сети Петри.

7. Что следует предпринять для реализации стратегии предотвращения тупико-

вых ситуаций? Какие реальные проблемы при этом возникают?

8. Что представляет собой «обход тупика»? Приведите алгоритм банкира Дейк-

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

для борьбы с тупиковыми ситуациями?

9. Что такое «опасное состояние»? Приведите пример опасного состояния на мо-

дели состояний системы.

10. Опишите метод обнаружения тупика посредством редукции графа повторно

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

И. Опишите алгоритм обнаружения тупика по наличию замкнутой цепочки за-

просов.

Глава 9. Архитектура

операционных систем

Как комплекс системных управляющих и обрабатывающих программ (см. главу 1),

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

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

вать надежное и эффективное выполнение вычислений. Большинство потенци-

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

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

рой и основными принципами построения.

В-главе 1 мы упомянули несколько наиболее распространенных классификаций.

Очевидно, что системы, ориентированные на диалог, должны иметь иные страте-

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

ботки. Диалоговое взаимодействие предполагает реализацию развитой интерфей-

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

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

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

мов, которые позволят пользователям эффективно управлять своими вычислени-

ями.

Аналогично, и системы, реализующие мультизадачный режим работы, отличают-

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

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

информационной безопасности. А это, в свою очередь, налагает определенные тр

бования и на идеологию построения операционной системы, и на выбор конкр

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

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

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

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

пер

ционной системой, мы в этой главе рассмотрим и интерфейсы прикладного г

граммирования.

о-

Основные принципы построения операционных систем

279

Основные принципы построения

операционных систем

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

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

мобильности (переносимости) и совместимости, принцип открытости, принцип ге-

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

Принцип модульности

Операционная система строится из множества программных модулей. Под моду-

лем в общем случае понимают функционально законченный элемент системы,

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

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

наличии заданных интерфейсов. Способы обособления составных частей опера-

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

всего разделение происходит именно по функциональному признаку. В значитель-

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

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

Особо важное значение при построении операционных систем имеют привилеги-

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

лее эффективно использовать ресурсы вычислительной системы. Как мы уже зна-

ем (см. главу 1), свойство реентерабельности может быть достигнуто различными

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

мяти под переменные для нового вычислительного процесса (задачи). В некото-

рых системах реентерабельность программы получают автоматически. Этого можно

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

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

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

памяти, которая распределяется по запросам от выполняющихся задач. Естествен-

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

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

стемных модулей.

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

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

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

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

системах.

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

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

°и памяти для более скорой реакции системы на возникающие события и более

Ффективной организации вычислительных процессов. Эти модули вместе с не-

торьгми системными структурами данных, необходимыми для функционирова-

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

Та

к как это действительно ее самая главная, центральная часть, основа системы.

280 Глава 9, Архитектура операционных СИСТЙИ.

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

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

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

маемый ядром, был не слишком большим. В его состав, как правило, входят мо-

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

состояния счета в состояние ожидания, готовности и обратно, средства по распре-

делению основных ресурсов, таких как оперативная память и процессор. В главе 1

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

роядерными (монолитными). В микроядерных операционных системах само ядро

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

сервисные модули могут размещаться и в оперативной памяти. В противополож-

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

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

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

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

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

модулей, которые получают название транзитных. Транзитные программные мо-

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

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

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

мин «диск-резидентный».

Принцип особого режима работы

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

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

ты процессора. Это необходимо по нескольким причинам. Во-первых, введение

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

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

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

операционной системы, так и прикладных задач пользователей. Категорически

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

(преднамеренно или в связи с появлением ошибок вычислений) в вычисления,

связанные с супервизорной частью операционной системы. Во-вторых, ряд функ-

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

рационной системы. К этим функциям мы, прежде всего, должны отнести функции,

связанные с управлением процессами ввода-вывода данных. Вспомните основные

принципы организации ввода-вывода (см. главу 5): все операции ввода-вывода дан

ных объявляются привилегированными. Это легче всего сделать, если процессор

может работать, как минимум, в двух режимах: привилегированном (режим су

первизора) и пользовательском. В первом режиме процессор может выполнять вс£

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

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

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

циальным системным регистрам — эти регистры должны быть доступны тольк

псновные принципы построения операционных систем 281

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

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

к запрещенному регистру должна вызывать прерывание (исключение), и централь-

нЫ

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

системы для управления выполняющимися вычислениями.

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

мы для выполнения этих (и некоторых других) операций обращаются к суперви-

зорной части операционной системы (модуль супервизора иногда называют су-

первизором задач) с соответствующим запросом. При этом процессор должен

переключиться в привилегированный режим работы. Чтобы программы не могли

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

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

в строгом соответствии с принятыми правилами. Каждый запрос имеет свой иден-

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

уточняющих запрашиваемую у операционной системы функцию (операцию). По-

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

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

выполнение операции, как правило, передается соответствующему модулю опера-

ционной системы. Множество запросов к операционной системе образует соот-

ветствующий системный интерфейс прикладного программирования (Application

Program Interface, API).

Принцип виртуализации

В наше время уже не требуется пояснять значение слова «виртуальный», ибо о

виртуальных мирах, о виртуальной реальности знают даже дети. Принцип виртуа-

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

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

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

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

свойства и работать с некоторой абстракцией, вобравшей в себя наиболее значи-

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

определенного набора планировщиков процессов и распределителей ресурсов (мо-

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

сов.

Следует заметить, что сама операционная система существенно изменяет наши

представления о компьютере. Она виртуализирует его, добавляя ему функциональ-

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

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

Компьютер совершенно иначе, чем без нее.

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

вляется понятие виртуальной машины. По сути, любая операционная система,

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

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

1е

аппаратные и иные ресурсы, заменяя их некоторой абстракцией. В результате