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

При выполнении программ может случиться ситуация, когда одна или несколько задач не могут быть выполнены в течение значительного времени из-за высокой нагрузки в вычислительной системе. Введение механизма динамических приоритетов позволяет реализовать быстрое выполнение коротких задач и гарантировать выполнение любых запросов. Эта дисциплина используется в ОС UNIX.
Каждый процесс имеет два атрибута приоритета, с учетом которого распределяется процессорное время между исполняющимися задачами:
- текущий приоритет, на основе которого осуществляется планирование;
- заказанный относительный приоритет (nice number).
Более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования.
Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (высокий приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет (0 – 65), чем в режиме ядра (66 – 95, системный диапазон). Приоритеты в диапазоне 96 – 127 относятся к процессам с фиксированным приоритетом.
Процессу, ожидающему недоступный в данный момент ресурс, система присваивает приоритет сна (sleep) из диапазона системных приоритетов и связанное с событием, вызвавшим это состояние. Когда процесс пробуждается, ему присваивается приоритет, равный приоритету сна, который находится в системной области, поэтому вероятность выбора такого процесса на выполнение велика. Такой подход позволяет быстро завершить системный вызов.
После завершения системного вызова восстанавливается приоритет режима задачи, сохраненный перед выполнением системного вызова. Это может привести к снижению приоритета и переключению контекста.
Для принятия решения о выборе следующего запускаемого процесса планировщику необходима информация об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний по таймеру по каждому тику таймера. Когда процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.
Каждую секунду процессор пересчитывает приоритеты процессов, готовых к выполнению, что приводит к перемещению процессов в более приоритетные очереди и повышает вероятность их последующего запуска.
Данный алгоритм планирования обеспечивает:
- интересы низкоприоритетных процессов, так как в результате длительного ожидания их приоритет и вероятность выполнения увеличиваются;
- более вероятный выбор интерактивных процессов по сравнению с вычислительными.

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

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

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

Различают системы «мягкого» и «жесткого» реального времени. Различия зависят от требований к системе:
- в «жесткой» системе нарушение временных ограничений не допустимо;
- в «мягкой» системе нарушение временных ограничений нежелательно.

Основные требования к операционной системе реального времени:
1) мультипрограммность и многозадачность (многопоточность). ОС должна активно использовать прерывания для диспетчеризации. Максимальное время выполнения того или иного действия должно быть известно заранее и соответствовать требованиям приложения;

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

3) наследование приоритетов. ОСРВ должна допускать наследование приоритета, то есть повышение уровня приоритета потока до уровня приоритета потока, который его вызывает. Наследование означает, что блокирующий ресурс поток наследует приоритет потока, который он блокирует;

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

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

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

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

Однозадачность – один процесс должен завершиться прежде, чем может начаться другой.

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

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

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

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

Приоритет каждого потока определяется по:
- классу приоритета процесса, которому принадлежит поток;
- уровню приоритета потока внутри класса приоритета его процесса.

Уровни приоритетов Windows разделены на два класса:
- реального времени (приоритеты от 16 до 31) используются для выполнения основных функций ОС и обычно не применяются для приложений;
- переменного приоритета (от 0 до 15) – определяет процессорный приоритет приложения; приоритет 0 – для бесстраничного системного потока.

Базовые уровни приоритетов:
- низкий – запускает приложение с уровнем приоритета 4;
- обычный – запускает приложение с уровнем приоритета 7;
- высокий – запускает приложение с уровнем приоритета 13;
- реального времени – запускает приложение с уровнем приоритета 24.

В Windows каждый процесс имеет свое адресное пространство до 4 Гб памяти (не физическое ОЗУ). Физическая память ограничена системными ресурсами: ОЗУ и дисковым пространством. Windows выделяет приложению 2 Гб памяти, а остальные 2 Гб резервируются для нужд ядра.

