Операционные системы. Часть 1. Основы управления ресурсами: Учебное пособие

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра "Персональные ЭВМ"

А. В. Рощин

ОПЕРАЦИОННЫЕ СИСТЕМЫ Часть 1

ОСНОВЫ УПРАВЛЕНИЯ РЕСУРСАМИ

Москва 2007

2

УДК 681.3 Операционные системы. Часть 1. Основы управления ресурсами. Учебное пособие/ А.В.Рощин. – М.: МГУПИ, 2007. – 119 с.: ил.

Рекомендовано Ученым Советом МГУПИ в качестве учебного пособия для специальности 2201. Рецензенты:

Предлагаемая

профессор Зеленко Г.В. доцент Туманов М.П. работа

может

рассматриваться

как

пособие-

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

© А.В.Рощин. 2007.

3

1 1.1 1.2 1.3 1.4

ВВЕДЕНИЕ

4

ОСНОВНЫЕ ФУНКЦИИ ОПЕРАЦИОННЫХ СИСТЕМ Классификация операционных систем Структура операционной системы ОС как система управления ресурсами Контрольные вопросы

8 8 17 36 52

2 МУЛЬТИПРОГРАММИРОВАНИЕ 2.1 Системы пакетной обработки 2.2 Мультипрограммирование в системах разделения времени 2.3 Мультипрограммирование в системах реального времени 2.4 Мультипроцессорная обработка 2.5 Контрольные вопросы 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10

56 58 63 65 68 70

ПРОЦЕССЫ И ПОТОКИ Планирование процессов и потоков Создание процессов и потоков Планирование и диспетчеризация потоков Состояния потока Вытесняющие и невытесняющие алгоритмы планирования Алгоритмы планирования, основанные на квантовании Алгоритмы планирования, основанные на приоритетах Смешанные алгоритмы планирования Планирование в системах реального времени Контрольные вопросы

72 72 79 84 88 91 96 100 105 109 114

ЗАКЛЮЧЕНИЕ

117

4

Введение Стало уже избитым местом предлагать определение понятию «Операционная система». К сожалению, до сих пор не существует общепринятого и краткого определения операционной системы (ОС). Далее мы попытаемся дать определение ОС через список функций, которые на нее обычно возлагаются, но необходимо помнить, что многие из программных продуктов, предлагаемых на рынке в качестве ОС, не выполняют (а иногда выполняют, но так, что лучше бы и не брались совсем) некоторые из этих функций [1]. Бэррон (Barron) определяет операционную систему так: "Я не знаю, что это такое, но всегда узнаю ее, если увижу". Эта фраза была сказана в первой половине 70-х годов прошлого века, когда операционные системы действительно

отличались

большим

разнообразием

структуры

и

выполняемых функций. С тех времен положение мало изменилось. С одной стороны, системы "общего назначения" — Unix, Windows ХР, z/OS похожи друг на друга настолько, что доходит до анекдотов: например, в 1998 году OS/390 прошла тесты консорциума X-Open и отныне может на законных основаниях называться UNIX (ТМ). С

другой

стороны,

оставив

в

стороне

"универсальные

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

5

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

носящий

(и

не без

оснований!)

гордое

наименование

Операционной Системы Реального Времени [www.microchip.com]. Те, кто постарше, могут вспомнить и еще один программный продукт, на "обычные" ОС внешне и функционально мало похожий, но сообщающий при

загрузке:

"Loading

Doom

Operating

System"

(Загружается

Операционная Система Doom). Споры о том, является ли операционной системой Windows 95/98/МЕ не утихают с 1993 года, времени появления первых бета-версий того, что тогда еще называлось Chicago (возможно, масла в огонь этих споров добавил тот факт, что прямой предок Chicago, Windows 3.x, никогда не назывался ОС ни в документации, ни в рекламных текстах), так что, как видим, не все могут узнать ОС, даже увидев ее. Дополнительную путаницу вносит то обстоятельство, что в наше время все менее и менее понятным становится ответ на вопрос, что же такое компьютер. Определение, согласно которому компьютер состоит из системного блока, монитора, клавиатуры и манипулятора "мышь", естественно, никуда не годится — под него не подходят даже портативные компьютеры или монтируемые в стойку серверы с IBM PC-совместимой архитектурой. Если же попытаться определить компьютер как устройство, имеющее где-то внутри полностью программируемый процессор фоннеймановской архитектуры, в число "компьютеров" попадет неожиданно много устройств. Многие из этих компьютеров работают под управлением того или иного продукта, позиционируемого на рынке как операционные системы: QNX, VxWorks и др. Существуют программы, разработанные полностью самостоятельно, без использования чужого кода, но некоторые их модули

6

также называются ОС. Бывает и так, что отдельные подсистемы программного комплекса, не называясь ОС, все-таки являются ею. Возникают и совсем анекдотические ситуации, когда разработчик пишет свою собственную ОС, не подозревая об этом. Это случается не только при разработке встраиваемых приложений, но и при написании программ (особенно многопоточных и требовательных к ресурсам) для компьютеров и ОС общего назначения. Основные функции операционных систем По современным представлениям операционная система должна уметь делать следующее [1]: − обеспечивать загрузку прикладных программ в память и их исполнение, − обеспечивать управление памятью; в простейшем случае это указание единственной загруженной программе адреса, на котором кончается память, доступная для использования, и начинается

память,

занятая

системой,

в

многопроцессных

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

здесь

сказано

не

случайно

—

часть

систем

ограничивается командной строкой, в то время как другие на 90% состоят из интерфейсной подсистемы).

7

Существуют ОС, функции которых этим и исчерпываются. Одна из хорошо известных систем такого типа — дисковая операционная система MS DOS. Более развитые ОС предоставляют также следующие возможности: − параллельное (или псевдопараллельное, если машина имеет только один процессор) исполнение нескольких задач, − организацию взаимодействия задач друг с другом, − организацию

межмашинного

взаимодействия

и

разделения

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

8

1

ОСНОВНЫЕ ФУНКЦИИ ОПЕРАЦИОННОЙ СИСТЕМЫ

1.1

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

Классификация ОС По тому, какие из вышеперечисленных функций реализованы и каким было уделено больше внимания, а каким меньше, системы можно разделить на несколько классов (рисунок 1.1).

Рисунок 1.1 – Классификация операционных систем ДОС (Дисковые Операционные Системы) Это системы, берущие на себя выполнение только первых четырех функций. Как правило, они представляют собой некий резидентный набор подпрограмм, не более того. ДОС загружает пользовательскую программу в память и передает ей управление, после чего программа делает с системой все, что ей заблагорассудится. При завершении программы считается хорошим тоном оставлять машину в таком состоянии, чтобы ДОС могла продолжить работу. Если же программа приводит машину в какое-то другое состояние, что ж, ДОС ничем ей в этом не может помешать.

9

Характерный пример — различные загрузочные мониторы для машин

класса

Spectrum.

Как

правило,

такие

системы

работают

одновременно только с одной программой. Дисковая операционная система MS DOS для IBM PC-совместимых машин является прямым наследником одного из таких резидентных мониторов. Существование систем этого класса обусловлено их простотой и тем, что они потребляют мало ресурсов. Для машин класса Spectrum это более чем критичные параметры. Еще одна причина, по которой такие системы могут использоваться даже на довольно мощных машинах — требование программной совместимости с ранними моделями того же семейства компьютеров. ОС общего назначения К этому классу относятся системы, берущие на себя выполнение всех вышеперечисленных функций. Разделение на ОС и ДОС идет, повидимому, от систем IBM DOS/360 и OS/360 для больших компьютеров этой фирмы, клоны которых известны у нас в стране под названием ЕС ЭВМ серии 10ХХ. Здесь

под

ОС

мы

будем

подразумевать

системы

"общего

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

10

широко распространенные системы, как Windows 2000, системы семейства Unix. Системы виртуальных машин Такие системы стоят несколько особняком. Система виртуальных машин — это ОС, допускающая одновременную работу нескольких программ, но создающая при этом для каждой программы иллюзию того, что машина находится в полном ее распоряжении, как при работе под управлением ДОС. Зачастую, "программой" оказывается полноценная операционная система – примерами таких систем являются VMWare для машин с архитектурой х86 или VM для System/370 и ее потомков. Виртуальные машины являются ценным средством при разработке и тестировании кросс-платформенных приложений. Реже они используются для отладки модулей ядра или самой операционной системы. Такие системы отличаются высокими накладными расходами и сравнительно низкой надежностью, поэтому относительно редко находят промышленное применение. Часто СВМ являются подсистемой ОС общего назначения: MS DOS и MS Windows-эмуляторы для UNIX и OS/2, подсистема WoW в Windows NT/2000/XP, сессия DOS в Windows З.х/95/98/МЕ, эмулятор RT-11 в VAX/VMS. В системах виртуальных машин, как правило, приходится уделять много внимания эмуляции работы аппаратуры. Например, несколько программ могут начать программировать системный таймер. СВМ должна отследить такие попытки и создать для каждой из программ иллюзию, что она запрограммировала таймер именно так, как хотела. Разработка таких систем является сложным и часто неблагодарным делом. Архитектура таких систем сильно зависит от свойств виртуализуемой аппаратуры, поэтому мы почти не будем обсуждать этот класс ОС.

11

Системы реального времени Это

системы,

приложений

предназначенные

реального

времени

для —

облегчения

программ,

разработки

управляющих

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

такого

приложения

может

быть

программа

бортового

компьютера fly-by-wire (дословно — "летящий по проволоке", т. е. использующий систему управления, в которой органы управления не имеют механической и гидравлической связи с рулевыми плоскостями) самолета,

системы

промышленным

управления

оборудованием.

атомной Подобные

электростанцией системы

или

должны

поддерживать многопоточность, гарантированное время реакции на внешнее событие, простой доступ к таймеру и внешним устройствам. Способность гарантировать время реакции является отличительным признаком систем реального времени. Важно учитывать различие между гарантированностью и просто высокой производительностью и низкими накладными расходами. Далеко не все алгоритмы и технические решения, даже и обеспечивающие отличное среднее время реакции, годятся для приложений и операционных систем РВ. По другим признакам эти системы могут относиться как к классу ДОС (RT-11), так и к ОС (OS-9, QNX). Качественная реализация современных мультимедиа приложений предъявляет к системе те же требования, что и промышленные задачи реального времени. В мультимедиа основной проблемой является синхронизация изображения на экране со звуком. Именно в таком порядке. Звук

обычно

генерируется

внешним

аппаратным

устройством

с

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

12

же звука и изображения фиксируется человеком уже при задержках около 30 мс. Поэтому системы высококачественного мультимедиа должны обеспечивать синхронизацию с такой же или более высокой точностью, что мало отличается от реального времени. Так

называемое

предоставляемое

"мягкое

современными

реальное Win32

время"

(soft

платформами,

real не

time),

является

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

системы,

предназначенные

для

разработки

программ

в

двухмашинной конфигурации, когда редактирование, компиляция, а зачастую и отладка кода производятся на инструментальной машине (в англоязычной литературе ее часто называют host — дословно, "хозяин"), а потом скомпилированный код загружается в целевую систему. Чаще всего они

используются

прошиваемых

в

для

написания

и

отладки

ПЗУ.

Примерами

таких

ОС

программ,

позднее

являются

системы

программирования микроконтроллеров Intel, Atmel, PIC и др., системы Windows СЕ, Palm OS и т. д. Такие системы, как правило, включают в себя: − набор

