- •Операционные системы
- •Введение
- •Глава 1 понятие и эволюция операционных систем
- •1.1. Определение операционной системы
- •1. 2. История развития операционных систем
- •1.3. Основные характеристики ос
- •1.4. Принципы построения ос
- •Глава 2 архитектура вычислительной системы
- •2.1. Особенности методов построения
- •Глава 3 управление процессами
- •3.1. Операции над процессами
- •3.2. Основная концепция обработки прерываний
- •3.3. Переключение контекста в ec эвм
- •Глава 4 управление асинхронными параллельными процессами
- •If q(s) очередь не пуста?
- •Глава 5 управление основной памятью
- •Глава 6 управление виртуальной памятью
- •6.1. Концепция виртуальной памяти
- •1.Признак обращения 0 - было
- •2.Признак модификации записи 0 - неизменен.
- •6.2. Динамическая страничная организация
- •6.3. Сегментная организация виртуальной памяти
- •6.4. Комбинированная странично-сегментная организация памяти
- •6.5. Двухуровневая страничная организация
- •Глава 7 многозадачность и многонитевость
- •7.1. Понятие многонитевости
- •7.2. Реализация многонитевой обработки в windows 95
- •7.3. Подкачка страниц памяти
- •Глава 8 управление процессорами и заданиями в однопроцессорном вычислительном комплексе
- •Глава 9 управление процессорами и заданиями в мультипроцессорных вычислительных комплексах.
- •9.1. Решение фирмы Сompaq
- •Глава 10 управление периферийными устройствами
- •10.1. Физическая организация периферийных устройств
- •10.2. Организация программного обеспечения ввода-вывода
- •Глава 11 подсистема управления данными
- •11.1. Система управления файлами
- •11.2. Способы доступа и организации файлов
- •11.3. Управление внешней памятью
- •11.4. Способы распределения памяти на диске
- •Глава 12 Современные концепции и технологии проектирования операционных систем
- •12.1. Требования, предъявляемые к ос 90-х годов
- •12.2. Тенденции в структурном построении ос
- •Глава 13 История и общая характеристика семейства операционных систем unix
- •Глава 14 История Windows nt
- •14.1. Версии Windows nt
- •14.2. Структура: nt executive и защищенные подсистемы
- •14.3 Области использования Windows nt
- •Литература:
Глава 8 управление процессорами и заданиями в однопроцессорном вычислительном комплексе
Подсистемы управления процессорами и заданиями в ОС выполняют сходные функции: планирование загрузки процессоров и планирование загрузки вычислительных комплексов, имеют сходные механизмы планирования, работающие на разных уровнях - процессов и заданий пользователя соответственно.
В однопроцессорной ЭВМ подсистема управления процессорами выполняет единственную функцию - диспетчирования процессов, то есть планирует загрузку ЦП.
Подсистема управления заданиями управляет прохождением заданий в ВС и выполняет следующие функции:
1.Предоставление языковых средств управления работами в вычислительной системе (Job Control Language (JCL) в ОС ЕС ЭВМ, Shell в UNIX).
2.Ввод и интерпретация заданий/команд.
3.Выделение и освобождение необходимых ресурсов.
4.Планирование заданий на выполнение.
5.Сбор и предоставление информации о состоянии заданий.
В однопроцессорном вычислительном комплексе существует три основных уровня планирования:
1.Планирование на верхнем уровне или планирование заданий.
На этом уровне осуществляется выбор заданий пользователем для выполнения и их запуск. Выбранные задания становятся готовыми процессами. Эту работу выполняет системный компонент - планировщик заданий.
2.Планирование на нижнем уровне или диспетчирование процессов.
Здесь осуществляется выбор готового процесса для выполнения, то есть предоставление ему ЦП. Выбранный процесс становится активным. Эту работу выполняет системный компонент - диспетчер.
3.Планирование на промежуточном уровне.
На данном уровне определяется, каким процессам будет разрешено состязаться за захват ЦП, то есть быть готовыми, и какие процессы будут кратковременно приостановлены (задержаны) для оптимизации загрузки системы. Промежуточное планирование управляет текущей производительностью вычислительной системы.
В соответствии с тремя уровнями планирования, из которых два обязательны, существует двух и трехуровневые системы планирования.
Типичная двухуровневая система планирования представлена на рис.8.1.
Рис.8.1. Двухуровневая процедура планирования
Двухуровневая процедура вводится в системах с ограниченным мультипрограммированием, что определяется ограниченными ресурсами и производительностью вычислительной системы. Это основная схема для ВС с реальной ОП без поддержки систем реального времени (СРВ).
В вычислительных системах с ВП, допускающих неограниченный уровень мультипрограммирования и СРВ, требующих высокой реактивности системы, используется трехуровневая система планирования, представленная на рис.8.2.
Рис. 8.2. Трехуровневая система планирования
Эффективное планирование заданий и процессов является сложной проблемой, поскольку должно учитываться много противоречивых требований, таких, как:
-
cправедливость;
-
максимальная пропускная способность;
-
приемлемое время ответа для максимального числа интерактивных пользователей;
-
предсказуемость (задание должно выполняться примерно за одно время независимо от загрузки вычислительной системы);
-
минимум накладных расходов на выполнение планирования;
-
сбалансированность использования ресурсов;
-
исключение бесконечного откладывания;
-
учет приоритетов;
-
отдавать предпочтение процессам, занимающим ключевые ресурсы;
-
плавная деградация при увеличении нагрузок.
Для того чтобы реализовать перечисленные требования, механизм планирования должен знать и учитывать следующие факторы:
-
является ли процесс обменным (активно использующим операции ввода/вывода) или вычислительным (активно использующим процессор);
-
является ли процесс пакетным или диалоговым;
-
уровень реактивности интерактивного процесса;
-
приоритетность процесса;
-
частоту прерываний по отсутствию нужной страницы;
-
частоту прерывания с низкого приоритета на высокий;
-
длительность периода ожиданий ЦП процесса;
-
суммарное использование времени ЦП и оценочное время, необходимое для завершения.
Существует множество различных алгоритмов планирования процессов, преследующих различные цели и обеспечивающих различное качество мультипрограммирования. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на приоритетах, и алгоритмы, основанные на квантовании.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если::
1)процесс завершился и покинул систему;
2)произошла ошибка;
3)процесс перешел в состояние ОЖИДАНИЕ4
4)исчерпан квант процессорного времени, отведенный данному процессу.
Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение, в соответствии с определенным правилом, выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.
Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По - разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO).
Многие современные системы планирования основываются на системе приоритетов, которая воплощается в соответствующих дисциплинах планирования. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии.
Приоритеты подразделяются на статические, назначаемые извне системы администрацией ВЦ, и динамические, присваиваемые системой автоматически в соответствии с поведением, потребностями в ресурсах и прочими характеристиками процессов.
Начальные значения динамических приоритетов обычно устанавливаются на основе статического, но действуют в течение короткого времени. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.
В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.
Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.
Для установления значений приоритетов заданий и процессов используются следующие дисциплины планирования и их различные комбинации:
-
Планирование по сроку завершения, гарантирующее выполнение задания в назначенное время. Это сложная проблема в мультипрограммных системах, поскольку пользователь должен точно указать все требуемые ресурсы. Необходимо активное управление ресурсами, что связано с высокими накладными расходами. Недостаток: несправедливо к другим пользователям (протекционизм).
-
Планирование по принципу FIFO, где ЦП предоставляется процессам в порядке готовности, и они выполняются до завершения или блокировки. Это самая простая дисциплина планирования - фактически без переключения ЦП. Формально - справедливый принцип, но фактически не справедлив, так как длинные задания заставляют ждать короткие. Менее важные - заставляют ждать более важные. Характеризуется небольшим колебанием времени выполнения и большей предсказуемостью, нежели другие дисциплины. Используется только в пакетных системах, обычно в комбинации с другими дисциплинами и не гарантирует реактивности системы.
-
Циклическое, или круговое планирование, где каждому готовому процессу в цикле представляется квант времени. По истечении кванта времени процесс переходит в конец очереди готовых процессов. При блокировке квант теряется. Эффективно для СРВ, так как гарантирует приемлемое время ответа для всех интерактивных пользователей. Основная проблема выбора - оптимальный размер кванта. Стараются выбрать такой размер, чтобы большинство рядовых запросов обслуживалось за один квант.
-
Планирование по принципу - "кратчайшее задание - первым" или "по наименьшему оставшемуся времени выполнения". Максимальный приоритет назначается процессу либо заданию с минимальным оценочным временем до завершения. Недостаток: время ожидания на большие задания растет; большие издержки на регистрацию истекшего времени обслуживания. Достоинство: сокращение очередей заданий и ожидающих процессов; стремится к минимальному времени ожиданий для заданий.
-
Планирование по времени нахождения в системе, в которой приоритет есть функция времени обслуживания и времени ожидания.
Приоритет =
Приоритет отдает меньшее предпочтение коротким заданиям и без предубеждения относится к длинным. Чем реже процесс получает ЦП, тем выше его приоритет. Задания с вводом/выводом повышают приоритет.
-
Сеть многоуровневых очередей с обратными связями (рис.8.3), которая имеет следующие достоинства:
-
определяет характер процессов и разделяет на соответствующие категории;
-
отдает предпочтение коротким процессам;
-
отдает предпочтение обменным процессам с хорошим коэффициентом использования устройств ввода/вывода. Это наиболее совершенный и сложный механизм планирования.
Рис. 8.3. Сеть многоуровневых очередей
Сеть представляет собой упорядоченную структуру очередей готовых процессов, работающих с различными дисциплинами обслуживания. Каждый процесс входит в сеть очередей с конца верхней очереди и перемещается по FIFO пока не получит ЦП. Процесс выполняется. Если в течение кванта процесс запросил выполнение операции ввода/вывода, то он после завершения операции будет установлен в очередь готовых процессов текущего уровня. Если в течение выделенного кванта времени процесс не завершился, то он устанавливется в очередь готовых процессов следующего уровня, у которого понижен приоритет и увеличен квант времени. Таким образом, чем больше время работы процесса, тем больший квант времени выделяется, но меньше приоритет, что приводит к получению ЦП реже, но на более длительный период.
Таким образом, сеть многоуровневых очередей - это адаптивный механизм планирования, который реагирует на изменение поведения системы.
В ОС OS/2, UNIX приоритеты устанавливаются с помощью класса приоритета и уровня приоритета в классе. Есть три класса приоритета и 32 различных уровня приоритета для класса.
Существует три класса приоритета:
критический или высокий - для программ управления процессом или связью с другими компьютерами;
обыкновенный - для большинства программ пользователя;
запасной или низкий - задачи и процессы из этого класса выполняются, если в очереди нет критических или обыкновенных задач.