Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 70
Текст из файла (страница 70)
It generates a dispatching tablefor the run-time dispatcher off-line. For this purpose it needs complete priorknowledge about the task-set characteristics, e.g., maximum execution times,precedence constraints, mutual exclusion constraints, and deadlines. The dispatching table (see Fig. 9.2) contains all information the dispatcher needs at run time todecide at every point of the sparse time-base which task is to be scheduled next.
Therun-time overhead of the dispatcher is small. The system behavior is deterministic.A scheduler is called dynamic (or on-line) if it makes its scheduling decisions atrun time, selecting one out of the current set of ready tasks. Dynamic schedulers areflexible and adapt to an evolving task scenario. They consider only the current taskrequests. The run-time effort involved in finding a schedule can be substantial.
Ingeneral, the system behavior is non-deterministic.Non-preemptive and Preemptive Scheduling. In non-preemptive scheduling, thecurrently executing task will not be interrupted until it decides on its own to releasethe allocated resources. Non-preemptive scheduling is reasonable in a task scenariowhere many short tasks (compared to the time it takes for a context switch) must beexecuted.
In preemptive scheduling, the currently executing task may be preempted, i.e., interrupted, if a more urgent task requests service.Centralized Versus Distributed Scheduling. In a dynamic distributed real-timesystem, it is possible to make all scheduling decisions at one central site or tosoftreal-time schedulingdynamichardstaticFig. 10.1 Taxonomy of real-time scheduling algorithmspreemptivepreemptivenon-preemptivenon-preemptive10.1 The Scheduling Problem241develop cooperative distributed algorithms for the solution of the schedulingproblem.
The central scheduler in a distributed system is a critical point of failure.Because it requires up-to-date information on the load situations of all nodes, it canalso contribute to a communication bottleneck.10.1.2Schedulability TestA test that determines whether a set of ready tasks can be scheduled such that eachtask meets its deadline is called a schedulability test. We distinguish between exact,necessary, and sufficient schedulability tests (Fig. 10.2).A scheduler is called optimal if it will always find a feasible schedule wheneverit exists.
Alternatively, a scheduler is called optimal, if it can find a schedulewhenever a clairvoyant scheduler, i.e., a scheduler with complete knowledge ofthe future request times, can find a schedule. Garey and Johnson [Gar75] haveshown that in nearly all cases of task dependency, even if there is only one commonresource, the complexity of an exact schedulability test algorithm belongs to theclass of NP-complete problems and is thus computationally intractable. Sufficientschedulability test algorithms can be simpler at the expense of giving a negativeresult for some task sets that are, in fact, schedulable.
A task set is definitely notschedulable if a necessary schedulability test gives a negative result. If a necessaryschedulability test gives a positive result, there is still a probability that the task setmay not be schedulable. The task request time is the instant when a request for atask execution is made. Based on the request times, it is useful to distinguishbetween two different task types: periodic and sporadic tasks. This distinction isimportant from the point of view of schedulability.If we start with an initial request, all future request times of a periodic taskare known a priori by adding multiples of the known period to the initial requesttime. Let us assume that there is a task set {Ti} of periodic tasks with periods pi,deadline interval di, and execution time ci.
The deadline interval is the durationbetween the deadline of a task and the task request instant, i.e., the instant when atask becomes ready for execution. We call the difference di ci the laxity li of atask. It is sufficient to examine schedules of length of the least common multiplesof the periods of these tasks, the schedule period, to determine schedulability.if the sufficient schedulabilitytest is positive, these tasks aredefinitely schedulablesufficientschedulability testif the necessary schedulabilitytest is negative, these tasks aredefinitely not schedulableexactschedulability testnecessaryschedulability testincreasing task set complexityFig.
10.2 Necessary and sufficient schedulability test24210 Real-Time SchedulingA necessary schedulability test for a set of periodic tasks states that the sum ofthe utilization factorsm¼Xci =pi bn,must be less or equal to n, where n is the number of available processors. This isevident because the utilization factor of task Ti, mi, denotes the percentage of timetask Ti requires service from a processor.The request times of sporadic tasks are not known a priori.
To be schedulable, theremust be a minimum interval between any two request times of sporadic tasks.Otherwise, the necessary schedulability test introduced above will fail. If there is noconstraint on the request times of task activations, the task is called an aperiodic task.10.1.3 The Adversary ArgumentLet us assume that a real-time computer system contains a dynamic scheduler withfull knowledge of the past but without any knowledge about future request times oftasks.
Schedulability of the current task set may depend on when a sporadic taskwill request service in the future.The adversary argument [Mok93, p. 41] states that, in general, it is not possibleto construct an optimal totally on-line dynamic scheduler if there are mutualexclusion constraints between a periodic and a sporadic task. The proof of theadversary argument is relatively simple.Consider two mutually exclusive tasks, task T1 is periodic and the other task T2is sporadic, with the parameters given in Fig. 10.3. The necessary schedulability testintroduced above is satisfied, becausem ¼ 2=4 þ 1=4 ¼ 3=4b1:Whenever the periodic task is executing, an adversary requests service for thesporadic task. Due to the mutual exclusion constraint, the sporadic task must waituntil the periodic task is finished.
Since the sporadic task has a laxity of 0, it willmiss its deadline.conflictconflictT2T1T1T2 T1: c=2, d=4, p=4, periodicT2: c=1, d=1, p=4, sporadicT1T1 and T2 are mutually exclusiveT2 clairvoyantscheduler shiftstask T167T2T11234Fig. 10.3 The adversary argument5810.2 Worst-Case Execution Time243The clairvoyant scheduler knows all the future request times of the sporadictasks and at first schedules the sporadic task and thereafter the periodic task in thegap between two sporadic task activations (Fig. 10.3).The adversary argument demonstrates the importance of information about thefuture behavior of tasks for solving the scheduling problem.
If the on-line schedulerdoes not have any further knowledge about the request times of the sporadic task,the dynamic scheduling problem is not solvable, although the processor capacity ismore than sufficient for the given task scenario. The design of predictable hard realtime systems is simplified if regularity assumptions about the future schedulingrequests can be made. This is the case in cyclic systems that restrain the points intime at which external requests are recognized by the computing system.10.2Worst-Case Execution TimeA deadline for completing an RT transaction can only be guaranteed if the worstcase execution times (WCET) of all application tasks and communication actionsthat are part of the RT-transaction are known a priori. The WCET of a task is aguaranteed upper bound for the time between task activation and task termination.It must be valid for all possible input data and execution scenarios of the task andshould be a tight bound.In addition to the knowledge about the WCET of the application tasks, we mustfind an upper bound for the delays caused by the administrative services of theoperating system, the worst-case administrative overhead (WCAO).
The WCAOincludes all administrative delays that affect an application task but are not underthe direct control of the application task (e.g., those caused by context switches,scheduling, cache reloading because of task preemption by interrupts or blocking,and direct memory access).This section starts with an analysis of the WCET of a non-preemptive simpletask. We then proceed to investigate the WCET of a preemptive simple task beforelooking at the WCET of complex tasks and, finally, we discuss the state of the artregarding the timing analysis of real-time programs.10.2.1 WCET of Simple TasksThe simplest task we can envision is a single sequential S-task that runs ondedicated hardware without preemption and without requiring any operating systemservices.
The WCET of such a task depends on:1. The source code of the task2. The properties of the object code generated by the compiler3. The characteristics of the target hardware24410 Real-Time SchedulingIn this section, we investigate the analytical construction of a tight worst-caseexecution time bound of such a simple task on hardware, where the execution timeof an instruction is context independent.Source Code Analysis. The first problem concerns the calculation of the WCET of aprogram written in a higher-level language, under the assumption that the maximumexecution times of the basic language constructs are known and context independent.In general, the problem of determining the WCET of an arbitrary sequential programis unsolvable and is equivalent to the halting problem for Turing machines.
Consider,for example, the simple statement that controls the entry to a loop:S: whileðexpÞdo loop;It is not possible to determine a priori after how many iterations, if at all, theBoolean expression exp will evaluate to the value FALSE and when statement Swill terminate. For the determination of the WCET to be a tractable problem thereare a number of constraints that must be met by a the program [Pus89]:1. Absence of unbounded control statements at the beginning of a loop2. Absence of recursive function calls3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
