АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. Ситуационные задачи и тестовые задания.
  3. II. Основные задачи и функции
  4. II. Расчетная часть задания
  5. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  6. II. Цель и задачи государственной политики в области развития инновационной системы
  7. III. Задания для самостоятельной работы по изучаемой теме.
  8. III. Задания для самостоятельной работы по изучаемой теме.
  9. III. Задания для самостоятельной работы по изучаемой теме.
  10. III. Задания для самостоятельной работы по изучаемой теме.
  11. III. Задания для самостоятельной работы по изучаемой теме.
  12. III. Задания для самостоятельной работы по изучаемой теме.

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

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

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

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

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

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

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

Символами 1 t i, 2 t i, 3 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 it £ 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). Качество регулирования зависит от соотношения между частотой дискретизации и продолжительностью крутого фронта входных сигналов. Для различных контуров регулирования (например, в подсистеме управления подвеской и подсистеме управления двигателем) максимальная крутизна фронтов (определяемая длиной интервала Tf на рис.5) существенно различна. Поэтому для обеспечения одинакового качества работы задачи, реализующие функцию регулирования для различных подсистем, должны выполняться с различной частотой.

Выбор величины P периода следования заданий, реализующих функцию регулирования, определяется с учетом двух противоречивых обстоятельств: с одной стороны, с увеличением P понижается качество регулирования, с другой стороны, с уменьшением P растет объем вычислений на реализацию функции регулирования. Считается, что рациональным разрешением этого противоречия является выбор величины P в диапазоне то 0.05 Tf до 0.1 Tf где Tf – длина крутого фронта входного сигнала 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 воз(1 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 следуют не строго периодически, но не чаще чем с интервалом Pi:

t воз((j +1) t i) - t воз(jt i) ³ Pi

Для каждой из асинхронных задач 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 1 на рис. 6: интервалы существования заданий 1 t 1 и 2 t 1 перекрываются между собой и с интервалами существования заданий других типов – заданиями 1 t 2 и 2 t 2, а также с заданием типа t 3.

 
 

 

 


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

 

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

В условиях перекрытия интервалов существования заданий решение о том, какому из заданий следует предоставить процессор, принимается в соответствии с используемой дисциплиной планирования. Как указывалось в подразделе 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 используется в ходе разработки СРВ. К таким характеристикам относятся, например, значения модельных параметров:

· период Pi,

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

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

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

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

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

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

Значения параметров, характеризующих действующее задание 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. Какие типы памяти могут использоваться для размещения дескрипторов задач и заданий?

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

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



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