Задачи и задания. Каждая прикладная задача t i представляет собой внутренне замкнутую (по передачам управления) компоненту комплекса программных средств

Каждая прикладная задача t _i представляет собой внутренне замкнутую (по передачам управления) компоненту комплекса программных средств. Для каждой задачи определяется ее корневая программа, которая представляет последовательный алгоритм исполнения этой задачи. Алгоритм, реализуемый корневой программой задачи, строится с использованием тех же средств и принципов, которые используются при построении последовательных вычислительных процедур, то есть, состоит из последовательности операторов с ветвлениями и циклами, с вызовами процедур, допускающих несколько уровней вложенности. Определяющее различие между корневой программой задачи и вычислительной процедурой состоит в способах активизации и завершения исполнения.

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

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

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

а) задача (task) – статический объект, элемент статической структуры программного приложения,

б) задание (job) – динамический объект, процесс исполнения задачи.

События, означающие необходимость исполнения задачи t _i, составляют отдельный тип системных событий – этот тип системных событий будем называть возникновением задания _jt _i (job arrival) и обозначать символом e _воз(t _i). В ходе работы СРВ каждая из прикладных задач t _i может выполняться многократно: любое событие типа e _воз(t _i), приводит к возникновению очередного задания.

Символами ₁ t _i, ₂ t _i, ₃ t _i, … будем обозначать последовательно возникающие задания на выполнение задачи t _i. Отношение между задачей t _i и заданием _jt _i в точности повторяет отношение между типом переменной (например, типом int) и конкретной переменной этого типа (например, переменной int x), между классом объектов и экземплярами этого класса (рис. 4).

Рис. 4. Характер отношений между задачами и заданиями

Поэтому задание _jt _i уместно называть экземпляром задачи t _i. Аналогично символом e _воз(_jt _i) будем обозначать отдельный экземпляр событий типа e _воз(t _i), а именно, конкретное событие этого типа, приводящее к возникновению задания _jt _i.

3.1. Интервалы существования заданий. Системное событие, заключающееся в завершении задания _jt _i, обозначим символом e _зав(_jt _i). Моменты времени возникновения и завершения задания _jt _i будем обозначать соответственно символами t (e _воз(_jt _i)) и t (e _зав(_jt _i) или в сокращенной форме t _воз(_jt _i) и t _зав(_jt _i).

Задание _jt _i существует (действует) в рамках интервала времени [ t _воз(_jt _i), t _зав(_jt _i)]. В момент t _воз(_jt _i) возникает потребность в том, чтобы программное приложение выполнило функцию, соответствующую задаче t _i. Для выполнения этой функции система строит и запускает задание t _ij. Завершение задания в момент t _зав(_jt _i) происходит либо естественным путем, то есть, в результате выполнения заданием _jt _i оператора завершения своей работы, либо в результате выполнения каким-то другим заданием действий по принудительному завершению задания _jt _i. И в том и в другом случае выделенные для выполнения _jt _i ресурсы освобождаются, задание _jt _i прекращает свой существование. Заданиями, действующими в момент времени t, являются все те задания _jt _i, для которых выполняется неравенство t _воз(_jt _i)£ t £ t _зав(_jt _i). Продолжительность интервала существования

r (_jt _i) = t _воз(_jt _i) – t _зав(_jt _i)

называется временем отклика задания _jt _i.

В общем случае в ходе работы КС может возникать неограниченное число однотипных заданий (неограниченное число экземпляров задачи t _i). При этом величина времени отклика r (_jt _i) для однотипных заданий может варьироваться в широких пределах, т.е., при j ¹ k значения r (_jt _i) и r (_kt _i) могут не совпадать. Такое несовпадение возникает по двум причинам. Во-первых, из-за различий в объемах вычислений, выполняемых в рамках _jt _i. и _kt _i. Если обозначить символом _jc _i требуемый для выполнения _jt _i объем процессорного времени (суммарную продолжительность непосредственного облуживания задания центральным процессором), то при j ¹ k значения _jc _i и _kc _i могут не совпадать. Другая возможная причина различий в величине времени отклика для _jt _i. и _kt _i состоит в том, что аппаратные и информационные ресурсы, требуемые для выполнения t _i (в частности, ресурс процессора) могут в рамках интервалов существования _jt _i и _kt _i по-разному отвлекаться на выполнение других заданий.

3.2. Периодичность возникновения однотипных заданий. Условия использования СРВ могут накладывать ограничения на продолжительность временного интервала между возникновением соседних однотипных заданий _jt _i и _{j +1} t _i. Так, при реализации приложением КС функций регулирования (рис. 5) входными параметрами задачи, вычисляющей величину управляющего воздействия u (t), являются:

а) величина f (t) регулирующего воздействия,

