Виды ресурсов вычислительной системы
СИСТЕМНОЕ ПРОГРАММНОЕ
ОБЕСПЕЧЕНИЕ
НОВОЧЕРКАССК
Г.
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ.. 2
Введение.. 5
1. Общие понятия.. 6
1.1 Виды ресурсов вычислительной системы.. 6
1.2 Структура программного обеспечения. 7
2. Назначение и функции операционной системы... 9
2.1 Классификация операционных систем. 9
2.2 Операционные системы для автономного компьютера. 10
Функциональные компоненты ОС для автономного. 11
компьютера. 11
2.3 Сетевые операционные системы.. 11
Функциональные компоненты сетевой ОС.. 12
Варианты построения сетевых ОС.. 13
2.4 Одноранговые и серверные операционные системы.. 15
Операционные системы в одноранговых сетях. 15
Операционные системы в сетях с выделенными серверами. 16
3. Архитектура операционной системы... 18
3.1 Принципы построения ОС.. 18
3.2 Виды программных модулей. 20
3.3 Ядро и вспомогательные модули операционной системы.. 22
3.4 Классическая архитектура операционной системы.. 25
3.5 Микроядерная архитектура ОС.. 26
3.6 Обеспечение безопасности вычислительной системы.. 28
4. Управление процессами и потоками.. 30
4.1 Мультипрограммирование. 30
Мультипрограммирование в системах пакетной обработки. 30
Мультипрограммирование в системах разделения времени. 32
Мультипрограммирование в системах реального времени. 32
Мультипроцессорная обработка. 33
4.2 Планирование процессов и потоков. 35
Понятия «процесс» и «поток». 35
Реализация процессов и потоков. 38
Планирование и диспетчеризация потоков. 40
Вытесняющие и невытесняющие алгоритмы планирования. 41
Алгоритмы планирования, основанные на квантовании. 42
Алгоритмы планирования, основанные на приоритетах. 44
Смешанные алгоритмы планирования. 45
Планирование в системах реального времени. 46
Моменты перепланировки. 47
4.3 Мультипрограммирование на основе прерываний. 48
Назначение и типы прерываний. 48
Механизм прерываний. 50
4.4 Синхронизация процессов и потоков. 51
Критическая секция. 52
Запрещение прерываний. 53
Блокирующие переменные. 53
Семафоры.. 57
Синхронизирующие объекты ОС.. 59
Тупики. 59
5. Управление памятью... 62
5.1 Функции ОС по управлению памятью.. 62
5.2 Типы адресов. 62
5.3 Методы распределения памяти. 64
5.3.1 Распределение памяти без использования диска. 65
Распределение памяти фиксированными разделами. 65
Распределение памяти динамическими разделами. 66
Распределение памяти перемещаемыми разделами. 68
5.3.2 Виртуальная память. 69
Понятие виртуальной памяти. 69
Страничное распределение памяти. 70
Сегментное распределение памяти. 75
Странично-сегментное распределение памяти. 77
5.4 Кэширование данных. 78
Кэш-память. 78
Функционирование кэш-памяти. 80
Способы отображения основной памяти на КЭШ... 83
6. Управление вводом-выводом.. 88
6.1 Физическая организация устройств ввода-вывода. 88
6.2 Организация программного обеспечения ввода-вывода. 89
Обработка прерываний. 91
Драйверы устройств. 91
Независимый от устройств слой операционной системы.. 91
Пользовательский слой программного обеспечения. 92
7. Файловые системы... 94
7.1 Логическая организация файловой системы.. 94
Имена файлов. 94
Типы файлов. 95
Логическая организация файла. 96
7.2 Физическая организация файловой системы.. 98
Структура жесткого диска. 98
Физическая организация и адресация файла. 100
Права доступа к файлу. 103
Кэширование диска. 104
7.3 Общая модель файловой системы.. 104
7.4 Отображаемые в память файлы.. 107
7.5 Современные архитектуры файловых систем. 108
7.6 Физическая организация файловой системы FAT. 110
7.7 Физическая организация файловой системы NTFS. 115
7.8 Сравнение файловых систем. 123
8. Системы программирования.. 124
8.1 Состав систем программирования. 124
8.2 Компоненты систем программирования. 126
Текстовые редакторы.. 126
Трансляторы, компиляторы и интерпретаторы.. 126
Схема работы транслятора. 127
Список литературы... 129
Введение
В соответствии с Государственным образовательным стандартом 2000 г. по направлению подготовки дипломированного специалиста 651900 «Автоматизация и управление» в курсе «Системное программное обеспечение» рассмотрены следующие темы: виды ресурсов вычислительной системы, структура программного обеспечения, назначение и функции операционной системы, архитектура операционной системы, управление процессами и потоками, управление памятью, управление вводом-выводом, файловые системы, системы программирования.
В данном курсе рассматривается не конкретная операционная система (ОС) и даже не конкретный тип операционных систем. В нем операционные системы рассматриваются с самых общих позиций, а описываемые фундаментальные концепции и принципы построения справедливы для большинства ОС.
Действительно, различия между существующими ОС не столь существенны, как это может показаться на первый взгляд. Разработчики операционных систем живут в едином мире без жестких границ, не препятствующих миграции хорошо зарекомендовавших себя концепций и механизмов из одной системы в другую. В результате в подавляющем большинстве ОС нам встречаются одни и те же принципы управления ресурсами компьютера: мультипрограммирование и мультипроцессирование, виртуальная память и свопинг, отображаемые в память файлы и удаленный вызов процедур. Это позволяет при изучении ОС эффективно использовать подход «от общего к частному», отделяя детали реализации от основополагающей идеи.
Общие понятия
Компьютера
Функции операционной системы автономного компьютера обычно группируются либо в соответствии с типами локальных ресурсов, которыми управляет ОС, либо в соответствии со специфическими задачами, применимыми ко всем ресурсам. Иногда такие группы функций называют подсистемами. Наиболее важными функциями ОС по управлению локальными ресурсами автономного компьютера являются:
- управление процессами (программами);
- управление памятью;
- управление файловой системой или файловыми системами;
- управление устройствами и операциями ввода/вывода;
- обеспечение защиты данных и администрирование данных;
- обеспечение интерфейса прикладного программирования;
- формирование интерфейса пользователя.
Варианты построения сетевых ОС
Существует несколько подходов к построению сетевых ОС.
Сетевые службы представлены в виде оболочки ОС (рис. 2.2, а). При таком подходе сетевая ОС представляет собой совокупность локальной ОС и надстроенной над ней сетевой оболочки. При этом в локальную ОС встраивается минимум сетевых функций, необходимых для работы сетевой оболочки, которая выполняет основные сетевые функции. В качестве примера можно указать продукты фирмы Microsoft: LAN Server и LAN Manager.
Сетевые службы глубоко встроены в ОС (рис. 2.2, б). Более эффективен подход, при котором сетевая ОС с самого начала проектируется для работы в сети. Сетевые функции у этих ОС глубоко встроены в основные модули системы, что обеспечивает их логическую стройность, простоту эксплуатации и модификации, а также высокую производительность. Важно, что при таком подходе отсутствует избыточность. Если все сетевые функции хорошо интегрированы, то все внутренние механизмы такой ОС могут быть оптимизированы для выполнения сетевых функций. Например, ОС Windows NT от Microsoft за счет встроенности сетевых средств обеспечивает более высокие показатели производительности и защищенности информации по сравнению с сетевой ОС LAN Manager той же фирмы (совместная разработка с IBM), являющейся надстройкой над локальной операционной системой OS/2.
В настоящее время сетевые функции встраиваются в ядро ОС, являясь ее неотъемлемой частью. Операционные системы получили средства для работы со всеми основными технологиями локальных (Ethernet, Fast Ethernet, Gigabit Ethernet, Token Ring, FDDI, ATM) и глобальных (Х.25, frame relay, ISDN, ATM) сетей, а также средства для создания составных сетей (IP, IPX, AppleTalk, RIP, OSPF, NLSP).
Сетевые службы поставляются в виде отдельных продуктов, которые, как правило, дополняют возможности сетевых ОС (рис. 2.2, в). Например, сервер удаленного управления WinFrame (компания Citrix) дополняет возможности сервера удаленного доступа Windows NT.
Рис. 2.2. Варианты построения сетевых ОС: а – сетевая оболочка,
б – встроенные службы, в – отдельные продукты
Принципы построения ОС
Каждая ОС является сложной и уникальной программной системой. Однако в их основу положены общие принципы перечисленные ниже.
· Принцип модульности. Предусматривает построение ОС из функционально законченных модулей. Выполнение модулей ОС не должно зависеть от их расположения в памяти. Перед размещением модуля в памяти производится его настройка под фактические адреса. Существенную роль при этом играют способы адресации процессора и алгоритм распределения памяти, реализованный в ОС.
· Принцип функциональной избирательности. В ОС выделяются наиболее важные и часто используемые модули, которые являются основой системы. Эту часть называют ядром ОС. Модули ядра выполняют такие базовые функции ОС, как управление процессами, памятью, устройствами ввода-вывода, системой прерываний. Модули ядра постоянно находятся в оперативной памяти и называются резидентными. Остальные системные модули хранятся на жестком диске и называются транзитными.
· Принцип генерируемости. Позволяет настроить ядро и остальные компоненты ОС исходя из конкретной конфигурации ЭВМ и круга решаемых задач. Процедура настройки называется инсталляцией.
· Принцип функциональной избыточности. Обеспечивает возможность выполнения одной и той же операции различными способами и средствами, что определяет универсальность и гибкость ОС.
· Принцип независимости программ от внешних устройств. Позволяет осуществлять обмен данными и управление внешними устройствами независимо от их характеристик. Это достигается за счет того, что связь программ с конкретными устройствами производится не на уровне трансляции программы, а в период ее исполнения. Например, программе, выполняющей обработку последовательного набора данных, безразлично, какой носитель будет использоваться для их хранения. Непосредственное управление обменом данных между системой и внешними устройствами выполняют специальные программы, называемые драйверами.
· Принцип совместимости. ОС должна иметь средства для выполнения прикладных программ, написанных для других ОС. Следует различать совместимость на уровне двоичных кодов и на уровне исходных текстов. Понятие совместимости включает также поддержку пользовательских интерфейсов других ОС.
· Принцип расширяемости (открытой и наращиваемой ОС). Аппаратные средства компьютера устаревают за несколько лет, а ОС может использоваться десятилетиями (например, ОС UNIX). Поэтому необходимо чтобы в ОС можно было легко внести изменения и дополнения, не нарушая ее целостности. Изменения ОС обычно заключаются в приобретении ею новых свойств, например поддержке новых типов внешних устройств или новых сетевых технологий. Расширяемость достигается за счет модульной структуры ОС. Взаимодействие модулей осуществляется только через функциональный интерфейс.
· Принцип переносимости (мобильности). Код ОС должен легко переноситься с процессора одного типа на процессор другого типа и с аппаратной платформы одного типа на аппаратную платформу другого типа. Аппаратные платформы различаются не только типом процессора, но и архитектурой всего компьютера. переносимые ОС имеют несколько вариантов реализации для разных платформ, т. е. являются многоплатформенными.
· Принцип надежности и отказоустойчивости. Система должна быть защищена как от внутренних, так и от внешних ошибок, сбоев и отказов. Ее действия должны быть всегда предсказуемыми, а приложения не должны иметь возможности наносить вред ОС. Важно, включает ли ОС программную поддержку аппаратных средств обеспечения отказоустойчивости, таких как дисковые массивы (RAID) или источники бесперебойного питания.
· Принцип максимальной производительности. ОС должна обладать настолько хорошим быстродействием и временем реакции, насколько это позволяет аппаратная платформа. На производительность ОС влияет архитектура ОС, многообразие функций, качество программирования кода, аппаратная платформа, на которой работает ОС.
· Принцип обеспечения безопасности вычислений. Операционная система должна защищать данные и другие ресурсы ВС от несанкционированного доступа, обладать средствами защиты ресурсов одних пользователей от других пользователей.
Виды программных модулей
Под модулем, в общем случае, понимают функционально законченный элемент программы, выполненный в соответствии с межмодульными интерфейсами. Модуль имеет средства сопряжения с подобными элементами данной или другой программы и предполагает легкий способ модификации и замены при наличии заданных интерфейсов. Разделение ОС на модули происходит именно по функциональному признаку.
Модули, в особенности системные, могут использоваться как программные ресурсы и могут быть разделены несколькими выполняющимися процессами. Различают привилегированные, непривилегированные и реентерабельные программные модули.
Привилегированные модули, работают в привилегированном режиме при отключенной системе прерываний. Т.е. никакие внешние события не могут прервать работу модуля, и он непрерывно выполняется от начала до конца. Такой модуль может выступать как попеременно разделяемый ресурс. Структура привилегированного модуля приведена на рис. 3.1.
Рис. 3.1. Структура привилегированного модуля
Непривилегированные модули – это обычные программные модули, которые могут быть прерваны во время своей работы. В общем случае их нельзя считать разделяемыми, поскольку после прерывания его в рамках одного вычислительного процесса и вызова его вновь из другого процесса, промежуточные результаты прерванных вычислений могут быть утеряны.
Реентерабельные (reenterable) – повторно прерываемые модули допускают повторное многократное прерывание своего исполнения и повторный запуск из других процессов.
На рис. 3.2 приведен пример использования реентерабельного модуля В процессами А и С. Опишем состояние процессов в каждый из моментов времени Т1-Т6:
Т1 – модуль А обращается к модулю В;
Т2 – при выполнении модуля В, поступил запрос на прерывание от внешнего устройства (модуля С). Приоритет у процесса С выше, чем у А и В, поэтому модуль В временно прекращает свою работу и управление передается модулю С для обработки поступившего запроса;
Т3 – во время работы модуль С обратился к модулю В;
Т4 – модуль С получает результат своего запроса от модуля В;
Т5 – завершается обслуживание внешнего устройства и управление передается модулю В. Далее модуль В завершает процесс, инициированный модулем А, используя значения переменных, сохраненных в момент прерывания Т2;
Т6 – модуль В завершает свою работу и результат передается модулю А.
| А |
| В |
| С |
| T1 |
| T2 |
| T3 |
| T4 |
| T5 |
| T6 |
| T |
| T |
| T |
Рис. 3.2. Использование реентерабельного модуля В процессами А и С
Принцип реентерабельности достигается за счет отделения кода программы от данных. При каждом обращении к модулю ему выделяется новая область памяти под данные. Выделение памяти может реализовано 2 способами: статическим и динамическим. Структура реентерабельного модуля при наиболее распространенном динамическом способе выделения памяти приведена на рис. 3.3.
Рис. 3.3. Структура реентерабельного модуля
В головной части реентерабельного модуля из системной привилегированной секции осуществляется запрос на получение в системной области памяти блока ячеек, необходимого для размещения всех текущих данных. При этом на вершину стека помещается указатель на начало области данных и ее объем. В этой системной области памяти располагаются текущие переменные реентерабельного модуля.
В конце привилегированной секции система прерываний включается, поэтому работа центральной (основной) части реентерабельного модуля может быть прервана. Если прерывания не было, то в третьей секции модуля осуществляется запрос на освобождение использованного блока системной памяти. Если же во время работы центральной секции возникает прерывание и к этому же реентерабельному модулю обращается другой процесс, то для нового процесса заказывается новый блок памяти и системной области памяти. На вершину стека записывается новый указатель. Возможно многократное повторное вхождение в реентерабельный модуль до тех пор, пока в соответствующей системной области памяти есть место.
При статическом способе выделения памяти для фиксированного числа процессов заранее резервируются области памяти для хранения переменных реентерабельных модулей: для каждого процесса – своя область памяти. Чаще всего в качестве таких процессов выступают процессы ввода/вывода и речь идет о реентерабельных драйверах, управляющих параллельно несколькими однотипными устройствами.
Кроме реентерабельных существуют еще и повторно входимые модули (reentrance). Повторно входимые модули состоят из привилегированных секций и повторное обращение к ним возможно только после завершения работы какой-нибудь из секций. Т.е. в таких модулях четко определены все допустимые точки входа для прерывания модуля. Повторно входимые модули встречаются чаще, чем реентерабельные.
Микроядерная архитектура ОС
В микроядерной архитектуре в привилегированном режиме работает только небольшая часть ОС, называемая микроядром.
В состав микроядра обычно входят машинно-зависимые модули и некоторые базовые модули, обеспечивающие управление процессами, устройствами ввода/вывода, прерываниями, виртуальной памятью и пересылкой сообщений, т.е. функции, которые трудно выполнить программам, работающим в режиме пользователя.
Все остальные более высокоуровневые функции ядра оформляются в виде специализированных компонентов ОС – серверов, работающих в пользовательском режиме. Основным назначением серверов является обслуживание запросов других приложений – клиентов (например, создание процесса, выделение памяти и т.д.). Роль посредника при взаимодействии выполняет микроядро.
Инициатором взаимодействия является клиент (рис. 3.9), который посылает запрос на обслуживание серверу. Непосредственная передача сообщений между приложениями невозможна, т. к. их адресные пространства изолированы друг от друга. Микроядро в привилегированном режиме имеет доступ к адресным пространствам всех приложений и поэтому может выступать в качестве посредника. Микроядро принимает сообщение клиента и передает его серверу. Сервер выполняет запрошенную операцию и передает результат клиенту (через микроядро) с помощью другого сообщения.
Рис. 3.9. Взаимодействие клиента и сервера
При таком построении ОС работает более медленно, чем ОС с классической архитектурой, т.к. чаще выполняются переходы между привилегированным режимом и пользовательским – четыре перехода вместо двух (рис. 3.10). Именно по этой причине микроядерный подход не получил широкого распространения.
Однако подход с использованием микроядра имеет и существенные достоинства:
- облегчает разработку качественного и надежного программного обеспечения;
- облегчает реализацию дополнительных требований к современным ОС (переносимость, надежность, расширяемость и т.д.);
- возможность вызова функций одного приложения из другого приложения;
- имеет механизмы поддержки распределенных вычислений.
Рис. 3.10. Смена режимов при выполнении системного вызова
Наиболее ярким представителем микроядерной ОС является ОСРВ QNX, микроядро которой в разных версиях занимало объем от 8К до 46К, т.е. могло целиком разместиться во внутреннем кэше процессора.
ОС Windows, построенную на идеологии клиент-сервер, трудно назвать микроядерной из-за размера её ядра.
Мультипрограммирование
Мультипрограммирование или многозадачность (multitasking) – это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько процессов (задач).
В первых ВС любая программа могла выполняться только после завершения предыдущей. Центральный процессор при этом выполнял программу и осуществлял управление операциями ввода/вывода. Поэтому пока выполнялся обмен данными с внешним устройством, процессор простаивал, дожидаясь завершения операции ввода/вывода. Машинное время в то время стоило очень дорого, поэтому было предложено организовать так называемый мультизадачный режим работы ВС. Суть заключалась в том, что пока один процесс ожидает завершения операции ввода/вывода, другая программа может быть поставлена на выполнение.
Мультипрограммирование позволяет повысить эффективность использования ресурсов ВС. При реализации мультизадачности существуют разные критерии эффективности:
- пропускная способность – количество задач, выполняемых ВС в единицу времени;
- удобство работы пользователей, заключающееся в их возможности работать в интерактивном режиме сразу с несколькими приложениями;
- реактивность системы – способность системы выдерживать заранее заданные интервалы времени между запуском процесса и получением результата.
В зависимости от выбранного критерия эффективности ОС делятся на системы пакетной обработки, системы разделения времени и системы реального времени. Некоторые операционные системы могут поддерживать одновременно несколько режимов, например, часть задач может выполняться в режиме пакетной обработки, а часть – в режиме реального времени или в режиме разделения времени.
Планирование процессов и потоков
Понятия «процесс» и «поток»
Для реализации многозадачности необходимо определить, каким образом ОС будет разделять между задачами процессор и другие ресурсы компьютера. С этой целью было введено понятие последовательного процесса или просто процесса.
Процесс – некая последовательность действий, выполняемая процессором с привлечением необходимых ресурсов (памяти, внешних устройств и т. д.). Процесс определяется программой, соответствующей данной задаче.
Программа представляет собой последовательность команд (поток команд). После запуска программы она загружается из внешней памяти компьютера в оперативную и ставится на выполнение процессором. Каждая команда занимает в памяти по конкретным физическим адресам одну или несколько ячеек памяти (байтов). Процессор последовательно выбирает команды из памяти и их выполняет. Для выборки команд из памяти используется специальный регистр, называемый программным счетчиком (program counter – PC), который содержит адрес текущей команды. Регистры процессора и переменные в оперативной памяти содержат текущие данные программы. Во время своей работы программа может использовать и другие ресурсы компьютера: открытые файлы, внешние устройства и т. д.
В литературе используется и такое определение процесса. Процесс (задача) – это выполнение отдельной программы с ее данными на последовательном процессоре.
Примеры процессов (задач): выполнение прикладных программ пользователей, утилит и других системных обрабатывающих программ, трансляция исходной программы, ее компоновка, исполнение. Причем трансляция какой-нибудь исходной программы является одним процессом, а трансляция следующей исходной программы – другим процессом, поскольку, хотя транслятор как объединение программных модулей здесь выступает как одна и та же программа, но данные, которые он обрабатывает, являются разными.
Процесс представляет собой обособленное явление, что необходимо для того, чтобы защитить один процесс от влияния другого, поскольку они совместно используют ресурсы компьютера и конкурируют друг с другом за обладание ими. ОС считает процессы совершенно не связанными друг с другом и берет на себя роль арбитра в спорах процессов за ресурсы. Каждый процесс имеет собственные (рис. 4.2): виртуальное адресное пространство; глобальные переменные; открытые файлы; внешние устройства; состояние; программный счетчик РС; регистры процессора; стек.
Рис. 4.2. Выполнение процесса на процессоре
Таким образом, процесс реализует две главные концепции: группирование ресурсов для программы и выполнение программы на процессоре.
Выделяют три основных состояния процесса:
Готовность – все необходимые ресурсы для процесса выделены, он готов выполняться, однако процессор занят выполнением другого процесса.
Выполнение – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором.
Ожидание – процесс заблокирован и не может выполняться до осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса.
В ходе жизненного цикла каждый процесс переходит из одного состояния в другое, в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе.
Рассмотренная трактовка термина «процесс» существовала долгое время, пока не возникла необходимость в организации параллельной обработки в рамках одного процесса (приложения, программы). Для реализации этой необходимости было введено новое понятие – поток или нить (thread).
В новой трактовке понятие процесс меняет смысл. В операционных системах, где существуют и процессы, и потоки, процесс рассматривается операционной системой как заявка на потребление всех видов ресурсов, кроме одного – процессорного времени. Этот последний важнейший ресурс распределяется операционной системой между потоками. Процессу ОС выделяет область памяти и другие ресурсы, которые совместно используются всеми его потоками. В простейшем случае процесс состоит только из одного потока. Поток получил свое название благодаря тому, что он представляет собой последовательность (поток) выполняемых команд программы. В рамках одного процесса может функционировать множество потоков, которые разделяют между собой (рис. 4.3): единое адресное пространство процесса; глобальные переменные; открытые файлы; внешние устройства и т.д.
При этом каждый из потоков имеет собственные: программный счетчик; регистры процессора; стек; состояние.
Например, при работе текстового редактора (один процесс) квазипараллельно выполняются три потока: ввод данных пользователя с клавиатуры, переформатирование документа, периодическое автосохранение документа.
Многопоточность в рамках одного процесса (приложения) позволяет повысить эффективность работы приложения. Например, в рассмотренном примере, при попытке записи на диск, если он занят другим процессом, ОС может не выполнять переключение на другой процесс, а поставить на выполнение другой поток выполняемого процесса.
Рис. 4.3. Выполнение потока текущего процесса на процессоре
Планирование и диспетчеризация потоков
На протяжении существования процесса выполнение его потоков может быть многократно прервано и продолжено. В системе, не поддерживающей потоки, все сказанное ниже о планировании и диспетчеризации относится к процессу в целом.
Переход от выполнения одного потока к другому осуществляется в результате планирования и диспетчеризации.
Планирование потоков включает в себя решение двух задач:
- определение момента времени для смены текущего активного потока;
- выбор для выполнения потока из очереди готовых потоков.
Существует множество различных алгоритмов планирования потоков, по-своему решающих каждую из приведенных выше задач. Планирование потоков осуществляется на основе информации, хранящейся в дескрипторах процессов и потоков. При планировании могут приниматься во внимание приоритеты потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращений к вводу-выводу и другие факторы. ОС планирует выполнение потоков независимо от того, принадлежат ли они одному или разным процессам. Так, например, после выполнения потока некоторого процесса ОС может выбрать для выполнения другой поток того же процесса или же назначить к выполнению поток другого процесса.
В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. ОС работает в условиях неопределенности – потоки и процессы появляются в случайные моменты времени и также непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси. Однако для выработки оптимального решения динамический планировщик требует значительного времени.
Статический тип планирования может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени. Статический планировщик принимает решения о планировании не во время работы системы, а заранее (off-line). Динамический и статический планировщики можно уподобить диспетчеру железной дороги, который пропускает поезда строго по предварительно составленному расписанию, и регулировщику на перекрестке автомобильных дорог, который решает, какую машину остановить, а какую пропустить, в зависимости от ситуации.
Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому потоку/процессу, когда и на какое время должен быть предоставлен процессор. После того как расписание готово, оно может использоваться операционной системой для переключения потоков и процессов. При этом накладные расходы ОС на исполнение расписания оказываются значительно меньшими, чем при динамическом планировании, и сводятся лишь к диспетчеризации потоков/процессов.
Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статистического) решения, то есть в переключении процессора с одного потока на другой. Диспетчеризация сводится к следующему:
- сохранение контекста текущего потока, который требуется сменить;
- загрузка контекста нового потока, выбранного в результате планирования;
- запуск нового потока на выполнение.
ОС выполняет планирование потоков, принимая во внимание их состояние. В мультипрограммной системе поток/процесс может находиться в одном из трех основных состояний: готовность, выполнение, ожидание. В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятым в данной операционной системе.
В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности – несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Каждый описатель потока, кроме всего прочего, содержит по крайней мере одну ссылку на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. В качестве примера на рис. 4.4 показана очередь готовых потоков, для которой запланированный порядок выполнения выглядит так: А, В, Е, D, С.
Рис. 4.4. Очередь потоков
Вытесняющие и невытесняющие алгоритмы планирования
Алгоритмы планирования можно разделить на невытесняющие или вытесняющие.
Невытесняющие (non-preemptive) алгоритмы основаны на том, что активный поток выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление диспетчеру ОС, для того, чтобы тот выбрал из очереди другой, готовый к выполнению поток;
Вытесняющие (preemptive) алгоритмы основаны на том, что решение о переключении процессора с выполнения одного протока на выполнение другого потока принимается диспетчером ОС, а не самим активным потоком (Windows NT, OS/2, UNIX).
Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации механизма диспетчеризации потоков.
В первом случае механизм диспетчеризации распределен между ОС и прикладными программами. Прикладная программа, получив управление от ОС, сама определяет момент завершения своей очередной итерации и передает управление ОС с помощью какого-либо системного вызова, а ОС формирует очереди задач и выбирает в соответствии с некоторым алгоритмом (например, с учетом приоритетов) следующую задачу на выполнение.
При этом управление системой теряется на произвольный период времени, который определяется приложением, а не пользователем. Пока приложение выполняет какую-либо задачу, пользователь не может переключиться на другую задачу. Поэтому разработчики приложений должны возлагать на себя функции планировщика, создавая свои программы так, чтобы они выполняли задачи небольшими частями. Например, программа перекодирования видеоданных может обработать часть видеофайла и вернуть управление ОС. После выполнения других задач ОС возвратит управление программе перекодирования, чтобы та обработала следующую часть видеофайла. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста.
При вытесняющей многозадачности механизм диспетчеризации потоков целиком сосредоточен в операционной системе, и программист пишет свое приложение, не заботясь о том, как оно будет выполняться параллельно с другими задачами. При этом ОС определяет момент снятия с выполнения активной задачи. В системах с вытесняющей многозадачностью зависание системы, как правило, исключено, т.к. диспетчер задач снимет зависшую задачу с выполнения.
Вытесняющие алгоритмы планирования могут быть основаны на квантовании, приоритетах и сочетании квантования и приоритетов.
Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому по<