45446

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

Доклад

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

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

Русский

2013-11-17

156.5 KB

46 чел.

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

Задачи СРВ.

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

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

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

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

  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. Если временные характеристики нарушены, то должно сформироваться отказное состояние системы.

 


 

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

80897. Информационное обеспечение муниципального управления 45.52 KB
  Распоряжения главы администрации и его заместителей протоколы заседаний коллегии ведомости учета изданных мун. Население выражает свое отношение к дти мун. Общественные объединения граждан выражают отношение к деятельности мун.
80898. Сущность и содержание муниципального управления 43.04 KB
  Местное самоуправление в РФ форма осуществления народом своей власти обеспечивающая в пределах установленных Конституцией РФ федеральными законами а в случаях установленных федеральными законами законами субъектов РФ самостоятельное и под свою ответственность решение населением непосредственно и или через органы местного самоуправления вопросов местного значения исходя из интересов населения с учетом исторических и иных местных традиций . Дана характеристика основных признаков местного самоуправления отличающих его от...
80899. Система муниципальных правовых актов (МПА), Устав муниципального образования 43.13 KB
  РФ федеральным конституционным законам ФЗ №131ФЗ другим федеральным законам и иным нормативным правовым актам РФ а также конституциям уставам законам иным нормативным правовым актам субъектов РФ. В систему МПА входят: 1 устав МО правовые акты принятые на местном референдуме сходе граждан; 2 нормативные и иные правовые акты ПО МО; 3 правовые акты главы МО постановления и распоряжения главы местной администрации иных ОМС и должностных лиц МС предусмотренных уставом МО. Устав МО и оформленные в виде правовых актов решения...
80900. ПОНЯТИЕ, ОСОБЕННОСТИ, ФУНКЦИИ И ЗАКОНЫ СОЦИАЛЬНОГО УПРАВЛЕНИЯ 44.44 KB
  В основе социального управления лежит приоритет человеческого фактора над всеми иными. Функции управления не являются универсальными так как зависят от вида рассматриваемой организации. Законы управления.
80901. МОДЕЛИ СОЦИАЛЬНОГО УПРАВЛЕНИЯ И ИХ ХАРАКТЕРИСТИКА 44.37 KB
  Под моделью управления следует понимать теоретически выстроенную целостную совокупность представлений о том как выглядит и как должна выглядеть система управления как она воздействует и как должна воздействовать на объект управления как она адаптируется и как должна адаптироваться к изменениям во внешней среде чтобы управляемая организация могла добиваться поставленных целей устойчиво развиваться и обеспечивать свою жизнеспособность. Модель управления включает в себя базовые принципы управления стратегическое видение целевые установки и...
80902. ХАРАКТЕРИСТИКА СРЕДЫ УПРАВЛЕНИЯ. БЛАГОПРИЯТНАЯ, НЕЙТРАЛЬНАЯ, АГРЕССИВНАЯ СРЕДА УПРАВЛЕНИЯ 43.99 KB
  Среда управления это совокупность внутренних и внешних субъектов сил активно влияющих на положение и перспективы организации на эффективность деятельности менеджеров. Типы среды: микросреда мезосреда макросреда. Микросреда внутр среда организации ее собственный персонал и взаимодействие человека с условиями жизни в личном окружении; Мезосреда среда непосредственного окружения партнеры поставщики потребители или социокультурная среда и сфера труда; Макросреда среда...
80903. ПОНЯТИЕ И КЛАССИФИКАЦИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В УПРАВЛЕНИИ 44.22 KB
  Об информации информационных технологиях и о защите информации ИТ процессы методы поиска сбора хранения обработки предоставления распространения информации и способы осуществления таких процессов и методов. Информационная технология ИТ процесс использующий совокупность методов и средств реализации операций сбора регистрации передачи накопления и обработки информации на базе программноаппаратного обеспечения для решения управленческих задач экономического объекта. Особенности ИТ: цель процесса получение информации; предмет...
80904. ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ДЛЯ ОБЕСПЕЧЕНИЯ УПРАВЛЕНЧЕСКОЙ ДЕЯТЕЛЬНОСТИ 85.5 KB
  ИТ включают в себя методы преобразования информации по заданному свойству в заданном направлении, что реализуется соответствующими средствами, называемыми инструментальными. Они включают в себя необходимый технических комплекс и соответствующее программное обеспечение, образуя сложные программно - аппаратные компьютерные системы с разнообразными функциями и возможностями поддержки управленческой деятельности.
80905. ГОСУДАРСТВЕННАЯ ИНФОРМАЦИОННАЯ ПОЛИТИКА (ГИП), ОСНОВНЫЕ НАПРАВЛЕНИЯ ИНФОРМАТИЗАЦИИ ГОСУДАРСВТЕННОГО И МУНИЦИПАЛЬНОГО УПРАВЛЕНИЯ 46.21 KB
  ГИП комплекс политических правовых экономических социальнокультурных и организационных мероприятий государства направленный на обеспечение конституционного права граждан на доступ к информации. ГИП это особая сфера жизнедеятельности людей связанная с воспроизводством и распространением информации удовлетворяющей интересы государства и гражданского общества и направленная на обеспечение творческого конструктивного диалога между ними и их представителями. Различают аспекты ГИП: технологический регулирование процесса развития...