45446

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

Доклад

Информатика, кибернетика и программирование

Планирование задач. Общие принципы планирования задач. Алгоритмы планирования периодических задач. Алгоритмы планирования спорадических и апериодических задач Планировщик заданий.

Русский

2013-11-17

156.5 KB

42 чел.

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

Задачи СРВ.

СРВ представляют собой набор взаимодействующих между собой заданий или задач.

Задача является одиночным объектом, управление которым осуществляется оболочкой СРВ.

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

Задачи классифицируют по двум категориям:

  1.  Требование по времени функционирования.
  2.  Вид или тип функционирования.

Требование по времени функционирования:

  •  задачи в ЖРВ (жестком реальном времени)
    •  задачи в МРВ (мягком реальном времени)
    •  задачи в «нереальном времени»

Задача ЖРВ – это задача, чье логически правильное  или своевременное исполнение считается критическим для действия всей системы.

Предельный срок исполнения называется жестким сроком исполнения. Неспособность удовлетворять этому требованию ведет к отказу всей системы.

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

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

Вид или тип функционирования:

  •  периодические задачи
  •  апериодические задачи (асинхронные)
  •  спорадические задачи
  •  фоновые задачи
  •  аппендикс
  •  

Периодические задачи

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

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

Рис.3.

Тц – время цикла (единица измерения в СРВ). Цикл делится на несколько групп (метки).

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

Апериодические задачи

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

Функционирование осуществляется только в том случае, если периодические задачи не выполняются.

Функции диагностики и выдача справочной информации, сохранение информации на внешнем носителе.

Спорадические задачи

Спорадические задачи – это апериодические задачи с жестким крайним сроком исполнения.

Приоритет устанавливается на уровне периодических задач, имеют непредсказуемый характер.

Рис.4.

Для обработки выделяется отдельная периодическая задача, которая будет контролировать выполнение.

Фоновые задачи

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

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

Может исполняться несколько циклов функционирования системы.
    
Задачи аппендиксы

Задачи аппендиксы – это задачи, которые исполняются до старта ОС и имеют приоритет выше, чем сама ОС.

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

Планирование задач СРВ.

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

Алгоритм реализуется при помощи планировщика задач.

Алгоритмы: статические и динамические.

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

Достоинства:

1. Предсказуемость (если система предсказуема на первом шаге, то она предсказуема на всех остальных);

2. Простота обнаружения ошибок (любая ошибка является следствием неправильно построенной последовательности задач);

Недостатки:

1. Использование в каждом цикле одной и той же последовательности задачи

2. Не допускается изменение очередности исполнения

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

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

Достоинства:

1. Оптимальное распределение временных участков для задач

2. Возможность дополнения списка задач в процессе функционирования системы

Недостатки:

1. Сложность реализации алгоритма

2. Повышенные требования к вычислительному узлу

3. Предсказуемость системы зависит от алгоритма на каждом этапе планирования

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

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

Существует 2 подхода:

1. Фиксированный приоритет задачи (приоритет вычисляется один раз до запуска и остается неизменным)

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

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

1. Алгоритмы планирования задач с фиксированным приоритетом

2. Вытесняющий алгоритм планирования задач (вытеснение одной задачи другой в зависимости от приоритета)

3. основные алгоритмы планирования:

   3.1. RM (Rate Monotonic) – алгоритм с фиксированным приоритетом. Алгоритм назначается по следующему принципу: чем меньше вызывается периодическая задача, тем больше приоритет. Данный алгоритм всегда формирует оптимальную последовательность задач.

 

 3.2. EDF – алгоритм с динамическим планированием задачи. Чем меньше срок выполнения, тем выше приоритет. Каждый раз задачи выстраиваются заново в зависимости от критического срока выполнения. Реализованный алгоритм зависит от количества задач в определенный момент времени.

   3.3. LSTF – алгоритм планирования. Приоритет назначается по следующему принципу: чем меньше время связывания задачи, тем выше ее приоритет.

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

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