Если объем ОЗУ меньше, чем 4 Гб, то Windows использует механизм виртуальной памяти: когда объем ОЗУ будет исчерпан, часть содержимого физической памяти переносится на жесткий диск. Этот механизм называется подкачкой.

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

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

Программист обращается к памяти с помощью некоторого набора логических имен. Имена переменных и входных точек модулей составляют область имен.
Физическая память представляет собой множество ячеек, которые пронумерованы, к каждой ячейке можно обратиться, указав ее порядковый номер (адрес). Количество ячеек физической памяти ограничено и фиксировано.
Системное программное обеспечение должно связать каждое указанное пользователем имя с физической ячейкой памяти, т.е. осуществить отображение пространства имен на физическую память компьютера. Это происходит в два этапа;
- посредством системы программирования;
- посредством операционной системы (с помощью специальных программных модулей управления памятью и использования соответствующих аппаратных средств вычислительной системы).
Между этими этапами обращение к памяти имеет форму виртуального или логического адреса. Множество всех допустимых значений виртуального адреса для некоторой программы определяет ее виртуальное адресное пространство или виртуальную память.
Виртуальное адресное пространство зависит от:
- архитектуры процессора;
- системы программирования.
Виртуальное адресное пространство не зависит от:
- объема реальной физической памяти, установленной в компьютере.
Адреса команд и переменных в готовой машинной программе, подготовленной к выполнению системой программирования, как раз и являются виртуальными адресами.
В результате работы системы программирования полученные виртуальные адреса могут иметь как двоичную, так и символьно-двоичную форму, т.е. привязка к физическим адресам производится на этапе загрузки программы в память перед ее непосредственным выполнением.
Если система программирования генерирует абсолютную двоичную программу, то виртуальные адреса точно соответствуют физическим. Часть программ любой ОС должны быть абсолютными двоичными программами, размещаться по фиксированным физическим адресам и обеспечивать размещение остальных программ на различных физических адресах.
В простейших компьютерных системах используется тождественность виртуального адресного пространства исходному пространству имен. Отображение выполняется самой ОС, которая во время исполнения использует таблицу символьных имен. Данная схема используется в трансляторах, в которых стадии исполнения и трансляции практически неразличимы.
В простейшем случае транслятор-компилятор генерирует относительные адреса, которые являются виртуальными и впоследствии настраиваются на один из непрерывных разделов. Второе отображение осуществляется перемещающим загрузчиком. После загрузки виртуальный адрес теряется, и доступ выполняется непосредственно к физическим адресам.
Термин виртуальная память фактически относится к системам, которые сохраняют виртуальные адреса во время исполнения. Второе отображение осуществляется в процессе выполнения задачи, поэтому адреса физических ячеек могут изменяться.
Простое непрерывное распределение – это самая простая схема, согласно которой вся память условно может быть разделена на три части:
- область, занимаемая операционной системой;
- область, в которой размещается исполняемая задача;
- незанятая ничем (свободная) область памяти.
Эта схема предполагает, что ОС не поддерживает мультипрограммирования, поэтому не возникает проблемы распределения памяти между несколькими задачами. Чтобы предоставить задачам максимальный объем памяти, ОС строится таким образом, чтобы постоянно в памяти располагалась только самая нужная ее часть – ядро ОС, остальные модули загружаются при необходимости.
Эта схема влечет два вида потерь:
- потери процессорного времени из-за простоя в связи с вводом/выводом;
- потери самой оперативной памяти, так как она не всегда используется полностью.
Если программа должна будет использовать логическое (и виртуальное) адресное пространство, которое превышает свободную область памяти, или больше всей памяти компьютера, то используется распределение с перекрытием, оверлейная структура. Этот метод предполагает, что вся программа может быть разбита на части – сегменты. Каждая оверлейная программа имеет одну главную часть (main) и несколько сегментов (segment), причем, в памяти одновременно могут находиться только главная часть и один или несколько сегментов.

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

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

Дата добавления: 2014-10-15