Управление задачами

Размещено на http://www.allbest.ru/

Индивидуальная работа

на тему: «Управление задачами»

по дисциплине «Системы реального времени»

Оглавление

• Введение
• 1. Работа планировщика
• 2. Планирование в ОС РВ
• 3. Выбор алгоритма планирования
• 4. Классы алгоритмов планирования
• 5. Планирование задач в мультипроцессорных (распределенных) системах
• Выводы
• Используемая литература
• Введение
• Ядро ОСРВ обеспечивает функционирование промежуточного абстрактного уровня ОС, который скрывает от прикладного ПО специфику технического устройства процессора (нескольких процессоров) и связанного с ним аппаратного обеспечения
• Основные сервисы
• Указанный абстрактный уровень предоставляет для прикладного ПО пять основных категорий сервисов.
• · Управление задачами. Самая главная группа сервисов. Позволяет разработчикам приложений проектировать программные продукты в виде наборов отдельных программных фрагментов, каждый из которых может относиться к своей тематической области, выполнять отдельную функцию и иметь свой собственный квант времени, отведенный ему для работы. Каждый такой фрагмент называется задачей. Сервисы в рассматриваемой группе обладают способностью запускать задачи и присваивать им приоритеты. Основной сервис здесь -- планировщик задач. Он осуществляет контроль за выполнением текущих задач, запускает новые в соответствующий период времени и следит за режимом их работы.
• · Динамическое распределение памяти. Многие (но не все) ядра ОСРВ поддерживают эту группу сервисов. Она позволяет задачам заимствовать области оперативной памяти для временного использования в работе приложений. Часто эти области впоследствии переходят от задачи к задаче, и посредством этого осуществляется быстрая передача большого количества данных между ними. Некоторые очень малые по размеру ядра ОСРВ, которые предполагается использовать в аппаратных средах с строгим ограничением на объём используемой памяти, не поддерживают сервисы динамического распределения памяти.
• · Управление таймерами. Так как встроенные системы предъявляют жёсткие требования к временным рамкам выполнения задач, в состав ядра ОСРВ включается группа сервисов, обеспечивающих управление таймерами для отслеживания лимита времени, в течение которого должна выполняться задача. Эти сервисы измеряют и задают различные промежутки времени (от 1 мкс и выше), генерируют прерывания по истечении временных интервалов и создают разовые и циклические будильники.
• · Взаимодействие между задачами и синхронизация. Сервисы данной группы позволяют задачам обмениваться информацией и обеспечивают её сохранность. Они так же дают возможность программным фрагментам согласовывать между собой свою работу для повышения эффективности. Если исключить эти сервисы из состава ядра ОСРВ, то задачи начнут обмениваться искаженной информацией и могут стать помехой для работы соседних задач.
• · Контроль устройства ввода/вывода. Сервисы этой группы обеспечивают работу единого программного интерфейса, взаимодействующего со всем множеством драйверов устройств, которые являются типичными для большинства встроенных систем.

1. Работа планировщика

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

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

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

Каждый раз, когда планировщик задач получает сигнал о наступлении некоторого внешнего события (триггер), причина которого может быть как аппаратная, так и программная, он действует по следующему алгоритму.[8]

1. Определяет, должна ли текущая выполняемая задача продолжать работать.

2. Устанавливает, какая задача должна запускаться следующей.

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

4. Устанавливает контекст для следующей задачи.

5. Запускает эту задачу.

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

Выполнение задачи

В обычных ОСРВ задача может находиться в 3-х возможных состояниях:

1. Задача выполняется;

2. Задача готова к выполнению;

3. Задача заблокирована.

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

Основная функция администратора ОСРВ заключается в составлении такого планировщика задач.

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

Алгоритмы планирования

В настоящее время для решения задачи эффективного планирования в ОСРВ наиболее интенсивно развиваются два подхода.

· Статические алгоритмы планирования (RMS, Rate Monotonic Scheduling). Используют приоритетное вытесняющее планирование. Приоритет присваивается каждой задаче до того, как она начала выполняться. Преимущество отдается задачам с самыми короткими периодами выполнения.

· Динамические алгоритмы планирования (EDF, Earliest Deadline First Scheduling). Приоритет задачам присваивается динамически, причем предпочтение отдается задачам с наиболее ранним предельным временем начала (завершения) выполнения.

При больших загрузках системы EDF более эффективен, нежели RMS.

2. Планирование в ОС РВ

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

Используемые в ОС общего назначения алгоритмы круговой диспетчеризации неприменимы в чистом виде в ОС РВ. Рассмотрим основные виды планирования применительно к задачам реального времени.

- Вытесняющее планирование с использованием круговой стратегии

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

- Невытесняющее планирование на основе приоритетов

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

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

Основной недостаток приведенных методик - непрерывный квант времени, в течение которого процессором владеет только один процесс.

Планировщики ОС РВ должны иметь возможность сменить процесс до истечения “time slice”, если в этом возникла необходимость, т.е. использовать вытесняющее планирование. Это могут быть две следующие методики:

- Вытесняющее планирование на основе приоритетов с точками вытеснения

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

- Вытесняющее планирование на основе приоритетов с немедленным вытеснением

Используется в приложениях Hard RT. Заключается в том, что ОС отвечает на прерывание практически немедленно, если только она не выполняет код критического раздела, который не может быть прерван. Задержки планирования при этом снижаются до 100 микросекунд и менее.

3. Выбор алгоритма планирования