Существует 5 алгоритмов планирования спорадических задач:

1. Планирование спорадической задачи как фоновой задачи

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

   б). Планирование спорадической задачи как фоновой без создания дополнительного процесса.

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

2. «Политика выбора»

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

Недостатки:  Несовместимость циклического характера алгоритма и случайного характера спорадических задач

Достоинство:  Позволяет четко спланировать время исполнения всех задач (самоопределяющий алгоритм).

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

4. Деферабельный сервер

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

В процессе функционирования системы данная задача может прерывать периодические задачи несколько раз.

5. Спорадический сервер

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

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

- нагрузка системы на отказ (BUBreakDown Utilization)

- нормализованное среднее время ответа (NMRT)

- гарантированная скорость обработки задач (GR)

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

NMRT – отн-ие между интервалом времени от готовности задач к выполнению до ее окончания.

, где

tовз – окончание вып-ия задачи; tнвз – нач. выполнения задачи; tобр - фактическое время процессора

Чем больше NMRT, тем больше времени простоя задачи.

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

, где nгар – гарантированное количество задач;

       N – общее количество задач, ожидающих выполнение.

Если GR>1, то система расписабельная

Если GR<1, то система нерасписабельная

Чем больше GR, тем больше запас времени для выполнения задач.

Планировщик заданий.

Планировщик заданий – средство, которое предназначено для использования на вычислительном узле.

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

Планировщик бывают: глобальный и местный.

Задачи глобального планировщика:

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

2. Создание алгоритма формирования образов узла (функций узла с входными и выходными данными). Построение алгоритма для вычисления параметров производительности.

Задачи местного планировщика:

1. Реализация на каждом узле с целью распределения задач на заданный цикл функционирования. Местные планировщики различных узлов являются независимыми программами. Любой местный планировщик является задачей для глобального планировщика и так же подлежит планированию.

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

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

2. Распределение ресурсов между задачами связано с понятием «гонок». «Гонка» - ситуация по захвату доступа к ресурсу задачей с немаксимальным приоритетом. Понятие «гонка» связано с операционной системой реального времени. В данной ситуации необходимо обеспечить распределение ресурсов или сервер ресурсов.

3. Распределение времени между задачами

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

Алгоритм функционирования планировщика.

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

Имя группы

Параметры

Список задач

prt 0

prt 1

з 1, з 5, з 3

з 4, з 2, з 6

Перечень параметров и их значений зависит от типа задач. Для периодических и фоновых задач должны быть установлены следующие параметры:

- стартовая метка запуска;

- период запуска или период исполнения;

- ККС.

Имя группы

Стартовая метка

ККС

Т

Список задач

prt 0

prt 1

0

5

5

5

1

1

з 1, з 5, з 3

з 4, з 2, з 6

Особенность фоновых задач: возможность указания ККС и Т могут быть указаны в диапазоне значений.


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

apt: метка <список> <p> //для апериодических задач

spt: метка <список> <p> //для спорадических задач

Для всех апериодических и спорадических задач устанавливается единый ККС, собственный для apt и spt. Для апериодических задач ККС устанавливается в диапазоне. Если задача различается по приоритету, то создается для одной метки несколько списков задач.

Имя

Стартовая метка

Список задач

Р

apt 0

apt 1

5

5

6

5

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

Анализ таблиц планировщика и исполнение.

Анализ таблиц планировщика

Таблица планировщика является основной входной информацией для построения списка задач исполнения. Список задач для каждой метки может меняться в зависимости от характеристик конечных задач.

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

Исполнение планировщика

завершающая стадия процедуры планирования задач.

Местный планировщик является задачей аппендиксом. Глобальный планировщик является операционной системой и исполняется по нулевой метке.

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

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

3ий шаг: На основании анализа строится список задач для каждой метки по типам.

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

Примечание:

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