компиляторов

и

ассемблеров,

работающих

на

инструментальной машине с "нормальной" ОС; − библиотеки, выполняющие большую часть функций ОС при работе программы (но не загрузку этой программы!); − средства отладки.

13

Иногда встречаются кросс-системы, в которых компилятор работает не на инструментальной машине, а в целевой системе — так, например, устроена среда разработки для семейства микропроцессоров Transputer компании Inmos.. Системы промежуточных типов Существуют системы, которые нельзя отнести ни к одному из перечисленных выше классов. Такова, например, система RT-11, которая, по сути своей, является ДОС, но позволяет одновременное исполнение нескольких программ с довольно богатыми средствами взаимодействия и синхронизации. Другим примером промежуточной системы являются MS Windows 3.x и Windows 95, которые, как ОС, используют аппаратные средства процессора для защиты и виртуализации памяти и даже могут обеспечивать некоторое подобие многозадачности, но не защищают себя и программы от ошибок других программ, подобно ДОС. Некоторые системы реального времени, например QNX, могут использоваться как в качестве самостоятельной ОС, загружаемой с жесткого диска в оперативную память, так и, будучи прошиты в ПЗУ. Эти системы могут быть отнесены одновременно и к ОС общего назначения, и к системам кросс-разработки. Таких примеров "гибридизации" можно привести множество. Семейства операционных систем Часто можно проследить преемственность между различными ОС, необязательно

разработанными

одной

компанией.

Отчасти

такая

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

прикладного

программного

обеспечения, отчасти –

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

основании

такой

преемственности

можно

выстроить

"генеалогические деревья" операционных систем и — с той или иной

14

обоснованностью — объединять их в семейства. Впрочем, в отличие от древа происхождения биологических видов, граф родства ОС не является деревом и нередко содержит циклы, поэтому стройную многоуровневую классификацию построить не всегда удается. Тем не менее, можно выделить минимум три семейства ныне эксплуатирующихся ОС и еще несколько — вымерших или близких к тому. Три ныне процветающих семейства: − ОС компьютеров фирмы IBM – OS/390, z/OS и IBM VM, − Обширное,

бурно

развивающееся

и

имеющее

трудно

определимые границы семейство Unix: •

Unix System V Release 4.x: SunSoft Solaris, SCO UnixWare;

•

Berkeley Software Distribution Unix: BSDI, FreeBSD;

•

Linux,

− Семейство

прямых

и

косвенных

потомков

Control

Program/Monitor (СР/М) фирмы Digital Research. Еще одно практически вымершее к настоящему моменту, но оставившее в наследство ряд важных и интересных концепций семейство – это операционные системы для мини- и микрокомпьютеров фирмы DEC: RT-11, RSX-11 и VAX/VMS. Нужно отметить, впрочем, что современные версии Windows, несмотря на низкую надежность, сложность конфигурации и поддержки и ряд функциональных недостатков, вполне адекватны большинству задач конторской автоматизации. Проблемы возникают, когда задачи, стоящие перед организацией, выходят за пределы распечатки прайс-листов из MS Excel и набора писем в MS Word. Основная проблема MS Windows состоит вовсе не в том, что это не "настоящая" операционная система, а в том, что она не обеспечивает путей плавного и безболезненного перехода к другим платформам, даже если

15

возникнет необходимость такого перехода. Строго говоря, тот же недостаток свойственен многим другим закрытым (closed) платформам, поставляемым

одной

фирмой

и

использующим

нестандартные

"фирменные" интерфейсы. Пока "закрытое" решение соответствует вашим требованиям,

все

хорошо,

но

когда

вы

выходите

за

пределы

технологических возможностей данного решения, вы оказываетесь в тупике. Открытые системы Альтернативой закрытым решениям является концепция открытых систем. Идея открытых систем исходит из того, что для разных задач необходимы разные системы — как специализированные, так и системы общего назначения, просто по-разному настроенные и сбалансированные. Сложность состоит в том, чтобы обеспечить: − взаимодействие разнородных систем в гетерогенной сети, − обмен данными между различными приложениями на разных платформах, − переносимость прикладного ПО с одной платформы на другую, хотя бы путем перекомпиляции исходных текстов, − по возможности однородный пользовательский интерфейс. Эти задачи решаются при помощи открытых стандартов – стандартных

сетевых

протоколов,

стандартных

форматов

данных,

стандартизации программных интерфейсов – API (Application Program Interface, интерфейс прикладных программ) и, наконец, стандартизации пользовательского интерфейса. Для того чтобы как-то обеспечить переносимость программ между системами

различных

типов,

принимались

различные

стандарты

интерфейса между пользовательской (обычно говорят — прикладной, но это не всегда правильно) программой и ОС. Одним из первых таких

16

стандартов был стандарт библиотек ANSI С. Он основан на системных вызовах ОС Unix, но функции MS DOS для работы с файлами (использующие file handle) тоже достаточно близки к этому стандарту. Позднее делалось еще несколько попыток стандартизировать интерфейс системных вызовов. Одной из относительно удачных попыток такого рода был POSIX (Portable Operating System Interface [based on] uniX – переносимый интерфейс операционной системы, основанный на Unix), который в той или иной форме поддерживается всеми системами семейства Unix и некоторыми ОС, не входящими в это семейство, например Windows NT. Наибольший же успех имела деятельность консорциума Х/Open, который в 1998 году сертифицировал операционную систему OS/390 фирмы IBM как соответствующую спецификациям Unix/95 и, таким образом, дал представителю самого древнего из современных родов операционных систем право называться UNIX ™.

17

1.2 Структура операционной системы Структура

и

сложность

операционных

систем

существенно

изменяется по мере развития, как самих операционных систем, так и аппаратного обеспечения [2]. Операционная система CTSS, разработанная в Массачусетском технологическом институте (МТИ) в 1963 году занимала в памяти около 36 тысяч 36-разрядных слов. OS/360, разработанная фирмой IBM через год, содержала уже более миллиона машинных команд. Система Multics, совместно разработанная специалистами МТИ и Bell Laboratories в 1975 году содержала уже около 20 миллионов команд. Увеличение размера и сложности операционных систем привело к возникновению трех распространенных проблем: − операционные системы доходят до пользователя с существенным опозданием, − в

системах

присутствуют

скрытые

ошибки,

требующие

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

18

Структура операционной системы во многом зависит от того, к какому из типов она относится. Типов операционных систем можно выделить много, однако по большому счету можно выделить следующие: − микроядерные, − монолитные, − многоуровневые, − виртуальные машины, − экзоядро, − модель клиент-сервер. Микроядро – это минимальная часть операционной системы, являющаяся основой для модульных и переносимых расширений. Основная идея микроядра – создать необходимую среду верхнего уровня, из которой можно получить доступ ко всем функциям уровня аппаратного обеспечения [3]. В

микроядре

содержится

минимальное

количество

кода,

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

19

прикладной программы. Обычно микроядро поддерживает пять различных типов сервисов [3]: − управление виртуальной памятью, − управление заданиями и потоками, − межпроцессные

коммуникации

(IPC

–

inter-process

communication), − управление вводом-выводом и прерываниями, − обеспечение клиент-серверного сервиса. Другие функции операционной системы размещаются в других сервисах ОС, работающих как приложения микроядра. Суть микроядерной архитектуры состоит в следующем [4]. В привилегированном режиме работает только очень небольшая часть операционной системы, называемая микроядром. Микроядро защищено от остальных частей ОС и от приложений. Набор функций микроядра соответствует функциям слоя базовых механизмов обычного ядра. Это те функции, которые нельзя выполнить в пользовательском режиме. На рисунке 1.2 показан механизм переноса основного объема функций ядра в пространство пользователя [4]. Благодаря своим размерам и способности поддерживать стандартные сервисы программирования микроядро проще ядер монолитных или модульных операционных систем.

Рисунок 1.2 – Перенос основного объема функций ядра в пространство пользователя

20

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

какие

из

системных

функций

следует

выполнять

в

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

в пользовательский режим,

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

невозможна, друг

привилегированном

от

так

друга.

режиме,

как

их

адресные

Микроядро,

имеет

доступ

пространства

выполняющееся ко

всем

в

адресным

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

ярким

представителем

микроядерных

ОС

является

операционная система реального времени QNX. Микроядро QNX планирует только планирование и диспетчеризацию процессов, их взаимодействие, обработку прерываний и сетевые службы нижнего уровня. Такое микроядро обеспечивает лишь два десятка системных вызовов и имеет размер от 8 до 46 килобайт.

21

Рисунок 1.3 – Реализация системного вызова в микроядерной архитектуре Для построения минимальной системы QNX к микроядру следует добавить менеджер процессов, который создает процессы, управляет ими и их памятью. Для применения QNX в настольной ПЭВМ, к микроядру следует добавить также файловую систему и менеджер устройств. Все эти менеджеры выполняются вне пространства ядра, так что ядро остается небольшим. Рассмотрим кратко достоинства и недостатки микроядерных ОС. К достоинствам их можно отнести: − переносимость, обусловленная тем, что весь машинно-зависимый код изолирован в микроядре, − расширяемость, обусловленная ограниченным набором четко определенных

интерфейсов

микроядра;

добавление

новой

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

22

защищает его от других серверов

ОС (в традиционной

операционной системе все модули могут влиять друг на друга); повышению надежности способствует также уменьшенный объем кода микроядра, − пригодность для распределенных вычислений, так как использует механизмы клиент-серверного взаимодействия, причем серверы микроядерной ОС могут находиться как на одном, так и на разных компьютерах. Основным недостатком микроядерной ОС является сниженная по сравнению с классической ОС производительность. Дело в том, что при классической

организации

ОС

выполнение

системного

вызова

сопровождается двумя переключениями режимов, а при микроядерной архитектуре – четырьмя. Ситуация иллюстрируется рисунком 1.4.

Рисунок 1.4 – Смена режимов при выполнении системного вызова Серьезность этого недостатка хорошо иллюстрирует история развития Windows NT [3]. В версиях 3.1 и 3.5 диспетчер окон, графическая оболочка и высокоуровневые драйверы графических устройств были включены в состав сервера пользовательского режима, и вызов этих функций осуществлялся в соответствии с микроядерной схемой. Однако, разработчикам стало ясно, что такой механизм существенно снижает быстродействие системы, поэтому в версии 4.0 перечисленные выше

23

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

ОС.

В

монолитной

ОС,

даже

если

она

сильно

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

обращении

к

системным

вызовам,

поддерживаемым

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

программа,

процедуру,

вызывающая

требуемую

служебную

24

− набор служебных процедур, выполняющих системные вызовы, − набор утилит, обслуживающих служебные процедуры. На рисунке 1.5 изображена указанная структура разделения процедур на три уровня [5].

Рисунок 1.5 – Простая модель монолитной системы Обобщением модели, изображенной на рисунке 1.5 является организация операционной системы в виде уровней иерархии и уровней абстракции [2]. В иерархической структуре современной операционной системы различные функции находятся на разных уровнях иерархии, в зависимости от их сложности, характеристик и уровня абстракции. Работа компонентов одного уровня основана на работе компонентов низших уровней. В идеале изменение одного уровня не должно влиять на все остальные уровни. Для

понимания

обобщенной

структуры

многоуровневой

операционной системы рассмотрим пример, приведенный в [2]. − Уровень 1. В него входят электронные схемы – регистры, ячейки памяти, логика. Над элементами этого уровня выполняются такие

25

