Лекции. Системы реального времени (2015) (all in one) (1185224), страница 2

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

Текст из файла (страница 2)

is monotonically non decreasing.When win  win 1 the solution to the equation has been found; wi0must not be greater that Ri (e.g. 0 or Ci )Response Time Calculation Algorithmfor i in 1..N loop -- for each process in turnn := 0win : Ciloopcalculate new win 1if win 1  win thenRi  winexitend ifif win 1exitend ifn := nend loopend loopvalue found Ti thenvalue not found+ 1Task Set ATaskabcPeriodT71220ComputationTimeC335PriorityP321wb0  3Ra  33w  3   3  6762wb  3    3  67Rb  61bwc0  55 5 wc1  5    3  3  11712 11 11 wc2  5  33  147 12 14 wc3  5  3 7 14 3  1712 17 17 wc4  5  33  207 12  20  20 5wc  5  3 3  20 7  12 Rc  20Task Set BProcess Period ComputationTime Priority Response timeTCPRabc8040204010512380155The combined utilization is 1.0This was above the utilization threshold for three tasks(0.78), therefore it failed the testThe response time analysis shows that the task set willmeet all its deadlinesResponse Time AnalysisIs sufficient and necessary (exact)If the task set passes the test they will meetall their deadlines; if they fail the test then,at run-time, a task will miss its deadline(unless the computation time estimationsthemselves turn out to be pessimistic)Sporadic TasksSporadics tasks have a minimum inter-arrival timeThey also require D<TThe response time algorithm for fixed priorityscheduling works perfectly for values of D less thanT as long as the stopping criteria becomesWi n 1  DiIt also works perfectly well with any priorityordering — hp(i) always gives the set of higherpriority tasksAperiodic TasksThese do not have minimum inter-arrival timesCan run aperiodic tasks at a priority below thepriorities assigned to hard processes, therefore,they cannot steal, in a pre-emptive system,resources from the hard processesThis does not provide adequate support to softtasks which will often miss their deadlinesTo improve the situation for soft tasks, a server canbe employedExecution-time ServersA server:Has a capacity/budget of C that is available to itsclient tasks (typically aperiodic tasks)When a client runs it uses up the budgetThe server has a replenishment policyIf there is currently no budget then clients do notrunHence it protects other tasks from excessiveaperiodic activityPeriodic Server (PS)Budget CReplenishment Period T, starting at say 0Client ready to run at time 0 (or T, 2T etc) runswhile budget available, is then suspendedBudget ‘idles away’ if no clientsAnalyzed as a periodic taskDeferrable Server (DS)Budget CPeriod T – replenished every T time units (back toC)Anytime budget available clients can executeClient suspended when budget exhaustedDS is referred to as bandwidth preservingFor example 10ms every 50msRetain capacity as long as possiblePS is not bandwidth preservingTask Sets with D < TFor D = T, Rate Monotonic priority ordering isoptimalFor D < T, Deadline Monotonic priorityordering is optimalDi  D j  Pi  PjResponse time analysis is applicable “as is”to task sets with D ≤ TD < T Example Task SetTaskabcdPeriod Deadline ComputationTime Priority Response timeTDCPR2015102057102033434321361020Proof that DMPO is OptimalDeadline monotonic priority ordering (DMPO) isoptimal if any task set, Q, that is schedulable bypriority scheme, W, is also schedulable by DMPOThe proof of optimality of DMPO involvestransforming the priorities of Q (as assigned by W)until the ordering is DMPOEach step of the transformation will preserveschedulabilityDMPO Proof ContinuedLet i and j be two tasks (with adjacent priorities) in Qsuch that under W: Pi  Pj  Di  D j Define scheme W’ to be identical to W except that tasks iand j are swappedConsider the schedulability of Q under W’All tasks with priorities greater than Pi will be unaffectedby this change to lower-priority tasksAll tasks with priorities lower than Pj will be unaffected;they will all experience the same interference from i andjTask j, which was schedulable under W, now has a higherpriority, suffers less interference, and hence must beschedulable under W’DMPO Proof ContinuedAll that is left is the need to show that task i, which has hadits priority lowered, is still schedulableUnder WR j  D j , D j  Di and Di  TiHence task i only interferes once during the execution of jIt follows that:R'i  R j  D j  DiIt can be concluded that task i is schedulable after theswitchPriority scheme W’ can now be transformed to W" bychoosing two more tasks that are in the wrong order forDMP and switching themСПАСИБО ЗА ВНИМАНИЕhbd@cs.msu.suИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 3:Динамическое планирование вычисленийи оценка планируемости – 2Кафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.Fixed-Priority Scheduling (FPS)This is the most widely used approachEach task has a fixed, static, priority which iscomputer pre-run-timeThe runnable tasks are executed in the orderdetermined by their priorityIn real-time systems, the “priority” of a task isderived from its temporal requirements, not itsimportance to the correct functioning of the systemor its integrityEarliest Deadline First (EDF)The runnable tasks are executed in the orderdetermined by the absolute deadlines of the tasksThe next task to run being the one with theshortest (nearest) deadlineAlthough it is usual to know the relative deadlinesof each task (e.g.