2. Если временные характеристики нарушены, то должно сформироваться отказное состояние системы.

 


 

А также другие работы, которые могут Вас заинтересовать

41223. История возникновения и перспективы применения штрихового кодирования 1.42 MB
  История возникновения и перспективы применения штрихового кода Вид и размер штрихового кода EN13.5 Определение размера штрихового кода.2 Плотность штрихового кода.
41224. Сравнительная психология (зоопсихология) 307 KB
  Предмет изучения зоопсихологии это психическая деятельность животных это комплекс проявлений поведения и психики единый процесс психического отражения как продукт внешней активности животного. Изучение животных стоящих на разных ступенях развития от амёбы до приматов. Ощущения животных рассматриваются как первостепенные явления психики нижняя грань интеллект высшая грань. Импритинг видовая память процессы запечатления Лоренц этологизм поведения животных; 4.
41225. КОНЦЕПЦИИ ЛОГИСТИКИ 125 KB
  Практическими примерами использования информационной концепции логистики являются широко распространенные информационнопрограммные модули MRP I MRP II DRP OPT QR CR и т. К числу ее важнейших функций относятся в частности контроль за состоянием запасов включая расчет точки заказа формирование связей производства снабжения и сбыта с использованием обеспечивающего комплекса системы MRP. Работа системы DRP осуществляется поэтапно: 1 агрегированное планирование с использованием прогнозов и данных о фактически поступивших заказах; 2...
41226. Классификационные признаки микроконтроллеров 878 KB
  Модификация памяти и чтение из нее необходимых данных осуществляется только лишь с помощью специальных команд чтения записи; в система команд должна содержать минимальное число наиболее часто используемых простейших команд одинаковой длины: г состав системы команд должен быть оптимизирован с учетом требований компиляторов языков высокого уровня. Центральное процессорное устройство Процессор формирует адрес очередной команды выбирает команду из памяти и организует ее выполнение. Благодаря специальным командам их можно...
41227. ИНТЕРФЕЙСЫ ИЗМЕРИТЕЛЬНЫХ СИСТЕМ 925.5 KB
  Применяются параллельные интерфейсы Centronics магистральные приборный интерфейс GPIB IEEE 488 и функционально-модульные системы CMC и VXI. Магистральный интерфейс VXI Стандарт VXI является одним из прогрессивных направлений развития шины VMEbus VMEbus eXtention for Instrumenttion VXI расширение VMEbus для измерительной техники. Основываясь на шине VMEbus и полностью включая ее как подмножество интерфейс VXI представляет собой самостоятельный стандарт на контрольноизмерительную и управляющую аппаратуру высшего класса...
41228. Восьмиточечная графика 1.09 MB
  Графика, выводимая с помощью матричных ПУ, представляется в виде отдельных точек, формирующих изображение. Графическое изображение ПУ выводит построчно, обычно строки графики расположены вплотную друг к другу. Графическая строка состоит из вертикальных колонок. Высота колонки может быть 8, 9 или 24 точки.
41229. Системные и локальные шины 257.5 KB
  Системные и локальные шины [0. Стоимость такой организации получается достаточно низкой поскольку для реализации множества путей передачи информации используется единственный набор линий шины разделяемый множеством устройств. Одна из причин больших трудностей возникающих при разработке шин заключается в том что максимальная скорость шины главным образом лимитируется физическими факторами: длиной шины количеством подсоединяемых устройств. Эти физические ограничения не позволяют произвольно ускорять шины.
41231. Групова динаміка 66 KB
  Що вивчає групова динаміка Групова динаміка вивчає: безпосередньо групи процеси в групах Рівні дослідження: Індивідуальний – вивчаються індивідуалиособистості групи в психологічному аспекті Груповий – вивчаються групи в цілому і їх соціальний контекст соціологічний аспект Змішаний – вивчаються групи в різних аспектах як правило одночасно. Наукові припущення: групи та групові процеси – це реальність групи – це більш ніж склад її...