действия, как очистка содержимого, считывание содержимого и т.д. − Уровень

2.

Набор

выполняются

такие

команд

процессора.

операции,

как

На

этом

сложение,

уровне

вычитание,

пересылки и т. д. − Уровень 3. Содержит концепцию процедуры (подпрограммы), а также операции вызова и возврата. − Уровень 4. Уровень прерываний. Здесь организуется выполнение процессором процедуры обработки прерывания с сохранением текущего контекста. Реально перечисленные уровни не входят в операционную систему, они представляют аппаратную реализацию процессора. Однако, здесь появляются элементы, которые можно отнести к понятию операционной системы – процедуры обработки прерываний. − Уровень

5.

Уровень

работающая многозадачной

процесса,

программа.

под

которым

Фундаментальное

операционной

системе

понимается

требование –

к

способность

приостанавливать процессы и возобновлять их выполнение. − Уровень 6. Здесь осуществляется работа на физическом уровне со вспомогательными устройствами памяти компьютера. − Уровень 7. Создает логическое адресное пространство процессов. Этот уровень организует виртуальное адресное пространство в виде блоков, которые могут перемещаться между основной памятью

и

использоваться

вспомогательной. страницы

В

качестве

постоянного

блоков

размера,

могут

сегменты

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

26

− Уровень 8. Отвечает за обмен информацией и сообщениями между процессами. Одним из инструментов этого уровня является канал, передающий выход одного процесса на вход другого. На этом уровне может осуществляться связь с процессами внешних устройств или с файловыми процессами. − Уровень 9. Обеспечивает долгосрочное хранение файлов. Здесь используется логический уровень хранения (название файла, длина) в отличие от физического уровня хранения (дорожка, сектор, головка) уровня 6. − Уровень 10. Предоставляет доступ к внешним устройствам с помощью стандартных интерфейсов. − Уровень 11. Поддерживает связь между внешними и внутренними идентификаторами системных ресурсов и объектов (имя файла и его дескриптор). Эта связь поддерживается с помощью каталога, который содержит взаимное отображение внешних и внутренних идентификаторов и права доступа. − Уровень 12. Предоставляет полнофункциональные средства поддержки процессов. В отличие от уровня 5, на котором реализована

поддержка

регистров

процессора

и

логика

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

пространство,

список

объектов

и

процессов

взаимодействия, правила и ограничения этого взаимодействия. − Уровень 13. Обеспечивает взаимодействие операционной системы с пользователем. Этот уровень обычно называется оболочкой (shell).

Оболочка

принимает

команды

пользователя,

интерпретирует их, создает необходимые процессы и управляет ими. На этом уровне создаются графические оболочки.

27

Представим иерархическую модель операционной системы в виде таблицы. Таблица 1.1 – Иерархическая модель операционной системы Уровень Название 13 Оболочка 12

Объекты Среда программирования пользователя Процессы пользователя

11

Процессы пользователя Каталоги

10

Устройства

9

Файловая система

Внешние устройства (принтер, монитор, мышь) Файлы

8

Коммуникации

Конвейеры

7

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

Сегменты, страницы

6 5 4

Прерывания

3 2

Процедуры Набор команд

1

Электронные схемы

Каталоги

Блоки данных, каналы, устройства Примитивные процессы, семафоры, список процессов Процедуры обработки прерываний Процедуры, стеки вызова Стек вычислений, интерпретатор команд, данные Регистры, шлюзы, шины и т. д.

Операции Инструкции командного языка оболочки Завершение, приостановка, возобновление процесса Создание, удаление, подключение, поиск Открытие, закрытие, чтение, запись Создание, удаление, открытие, закрытие, чтение, запись Создание, удаление, открытие, закрытие, чтение, запись Чтение, запись, выборка Чтение, запись, распределение, выборка Приостановка, возобновление выполнения, ожидание, передача сигнала Вызов, маскирование, повтор Вызов, возврат Пересылка, сложение, вычитание, ветвление Очистка, пересылка, активация

Первой системой, построенной таким образом, была система THE, созданная в Technische Hogeschool Eindhoven в Нидерландах Э. Дейкстрой и его студентами в 1968 году. Это была простая пакетная система для компьютера Electrologica X8, память которой состояла из 32 К 27разрядных слов. Система состояла из шести уровней, как показано в таблице 1.2 [5]. Уровень 0 занимался распределением времени процессора, переключая

процессы

при

возникновении

прерываний

или

при

28

срабатывании таймера. То есть, уровень 0 обеспечивал базовую многозадачность процессора. Уровень 1 управлял памятью. Он выделял процессам пространство в оперативной памяти и на магнитном барабане объемом 512 К слов для тех частей процессов (страниц), которые не помещались в оперативной памяти. Программное обеспечение уровня 1 обеспечивало попадание нужных страниц в оперативную память по мере необходимости. Таблица 1.2 – Структура операционной системы THE Уровень

Функция

5

Оператор

4

Программы пользователя

3

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

2

Связь оператор-процесс

1

Управление памятью и барабаном

0

Распределение процессора и многозадачность

Уровень

2

управлял

связью

между

консолью

оператора

и

процессами. Уровень 3 управлял устройствами ввода-вывода и буферизовал потоки информации к ним или от них. На уровне 4 работали пользовательские программы, которым не надо было заботиться

ни о процессах, ни о памяти, ни о консоли, на об

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

машины.

Современному

пользователю

или

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

Обычно

пользователь-программист

имеет

дело

с

29

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

перед

пользователем

в

виде

виртуальной

машиной,

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

образом,

любая

операционная

система

фактически

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

при

попытке

организовать

многозадачную

и/или

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

30

Система

виртуальных

машин

–

это

ОС,

допускающая

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

Создание

операционной

системы,

основанной

на

виртуальных машинах, было обусловлено желанием большого числа пользователей IBM/360 работать в режиме разделения времени. Исходная версия OS/360 предназначалась исключительно для пакетной обработки заданий. Следуя пожеланиям пользователей, в фирме IBM попытались разработать систему разделения времени TSS/360, которая оказалась однако громоздкой и медлительной, и успеха не имела. За разработку требуемой системы взялась группа из научного центра IBM в Кембридже, и разработала систему, которую фирма IBM и приняла в качестве законченного продукта. Эта система до сих пор используется на мейнфреймах. В оригинале созданная система называлась CP/CMS, затем была переименована

в

VM/370

[5,

6].

Эта

система

предоставляла

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

который

работает

с

оборудованием

и

обеспечивает

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

31

Так как каждая такая виртуальная машина полностью идентична настоящему оборудованию, на каждой из них может работать любая операционная системе, которая работает на реальной аппаратуре. На разных виртуальных машинах могут одновременно работать различные операционные системы. Идея таких виртуальных машин используется и в настоящее время. Фирма Intel при моральной поддержке фирмы Microsoft в разработке нового поколения 32-разрядных процессоров (386+) предусмотрела режим виртуального процессора 8086. В этом режиме процессор работает как обычный процессор 8086(8088), включая 16-разрядную адресацию памяти с ограничением адресного пространства в 1 Мбайт. Этот

режим

используется

системой

Windows

и

другими

операционными системами для запуска программ MS-DOS. Программы запускаются в режиме виртуального процессора 8086. Пока они выполняют обычные команды, они работают напрямую с оборудованием. Как только программа обращается операционной системе для выполнения системного вызова, или пытается сама осуществить ввод-вывод данных, генерируется исключение и управление передается монитору виртуальной машины. Затем уже монитор виртуальной машины разбирается с тем, как выполнять соответствующий запрос. Другое

использование

виртуальных

машин

можно

продемонстрировать на примере виртуальной Java-машине. Когда фирма Sun разработала язык программирования Java, она разработала и виртуальную Java-машину (JVM – Java Virtual Machine). Компилятор языка Java выдает код для JVM, который затем выполняется интерпретатором JVM. Экзоядро. В системе VM/370 каждый пользователь получает в свое распоряжение точную копию настоящей машины. 386 процессор в режиме

32

виртуальной машины 8086 предоставляет каждому пользователю точную копию другой машины. Развивая эту идею дальше, в Массачусетском технологическом институте разработали систему, которая предоставляет каждому пользователю абсолютную копию реального компьютера, но с подмножеством ресурсов [7]. Например, одна виртуальная машина может получить блоки на диске с номерами от 0 до 1023, другая – от 1024 до 2047 и т. д. На нижнем уровне в режиме ядра работает программа, которая называется экзоядро (exokernel). Она занимается распределением ресурсов для виртуальных машин и проверкой их использования. Каждая виртуальная машина на уровне пользователя может работать с собственной операционной системой (как в системе виртуальных машин), но при этом она ограничена набором ресурсов, которые она запросила, и которые ей были предоставлены. Преимущество экзоядра заключается в том, что можно обойтись без уровня отображения. В случае системы виртуальных машин каждая виртуальная машина считает, что она монопольно владеет всеми ресурсами. Поэтому монитор виртуальной машины должен поддерживать таблицы

преобразования

адресов

для

всех

ресурсов.

В

случае

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

33

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

Рисунок 1.6 – Модель клиент-сервер Модель клиент-сервер показан на рисунке 1.6. На рисунке показано, что в задачу ядра входит только управление связью между клиентами и серверами. Такая организация дает системе следующие преимущества: − Благодаря разделению операционной системы на части, каждая из которых управляет только одним элементом (файловой системой,

процессами,

терминалом,

памятью),

все

части

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

34

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

35

1.3

ОС как система управления ресурсами

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

представляет

собой

базовое

понятие

для

большинства

современных операционных систем и часто определяется, как программа в стадии выполнения. Надо четко различать понятия программа и процесс. Программа – это статический объект, представляющий собой файл с кодами и данными. Процесс – это динамический объект, который возникает в оперативной памяти после того, как пользователь или операционная система запустит программу на выполнение. В этом случае создается новая единица вычислительной работы. Это, конечно, очень грубое представление, но оно достаточно для решения задачи распределения ресурсов. Цель задачи управления ресурсами – наиболее эффективное управление

их

использование.

Например,

мультипрограммная

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

36

Критерий эффективности, в соответствии с которым операционная система осуществляет управление ресурсами, зависит от назначения ОС. В одних системах важна пропускная способность вычислительной системы, в других – время реакции. Управление ресурсами организуют в соответствии с выбранными критериями эффективности. В задачу управления любыми ресурсами входит четыре типа подзадач [4]: − планирование ресурса – определение, какому процессу, когда и в каком количестве (если ресурс может выделяться частями) следует выделить данный ресурс, − удовлетворение запроса на ресурс, − отслеживание состояния и учет использования ресурса – поддержание оперативной информации о том, занят или свободен ресурс, и какая доля ресурса уже распределена, − разрешение конфликтов между запросами ресурсов. Алгоритмы, реализованные в каждой операционной системе для реализации этих подзадач, определяют облик операционной системы в целом и отдельные ее характеристики – производительность, область применения, пользовательский интерфейс и т. д. Например, алгоритм управления процессором в значительной мере определяет, является ли операционная система системой разделения времени, системой пакетной обработки или системой реального времени. Сложность

задачи

организации

эффективного

использования

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

возникновения

запросов

на

потребление

ресурсов.

В

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

37

Операционная система обслуживает эти очереди по различным алгоритмам – в порядке поступления, на основе приоритетов, кругового обслуживания и т. д. и т. п. Исследованием и синтезом дисциплин обслуживания

заявок

в

очередях

занимается

область

прикладной