25ms after release), the absolutedeadlines are computed at run time and hence thescheme is described as dynamicResponse Time Equation Ri Ri  Ci    C jjhp ( i ) T jWhere hp(i) is the set of tasks with priority higher than task iSolve by forming a recurrence relationship:win 1 win  Ci   Cjjhp ( i ) Tj 012nw,w,w,...,wThe set of values i i ii ,..

is monotonically non decreasing.When win  win 1 the solution to the equation has been found; wi0must not be greater that Ri (e.g. 0 or Ci )Mars PathfinderPriority Ceiling ProtocolA high-priority task can be blocked at most onceduring its execution by lower-priority tasksDeadlocks are preventedTransitive blocking is preventedMutual exclusive access to resources is ensured (bythe protocol itself)Response Time and BlockingRi  Ci  Bi  I i Ri Ri  Ci  Bi    C jjhp ( i )  T j nwi n 1wi  Ci  Bi    C jjhp ( i ) T jAn Extendible Task ModelSo far: Deadlines can be less than period (D<T) Sporadic and aperiodic tasks, as well as periodictasks, can be supported Task interactions are possible, with the resultingblocking being factored into the response timeequationsMore: Arbitrary Deadlines OffsetsArbitrary DeadlinesArbitrary DeadlinesTo cater for situations where D (and potentially R) > Tnw(q) n 1iwi ( q )  Bi  ( q  1)Ci   C jTj jhp ( i ) Ri (q)  win (q)  qTiThe number of releases is bounded by the lowest value of qfor which the following relation is true: R (q )  TiiThe worst-case response time is then the maximum valuefound for each q:Ri maxq  0 ,1, 2 ,...Ri (q)[A.

Burns, K. Tindell and A.J. Wellings.Fixed Priority Scheduling with Deadlines Prior to Completion]OffsetsSo far assumed all tasks share a common release time(critical instant)TaskTDCRa8544b201048c2012416With offsetsTaskTa8b20c20D51012C444O0010R488Arbitrary offsets arenot amenable toanalysisNon-Optimal AnalysisIn most realistic systems, task periods are not arbitrary butare likely to be related to one anotherAs in the example just illustrated, two tasks have a commonperiod.

In these situations it is ease to give one an offset (ofT/2) and to analyse the resulting system using atransformation technique that removes the offset — and,hence, critical instant analysis appliesIn the example, tasks b and c (having the offset of 10) arereplaced by a single notional process with period 10,computation time 4, deadline 10 but no offsetNotional Task ParametersTa TbTn  2 2Cn  Max(Ca , Cb )Dn  Min( Da , Db )Pn  Max( Pa , Pb )Can be extended to more than two processesNon-Optimal AnalysisProcessanT810D510C44O00R48Non-Optimal AnalysisThis notional task has two important properties: If it is schedulable (when sharing a critical instant with allother tasks) then the two real tasks will meet theirdeadlines when one is given the half period offset If all lower priority tasks are schedulable when sufferinginterference from the notional task (and all other highpriority tasks) then they will remain schedulable whenthe notional task is replaced by the two real tasks (onewith the offset)These properties follow from the observation that thenotional task always uses more (or equal) CPU time thanthe two real tasksInsufficient PrioritiesIf insufficient priorities then tasks must sharepriority levelsIf task a shares priority with task b, theneach must assume the other interferesPriority assignment algorithm can be used topack tasks togetherAda requires 31, RT-POSIX 32 and RT-Java28Upper Bound for PD TestN(Ti  Di )Ci / Ti La  max  D1 ,..., DN , i 11UU is the utilisation of the task set, note upper bound notdefined for U=1[U.C.

Devi. An Improved Schedulability Test for UniprocessorPeriodic Task Systems]PD Test with BlockingСПАСИБО ЗА ВНИМАНИЕhbd@cs.msu.suИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 4:Статико-динамическое планирование вычисленийв системах интегрированной модульной авионикиКафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.Федеративная ИУС РВФедеративная ИУС РВ• Специализированные блоки– по назначению– по архитектуре• ПО различных подсистем – на различныхблоках– изоляция по памяти– нет конкуренции подсистем за процессорноевремя• Недостатки:– низкая переносимость и повторнаяиспользуемость ПО– «зоопарк» процессорных архитектур ипрограммных интерфейсовИУС РВ c архитектурой ИМАИУС РВ с архитектурой ИМАс сетью на базе коммутатораВычисленияВычисленияВычисленияВычисленияВычисленияКоммутаторВычисленияКоммуникацииКоммуникацииГрафикаГрафикаИУС РВ c архитектурой ИМА• Логически единый распределенныйвычислитель– унифицированные модули нескольких типов– единая архитектура процессоров– унифицированный программный интерфейс• Разделение вычислительных ресурсовмежду ПО различных подсистем• Проблемы:– изоляция по памяти– разделение процессорного времени• Решение: каждой подсистеме  разделИМА и разработка ПО• Особенности:– Стандартное API со стороны ОС– Статическое разделение времени, памятии ресурсов• Преимущества:– Надежность– Переносимость– Возможность повторного использования– Модульность– Упрощение верификации и сертификацииСтруктура ПО.

Характеристики

Список файлов лекций