Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 74
Текст из файла (страница 74)
In case this first sufficient schedulability test fails, more complex sufficient tests can be found in [Sha90]. The priorityceiling protocol is a good example of a predictable, but non-deterministic scheduling protocol.10.5 Alternative Scheduling Strategies255Example: The NASA Pathfinder robot on MARS experienced a problem that was diagnosed as a classic case of priority inversion, due to a missing priority ceiling protocol.
Thefull and most interesting story is contained in [Jon97]:Very infrequently it was possible for an interrupt to occur that caused the (mediumpriority) communications task to be scheduled during the short interval while the (highpriority) information bus thread was blocked waiting for the (low priority) meteorologicaldata thread. In this case, the long-running communications task, having higher prioritythan the meteorological task, would prevent it from running, consequently preventing theblocked information bus task from running.
After some time had passed, a watchdogtimer would go off, notice that the data bus task had not been executed for some time,conclude that something had gone drastically wrong, and initiate a total system reset.10.5Alternative Scheduling Strategies10.5.1 Scheduling in Distributed SystemsIn a control system, the maximum duration of an RT transaction is the criticalparameter for the quality of control, since it contributes to the dead time of a controlloop. In a distributed system, the duration of this transaction depends on the sum of thedurations of all processing and communication actions that form the transaction. Insuch a system, it makes sense to develop a holistic schedule that considers all theseactions together.
In a time-triggered system, the processing actions and the communication actions can be phase aligned (see Sect. 3.3.4), such that a send slot in the communication system is available immediately after the WCET of a processing action.It is already difficult to guarantee tight deadlines by dynamic scheduling techniques in a single processor event-triggered multi-tasking system if mutual exclusion and precedence constraints among the tasks must be considered.
The situationis more complex in a distributed system, where the non-preemptive access to thecommunication medium must be considered. Tindell [Tin95] analyzes distributedsystems that use the CAN bus as the communication channel and establishesanalytical upper bounds to the communication delays that are encountered by aset of periodic messages. These results are then integrated with the results of thenode-local task scheduling to arrive at the worst-case execution time of distributedreal-time transactions.
One difficult problem is the control of transaction jitter.Since the worst-case duration of a RT transaction in an event-triggered distributedsystem can be exceedingly pessimistic, some researchers are looking at dynamic besteffort strategies and try to establish bounds based on a probabilistic analysis of thescheduling problem. This approach is not recommended in hard-real time systems,since the characterization of rare events is extremely difficult. Rare event occurrencesin the environment, e.g., a lightning stroke into an electric power grid, will cause ahighly correlated input load on the system (e.g., an alarm shower) that is very difficultto model adequately.
Even an extended observation of a real-life system is notconclusive, because these rare events, by definition, cannot be observed frequently.25610 Real-Time SchedulingIn soft real-time systems (such as multimedia systems) where the occasionalmiss of deadline is tolerable, probabilistic analysis is widely used. An excellent surveyon the results of 25 years of research on real-time scheduling is contained in [Sha04].10.5.2 Feedback SchedulingThe concept of feedback, well established in many fields of engineering, usesinformation about the actual behavior of a scheduling system to dynamically adaptthe scheduling algorithms such that the intended behavior is achieved.
Feedbackscheduling starts with the establishment and observation of relevant performanceparameters of the scheduling system. In a multimedia systems, the queue size thatdevelops before a server process is an example of such a relevant performanceparameter. These queue sizes are continuously monitored and the producer ofinformation is controlled – either slowed down or speeded up – in order to keep thesize of the queue between given levels, the low and high watermark.By looking at the scheduling problem and control problem in an integratedfashion, better overall results can be achieved in many control scenarios. Forexample, the sample rate of a process can be dynamically adjusted based on theobserved performance of the physical process.Points to RememberlllllA 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.
A scheduler is calledstatic (or pre-run-time) if it makes its scheduling decisions at compile time. Itgenerates a dispatching table for the run-time dispatcher off-line.A test that determines whether a set of ready tasks can be scheduled so that eachtask meets its deadline is called a schedulability test. We distinguish betweenexact, necessary, and sufficient schedulability tests. In nearly all cases of taskdependency, even if there is only one common resource, the complexity of anexact schedulability test algorithm belongs to the class of NP-complete problemsand is thus computationally intractable.While the future request times of a periodic task are known a priori, only the minimum interarrival time of a sporadic task is known in advance.
The actual points intime when a sporadic task must be serviced are not known ahead of the request event.The adversary argument states that, in general, it is not possible to construct anoptimal totally on-line dynamic scheduler if there are mutual exclusion constraints between a periodic and a sporadic task. The adversary argument accentuates the value of a priori information about the behavior in the future.In general, the problem of determining the worst-case execution time (WCET) of anarbitrary sequential program is unsolvable and is equivalent to the halting problemfor Turing machines. The WCET problem can only be solved, if the programmerprovides additional application-specific information at the source code level.Bibliographic Notesllllllllll257In static or pre-run-time scheduling, a feasible schedule of a set of tasks thatguarantees all deadlines, considering the resource, precedence, and synchronization requirements of all tasks, is calculated off-line.
The construction of sucha schedule can be considered as a constructive sufficient schedulability test.The rate monotonic algorithm is a dynamic preemptive scheduling algorithmbased on static task priorities. It assumes a set of periodic and independent taskswith deadlines equal to their periods.The Earliest-Deadline-First (EDF) algorithm is a dynamic preemptive scheduling algorithm based on dynamic task priorities.
The task with the earliestdeadline is assigned the highest dynamic priority.The Least-Laxity (LL) algorithm is a dynamic preemptive scheduling algorithmbased on dynamic task priorities. The task with the shortest laxity is assigned thehighest dynamic priority.The priority ceiling protocol is used to schedule a set of periodic tasks that haveexclusive access to common resources protected by semaphores. The priorityceiling of a semaphore is defined as the priority of the highest priority task thatmay lock this semaphore.According to the priority ceiling protocol, a task T is allowed to enter a criticalsection only if its assigned priority is higher than the priority ceilings of allsemaphores currently locked by tasks other than T. Task T runs at its assignedpriority unless it is in a critical section and blocks higher priority tasks.
In thiscase, it inherits the highest priority of the tasks it blocks. When it exits the criticalsection, it resumes the priority it had at the point of entry into the critical section.The critical issue in best-effort scheduling concerns the assumptions about theinput distribution. Rare event occurrences in the environment will cause a highlycorrelated input load on the system that is difficult to model adequately.
Even anextended observation of a real-life system is not conclusive, because these rareevents, by definition, cannot be observed frequently.In soft real-time systems (such as multimedia systems) where the occasionalmiss of deadline is tolerable, probabilistic scheduling strategies are widely used.Anytime algorithms are algorithms that improve the quality of the result as moreexecution time is provided. They consist of a root segment that calculates a firstapproximation of the result of sufficient quality and a periodic segment thatimproves the quality of the previously calculated result.In feedback scheduling, information about the actual behavior of a schedulingsystem is used to dynamically adapt the scheduling algorithms such that theintended behavior is achieved.Bibliographic NotesStarting with the seminal work of Liu and Layland [Liu73] in 1973 on schedulingof independent tasks, hundreds of papers on scheduling are being published eachyear. In 2004 the Real-Time System Journal published a comprehensive survey25810 Real-Time SchedulingReal-Time Scheduling Theory: A Historical Perspective [Sha04].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