математики, называемая теорией массового обслуживания [8]. Эта теория часто используется для оценки эффективности различных алгоритмов управления очередями в операционных системах. Однако, многие конкретные

экземпляры

операционных

систем

отличаются

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

управления

операционной

ресурсами

системой

и

выполняются

прикладному

непосредственно

программисту

обычно

недоступны. Функции операционной системы обычно группируются либо в соответствии с типами ресурсов, которыми управляет операционная система, либо в соответствии со специфическими задачами, применимыми ко всем ресурсам. Иногда такие группы функций называют подсистемами. Наиболее важными подсистемами являются подсистемы управления: − процессами, − памятью, − файлами и − внешними устройствами. Подсистемами, общими для всех ресурсов являются подсистемы: − пользовательского интерфейса, − защиты данных и − администрирования.

38

Управление процессами Одной из важнейших подсистем операционной системы является подсистема

управления

процессами.

Эта

подсистема

самым

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

в

информационные

структуры

процесса

включаются

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

39

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

в

виду

защита

адресных

пространств,

осуществляемая

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

40

Эта информация обычно называется контекстом процесса. При этом говорят, что при смене процесса происходит переключение контекста. Операционная система занимается также синхронизацией процессов. Это

позволяет

процессу

приостанавливать

свое

выполнение

до

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

особые

средства

–

средства

межпроцессного

взаимодействия. В итоге можно сказать, что подсистема управления процессами: − планирует выполнение процессов, то есть, распределяет время между несколькими одновременно существующими в системе процессами, − создает и уничтожает процессы, − обеспечивает процессы необходимыми системными ресурсами, − обеспечивает синхронизацию процессов, − обеспечивает межпроцессное взаимодействие. Управление памятью

41

Память является для процесса таким же важным ресурсом, как и процессор. Процесс может выполняться, только если его коды и данные (не обязательно все) находятся в оперативной памяти. Управление памятью заключается в: − распределении имеющейся физической памяти между всеми существующими в системе процессами, − загрузке кодов и данных процессов в отведенные им области памяти, − настройке

адресно-зависимых

частей

кодов

процесса

на

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

операционных

системах

является

так

называемая

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

42

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

операционной

системы

«скрывать»

сложности

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

– файловой системе. Операционная система

43

представляет

отдельный

набор

данных,

накопителе,

в

файла

–

виде

хранящихся

простой

на

внешнем

неструктурированной

последовательности байтов, имеющей символьное имя и набор атрибутов (длина, время создания, время модификации и т. д.). Здесь происходит виртуализация набора данных, отдельные части которых могут быть произвольным образом разбросаны по накопителю, в логический образ – файл. Для удобства работы файлы группируются в каталоги, которые могут группироваться в каталоги более высокого уровня и т. д. Различные операционные системы позволяют использовать различное число уровней каталогов

(вложений).

Обычно

уровень

вложения

ограничивается

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

система

позволяет

пользователю

выполнять

с

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

дисков

различных типов, на флэш-накопителях, а также на накопителях всех других существующих или будущих типов, в виде иерархической структуры файлов и каталогов файловая система решает множество задач. Так, файловая система: − отображает

символьные

идентификаторы,

имена

файлов

во

внутренние

44

− преобразует символьные имена или внутренние идентификаторы файлов, с которыми работает пользователь или прикладная программа в физические адреса на дисках и других накопителях, − организует совместный доступ к файлам, − защищает файлы от несанкционированного доступа и т. д. Функционирование

файловой

системы

тесно

связано

с

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

данных,

возможностью

совместного

использования

и

множеством других характеристик. Программа, управляющая работой конкретной модели внешнего устройства и учитывающая все его особенности, обычно называется драйвером этого устройства. Драйвер может управлять единственной моделью устройства, например, модемом Onmi PCI фирмы ZyXEL, или группой устройств определенного типа, например, любыми Hayesсовместимыми модемами. Пользователю обычно важно наличие как можно большего количества разнообразных драйверов. От этого часто

45

зависит успех той или иной операционной системы. Так, именно отсутствие драйверов многих популярных внешних устройств было причиной низкой популярности OS/2. Созданием драйверов устройств занимаются как разработчики конкретной операционной системы, так и разработчики конкретных внешних устройств. Обычно операционная система поддерживает хорошо определенный

интерфейс

между

драйверами

и

остальной

частью

операционной системы. Часто этот интерфейс бывает открытым, иногда – частично. В

принципе,

никто

не

мешает

прикладным

программистам

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

высокоуровневого

унифицированного

интерфейса

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

выглядит

как

обмен

с

файлом,

имеющим

имя

и

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

46

В последнем случае принято различать защиту от ошибочного и от злонамеренного доступа. Первым уровнем защиты данных от несанкционированного доступа является процедура входа в систему. Операционная система должна убедиться, что в систему пытается войти пользователь, вход которого разрешен администратором. Функции защиты операционной системы непосредственно связаны с функциями администрирования: − администратор определяет права пользователей при обращении их к различным ресурсам системы (файлам, каталогам, принтерам, сканерам и т. д.), − администратор же ограничивает возможности пользователей при выполнении некоторых системно важных действий (завершение работы, установка системного времени, завершение чужих процессов, создание новых учетных записей, изменять права доступа к ресурсам и т. д.), − администратор

исключить

может

некоторые

возможности

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

событий,

которые

необходимо

фиксировать,

определяет

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

47

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

системы систем

это

(в

большинстве

любые

действия,

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

с

управлением аппаратурой), − когда использование системных функций помогает упростить написание приложение (это использование стандартных, часто используемых функций, таких как обработка строк, построение изображений и т. д.). Здесь следует отметить, что использование системных функций может осуществляться косвенно. Так, например, в C++ Builder имеется

48

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

функций,

называющегося

интерфейсом

прикладного

программирования (Application Programming Interface, API). Для прикладных программистов все особенности конкретной операционной системы представляются особенностями ее API. Именно поэтому операционные системы с различной внутренней организацией, но с одинаковым набором функций API представляются прикладному программисту одной и той же системой. Это упрощает стандартизацию операционных систем и улучшает переносимость приложений между различными системами. Приложения обращаются к функциям API с помощью системных вызовов. Этот способ обращения напоминает вызов процедур. − Операционной идентификатора

системе функции

передается и

запрос,

данных.

Этот

состоящий запрос

из

может

помещаться в стек, в регистры или в область памяти. − Затем управление передается операционной системе, которая выполняет требуемую функцию и помещает ее результаты в стек, в регистры или в область памяти. − Если функция выполнена с ошибкой, результат включает индикацию ошибок.

49

− Управление

возвращается

прикладной

программе,

которая

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

Это

могут

быть

конечные

пользователи,

администраторы,

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

операционные

пользовательского

системы

интерфейса.

поддерживают Они

развитые

предназначены

для

интерактивной работы за терминалами двух типов: − алфавитно-цифровыми и − графическими. При работе за алфавитно-цифровым терминалом пользователь имеет в своем распоряжении систему команд, которая отражает функциональные возможности конкретной операционной системы. Обычно командный язык операционной системы позволяет: − запускать и останавливать приложения, − выполнять различные операции с файлами и каталогами, − получать информацию о состоянии операционной системы (активные процессы, объем свободной оперативной и дисковой памяти, загрузка процессора и т. д.),

50

− администрировать систему. Команды могут вводиться не только с терминала в интерактивном режиме, но и из командного (пакетного) файла. При

использовании

графического

интерфейса

ввод

команд

упрощается – для выполнения многих команд достаточно выполнить некоторые действия мышью (хотя следует отметить, что для некоторых пользователей проще ввести командную строку, чем «кликать» мышью).

51

1.4 Контрольные вопросы 1. Что такое операционная система? 2. Функции операционной системы. 3. Что такое дисковая операционная система. 4. Классификация операционных систем. 5. Что такое ОС общего назначения? 6. Что такое ОС реального времени? 7. Что такое гибридные ОС? 8. Что такое системы виртуальных машин? 9. Примеры дисковых операционных систем. 10. Примеры систем реального времени. 11. Примеры систем общего назначения. 12. Что такое мягкое реальное время? 13. Что такое жесткое реальное время? 14. Что такое средства кросс-разработки? 15. Что такое семейства операционных систем? 16. Примеры семейств операционных систем. 17. Что такое открытые системы? 18. Что такое API? 19. Что такое стандарт ANSI C? 20. Что такое стандарт POSIX? 21. Структура операционной системы. 22. Микроядерные операционные системы. 23. Монолитные операционные системы. 24. Многоуровневые операционные системы. 25. Системы виртуальных машин. 26. Экзоядро. 27. Системы клиент-сервер.

52

28. Сервисы, поддерживаемые микроядром. 29. Суть микроядерной архитектуры. 30. Привилегированный и пользовательский режимы. 31. Механизм реализации функций-серверов. 32. Реализация системных вызовов в микроядерной архитектуре. 33. Достоинства и недостатки микроядерной архитектуры. 34. Смена режимов при выполнении системного вызова. 35. Модель монолитной структуры ОС. 36. Уровни абстракции ОС. 37. Иерархическая модель операционной системы. 38. Структура операционной системы THE. 39. Модель системы клиент-сервер. 40. Преимущества и недостатки клиент-серверной архитектуры. 41. Модель клиент-сервер в распределенной системе. 42. ОС, как система управления ресурсами. 43. Какими ресурсами управляет ОС? 44. Понятия программы и процесса. 45. Критерии эффективности ОС. 46. Планирование ресурса. 47. Удовлетворение спроса на ресурс. 48. Отслеживание состояния ресурса. 49. Разрешение конфликтов. 50. Управление процессами. 51. Ресурсы, необходимые для выполнения процесса. 52. История процесса в системе. 53. Состояния процесса. 54. Уровень привилегированности процесса. 55. Защита ресурсов процесса.

53

56. Адресное пространство процесса. 57. Прерывание выполнения процесса. 58. Возобновление выполнения процесса. 59. Контекст процесса. 60. Состояние среды системы. 61. Синхронизация процессов. 62. Соответствие между процессами и программами. 63. Функции подсистемы управления процессами. 64. Планирование процессов. 65. Создание и уничтожение процессов. 66. Обеспечение процессов ресурсами. 67. Обеспечение межпроцессного взаимодействия. 68. Управление памятью. 69. Распределение памяти. 70. Загрузка кодов программ. 71. Настройка кодов процесса на физические адреса. 72. Виртуальная память. 73. Трансляция виртуальных адресов. 74. Защита памяти. 75. Функции подсистемы управления памятью. 76. Отслеживание свободной памяти. 77. Выделение памяти процессам. 78. Вытеснение процессов из основной памяти. 79. Управление файлами. 80. Управление внешними устройствами. 81. Функции работы с файлами. 82. Файловая система. 83. Функции файловой системы.

54

84. Совместный доступ к файлам. 85. Подсистема управления внешними устройствами. 86. Драйверы устройств. 87. Защита данных и администрирование. 88. Средства обеспечения безопасности данных ОС. 89. Многопроцессорные системы. 90. Интерфейс прикладного программирования. 91. Системные вызовы. 92. Процесс выполнения системного вызова. 93. Пользовательский интерфейс. 94. Интерфейс командный строки. 95. Графические оболочки. 96. Функции интерфейса командной строки. 97. Функции графического интерфейса.

55

2

Мультипрограммирование

Как уже говорилось выше, важнейшей функцией операционной системы является организация рационального использования ресурсов. Располагающая

одними

и

теми

же

аппаратными

ресурсами,

но

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