б) показания v (t) датчиков состояния объекта регулирования.

Рис. 5. Внешние интерфейсы КС, выполняющей функции регулирования

Управляющие воздействия u (t) вычисляются строго периодически с периодом P. Величины f (t) и v (t) формируются внешним оборудованием в аналоговой форме – перед вводом в КС требуется их перевод в цифровую форму (дискретизация и квантование). Выбор частоты дискретизации определяет частоту возникновения заданий, реализующих вычисление u (t). Качество регулирования зависит от соотношения между частотой дискретизации и продолжительностью крутого фронта входных сигналов. Для различных контуров регулирования (например, в подсистеме управления подвеской и подсистеме управления двигателем) максимальная крутизна фронтов (определяемая длиной интервала T_f на рис.5) существенно различна. Поэтому для обеспечения одинакового качества работы задачи, реализующие функцию регулирования для различных подсистем, должны выполняться с различной частотой.

Выбор величины P периода следования заданий, реализующих функцию регулирования, определяется с учетом двух противоречивых обстоятельств: с одной стороны, с увеличением P понижается качество регулирования, с другой стороны, с уменьшением P растет объем вычислений на реализацию функции регулирования. Считается, что рациональным разрешением этого противоречия является выбор величины P в диапазоне то 0.05 T_f до 0.1 T_f где T_f – длина крутого фронта входного сигнала f (t).

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

Задачу t _i будем называть синхронной задачей, если соответствующие ей задания _jt _i следуют строго периодически, то есть, для любой пары соседних заданий _jt _i и (_{j +1}) t _i выполняется условие:

t _воз((_{j +1}) t _i) - t _воз(_jt _i) = P _i

где P _i - период выполнения задачи t _i.

Будем называть синхронной программную систему (подсистему), в которой все задачи являются строго периодическими. Для синхронной системы моменты t _воз(_jt _i) возникновения всех предстоящих заданий становятся известны заблаговременно, если известен момент T _старт инициализации (ре-инициализации) системы и известны смещения

j(t _i) = t _воз(₁ t _i) - T _старт

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

t _воз(_jt _i)= T _старт + (j -1) P _i + j(t _i)

Смещение j(t _i) принято называть фазой задачи t _i. В синхронной системе все системные события типа e _воз(t _i) генерируются путем использования часовых механизмов.

Задачу t _i будем называть асинхронной задачей, если задания t _ij следуют не строго периодически, но не чаще чем с интервалом P_i:

t _воз((_{j +1}) t _i) - t _воз(_jt _i) ³ P_i

Для каждой из асинхронных задач t _i системные события типа e _воз(t _i) генерируются либо периферийными устройствами (аппаратными блоками, обеспечивающими информационную связь СРВ с внешним оборудованием), либо программными компонентами. Системы (подсистемы), состоящие из асинхронных задач, называют событийными системами.

3.3. Жесткие и мягкие сроки выполнения заданий. В подразделе 2.1 отмечалось, что спецификации функций взаимодействия СРВ с внешними процессами могут содержать ограничения на значение r (_jt _i) времени отклика соответствующих заданий (см. табл. 1). Пусть для всех заданий типа _jt _i допустимая продолжительность интервала существования задания ограничена величиной D _i, то есть, одним из требований к реализации СРВ является выполнение неравенства r (_jt _i) £ D _i. Это означает установку предельного срока d (_jt _i) = t _воз(_jt _i) + D _i для момента завершения t _зав(_jt _i) задания _jt _i:

