- Cynthia Mavros and Ray Obenza
Guaranteeing Real-Time Performance Using RMA
Embedded Systems Conference, San Jose, CA, September 12-15 1995
Presentation slides of basics: real-time system goals are fast response, guaranteed deadlines, and stability in overload (critical deadlines still met even if all deadlines can't be met. Rate monotonic scheduling assigns highest priorities to tasks of highest rates (assuming uniprocessor, periodic tasks, independent tasks, task deadlines at end of period, no interrupts or task suspension, and no context switch overhead). Rate monotonic analysis is used to determine schedulability and reason about system timing behavior. First, the sum of all task utilizations (CPU time required per period of time) is less than a utilization bound (which is a function of the number of tasks), then the task set is schedulable. If this conservative test fails, then the response-time test can be applied: for independent, periodic tasks, if each task meets its first deadline with worst-case task phasing, then the deadlines can be met.
Extensions: context switching can be modelled as increased execution time. Preperiod deadlines can be handled with a modified utilization bound. Interrupts can be handled by analyzing the utilization of each task individually, and adding terms to account for possible preemption by other (higher priority) tasks.
Priority inversion can be caused by synchronization and mutual exclusion, non-preemptable code regions, and FIFO queues. Handled similar to interrupts, by adding a term to account for inversion. Synchronization protocols such as no preemption, priority inheritance, highest locker's priority, and priority ceiling can bound priority inversion. Aperiodic tasks can be handled with sporadic servers by modeling as periodic tasks, with a fixed execution budget C in replenishment interval T, and then assigning priorities.
The presentation finishes with an interesting case study. A six-event system that was not designed with RMS was analyzed with RMA. Net result: redesigned the schedule to be feasible, requiring 3 people 3 weeks of effort.
- [:]
Ashish Mehra, Atri Iniresan, and Kang G. Shin
``Structuring Communication Software for Quality-of-Service Guarantees''
IEEE Transactions on Software, 23(10), October 1997
Very interesting discussion of the architectural considerations for providing QoS guarantees in host communication software.
- Sathis Menon, Partha Dasgupta, and Richard J. LeBlanc, Jr.
``Asynchronous Event Handling in Distributed Object-Based Systems''
Discusses event handling in passive, object-based environments. Identifies the necessity for both thread-based and object-based event notification.
It isn't directly relevant to our problem because:
- it is aimed at passive object-based environments
- it allows threads to span processors
- it allows objects to move across processors
I'm not completely sure what they mean by event; I thought that event delivery is always asynchronous. The last paragraph of the Section 3 introduction confirms that. But in the introduction to Section 5, the authors say the are going to discuss ``synchronous and asynchronous delivery''. Does that really mean ``notification'', which is from the perspective of the object that initiates the event?
- Klara Nahrstedt and Jonathan M. Smith
``End-toEnd QoS Guarantees: Lessons Learned from OMEGA''
Experience report on an implementation of OMEGA architecture on a telerobotics application. OMEGA is an end-point architecture for provision of end-to-end QoS guarantees. Interesting for systems that must support QoS provision and negotiation; for us, that won't be until we get to dynamic scheduling.
The lessons learned about using AIX for real-time applications suggest that it isn't a good a real-time platform as Solaris. In particular, it had to be restricted to having only one user (does AIX have a real-time scheduling class with higher priority than all others?). They also restricted the implementation of the application and transport protocols to a single user process, and used joint scheduling by the protocol stack (what does that mean?). They recognize that their scheduler implementation has major limitations, but it's not discussed further here (they reference Nahrstedt's PhD thesis).
- [PublisherSubscriber:95]
Ragunathan Rajkumar, Mike Gagliardi, and Lui Sha
``The Real-Time Publisher/Subscriber Inter-Process Communication Model for Distributed Real-Time Systems: Design and Implementation''
First IEEE Real-Time Technology and Applications Symposium, May 1995.
Describes the real-time publisher/subscriber model. It looks a lot like our Event Channel, with publishers analogous to suppliers and subscribers analogous to consumers. They don't appear to have a QoS specification mechanism, though. It looks like scheduling is based on thread properties, which aren't addressed by the publisher/subscriber model. One interesting aspect of the model is the notion of separating priorities for subscription and data transfer, because those activities are handled by different threads.
- Lui Sha and John B. Goodenough
Real-Time Scheduling Theory and Ada
Computer 23:4, April 1990
Lists these measures of merit for real-time systems:
- predictably fast response to urgent events
- high degree of schedulability, which is the maximum degree of resource utilization at which task timing requirements can be met
- stability under transient overload: the ability to guarantee the deadlines of selected tasks
Reviews rate monotonic theory. For a set of independent periodic tasks, higher (fixed) priorities are assigned to tasks with shorter periods.
Theorem 1: A set of n independent periodic tasks scheduled by the rate monotonic algorithm will always meet its deadlines, for all task phasings, if C_1/T_1 + ... + C_n/T_n <= n(2**1/n - 1) = U(n)
where C_i and T_i are the execution time and period of task i, respectively. U(n) characterizes schedulability and converges to 69 percent (ln 2) as n approaches infinity.
A less pessimistic test is based on the critical zone theorem:
Theorem 2: For a set of independent periodic tasks, if each task meets its first deadline when all tasks are started at the same time, then the deadlines will always be met for any combination of start times.
If a critical task is excluded from the schedulable set, it might be possible to include it by using period transformation. The period of the task is reduced, so that it only performs part of its processing in each smaller period. This could allow its priority to be raised.
Next, scheduling of both aperiodic and periodic tasks is considered. If an aperiodic task can preempt a periodic task, then it's response time can typically be drastically reduced. Sporadic servers service aperiodic events but can be scheduled usings Theorems 1 and 2, because they are viewed as periodic tasks that perform polling.
Priority inversion, in which a high priority task is delayed by a lower priority task, can occur when the high priority task is blocked by another. The priority ceiling protocol, in which a low priority task inherits the priorities of higher tasks when executing, can help alleviate this problem.
Guidelines for programming real-time systems in Ada in order to support rate monotonic analysis are presented. They include sharing data between periodic tasks using a monitor, rather than calling each other directly. Most of the remainder of the guidelines have to do with priorities.
- Lui Sha, Ragunathan Rajkumar, John Lehoczky, and Krithi Ramamritham
``Mode Change Protocols for Priority-Driven Preemptive Scheduling''
J. Real-Time Systems, Vol. 1, 1989, pp. 243-264
Reprinted in John A. Stankovic and Krithi Ramamritham, Advances in Real-Time Systems, IEEE Computer Society Press, 1992.
Discusses mode changes, due to addition, deletion, or parameter changes of tasks. Presents a mode change protocol that is compatible with rate monotonic analysis. The protocol models a task parameter change as a task deletion/task addition pair. The protocol shows how to handle semaphores that are used for task synchronization. The analysis looks like a straightforward augmentation to RMS, and very useful.
The paper does not discuss the application-specific aspects of mode changes, such as deciding the task changes and the order in which they should be implemented. And the really hard issues, like deciding what each task should do when the ``global'' mode changes.
- Lui Sha and Shirish S. Sathaye
``A Systematic Approach to Designing Distributed Real-Time Systems''
Computer 26:9, September 1993, pp. 68-78
Describes extensions to generalized rate monotonic scheduling (GRMS) to support distributed systems. Schedulability is extended to include the delay a message incurs reaching its destination on a network, which includes the transmission delay and propagation delay. Preemption in distributed systems is more complicated than in centralized systems because increasing preemptability doesn't always lead to minimizing priority inversion. In special (over-preemption) situations, preemption does not reduce the worst-case duration of priority inversion.
The authors address over-preemption with a preemption control protocol. It includes phase control and rate control. The authors discusses analysis of systems that weren't designed to support GRMS. They quantify the effect on schedulability of limiting the granularity of priority. There are several detailed examples, I didn't go through them yet.
- Marc Shepard
``Managing Delays for Optimal Real-Time Performance''
Electronic Design Embedded Controllers Applications Issue, 1 October 1993, reprinted by Wind River Systems
Very brief, introductory discussion of delays due to priority assignment (scheduling), shared critical regions (access to shared resources), and interrupt lockouts. Common scheduling strategies include greater importance, most frequent deadlines (rate monotonic), and dynamic priorities. Greater importance has the disadvantage that short tasks that aren't as important as longer ones may not be scheduled frequently enough to always meet their deadlines. Rate monotonic has the disadvantage that tasks with infrequent deadlines may not be scheduled at sufficiently high priority. Dynamic priorities attempts to address this deficiency by raising a the priority of a task as its deadline approaches. It has the disadvantage of requiring additional overhead. Discussion of the other contributors to delay is also brief: critical regions, interrupt disable intervals, and interrupt service routines should be as short as possible.
- David B. Stewart and Pradeep K. Khosla
``Real-Time Scheduling of Sensor-Based Control Systems''
Real-Time Programming, ed. by W. Halang and K. Ramamritham, (Tarrytown, New York: Pergamon Press Inc.), 1992.
Interesting article that proposes a new scheduling algorithm, maximum-urgency-first (MUF), which combines the advantages of rate-monotonic, earliest-deadline first, and minimum laxity first scheduling algorithms. It has a schedulable bound of 100 percent for the critical set, the critical set is guaranteed to meet all of its deadlines, and it allows the scheduler to detect missed deadlines and notify the offending/affected tasks. MUF is the default scheduler for the Chimera RTOS. It is best suited to dynamic scheduling applications.
- David B. Stewart and Pradeep K. Khosla
``Mechanisms for Detecting and Handling Timing Errors''
Communications of the ACM 40:1, January 1997, pp. 87-93
Interesting article on kernel support for detection and handling of timing errors in hard and soft real-time systems. Timing errors include missed deadlines due to failure to complete execution on time, and incorrect estimates of execution time. (Though I think the distinction isn't clear for underestimates. It is useful for overestimates, which can lead to underutilization.)
The mechanisms are policy-independent, and have been incorporated into the Chimera RTOS. The overhead per rescheduler operation on a 25 MHz MC68030 is less than 1 microsecond.
This approach is most useful in hard-real time systems that need to handle thread overrun. The authors discuss some applications to soft real-time systems, using an application-specific policy such as ``borrowing'' execution time from the threads next execution cycle. Imprecise computations and adaptive (dynamic) real-time scheduling can be readily handled with this approach as well.
- [SunRT:95] Sun Microsystems
``Realtime Programming and Administration''
Sun System Interfaces Guide -- November 1995
Useful information about realtime programming on Suns: scheduling classes, memory locking, early dynamic linking, IPC, asynchronous I/O, asynchronous networking, and time functions. See also [KSZ:92].
Good intro to fixed priority scheduling.
- Hideyuki Tokuda and Tatsuo Nakajima
``Evaluation of Real-Time Synchronization in Real-Time Mach''
Proceedings of the USENIX Mach Symposium, November 20-22, 1991.
Interesting discussion of the synchronization model and primitives in Real-Time Mach. Several synchronization policies, namely kernelized monitor, basic priority, basic priority inheritance, priority ceiling, and restartable critical sections, are supported. Includes measurements of their execution time cost on a 25 MHz MC68030:
| Execution Time for Lock/Unlock Operation Pair with Single Thread | |
|---|---|
| Locking protocol | Lock/unlock time, microseconds |
| kernelized monitor | |
| basic priority | |
| basic priority inheritance | |
| priority ceiling | |
| restartable critical section | |
- [WBTK:95]
Victor Fay-Wolfe, John K. Black, Bhavanai Thuraisingham, and Peter Krupp
``Real-time Method Invocations in Distributed Environments''
University of Rhode Island, Department of Computer Science and Statistics Technical Report 95-244, 1995.
This paper describes the essential element to real-time CORBA extensions: how to do timed, distributed method invocations in a CORBA environment.
- [URI_RT_CORBA:97]
Victor Fay-Wolfe, Lisa Cingiser DiPippo, Roman Ginis, Michael Squandrito, Steven Wohlever, Igor Zykh,and Russell Johnston
``Real-Time CORBA''
Real-Time Technology and Applications Symposium '97, Montreal, Quebec, Canada
Describes requirements for real-time extensions to CORBA, and surveys current efforts.
Discusses the US Navy NRaD/University of Rhode Island (URI) RT CORBA system, which supports expression and enforcement of end-to-end timing constraints. Timing constraints are supported through timed distributed method invocations ({\tt TDMI}s); a {\tt TDMI} corresponds to TAO's {\tt RT\_Operation}; an {\tt RT\_Environment} structure contains QoS parameters similar to those in TAO's {\tt RT\_Info}. One difference between the two approaches is that {\tt TDMI}s express required timing constraints, {\em e.g.}, deadlines relative to the current time, while {\tt RT\_Operation}s publish their resource, {\em e.g.}, CPU time, requirements. The difference in approaches may reflect the different time scales, seconds versus milliseconds, respectively, and scheduling requirements, dynamic versus static, of the initial application targets. However, the approaches should be equivalent with respect to system schedulability and analysis. In addition, NRaD/URI supply a new CORBA Global Priority Service, analogous to TAO's Scheduling Service, and augment the CORBA Concurrency and Event Services. The initial implementation uses {\em earliest-deadline-first within importance level} dynamic, on-line scheduling, supported by global priorities. A global priority is associated with each {\tt TDMI}, and all processing associated with that TDMI inherits that priority. In contrast, TAO's scheduling is initially static and off-line, and uses importance as a ``tie-breaker'' following the analysis of other requirements such as data dependencies. Both NRaD/URI and TAO readily support changing scheduling policy by encapsulating it in their respective CORBA Global Priority and Scheduling Services.
- [XP:90]
Jia Xu and David Lorge Parnas
``Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations''
IEEE Trans. Software Engineering 16:3, March 1990, 360 - 369
Presents an algorithm for finding an optimal static schedule on a single processor. Interesting in that it considers precedence and exclusion relations. Benefits include elimination of the use of (costly) synchronization and mutual exclusion mechanisms, because all execution is pre-arranged to satisfy the specified precedence and exclusion relations. Similarly, the unpredictability and context switching cost of interrupts are eliminated, because they are handled synchronously. Our RT_Info would work very well for specifying thread parameters with this approach, after just adding specification of exclusion relations.
- [XP:93]
Jia Xu and David Lorge Parnas
``On Satisfying Timing Constraints in Hard-Real-Time Systems''
IEEE Trans. Software Engineering 19:1, January 1993, 70 - 84
Interesting survey and discussion of important issues in static scheduling. Very useful in explaining the motivation behind XP:90.
- Matthew J. Zelesko and David R. Cheriton
``Specializing Object-Oriented RPC for Functionality and Performance'' - (not reviewed)
- John A. Zinky, David E. Bakken, and Richard Schantz
``Overview of Quality of Service for Objects'' - Extends CORBA IDL with a quality of service description language (QDL). That's an interesting and useful approach to handling QoS, and the paper discusses some relevant issues such as end-to-end QoS, proxy objects, connection state (with a probably canonical example), adaptivity, and multiple connections. QDL isn't really described in this paper, but the authors do have some presentation slides with examples. From those, it appears that we'll have to develop our own QoS specification language.
- 上一篇： Real-Timearticlesummaries2
- 下一篇： 关于NP-hard问题
-
精密半导体参数测试解决方案 直播时间： 01月08日 10:00
/3 
文章评论（0条评论）
登录后参与讨论