управления

ресурсами

необходимо

решать

и

в

однопрограммных операционных системах (распределение памяти между системой, резидентами и приложением, распределение прерываний и т. д.), однако, в полный рост эти проблемы встают в мультипрограммных операционных системах. Здесь за ресурсы конкурируют сама система и несколько приложений. Поэтому большая часть задач управления ресурсами относится именно к мультипрограммным системам. Мультипрограммирование или многозадачность (multitasking) – это способ организации вычислительного процесса, при котором на одном процессоре

поочередно

выполняется

несколько

программ.

Эти

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

ввода-вывода,

мультипрограммирование

данные повышает

и

т.

д.

эффективность

Считается,

что

использования

вычислительной системы, однако само понятие эффективности часто понимается по-разному. Типичными критериями эффективности таких систем являются [4]: − пропускная способность – количество задач, выполняемых вычислительной системой в единицу времени,

56

− удобство работы пользователей, заключающееся в возможности пользователя одновременно работать на одной машине с несколькими приложениями, − реактивность системы – способность системы выдерживать заранее заданные интервалы времени между запуском программы и получением результата. В

зависимости

от

выбранного

критерия

эффективности

операционные системы делятся на − системы пакетной обработки, − системы разделения времени и − системы реального времени. Системы каждого типа имеют специфические механизмы и специфические области применения. Бывают комбинированные системы, в которых, например, часть задач выполняется в пакетном режиме, а часть в режиме разделения времени.

57

2.1 Системы пакетной обработки Использование пропускной

мультипрограммирования

способности

компьютера

для

главной

целью

повышения является

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

процессора,

является

переключение

процессора

на

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

одновременного

выполнения

выбираются

задачи,

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

58

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

выполнение

того

или

иного

задания

в

течение

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

центрального

процессора.

Специальная

инструкция

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

отрабатывает

команды,

поступающие

от

центрального

59

процессора. При этом контроллеры и центральный процессор работают асинхронно.

Рисунок 2.1 – Параллельное выполнение вычислений и операций вводавывода в системах с каналом

Рисунок 2.2 – Параллельное выполнение вычислений и операций вводавывода в системах с контроллерами Многие внешние устройства включают в себя движущиеся части, контроллер обычно выполняет свои команды медленнее, чем центральный процессор. Этот факт используется для организации параллельного выполнения вычислений и операций ввода-вывода. Вычисления могут выполняться между выдачей команд контроллерам внешних устройств. Такой механизм показан на рисунке 2.2.

60

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

эффект

достигается

при

наиболее

полном

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

ввода-вывода),

процессор

не

простаивает,

как

при

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

готова

выполняться,

но

вынуждена

ждать

освобождения

процессора, что удлиняет время ее выполнения. Так, на рисунке 2.3 видно, что в однопрограммном режиме задача А выполняется за 6 единиц

61

времени, а в мультипрограммном – 7. Задача В также вместо 5 единиц времени выполняется за 6. Зато суммарное время выполнения обеих задач в

мультипрограммном

режиме

составляет

всего

8

единиц,

а

в

однопрограммном – 11. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой

происходит по

инициативе активной задачи – активная задача отказывается от процессора из-за необходимости выполнения операции ввода-вывода.

Рисунок 2.3 – Время выполнения двух задач в однопрограммной системе (О) и в мультипрограммной системе (М) Этот механизм определяет высокую вероятность того, что одна задача может надолго занять процессор и выполнение других задач прекратится. Очевидно,

что

пакетная

система

повышает

эффективность

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

62

2.2 Мультипрограммирование в системах разделения времени В

системах

пользователям

разделения

времени

предоставляется

одному

или

возможность

нескольким

одновременной

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

системы

пакетной

обработки

не

могут

предоставить

такую

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

производительности

вычислительной

системы

и

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

63

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

очередного

кванта

времени.

Дополнительное

снижение

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

обслуживания

пользователей

система

одновременно

обслуживает несколько (иногда довольно много) пользователей.

64