t _зав(_jt _i) £ d (_jt _i).

Величины D (_jt _i) и d (_jt _i) называются соответственно относительным и абсолютным предельным сроком выполнения задания _jt _i. Обычно величина относительного срока выполнения устанавливается не для отдельного задания, а сразу для всего класса однотипных заданий. То есть, для задачи t _i задается величина D _i, определяющая относительный срок выполнения для всех заданий _jt _i типа t _i. Таким образом, для всех _jt _i должно выполняться неравенство

t _зав(_jt _i) £ t _воз(_jt _i) + D _i.

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

В многозадачных системах типичны ситуации, в которых интервалы существования заданий перекрываются, то есть, ситуации, в которых несколько заданий, одновременно претендуют на ресурс процессора. Более того, в общем случае могут перекрываться даже интервалы существования однотипных заданий, как в случае задачи t ₁ на рис. 6: интервалы существования заданий ₁ t ₁ и ₂ t ₁ перекрываются между собой и с интервалами существования заданий других типов – заданиями ₁ t ₂ и ₂ t ₂, а также с заданием типа t ₃.

Рис. 6. Перекрытие интервалов существования заданий

Обращаем внимание на значения параметров задачи t ₃ (P ₃= ¥, D ₃= ¥) и объем вычислений для задания ₁ t ₃ (₃ c ₁= ¥). Бесконечное значение P ₃ означает, что с момента инициализации приложения до завершения его работы задача t ₃ выполняется единственный раз. Бесконечное значение D ₃ означает, что требования к сроку завершения задания отсутствуют. Бесконечное значение ₃ c ₁ означает, что единственный экземпляр задачи t ₃ израсходует столько процессорного времени, сколько ему будет предоставлено, оно не завершается естественным образом, не ликвидируется принудительно другими заданиями. Задачи с такими значениями параметров называются фоновыми задачами. В состав приложений реального времени, как правило, включается по крайней мере одна фоновая задача.

В условиях перекрытия интервалов существования заданий решение о том, какому из заданий следует предоставить процессор, принимается в соответствии с используемой дисциплиной планирования. Как указывалось в подразделе 1.3, планирование использования процессорного времени является одной из функций операционных систем.

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

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

· проверка гарантированной своевременности выполнения заданий (проверка выполнимости заданий) в условиях использования конкретной дисциплины планирования,

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

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

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

Один из вариантов требований к системе мягкого реального времени состоит в том, чтобы среднее значение времени отклика r (_jt _i) для заданий типа t _i не превышало установленного значения D _i.

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

3.4. Межзадачные связи. Задачи, составляющие программное приложение СРВ, объединяются в систему множеством взаимных связей. Будучи статическими объектами, задачи именно взаимосвязаны, а не взаимодействуют. Взаимодействуют между собой задания, как динамические объекты (процессы исполнения задач), а спецификация межзадачных связей определяет структуру и типы этих взаимодействий. Отметим три основные разновидности межзадачных связей:

· обмен знаковой информацией (прием/передача сообщений),

· прием/передача сигнальной информации (синхронизация вычислений),

· динамическое разделение системных ресурсов.

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

Наряду с механизмами обмена сообщениями ОСРВ реализуют механизм приема/передачи сигнальных информационных посылок (сигналов). Этот механизм обеспечивают синхронизацию хода исполнения задач. В ходе обмена чисто сигнальной информацией не происходит передачи знаковых информационных элементов – весь смысл приема/передачи сигналов заключается в синхронизации операций, выполняемых взаимодействующими заданиями. Несмотря на отсутствие знаковой составляющей, прием/передачу сигналов следует отнести к механизмам информационных обменов, поскольку в этом случае передающая сторона информирует принимающую сторону о наступлении определенного момента времени. Формирование сигнала передающим заданием следует рассматривать как разновидность предоставления информационного ресурса.

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

