Теоретические основы операционных систем рв

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

- неактивный (ожидание). Задача создана и инициализирована, однако не готова для выполнения. То есть в этом состоянии процесс не имеет право на выполнение.

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

- выполнение. В этом состояние выполняются команды процесса.

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

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

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

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

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

Процесс планирования

Планирование является одной из основных функций ОС. В целях обеспечения требования функционирования программ в системах РВ необходимы стратегия для упорядочивания используемых системных ресурсов и механизм для использования наихудшей производительности при применении конкретной политик планирования. Есть два основных класса политики планирования: предварительное планирования и планирование во время выполнения процесса. Цели обоих типов планирования является учет временных ограничений.

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

Характеристики задачи фактической рабочей нагрузки

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

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

2. Время разблокирования (время входа задачи в систему), r_ij – время разблокирования экземпляра задачи.

3. Фаза φ – время разблокирования первого экземпляра задачи.

4. Время отклика – интервал времени между активацией задачи и ее завершения.

5. Абсолютный предел d_i – интервал времени, до которого задание должно быть завершено.

6. Относительный предел D_i – максимально допустимое время ответа задачи.

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

8. Период p_i – минимальный интервал времени между разблокировки последовательности задач.

9. Время выполнение e_i – максимальное время, которое требуется для завершения задачи i при условии, что она выполняется только одна и ей доступны все необходимые ресурсы.

Математически некоторые из приведённых параметров связаны следующим образом (слайд 3).

Типичная модель задач

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

Циклическая исполняющая система

Использование циклических исполняющих систем (ЦИС) достаточно распространено потому что такие системы просты и формируют полностью предсказуемый план представления. ЦИС могут рассматривается как планировщики, который заранее обусловлено чередуют и последовательно планируют выполнение периодических задач в соответствии с графиками. В общих чертах ЦИС – это таблица вызова процедур, где каждая задача является процедурой с единственным циклом do. При использовании подхода ЦИС решения по планированию принимаются периодически, а не в произвольный момент времени. Временный интервалы планирования момента принятия решений называются кадрами (фреймами) или малыми (второстепенными) циклами. Каждый кадр имеет продолжительность f называемое длинной кадра. Основной цикл есть минимальное время необходимое для выполнения задач, назначенных процессору с учетом предельных сроков и периодов для этих процессов. Основной цикл или гиперпериод есть наименьшее общее кратное всех периодов. Так как решения по планированию принимаются только в начале каждого кадра, то для каждого кадра отсутствует его прерывание при выполнении. Фаза каждой периодической задачи есть неотрицательное число кратное размеру кадра. Рис. 10.1.

Кадры должны иметь достаточную длину чтобы каждая задача могла начаться и закончиться в одном кадре. Это означает что размер кадра f должен быть больше чем время выполнения e_i каждой задачи.

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

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

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

Фиксированное приоритетное планирование с монотонной частотой

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

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

Пример использования алгоритма МЧ: таблица задает список задач для иллюстрации планирования МЧ.

Рис. 10.2 отображает МЧ планирования для определенного списка задач. Все задачи запускаются во времени равным 0. Поскольку у тау1 наименший период, то эта задача с наивысшим приоритетом и она рланируется первой. При время 4 запускается второй экземпляр тау1 и вытесняет тау3 так как у нее менший приоритет. Формула загрузки процессора:

Основные результаты применения политики МЧ

С практической точки зоения в случаи со статическими приоритетами важно знать при какаих условиях существует приемлемый план. Из следующей теоремы вытекает использование планирования АМЧ. Предполагается что относительный придельный срок завершения каждой задачи равен ее периоду. Теорема (граничное значение АМЧ): любое множество из периодических задач может быть подвержено МЧ планированию если загрузка процессора U не более чем m*(2^1/n - 1). Это оначает что где бы не находилась U на или ниже заданной границы загрузки план может быть составлен с использованием АМЧ.

Заметим что предел нагрузки при использовании АМЧ является достаточным но необходимым. На практике возможно построить список задач с общей наргузкой процессора больше придела АМЧ. При этом список может быть АМЧ планируемым. Многие сложные СРВ без проблем строятся с использованием более 80% нагрузки процессора.