2.3 Мультипрограммирование в системах реального времени Системы реального времени используются обычно для управления различными техническими объектами (например, станком, спутником, измерительной

установкой,

технологическими

процессами

баллистической (например,

ракетой)

стекловаренной

или печью,

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

системах

представляет

собой

реального

времени

фиксированный

мультипрограммная

набор

заранее

смесь

разработанных

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

65

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

генерации

соответствующего

вектора

прерывания

эти

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

прерываний.

Создание

механизма

векторных

прерываний

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

66

Здесь следует отметить, что повсеместно используемый подход к проектированию «обычных» вычислительных систем, основанный на оценке средней нагрузки, средней интенсивности заявок, среднего времени ожидания и т. д. совершенно не подходит к управляющим системам – системам реального времени. Эти системы должны проектироваться из учета возможности возникновения наихудшего сочетания условий при эксплуатации. Это приводит к тому, что управляющая вычислительная система большую часть времени будет бездействовать, а следовательно, средняя загрузка аппаратных средств будет очень малой. Это неизбежная плата за то, что в случае возникновения нештатной (аварийной) ситуации система сработает правильно, и технологический процесс не будет нарушен. Если не придерживаться такого подхода к управляющим системам реального времени, неизбежны новые чернобыли.

67

2.4 Мультипроцессорная обработка Мультипроцессорная

обработка

–

это

такая

организация

вычислительного процесса в мультипроцессорной системе, при которой несколько задача (процессов, потоков) одновременно выполняются на разных процессорах. Первые попытки мультипроцессорной обработки предпринимались с середины 50-х годов. Однако, в то время стоимость каждого процессора была настолько велика, а организация собственно многопроцессорной обработки настолько сложна, что предпринимались эти попытки в основном для повышения надежности некоторых систем, например, таких как ядерные реакторы. Теперь все иначе: использование многопроцессорных систем для создания

видеоэффектов

известно

уже

давно,

а

настольные

мультипроцессорные вычислительные системы – реальность сегодняшнего дня. Распространению многопроцессорных систем способствует также выпуск

ведущими

производителями

многоядерных

процессоров

(в

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

68

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

для

всех

процессоров

и,

соответственно,

планировать

и

распределять ресурсы приходится для нескольких процессоров. Конечно, в некоторых системах каждый процессор (или каждое ядро) имеет свой кэш, но это – лишь малая часть ресурсов, которыми приходится управлять. При

наличии

нескольких

процессоров

или

ядер

возрастает

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

ресурсам

и

программам.

При

этом

существенно

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

проблем

операционная

система

должна

тщательнее

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

должна

также

минимизировать

взаимозависимости

между

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

69

2.5 Контрольные вопросы 1. Мультипрограммирование. 2. Многозадачность. 3. Критерии эффективности многозадачных ОС. 4. Пропускная способность. 5. Удобство работы пользователей. 6. Реактивность системы. 7. ОС пакетной обработки. 8. ОС реального времени. 9. ОС разделения времени. 10. Особенности систем пакетной обработки. 11. Критерии эффективности систем пакетной обработки. 12. Функционирование системы пакетной обработки. 13. Формирование мультипрограммной смеси в ОС пакетной обработки. 14. Совмещение операций ввода-вывода. 15. Команды управления внешними устройствами. 16. Канальные программы. 17. Параллельная работа канала и процессора. 18. Контроллеры внешних устройств. 19. Совмещение операций в системах с контроллерами. 20. Влияние характера смеси задач на эффективность ОС. 21. Время выполнения каждой задачи в пакетных ОС. 22. Время выполнения всех задач в пакетных ОС. 23. Мультипрограммирование в системах разделения времени. 24. Реализация систем разделения времени. 25. Эффективность систем разделения времени. 26. Мультипрограммирование в системах реального времени. 27. Критерий эффективности системы реального времени.

70

28. Особенности смеси задач в системах реального времени. 29. Векторные прерывания. 30. Влияние векторных прерываний на эффективность работы систем реального времени. 31. Управление приоритетами прерываний. 32. Мультипроцессорная обработки. 33. Управление ресурсами при мультипроцессорной обработке. 34. Конфликты при мультипроцессорной обработке. 35. Взаимоблокировки.

71

3 Процессы и потоки 3.1 Планирование процессов и потоков Одной

из

основных

подсистем

мультипрограммной

ОС,

непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами и потоками [4], которая занимается их созданием и уничтожением, обеспечивает их взаимодействие и распределяет

процессорное время между несколькими одновременно

существующими в системе процессами и потоками. Подсистема

управления

процессами

и

потоками

отвечает

за

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

период.

При

выполнении

этих

функций

подсистема

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

за

управление

ресурсами,

такими

как

подсистема

управления памятью, подсистема ввода-вывода, файловая система. Когда в системе одновременно выполняется несколько независимых задач, то возникают дополнительные проблемы. Хотя потоки возникают и выполняются асинхронно, у них может возникнуть необходимость во взаимодействии, например при обмене данными. Согласование скоростей потоков также очень важно для предотвращения эффекта «гонок» (когда несколько потоков пытаются изменить один и тот же файл), взаимных блокировок или других коллизий, которые возникают при совместном

72

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

структуры

процесса.

Выполняется

коррекция

всевозможных очередей ОС и списков ресурсов, в которых имелись ссылки на завершаемый процесс. Понятия «процесс» и «поток» [4] Чтобы поддерживать мультипрограммирование, ОС должна определить и оформить для себя те внутренние единицы работы, между которыми будет разделяться процессор и другие ресурсы компьютера. В настоящее время в большинстве операционных систем определены два типа единиц работы. Более крупная единица работы, обычно носящая название процесса, или задачи, требует для своего выполнения нескольких более мелких работ, для обозначения которых используют термины «поток», или «нить». Итак, в чем же состоят принципиальные отличия в понятиях «процесс» и «поток»? Очевидно, что любая работа вычислительной системы заключается в выполнении некоторой программы. Поэтому и с процессом, и с потоком связывается определенный программный код, который для этих целей оформляется в виде исполняемого модуля. Чтобы этот программный код мог быть выполнен, его необходимо загрузить в оперативную память, возможно, выделить некоторое место на диске для хранения данных, предоставить доступ к устройствам ввода-вывода, например к последовательному порту для получения данных из подключенного к этому порту модема, и т. д. В ходе выполнения

программе

может

также

понадобиться

доступ

к

73

информационным

ресурсам,

например

файлам,

портам

TCP/UPD,

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

система

обеспечивает

каждый

процесс

отдельным

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

74

При

необходимости

операционной

системе,

взаимодействия которая,

процессы

выполняя

обращаются

функции

к

посредника,

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

необходимость

может

возникать.

Действительно,

при

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

75

Потоки

возникли

распараллеливания

в

операционных

вычислений.

Конечно,

системах задача

как

средство

распараллеливания

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

76

переход процессора от одной команды программы к другой. ОС распределяет процессорное время между потоками. Процессу ОС назначает адресное пространство и набор ресурсов, которые совместно используются всеми его потоками. Создание потоков требует от ОС меньших накладных расходов, чем процессов. В отличие от процессов, которые принадлежат разным, вообще говоря, конкурирующим приложениям, все потоки одного процесса всегда принадлежат одному приложению, поэтому ОС изолирует потоки в гораздо меньшей степени, нежели процессы в традиционной мультипрограммной системе. Все потоки одного процесса используют общие файлы, таймеры, устройства, одну и ту же область оперативной памяти, одно и то же адресное пространство. Это означает, что они разделяют одни и те же глобальные переменные. Поскольку каждый поток может иметь доступ к любому виртуальному адресу процесса, один поток может использовать стек другого потока. Между потоками одного процесса нет полной защиты, потому что, во-первых, это невозможно, а во-вторых, не нужно. Чтобы организовать взаимодействие и обмен данными, потокам вовсе не требуется обращаться к ОС, им достаточно использовать общую память – один поток записывает данные, а другой читает их. С другой стороны, потоки разных процессов попрежнему хорошо защищены друг от друга. Итак, мультипрограммирование более эффективно на уровне потоков, а не процессов. Каждый поток имеет собственный счетчик команд и стек. Задача, оформленная в виде нескольких потоков в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного (или параллельного в мультипроцессорной системе) выполнения отдельных ее частей. Например, если электронная таблица была разработана с учетом возможностей многопоточной обработки, то пользователь может запросить пересчет своего рабочего листа и одновременно продолжать заполнять таблицу. Особенно

77

эффективно

можно

использовать

многопоточность

для

выполнения

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

эффект

от

введения

многопоточной

обработки

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

78

3.2 Создание процессов и потоков Создать процесс – это, прежде всего, означает создать описатель (handle – дескриптор) процесса, в качестве которого выступает одна или несколько информационных структур, содержащих все сведения о процессе, необходимые операционной системе для управления им. В число таких сведений могут входить, например, идентификатор процесса, данные о расположении в памяти исполняемого модуля, степень привилегированности процесса (приоритет и права доступа) и т. п. Примерами описателей процесса являются блок управления задачей (ТСВ – Task Control Block) в OS/360, управляющий блок процесса (РСВ – Process Control Block) в OS/2, дескриптор процесса в UNIX, объект-процесс (object-process) в Windows NT. Создание описателя процесса знаменует собой появление в системе еще одного претендента на вычислительные ресурсы. Начиная с этого момента при распределении ресурсов ОС должна принимать во внимание потребности нового процесса. Создание процесса включает загрузку кодов и данных исполняемой программы данного процесса с диска в оперативную память. Для этого ОС должна обнаружить местоположение программы на диске, перераспределить оперативную память и выделить память исполняемой программе нового процесса. Затем необходимо считать программу в выделенные для нее участки памяти и, возможно, настроить программу в зависимости от размещения ее в памяти. В системах с виртуальной памятью в начальный момент может загружаться только часть кодов и данных процесса, с тем чтобы «подкачивать» остальные по мере необходимости. Существуют системы, в которых на этапе создания процесса не требуется непременно загружать коды и данные в оперативную память, вместо этого исполняемый модуль копируется из того каталога файловой системы, в котором он изначально

79

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

80

Рассмотрим в качестве примера [4] создание процессов в популярной версии операционной системы UNIX System V Release 4. В этой системе потоки не поддерживаются, в качестве единицы управления и единицы потребления ресурсов выступает процесс. При управлении процессами операционная система использует два основных типа информационных структур: дескриптор процесса и контекст процесса. Дескриптор процесса содержит такую информацию о процессе, которая необходима ядру в течение всего жизненного цикла процесса независимо от того, находится он в активном или пассивном состоянии, находится образ процесса в оперативной памяти или выгружен на диск. Дескрипторы отдельных процессов объединены в список, образующий таблицу процессов. Память для таблицы процессов отводится динамически в области ядра. На основании информации, содержащейся в таблице процессов, операционная

система осуществляет

планирование и синхронизацию

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

81

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

в

качестве

своего

значения

в

породивший

процесс

идентификатор порожденного процесса, а в порожденный процесс – NULL. Типичное разветвление на языке С записывается так: if( fork () ) { действия родительского процесса } else { действия порожденного процесса }

Идентификатор потомка может быть присвоен переменной, входящей в контекст родительского процесса. Так как контекст процесса наследуется его потомками, то потомки могут узнать идентификаторы своих «старших братьев», таким образом, сумма знаний наследуется при порождении и может быть распространена между родственными процессами. На независимости идентификатора процесса от выполняемой процессом программы построен механизм, позволяющий процессу перейти к выполнению другой программы с помощью системного вызова exec.

82

Таким образом, в UNIX порождение нового процесса происходит в два этапа – сначала создается копия процесса-родителя, затем у нового процесса производится замена кодового сегмента на заданный. Вновь созданному процессу операционная система присваивает целочисленный

идентификатор,

функционирования системы.

уникальный

на

весь

период

83

3.3 Планирование и диспетчеризация потоков На протяжении существования процесса выполнение его потоков может быть многократно прервано и продолжено. (В системе, не поддерживающей

потоки,

все

сказанное

ниже

о

планировании

и

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

Планирование

потоков

осуществляется

на

основе

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

приведенные

задачи.

Алгоритмы

планирования

могут

преследовать различные цели и обеспечивать разное качество мультипрограммирования. Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один поток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является максимально быстрое выполнение «коротких» задач, а в

84

третьем случае – преимущественное право занять процессор получают потоки

интерактивных

приложений. Именно особенности реализации

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

планировщики

могут

гибко

приспосабливаться

к

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

динамическим

и

статическим

планировщиками

аналогично

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

строго

по

предварительно

составленному

расписанию,

и

регулировщиком на перекрестке автомобильных дорог, не оснащенном светофорами, который решает, какую машину остановить, а какую пропустить, в зависимости от ситуации на перекрестке [4]. Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому потоку/процессу,

85

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

набора

задач,

например

о

максимальном

времени

выполнения каждой задачи, ограничениях предшествования, ограничениях по взаимному исключению, предельным срокам и т. д. После того как расписание готово, оно может использоваться операционной системой для переключения потоков и процессов. При этом накладные расходы ОС на исполнение расписания оказываются значительно меньшими, чем при динамическом планировании, и сводятся лишь к диспетчеризации потоков/процессов. Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статистического) решения, то есть в переключении процессора с одного потока на другой. Прежде чем прервать выполнение потока, ОС запоминает его контекст, с тем, чтобы впоследствии использовать эту информацию для возобновления выполнения данного потока. Контекст отражает состояние аппаратуры компьютера в момент прерывания потока – значение счетчика команд, содержимое регистров общего назначения, режим работы процессора, флаги, маски прерываний и параметры операционной среды – ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода, коды ошибок выполняемых данным потоком системных вызовов и т. д. Диспетчеризация обычно сводится к: − сохранению контекста текущего потока, который требуется сменить; − загрузке контекста нового потока; − запуску нового потока на выполнение.

86

Операция переключения контекстов ощутимо влияет на производительность вычислительной системы, поэтому модули ОС выполняют диспетчеризацию потоков совместно с аппаратными средствами процессора. В контексте потока можно выделить часть, общую для всех потоков данного процесса (ссылки на открытые файлы), и часть, относящуюся только к данному потоку (содержимое регистров, счетчик команд, режим процессора). Например, в среде NetWare 4.x различаются три вида контекстов: глобальный контекст (контекст процесса), контекст группы потоков и контекст отдельного потока. Соотношение между данными этих контекстов напоминает соотношение глобальных и локальных переменных в программе, написанной на языке С. Переменные глобального контекста доступны для всех потоков, созданных в рамках одного процесса. Переменные локального контекста доступны только для кодов определенного потока, аналогично локальным переменным функции. В NetWare можно создавать несколько групп потоков внутри одного процесса и каждая группа будет иметь свой контекст. Переменные, принадлежащие групповому контексту, доступны всем потокам, входящим в группу, но недоступны остальным потокам. Очевидно, что такая организация контекстов ускоряет переключение потоков, так как при переключении в пределах одной группы нет необходимости заменять контексты групп или глобальные контексты, достаточно лишь заменить контексты потоков, которые имеют меньший объем. Аналогично при переключении с потока одной группы на поток другой группы в пределах одного процесса глобальный контекст не изменяется, а изменяется лишь контекст группы. Переключение же глобальных контекстов происходит только при переходе с потока одного процесса на поток другого процесса.

87

3.4 Состояния потока ОС планирует потоки, принимая во внимание их состояние. В мультипрограммной системе поток может находиться в одном из трех основных состояний [4]: − выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором; − ожидание – пассивное состояние потока, в котором, поток заблокирован по своим внутренним причинам (ждет завершения операции ввода-вывода, получения сообщения от другого потока и т. д.); − готовность – также пассивное состояние потока, но в этом случае он заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые ресурсы, готов выполняться, однако процессор занят выполнением другого потока). В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе. Рассмотрим типичный граф состояния потока (рисунок 3.1). Только что созданный поток находится в состоянии готовности, он готов к выполнению и стоит в очереди к процессору. Когда в результате планирования подсистема управления потоками принимает решение об активизации данного потока, он переходит в состояние выполнения и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ожидания какого-нибудь события, либо будет принудительно «вытеснен» из процессора, например вследствие исчерпания отведенного ему кванта процессорного времени. В последнем случае поток возвращается в состояние готовности. В это же состояние поток переходит из состояния ожидания, после того как ожидаемое событие произойдет.

88

Рисунок 3.1 – Граф состояний потока в многозадачной среде В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности

–

соответственно

несколько

потоков.

ожидающих

и

Эти

готовых

потоки

образуют

очереди

потоков.

Очереди

потоков

организуются путем объединения в списки описателей отдельных потоков. Таким образом, каждый описатель потока, кроме всего прочего, содержит, по крайней мере, один указатель на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. Если предположить, что на рисунке 3.2 показана очередь готовых потоков, то запланированный порядок выполнения выглядит так: А, В, Е, D, С.

Рисунок 3.2 – Очередь потоков Одним

из

примеров

удачной

архитектуры можно привести ОС Solaris [2].

организации

многопоточной

89

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

потоками,

способствующий

значительной

гибкости

использования ресурсов. Здесь используются четыре отдельные концепции, связанные с потоками: − Процесс. Это обычный процесс Unix, который включает в себя пользовательское адресное пространство, стек и управляющий блок процесса. − Поток на пользовательском уровне. Эти потоки реализуются с помощью библиотеки потоков в адресном пространстве процесса; они

невидимы

для

операционной

системы.

Потоки

на

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

процессы.

Их

можно

рассматривать,

как

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

ядра.

элементами,

Эти

потоки

планирование

и

являются

фундаментальными

выполнение

которых

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

может

90

3.5 Вытесняющие и невытесняющие алгоритмы планирования Все множество алгоритмы планирования можно разделить на два принципиально различных класса: вытесняющие и невытесняющие [4]. − Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться до тех пор, пока он сам,

по

собственной

инициативе,

не

отдаст

управление

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

невытесняющем

мультипрограммировании

механизм

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

91

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

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

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

92

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

периода

никто

другой

не

изменит

данные.

Существенным

преимуществом невытесняющего планирования является более высокая скорость переключения с потока на поток. Почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT/2000,

OS/2,

VAX/VMS),

реализованы

вытесняющие

алгоритмы

планирования потоков (процессов). В последнее время дошла очередь и до ОС класса настольных систем, например OS/2 Warp и Windows 95/98. Примером

эффективного

использования

невытесняющего

планирования являются файл-серверы NetWare 3.x и 4.x, в которых в значительной степени благодаря такому планированию достигнута высокая скорость выполнения файловых операций. В соответствии с концепцией невытесняющего планирования, чтобы не занимать процессор слишком долго, поток в NetWare сам отдает управление планировщику ОС, используя следующие системные вызовы: − ThreadSwitch – поток, вызвавший эту функцию, считает себя готовым к немедленному выполнению, но отдает управление для того, чтобы могли выполняться и другие потоки; − ThreadSwitchWithDelay – функция аналогична предыдущей, но поток считает, что будет готов к выполнению только через определенное количество переключений с потока на поток;