Интервал доступа задания _jt _i к разделяемому ресурсу g называют критическим интервалом задания _jt _i по ресурсу g. Для получения доступа к ресурсу g задание запрашивает у ОС разрешение на использование g. Если в момент запроса заданием _jt _i ресурса g этот ресурс оказывается занят, то происходит приостановка задания _jt _i до момента освобождения g. Продолжительность таких приостановок зависит от распределения приоритетов между заданиями, конкурирующими за использование g и от длины критических интервалов конкурирующих заданий. Для обеспечения своевременности выполнения конкурирующих заданий необходимо по возможности минимизировать длину критических интервалов.

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

В действующей системе каждая из задач представляется уникальным идентификатором. Роль идентификатора задачи обычно выполняет указатель дескриптора задачи – структуры, содержащей значения ее системных характеристик. В составе системных характеристик задачи обязательно присутствует указатель (адрес) начала кода программы, представляющей алгоритм выполнения задачи. В ряду других характеристик задачи t _i могут указываться имя задачи, требуемый объем стека, уровень приоритета. Полный состав атрибутов, представляемых дескриптором задачи, определяются архитектурными особенностями аппаратной базы КС и операционной системы.

Ряд характеристик задачи t _i используется в ходе разработки СРВ. К таким характеристикам относятся, например, значения модельных параметров:

· период P_i,

· относительное значение D_i предельного срока выполнения,

· максимальный объем C_i = max(_jc_i) процессорного времени, требуемый для выполнения задачи,

· максимальное значение задержки регистрации J_i,

· максимальная длина B (t _i, g_x) критических интервалов задачи t _i по доступу к ресурсу g_x.

Значения модельных параметров могут использоваться для определения уровня приоритета задачи, для проведения анализа ее выполнимости. Некоторые из перечисленных модельных параметров могут использоваться и в ходе работы СРВ (представляться в составе дескриптора задачи).

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

Значения параметров, характеризующих действующее задание _jt _i, размещаются в дескрипторе задания. Дескриптор задания _jt _i может содержать, например, следующие поля:

· код текущего состояния задания,

· текущий уровень приоритета,

· указатель вершины стека приостановленного задания.

Операционная система выполняет порождение (creation) дескриптора задания _jt _i в порядке регистрации _jt _i. Состав полей порождаемого дескриптора задания определяется конструктивными особенностями ОС.

Контрольные вопросы.

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

2. В чем различие между задачами и заданиями как компонентами программной системы?

3. В каком смысле отношения между задачей и заданиями повторяют отношения между классом объектов и объектами этого класса?

4. Какие типы системных событий определяют временные рамки интервала существования задания?

5. Как формально определяется параметр, называемый временем отклика задания?

6. Какова связь между временем отклика задания и объемом процессорного времени, требуемого для выполнения задачи?

7. В какой мере могут различаться частоты активизации заданий для различных задач в одной и той же СРВ?

8. В чем различие между терминами «взаимосвязь задач» и «взаимодействие заданий»?

9. Какие разновидности межзадачных связей могут присутствовать в СРВ?

10. Допустимо ли пересечение интервалов существования однотипных заданий?

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

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

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

14. Зачем строятся и как используются формальные модели задач в СРВ?

15. Что происходит с заданием, запрашивающим доступ к занятому системному ресурсу?

16. Какие разновидности системных ресурсов разделяются задачами (заданиями) в СРВ?

17. Что понимается под интервалом доступа задачи (задания) к разделяемому системному ресурсу?

18. Почему следует минимизировать продолжительность интервалов доступа к разделяемым системным ресурсам?

19. Какие характеристики задач используются в ходе работы СРВ? Как называется структура, в которой хранятся характеристики задачи?

20. Какие типы памяти могут использоваться для размещения дескрипторов задач и заданий?

Поиск по сайту: