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

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

141

• инициатор (для пакетных задач) или LOGON (для интерактивных

задач).

Эти задачи существуют параллельно и выполняют управление

ресурсами на разных уровнях.

При завершении родительского процесса не обязательно

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

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

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

находящийся в корне всего дерева наследования. Такие процессы обычно

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

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

название демоны (daemon).

4.4. Нити

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

быть создан легко и быстро. С одной стороны, это позволяет в

максимальной степени обеспечивать распараллеливание работ по решению

нескольких задач или внутри одной задачи. Но, с другой стороны, если ОС

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

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

значительных "накладных расходов". Преодоление этого противоречия

было найдено в концепции "нитей" (thread, часто переводится также как

"поток"), реализованной в большинстве современных ОС и

зафиксированной в стандартах POSIX и DCE. Нитью называется отдельная

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

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

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

142

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

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

общими, а какие – локальными для нити. В большинстве современных ОС

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

нить имеет собственный:

• вектор состояния,

• приоритет,

• стек (в стеке же размещаются и локальные переменные).

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

взаимодействия и т. д. – являются общими для нити и породившего ее

процесса.

Любой процесс состоит из одной или нескольких нитей. Первая нить

– основная – порождается системой при запуске процесса. Основная нить

может порождать дочерние нити вызовом типа:

tid = createThread(thr_addr, stack).

Параметрами вызова являются: thr_addr – адрес нити; stack –

адрес стека, выделяемого для нити (стек может также назначаться

системой по умолчанию). Вызов возвращает идентификатор нити.

В программе (на языке C, например) нить выглядит как обычная

функция. Приведенный выше вызов передает управление на эту функцию,

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

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

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

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

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

изменен. Отношения между основной и дочерней нитями похожи на

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

предыдущем разделе.

143

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

обычно в составе API ОС имеются системные вызовы, позволяющие

приостановить выполнение нити и вновь разрешить ее выполнение:

suspendThread(tid);

resumeThread(tid).

Отметим две особенности, связанные с возможностью порождения

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

пользователей и для ОС. Во-первых, трудность для пользователей –

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

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

ресурсов (см. главы 8 и 9). Во-вторых, трудность для ОС – усложняется

задача планировщика процессорного времени: теперь единицей

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

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

так и между нитями в каждом процессе.

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

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

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

разных ОС?

2. Какие стадии оптимизации может проходить программа?

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

написанных на языках C, Pascal, Cobol, Fortran и на языке Ассемблера?

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

обязательной?

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

со статическим?

144

4. Почему во многих современных ОС значительная часть

системы выполняется в виде библиотек динамической компоновки?

5. Являются ли "родственные отношения" между процессами

обязательными? Являются ли они полезными?

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

выполняется вызовом fork и вызовом load.

7. Для чего могут быть полезны списки выхода? Приведите

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

состоящий из более чем одной процедуры.

8. Дайте определение нити. Какие ресурсы являются

собственными для нити?

9. Приведите примеры задач, решение которых требует

применения нитей?

10. В некоторых клонах ОС Unix нет специального механизма

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

пространство родителя. Чем вы объясните такое решение?

145

Глава 5. Монопольно используемые ресурсы

5.1. Свойства ресурсов и их представление

Процессорное время и оперативная память являются ключевыми

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

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

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

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

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

выводит платежную ведомость на принтер. Если мы в середине печати

отберем у процесса ресурс-принтер и отдадим его другому процессу, то

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

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

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

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

На том же примере печати поясним понятие неразделяемости: два

процесса не могут выводить данные на один и тот же принтер

одновременно. Ресурсы процессорного времени и памяти, как мы увидели

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

обладают.

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

вывода: принтеры, магнитные ленты, каналы связи и т.п., файлы (они

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

146

также вторичные ресурсы, порождаемые самой ОС, – системные

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

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

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

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

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

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

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

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

поступающие в процесс извне.

Наши ресурсы обладают также свойствами дискретности и

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

некоторыми неделимыми единицами (не может быть полтора принтера).

Второе – то, что число единиц ресурса всегда небесконечно.

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

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

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

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

принятой модели).

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

неименованных единиц ресурса. Неименованными мы считаем их в том

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

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

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

Из определений ОС (как с точки зрения разработчика, так и с точки

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

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

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

147

такой возможности в составе API ОС должны быть системные вызовы

типа:

resourceHandle = getResource

(class, number [,action] );

releaseResource(resourceHandle).

Первый вызов выделяет процессу number ресурсов из класса class

и возвращает манипулятор (handle) выделенного ресурса, который при

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

идентификации ресурса. Манипулятор каким-то образом адресует

дескриптор ресурса. В защищенных системах такой дескриптор

располагается в недоступном для процесса адресном пространстве.

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

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

дескриптор ресурса.

Второй вызов открепляет от процесса ранее выделенный ему ресурс.

Возможно, форма выделения/освобождения ресурса напомнила вам

знакомые операции открытия/закрытия файла – и недаром. Поскольку

файлы также являются ресурсами, операции open/close – частные

случаи операций getResource/releaseResource. Как правило, в

реальных API ОС нет общих операций выделения/освобождения ресурсов,

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

других названием и, возможно, составом параметров.

Третий, необязательный параметр операции getResource задает

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

предоставляют процессам возможности такого выбора). Во-первых (и это

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

процесс, выдавший запрос, до освобождения требуемого ресурса. Во-

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

после некоторой временной выдержки (timeout), в этом случае "умный"

148

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

выполнить и без этого ресурса, а позже повторить запрос. Как ОС должна

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

(требуемого объема ресурсов просто нет в системе)? По нашему

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

выдавшего его процесса. Но если ОС допускает динамическую

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

ожидании момента, когда ресурс будет введен в систему. Такие

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

ОС, так как ресурс может никогда и не быть введен. Для избежания таких

запросов целесообразно иметь в составе API вызов, возвращающий общее

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

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

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

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

Для каждого класса ресурсов ОС должна поддерживать дескриптор

класса, в который должны входить:

• идентификатор класса;

• общее число единиц в классе;

• число свободных единиц;

• таблица единиц ресурса;

• список процессов, ожидающих ресурс этого класса;

• точка входа в менеджер класса;

• и т.д.

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

содержащая, как минимум, индикатор занятости ресурса и идентификатор

процесса, которому ресурс распределен (если он не свободен).

149

Манипулятор ресурса каким-то образом адресует дескриптор

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

адресном пространстве, недоступном для процесса. Манипулятор

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

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

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

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

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

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

которого он получил в качестве параметра.

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

блоке контекста процесса.

5.2. Обедающие философы

Уже классической стала неформальная постановка задачи

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

философов" и показанная на рисунке 5.1.

150

Рисунок 5.1 Обедающие философы. Тупик

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

блюдо с рисом. Между каждой парой философов лежит палочка для еды,

палочек, следовательно, тоже пять. Для того, чтобы начать есть, философ

должен взять две палочки – слева и справа от себя. Таким образом, если

один из философов ест, его соседи справа и слева лишены такой

возможности, так как им недостает палочек. Каждый философ "работает"

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

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

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

синхронизированы. Ничего не говорится в условии о том, каким образом

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

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

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

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

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