93

− Delay – функция аналогична предыдущей, но задержка дается в миллисекундах; − ThreadSwitchLowPriority – функция отдачи управления, отличается от ThreadSwitch тем, что поток просит поместить его в очередь готовых к выполнению, но низкоприоритетных потоков. Планировщик NetWare использует несколько очередей готовых потоков (рисунок 3.3). Только что созданный поток попадает в конец очереди RunList, которая содержит готовые к выполнению потоки. После отказа от процессора поток попадает в ту или иную очередь в зависимости от того, какой из системных вызовов был использован при передаче управления. Поток поступает в конец очереди RunList при вызове ThreadSwitch, в конец очереди DelayedWorkToDoList при вызовах ThreadSwitchWithDelay или Delay или же в конец очереди LowPriorityRunList при вызове ThreadSwitchLowPriority. После того как выполнявшийся процессором поток завершит свой очередной цикл выполнения, отдав управление с помощью одного из вызовов передачи управления (или вызова ожидания на семафоре), планировщик выбирает для выполнения стоящий первым в очереди RunList поток и запускает его. Потоки, находящиеся в очереди DelayedWorkToDoList, после завершения условия ожидания перемещаются в конец очереди RunList. Потоки, находящиеся в очереди LowPriorityRunList, запускаются на выполнение только в том случае, если очередь RunList пуста. Обычно в эту очередь назначаются потоки, выполняющие несрочную фоновую работу. Очередь WorkToDoList является в системе самой приоритетной. В эту очередь попадают так называемые рабочие потоки. В NetWare, как и в некоторых других ОС, вместо создания нового потока для выполнения определенной работы может быть использован уже существующий системный поток. Пул рабочих потоков создается при старте системы для

94

системных целей и выполнения срочных работ. Рабочие потоки ОС обладают наивысшим приоритетом, то есть попадают на выполнение перед потоками из очереди RunList. Планировщик разрешает выполниться подряд только определенному количеству потоков из очереди WorkToDoList, а затем запускает поток из очереди RunList.

Рисунок 3.3 – Схема планирования потоков в NetWare Описанный невытесняющий механизм организации многопоточной работы в ОС NetWare 3.x и NetWare 4.x потенциально очень производителен, так

как

отличается

небольшими

накладными

расходами

ОС

на

диспетчеризацию потоков за счет простых алгоритмов планирования и иерархии контекстов. Но для достижения высокой производительности к разработчикам приложений для ОС NetWare предъявляются высокие требования,

так

как

распределение

процессорного

времени

между

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

95

3.6 Алгоритмы планирования, основанные на квантовании В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант. Смена активного потока происходит, если: − поток завершился и покинул систему; − произошла ошибка; − поток перешел в состояние ожидания; − исчерпан квант процессорного времени, отведенный данному потоку. Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Граф состояний потока,

изображенный

на

рисунке

3.4,

соответствует

алгоритму

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

Рисунок 3.4 – Граф состояний потока в системе с квантованием Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляются кванты одинаковой длины q (рисунок 3.5). Если в системе

96

имеется n потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оценить как q(n-l). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-l) все равно будет достаточно мало для того, чтобы пользователь не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Рисунок 3.5 – Иллюстрация расчета времени ожидания в очереди Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной системы). Действительно, поскольку время ожидания между двумя циклами выполнения равно q(n-l), а количество циклов B/q, где В – требуемое время выполнения, то W=B(n-l). Эти соотношения представляют собой весьма грубые оценки, основанные на предположении, что В значительно превышает q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут тратить на ввод-вывод, что количество потоков в системе может динамически меняться и т. д.

97

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

в

алгоритм

последовательной

обработки,

присущий

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

98

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

Рисунок 3.6 – Квантование с предпочтением потоков, интенсивно обращающихся к вводу-выводу

99

3.7 Алгоритмы планирования, основанные на приоритетах Другой важной концепцией, лежащей в основе многих вытесняющих алгоритмов

планирования,

является

приоритетное

обслуживание

[4].

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

порядок

их

выполнения.

Приоритет

–

это

число,

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

100

Во

многих

ОС

предусматривается

возможность

изменения

приоритетов в течение жизни потока. Изменение приоритета могут происходить по инициативе самого потока, когда он обращается с соответствующим вызовом к операционной системе, или по инициативе пользователя, когда он выполняет соответствующую команду. Кроме того, ОС сама может изменять приоритеты потоков в зависимости от ситуации, складывающейся в системе. В последнем случае приоритеты называются динамическими в отличие от неизменяемых, фиксированных, приоритетов. От того, какие приоритеты назначены потокам, существенно зависит эффективность работы всей вычислительной системы. В современных ОС во избежание разбалансировки системы, которая может возникнуть при неправильном назначении приоритетов, возможности пользователей влиять на приоритеты процессов и потоков стараются ограничивать. При этом обычные пользователи, как правило, не имеют права повышать приоритеты своим потокам, это разрешено делать (да и то в определенных пределах) только администраторам. В большинстве же случаев ОС присваивает приоритеты потокам по умолчанию. В качестве примера рассмотрим схему назначения приоритетов потокам, принятую в операционной системе Windows NT (рисунок 3.7). В системе определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 – для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для системных целей). При создании процесса он в зависимости от класса получает по умолчанию базовый приоритет в верхней или нижней части диапазона. Базовый приоритет процесса в дальнейшем может быть повышен или понижен операционной системой. Первоначально поток получает значение

101

базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значение базового приоритета некоторого процесса равно К. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [К-2, К+2]. Отсюда видно, что, изменяя базовый приоритет процесса, ОС может влиять на базовые приоритеты его потоков.

Рисунок 3.7 – Схема назначения приоритетов в Windows NT В Windows NT с течением времени приоритет потока, относящегося к классу потоков с переменными приоритетами, может отклоняться от базового приоритета потока, причем эти изменения могут быть не связаны с изменениями базового приоритета процесса. ОС может повышать приоритет потока (который в этом случае называется динамическим) в тех случаях, когда поток не полностью использовал отведенный ему квант, или понижать приоритет, если квант был использован полностью. ОС наращивает приоритет дифференцированно в зависимости от того, какого типа событие не дало потоку полностью использовать квант. В частности, ОС повышает приоритет в большей степени потокам, которые ожидают ввода с клавиатуры (интерактивным

приложениям)

и

в

меньшей

степени

–

потокам,

выполняющим дисковые операции. Именно на основе динамических приоритетов осуществляется планирование потоков. Начальной точкой отсчета для динамического приоритета является значение базового приоритета потока. Значение динамического приоритета потока ограничено снизу

102

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

с

две

разновидности

относительными

приоритетного

приоритетами

и

планирования:

обслуживание

с

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

одинаково:

выбирается

поток,

имеющий

наивысший

приоритет. Однако проблема определения момента смены активного потока решается по-разному. В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же произойдет ошибка, или поток завершится). На рисунок 3.8, показан граф состояний потока в системе с относительными приоритетами.

Рисунок 3.8 – Граф состояний потока в системе с относительными приоритетами В системах с абсолютными приоритетами выполнение активного потока прерывается кроме указанных выше причин, еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности (рисунок 3.9).

103

В системах, в которых планирование осуществляется на основе относительных приоритетов, минимизируются затраты на переключения процессора с одной работы на другую. С другой стороны, здесь могут возникать ситуации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения времени и реального времени такая дисциплина обслуживания не подходит: интерактивное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в системах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты используются широко.

Рисунок 3.9 – Граф состояний потоков в системах с абсолютными приоритетами В системах с абсолютными приоритетами время ожидания потока в очередях может быть сведено к минимуму, если ему назначить самый высокий приоритет. Такой поток будет вытеснять из процессора все остальные потоки (кроме потоков, имеющих такой же наивысший приоритет). Это делает планирование на основе абсолютных приоритетов подходящим для систем управления объектами, в которых важна быстрая реакция на событие.

104

3.8 Смешанные алгоритмы планирования 1Во многих операционных системах алгоритмы планирования построены с использованием и концепции квантования и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или

порядок

выбора

потока

из

очереди

готовых

определяется

приоритетами потоков. Именно так реализовано планирование в системе Windows NT, в которой квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом. Ему выделяется квант времени. Если во время выполнения в очереди готовых появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток. Вытесненный поток возвращается в очередь готовых, причем он становится впереди всех остальных потоков имеющих такой же приоритет. Рассмотрим более подробно алгоритм планирования в операционной системе UNIX System V Release 4. В этой ОС понятие «поток» отсутствует, и планирование осуществляется на уровне процессов. В этой системе реализована вытесняющая многозадачность, основанная на использовании приоритетов и квантования. Каждый процесс в зависимости от задачи, которую он решает, относится к одному из трех определенных в системе приоритетных классов: классу реального времени, классу системных процессов или классу процессов разделения времени. Назначение и обработка приоритетов выполняются для разных классов по-разному. Процессы системного класса, зарезервированные для ядра, используют стратегию фиксированных приоритетов. Уровень приоритета процессу назначается ядром и никогда не изменяется. Процессы

реального

времени

также

используют

стратегию

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

105

процессы не рассматриваются, то процессы реального времени надо тщательно проектировать, чтобы они не захватывали процессор на слишком долгое время. Характеристики планирования процессов реального времени включают две величины: уровень глобального приоритета и квант времени. Для каждого уровня приоритета по умолчанию имеется своя величина кванта времени. Процессу разрешается захватывать процессор на указанный квант времени, а по его истечении планировщик снимает процесс с выполнения. Процессы разделения времени были до появления UNIX System V Release 4 единственным классом процессов, и по умолчанию эта система назначает новому процессу именно этот класс. Состав класса процессов разделения времени наиболее неопределенный и часто меняющийся в отличие от системных процессов и процессов реального времени. Для справедливого распределения времени процессора между процессами в этом классе используется стратегия динамических приоритетов. Величина приоритета, назначаемого процессам разделения времени, вычисляется пропорционально значениям двух составляющих: пользовательской части и системной части. Пользовательская часть приоритета может быть изменена администратором и владельцем процесса, но в последнем случае только в сторону его снижения. Системная

составляющая

позволяет

планировщику

управлять

процессами в зависимости от того, как долго они занимают процессор, не уходя в состояние ожидания. У тех процессов, которые потребляют большие периоды процессорного времени без ухода в состояние ожидания, приоритет снижается, а у тех процессов, которые часто уходят в состояние ожидания после короткого периода использования процессора, приоритет повышается. Таким образом, процессам, ведущим себя не «по-джентельменски», дается низкий приоритет. Это означает, что они реже выбираются для выполнения. Это ущемление в правах компенсируется тем, что процессам с низким приоритетом даются большие кванты времени, чем процессам с высокими

106

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

пример

относится

к

операционной

системе

OS/2.

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

приоритетов.

На

множестве

потоков

определены

