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

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫРЕАЛЬНОГО ВРЕМЕНИЛекция 2:Динамическое планирование вычисленийи оценка планируемости - 1Кафедра АСВК,Лаборатория Вычислительных КомплексовБалашов В.В.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 dynamicFPS v EDFFPS is easier to implement as priorities are staticEDF is dynamic and requires a more complex runtime system which will have higher overheadIt is easier to incorporate tasks without deadlinesinto FPS; giving a task an arbitrary deadline is moreartificialIt is easier to incorporate other factors into thenotion of priority than it is into the notion of deadlineFPS v EDFDuring overload situations FPS is more predictable; Low priority process misstheir deadlines first EDF is unpredictable; a domino effect can occur inwhich a large number of processes miss deadlinesBut EDF gets more out of the processor!PreemptionWith priority-based scheduling, a high-priority task may bereleased during the execution of a lower priority oneIn a preemptive scheme, there will be an immediate switchto the higher-priority taskWith non-preemption, the lower-priority task will be allowedto complete before the other executesPreemptive schemes enable higher-priority tasks to bemore reactive, and hence they are preferredScheduling CharacteristicsSufficient – pass the test will meet deadlinesNecessary – fail the test will miss deadlinesExact – necessary and sufficientSustainable – system stays schedulable ifconditions ‘improve’Simple Task ModelThe application is assumed to consist of a fixed set of tasksAll tasks are periodic, with known periodsThe tasks are completely independent of each otherAll system's overheads, context-switching times and so onare ignored (i.e, assumed to have zero cost)All tasks have a deadline equal to their period (that is, eachtask must complete before it is next released)All tasks have a fixed worst-case execution timeStandard NotationBCDINPRTUWorst-case blocking time for the task (if applicable)Worst-case computation time (WCET) of the taskDeadline of the taskThe interference time of the taskNumber of tasks in the systemPriority assigned to the task (if applicable)Worst-case response time of the taskMinimum time between task releases, jobs, (task period)The utilization of each task (equal to C/T)Rate Monotonic Priority AssignmentEach task is assigned a (unique) priority based on itsperiod; the shorter the period, the higher the priorityi.e, for two tasks i and j,T i  T j  Pi  P jThis assignment is optimal in the sense that if any taskset can be scheduled (using pre-emptive priority-basedscheduling) with a fixed-priority assignment scheme,then the given task set can also be scheduled with arate monotonic assignment schemeNote, priority 1 is the lowest (least) priorityExample Priority AssignmentProcessabcdePeriod, T25604210575Priority, P53412Response 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 )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.