СРВ    

  Практика ~ 
  Тема 01 ~ 
  Тема 02 ~ 
  Тема 03 ~ 
  Тема 04 ~ 
  Тема 05 ~ 
  Тема 06 ~ 
  Тема 07 ~ 
  Тема 08 ~ 
  Тема 09 ~ 
  Тема 10 ~ 
  Тема 11 ~ 
/Студентам/СРВ/Тема 02

Тема 2
Терминология, основные понятия и определения

Как уже говорилось, СРВ - это программно-аппаратный комплекс, осуществляющий мониторинг какого-то объекта и/или управление им в условиях временнЫх ограничений. Возникающие на объекте события подлежат обработке в СРВ. Будем сопоставлять каждому типу события задачу.

Определение. ЗАДАЧА (TASK) - блок программного кода, ответственный за обработку тех или иных событий, возникающих на объекте управления.

Задача может быть "оформлена" в виде:

Определение. РАБОТА ЗАДАЧИ (JOB) - процесс исполнения блока программного кода в ходе обработки события.

Аналогия...

Каждая работа задачи характеризуется следующими временнЫми параметрами:

Диаграмма ниже иллюстрирует эти параметры:


          r           s               c       d
          *            ---------------        |
          |           |               |       |
          |           |               |       *
 -+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)
  0   1   2   3   4   5   6   7   8   9   10  11  12  13

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

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

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

Второй подход более прост и состоит в том, что времена исполнения непосредственно измеряются. Однако, в случае процессоров с конвейерами и кэшами такие измерения не дают гарантии, что будет измерено именно МАКСИМАЛЬНОЕ время исполнения того или иного кода (???). Наконец, системы, использующие механизмы подкачки страниц, также являются менее предсказуемыми и поэтому считается, что такого рода механизмы являются "врагами" систем реального времени. Недаром в различного рода стандартах, касающихся СРВ, предусмотрены средства блокировки страниц памяти.

Определение. Крайний срок называется ЖЕСТКИМ (HARD), если он ОБЯЗАН быть соблюден, при этом в системе должна существовать возможность проверки того, был ли соблюден крайний срок или нет. Несоблюдение такого крайнего срока ведет к катастрофическим последствиям (авария, гибель людей и т.п.)

Определение. Крайний срок называется МЯГКИМ (SOFT), если _иногда_ его допустимо не соблюдать. Несоблюдение такого крайнего срока не ведет к катастрофическим последствиям, а лишь к некоторому снижению производительности, ухудшению качества обслуживания, повышению стоимости результатов, бесполезной трате времени и т.п.

Для количественного выражения "иногда" используют или вероятностный подход ("допустимо несоблюдение крайнего срока в 5% случаях"), или подход, основанный на введении т.наз. "функции полезности". При этом, если полезность завершения работы после крайнего срока обращается в нуль, мягкий крайний срок называют ЧЕТКИМ.

Определение. Система реального времени называется ЖЕСТКОЙ, если все крайние сроки, характеризующие эту систему - жесткие.

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

Определение. Система реального времени называется МЯГКОЙ, если хотя бы один из крайних сроков, характеризующих эту систему, является мягким.

В качестве примеров такого рода можно привести системы мультимедиа, системы связи (например, сотовой) и т.п. Отметим также, что иногда мягкие системы называют ГИБКИМИ.

Характер возникновения событий на управляемом объекте отражается в следующей классификации задач:

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


      *       *       *       *       *       *       *
      |       |       |       |       |       |       |
      |       *       *       *       *       *       *   
 -+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)
  0   1   2   3   4   5   6   7   8   9   10  11  12  13

Период может быть больше относительного крайнего срока:


      r1      d1  r2      d2  r3      d3  r4      d4  r5
      *       |   *       |   *       |   *       |   *
      |       |   |       |   |       |   |       |   |
      |       *   |       *   |       *   |       *   |
 -+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)
  0   1   2   3   4   5   6   7   8   9   10  11  12  13
  

Период может быть меньше относительного крайнего срока:


      r1          r2      d1  r3      d2  r4      d3  r5
      *           *       |   *       |   *       |   *
      |           |       |   |       |   |       |   |
      |           |       *   |       *   |       *   |
 -+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)
  0   1   2   3   4   5   6   7   8   9   10  11  12  13
  

В последнем случае в один и тот же промежуток времени могут "сосуществовать" несколько экземпляров одной и той же задачи.

В дальнейшем будут использоваться следующие обозначения. {Tj} будет обозначать набор задач. Моменты времени, когда возникает необходимость в выполнении j-ой задачи, будут обозначаться как rjk. При этом для периодической задачи rj1 будет называться фазой задачи. Периодическая задача будет обозначаться как Tjj, pj, ej, Dj], где

При этом, если фаза задачи равна нулю, задача будет обозначаться как Tj[pj, ej, Dj]. Если же еще имеет место равенство периода и относительного крайнего срока, то будет использоваться обозначение Tj[pj, ej].

Для периодических задач имеют место следующие определения:

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

Определение. Гиперпериодом системы периодических задач называется наименьшее общее кратное периодов этих задач.

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

uj = ej/pj

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

U = ∑uj = ∑ ej/pj

Задачи могут быть зависимыми и независимыми. Задачи являются зависимыми, если имеет место одна из двух видов зависимостей:

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

Классификация алгоритмов планирования (АП), применяемых в СРВ. Выделяют 2 класса АП:

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

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

Определение. Расписание называется корректным, если соблюдены все крайние сроки.

Определение. Набор задач {Tj} называется планируемым некоторым АП, если этот АП всегда дает корректное расписание для этого набора задач.

Определение. Оптимальным АП называется такой АП, который для ЛЮБОГО набора задач дает корректное расписание, если таковое вообще существует для данного набора задач.

Дата последней модификации: 2010-05-15


/Студентам/СРВ/Тема 02

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

Valid HTML 4.0 Strict Valid CSS!