приоритетные классы – критический (time critical), серверный (server), стандартный (regular) и остаточный (idle), в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса имеют наивысший приоритет. В этот класс могут быть отнесены, например, системные потоки, выполняющие задачи управления сетью. Следующий по приоритетности класс предназначен, как это следует из его названия, для потоков, обслуживающих серверные приложения. К стандартному классу могут быть отнесены потоки обычных приложений. Потоки, входящие в остаточный класс, имеют самый низкий приоритет. К этому классу относится, например, поток, выводящий на экран заставку, когда в системе не выполняется никакой работы. Поток из менее приоритетного класса не может быть выбран для выполнения, пока в очереди более приоритетного класса имеется хотя бы один поток. Внутри каждого класса потоки выбираются также по приоритетам. Потоки, имеющие одинаковое значение приоритета, обслуживаются в циклическом порядке. Приоритеты могут изменяться планировщиком в следующих случаях: − Если поток находится в ожидании процессорного времени дольше, чем это задано системной переменной MAXWAIT, то его уровень приоритета будет автоматически увеличен операционной системой. При этом результирующее значение приоритета не должно

107

превышать нижней границы диапазона приоритетов критического класса. − Если поток ушел на выполнение операции ввода-вывода, то после ее завершения он получит наивысшее значение приоритета своего класса. − Приоритет потока автоматически повышается, когда он поступает на выполнение. ОС динамически устанавливает величину кванта, отводимого потоку для выполнения. Величина кванта зависит от загрузки системы и интенсивности подкачки. Параметры настройки системы позволяют явно задать границы изменения кванта. В любом случае он не может быть меньше 32 мс и больше 65 536 мс. Если поток был прерван до истечения кванта, то следующий выделенный ему интервал выполнения будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант не достигнет заранее заданного при настройке ОС предела. Благодаря такому алгоритму планирования в OS/2 ни один поток не будет «забыт» системой и получит достаточно процессорного времени.

108

3.9 Планирование в системах реального времени В системах реального времени, в которых главным критерием эффективности

является

обеспечение

заданного

времени

реакции,

планирование имеет особое значение. Любая система реального времени должна реагировать на сигналы управляемого объекта в течение заданных временных ограничений. Необходимость тщательного планирования работ облегчается тем, что в системах реального времени весь набор выполняемых задач известен заранее. Кроме того, часто в системе имеется информация о временах выполнения задач, моментах активизации, предельно-допустимых сроках ожидания ответа и т. д. Эти данные могут быть использованы планировщиком для создания статического расписания или для построения адекватного алгоритма динамического планирования. При разработке алгоритмов планирования в системах реального времени необходимо учитывать, какие последствия в этих системах возникают при несоблюдении временных ограничений. Если эти последствия катастрофичны, как, например, для системы управления полетами или атомной электростанцией, то операционная система реального времени, на основе которой строится управление объектом, называется жесткой (hard). Если же последствия нарушения временных ограничений не столь серьезны, то есть, сравнимы с той пользой, которую приносит система управления объектом, то система является мягкой (soft) системой реального времени. Примером

мягкой

системы

реального

времени

является

система

резервирования билетов. Если из-за временных нарушений оператору не удается зарезервировать билет, это не очень страшно – можно просто послать запрос на резервирование заново. В жестких системах реального времени время завершения выполнения каждой из критических задач должно быть гарантировано для всех возможных сценариев работы системы. Такие гарантии могут быть даны либо

109

в результате исчерпывающего тестирования всех возможных сценариев поведения управляемого объекта и управляющих программ, либо в результате построения статического расписания, либо в результате выбора математически обоснованного динамического алгоритма планирования. При построении расписания надо иметь в виду, что для некоторых наборов задач в принципе невозможно найти расписания, при котором удовлетворялись бы заданные временные характеристики. С целью определения возможности существования расписания могут быть использованы различные критерии. Например, в качестве простейшего критерия может служить условие, что разность между предельным сроком выполнения задачи (после появления запроса на ее выполнение) и временем ее вычисления (при условии непрерывного выполнения) всегда должна быть положительной. Очевидно, что такой критерий является необходимым, но недостаточным. Точные критерии, гарантирующие наличие расписания, являются очень сложными в вычислительном отношении. В мягких системах реального времени предполагается, что заданные временные ограничения могут иногда нарушаться, поэтому здесь обычно применяются менее затратные способы планирования. В зависимости от характера возникновения запросов на выполнение задач полезно разделять их на два типа: периодические и спорадические. Начиная с момента первоначального запроса все будущие моменты запроса периодической задачи можно определить заранее путем прибавления к моменту начального запроса величины, кратной известному периоду. Времена запросов на выполнение спорадических задач заранее не известны. Предположим, что имеется периодический набор задач {Ti} с периодами pi, предельными сроками di, и требованиями ко времени выполнения ci. Для проверки

возможности

существования

расписания

достаточно

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

110

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

следующее

достаточно

очевидное

утверждение:

сумма

коэффициентов использования μi = ci/pi должна быть меньше или равна k, где k – количество доступных процессоров, то есть:

μi = Σ ci/pi ≤ k При выборе алгоритма планирования следует учитывать данные о возможной зависимости задач. Эта зависимость может выступать, например, в виде ограничений на последовательность выполнения задач или их синхронизации, вызванной взаимными исключениями (запрете выполнения некоторых задач в течение определенных периодов времени). С практической точки зрения алгоритмы планирования зависимых задач более важны, чем алгоритмы планирования независимых задач. При наличии

дешевых

микроконтроллеров

нет

смысла

организовывать

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

существование

некоторого

предпочтения

последовательности

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

решения

требует

больших

вычислительных

ресурсов,

сравнимых с теми, которые требуются для собственно выполнения задач управления. Решение этой проблемы возможно за счет следующих мер: − Разделение проблемы планирования на две части, чтобы одна часть выполнялась заранее, перед запуском системы, а вторая, более

111

простая часть – во время ее работы. Предварительный анализ набора задач с взаимными исключениями может состоять, например, в выявлении так называемых запрещенных областей времени, в течение которых нельзя назначать выполнение задач, содержащих критические секции. − Введение ограничивающих предположений о поведении набора задач. При таком подходе планирование приближается к статическому. В качестве примера алгоритма для жестких систем реального времени с независимыми задачами и одним процессором, рассмотрим разработанный в 1973 году Лью и Лейландом [4]. Алгоритм является динамическим, то есть он использует вытесняющую многозадачность и основан на относительных статических (неизменяемых в течение жизни задачи) приоритетах. Алгоритм основан на следующих предположениях: − Запросы на выполнение всех задач набора, имеющих жесткие ограничения на время реакции, являются периодическими. − Все задачи независимы. Между любой парой задач не существует никаких ограничений на предшествование или на взаимное исключение. − Срок выполнения каждой задачи равен ее периоду pi. − Максимальное время выполнения каждой задачи ci известно и постоянно. − Время переключения контекста можно игнорировать. − Максимальный суммарный коэффициент загрузки процессора Σ ci/pi при существовании n задач не превосходит n (21/ n – 1). Эта величина при стремлении n к бесконечности приблизительно равна In 2, то есть 0,7.

112

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

113

3.10 Контрольные вопросы 1. Планирование процессов и потоков 2. Подсистема управления памятью. 3. Подсистема ввода-вывода. 4. Файловая подсистема. 5. Взаимодействие потоков. 6. Синхронизация потоков. 7. Взаимоблокировки потоков. 8. Понятия процесса и потока. 9. Мультипрограммирование на уровне процессов. 10. Защита процессов. 11. Адресное пространство процесса. 12. Виртуальное адресное пространство процесса. 13. Взаимодействие процессов. 14. Конвейеры. 15. Почтовые ящики. 16. Разделяемые секции памяти. 17. Способы распараллеливания вычислений в приложении. 18. Многопоточная обработка. 19. Основные отличия потоков от процессов. 20. Создание процессов и потоков. 21. Описатель процесса. 22. Блок управления задачей. 23. Управляющий блок процесса. 24. Дескриптор процесса. 25. Объект-процесс. 26. Контекст процесса. 27. Таблица процессов.

114

28. Планирование и диспетчеризация потоков. 29. Процессы планирования потоков. 30. Алгоритмы планирования потоков. 31. Динамическое планирование потоков. 32. Статическое планирование потоков. 33. Результат работы планировщика. 34. Накладные расходы при статической и динамической планировке процессов. 35. Процедуры диспетчеризации потоков. 36. Контекст потока. 37. Общая часть контекстов потоков процесса. 38. Типы контекстов. 39. Состояния потоков. 40. Активное состояние потока. 41. Пассивное состояние потока. 42. Состояние готовности потока. 43. Переход потока из одного состояния в другое. 44. Граф состояний потока. 45. Очередь готовых потоков. 46. Вытесняющие алгоритмы планирования. 47. Невытесняющие алгоритмы планирования. 48. Пример эффективного использования невытесняющего алгоритмы планирования. 49. Схема планирования потоков в NetWare. 50. Алгоритмы планирования, основанные на квантовании. 51. Граф состояний потока в системе с квантованием. 52. Оценка времени ожидания в очереди потоков. 53. Влияние величины кванта на эффективность ОС.

115

54. Алгоритмы планирования, основанные на приоритетах. 55. Работа ОС с фиксированными приоритетами. 56. Работа ОС с динамическими приоритетами. 57. Схема назначения приоритетов в Windows NT. 58. Планирование с абсолютными приоритетами. 59. Планирование с относительными приоритетами. 60. Граф состояний потока в системе с абсолютными приоритетами. 61. Граф состояний потока в системе с относительными приоритетами. 62. Смешанные алгоритмы планирования. 63. Пользовательская часть приоритета. 64. Системная часть приоритета. 65. Планирование потоков в системах реального времени. 66. Планирование потоков в системах разделения времени. 67. Обслуживание потоков, имеющих одинаковый приоритет. 68. Изменение приоритета планировщиком. 69. Динамическое изменение величины кванта потока. 70. Жесткие системы реального времени. 71. Мягкие системы реального времени. 72. Проверка возможности реализации расписания потоков. 73. Планирование зависимых задач. 74. Планирование независимых задач. 75. Пример алгоритма планирования для жестких систем реального времени.

116

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

117

Литература 1. Иртегов Д.В. Введение в операционные системы. – СПб.: БХВПетербург, 2002. – 624 с.: ил. 2. Столлингс В. Операционные системы, 4-е издание.: Перев. с англ. – М: Издательский дом «Вильямс», 2002. – 848 с.: ил. 3. Гордеев А.В., Молчанов А. Ю. Системное программное обеспечение. – СПб.: Питер, 2002. – 736 с.: ил. 4. Олифер Н.А., Олифер В.Г. Сетевые операционные системы. – СПб.: Питер, 2001. – 544 с.: ил. 5. Таненбаум Э. Современные операционные системы. 2-е изд. – СПб.: Питер, 2002. – 1040 с.: ил. 6. Rompogiannakis Y., Ntrjes G., Muth P., Paterakis M., Triantafillou P., Weikum G.: “Disk Scheduling for Mixed-Media Workloads in a Multimedia Server”, Proc. Sixth Int’l Conf. on Multimedia, ACM, pp. 297-302,1998. 7. Engler D. R., Kaashoek M.F., O’toole J. Jr.: “Exokernel: An Operating System Architecture for Application-Level Resource Management”, Proc. 15th Symp. on Operating Systems Principles, ACM, pp.251-266, 1955. 8. Клейнрок Л. Теория массового обслуживания. Пер. с англ. / Пер. И. И. Грушко; ред. В. И. Нейман. – М.: Машиностроение, 1979. – 432 с., ил.

118

Учебное пособие

Рощин Алексей Васильевич Операционные системы. Часть 1. Основы управления ресурсами. Учебное пособие.

Подписано к печати 20.09.2007 г. Формат 60 × 84 1/16. Объем 4,5 п.л. Тираж 100 экз. Заказ № 176

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