Лекция 3. Динамическое планирование 2 (Лекции 2015-2016)

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 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.