При проектировании RTS выбор приемлемого алгоритма планирования может зависеть от нескольких факторов, а именно:

· количество процессоров в системе,

· гомогенность (или гетерогенность) задач,

· отношения предшествования между заданиями,

· метод синхронизации заданий.

Также на выбор алгоритма планирования влияют программно-зависимые характеристики задания. К таким характеристикам можно отнести:

· Время готовности: Время, когда задание становится доступным для выполнения.

· Предельное время начала выполнения: Время, когда должно начаться выполнение задания.

· Предельное время завершения выполнения: Время, когда задание должно быть полностью завершено.

· Время выполнения: Время, требующееся заданию для полного выполнения.

· Приоритет: Мера относительной важности задания.

· Структура подзадач: Задача может быть разбита на обязательные и необязательные подзадачи.

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

Также, задания могут быть прерываемыми и непрерываемыми . Выполнение прерываемого задания может быть прервано другим и продолжено позднее; непрерываемые задания выполняются до завершения и не могут быть прерваны.

Виды алгоритмов планирования

· Статические,

· Динамические.

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

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

На базе этих основных типов сформированы классы алгоритмов планирования.

4. Классы алгоритмов планирования

Статическое планирование с использованием таблиц

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

Статическое вытесняющее планирование на основе приоритетов

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

Динамическое планирование на основе расписания

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

Динамическое планирование наилучшего результата

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

Планирование с предельными сроками

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

Виды задач

· Периодические;

· Апериодические;

· Спорадические.

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

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

Спорадические задачи - Апериодические задачи, характеризованные к жестким крайним срокам. Например, задачи в критическом положении запрашивающие некоторые действия от оператора.

Планирование периодических задач

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

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

Эти подходы вели к развитию вытесняющих политик планирования:

- Монотонизирующая норма (RM),

- Самый ранний крайний срок сначала (EDF),

- Наименьшее время cначала (LSTF)

Частотно-монотонное планирование

(Rate Monotonic Scheduling - RMS)

RMS политика назначает приоритет каждой задачи согласно следующему принципу: чем короче период задачи, тем выше её приоритет.

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

Для пояснения рассмотрим параметры периодических заданий.

· Период задания Т представляет собой интервал времени между поступлениями двух последовательных заданий одного типа.

· Частота заданий (измеряемая в Hz) 1/Т представляет собой величину, обратную периоду (в секундах). Например, задание с периодом 50 мс имеет частоту 20 Гц. Обычно окончание периода задания является жестким предельным сроком завершения задания, хотя некоторые задания могут иметь и более ранние предельные сроки.

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

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

U = С/Т

Например, если задание имеет период 80 мс и время выполнения 55 мс, то загруженность им процессора составляет 55/80 = 0.6875. В RMS заданием с наивысшим приоритетом является задание с наименьшим периодом; вторым по приоритетности является задание со вторым по краткости периодом и т.д. Соответственно, в случае готовности для выполнения нескольких заданий первым обслуживается задание с наименьшим периодом.

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

рис 4.1. Множество заданий в методе RMS

Метод RMS широко распространен и используется во многих промышленных приложениях. Это поясняется следующими причинами:

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

(2.) При использовании RMS проще обеспечить стабильность.

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

Вытесняющие политики планирования:

EDF (Earliest Deadline - First) и LSTF (Least Slack Time - First) политика работают с динамическими приоритетами.

В политике EDF, чем меньше крайний срок задачи, тем выше приоритет назначается на эту задачу.

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

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

Планирование апериодических задач

Фоновая политика

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

Политика выбора

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

Политика сохранения ресурса:

- Обмен Приоритета (Priority Exchange - PE);

- Деферабельный Сервер (DS).

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

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

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

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

Напротив, в PE политике, сервер обменивает приоритет с самым высоким приоритетом периодической задачи, если никакие запросы не происходят в начале периода сервера.

Политика Спорадического Сервера (SS):

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

Примеры реализации планирования в ОСРВ

ОСРВ QNX:

- Количество уровней приоритетов задач -32;

- Планирование задач - FIFO, RR, адаптивное.

ОСРВ OS-9:

- Количество уровней приоритетов задач -65532;

- Планирование задач - FIFO, RR, адаптивное.

ОСРВ VxWorks:

- Количество задач - неограниченно;

- Количество уровней приоритетов задач - 256;

- Планирование задач - вытеснение по приоритетам, RR .

5. Планирование задач в мультипроцессорных (распределенных) системах

В этих системах планировщик обычно разбивается на две отдельные компоненты:

(1) диспетчер процессоров,

(2) местный планировщик.

Диспетчер ответственен за назначение задач на распределенные процессоры системы.

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

Выводы

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

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

На модуль планирования в операционных системах реального времени возлагается ответственная задача - организовать очередь задач, которые смогут выполниться в установленные сроки. Стратегии планирования из “универсальных” ОС не могут этого гарантировать.

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

Были рассмотрены факторы, влияющие на выбор алгоритма планирования.

Перечислены основные классы алгоритмов планирования.

Рассмотрены особенности планирования в зависимости от её вида задачи: планирование периодических, апериодических, спорадических задач.

Приведены примеры планирования в ОС реального времени.

Используемая литература:

1. http://ru.wikipedia.org/wiki/Операционная_система_реального_времени

2. http://ru.wikipedia.org/wiki Диспетчер_операционной_системы

3. Столлингс В. Операционные системы - М: Издательский дом “Вильямс”, 2006.

Размещено на Allbest.ru