The last section of the paper is ``Performance Analysis''. It discusses priority assignment and timing analysis. Priority assignment is based on pairwise comparison of process importance, repeated methodically (and mechanically) until all possible pairings have been analyzed. It looks like a good approach: priorities are global, so this gets there eventually. It's different than, but maybe a useful extension to handle importance to, rate monotonic scheduling.
The timing analysis isn't as rigorous as we need. The authors suggest estimating durations of services, taking into account the effects of message passing and synchronization, and checking the most critical event sequence. We need more precision and assurance that all sequences have been checked.
A few examples: on a Motorola MVME 147S board with a 25 MHz 68030 processor, a VxWorks context switch takes 18 microseconds; on a 25 MHz MVME-167 board, it takes 4 microseconds. The time to get and release a semaphore on the 147S is 11 microseconds.
The scheduling system has a two-level hierarchy. Each real-time application has its own constant utilization server, and all non-real-time applications share a single constant utilization server. The constant utilization servers are responsible for dispatching for their application(s), and have a fixed size U that reflects their application(s)' CPU time requirements. The lower level OS schedule coordinates the constant utilization servers. It also decides whether to admit new applications, based on comparison of the sum of the current total U with that of the new application, with the processor speed.
This seems like a good approach. The constant utilization servers may map nicely to LWPs on Solaris.
Well presented and interesting, but primarily for systems that can take advantage of imprecise calculations where the more time that can be spent by a task on calculating a result, the better the result. Our application doesn't lend itself to that, at least initially. The lower level allocation across component tasks is similar to what we do when allocating CPU time to operations in a thread.
| Ordering Mechanisms | ||||
|---|---|---|---|---|
| Real-time stamps | Logical time stamps | |||
| Effects | local clocks | global clock | totally ordered | partially ordered |
| Multiple observers see different orderings | ||||
| Incorrectly perceived orderings | ||||
| Same computation exhibits different orderings | ||||
| Arbitrary orderings adopted | ||||
Another byproduct of the target application is that scheduling is dynamic, and uses modified (simplified to account for delayed preemption) rate monotonic. This application decomposes nicely into iterative handlers. Maximizing CPU utilization is important. For some other real-time applications, these assumptions and goals may not apply, of course. But, if they do, and the application can live with the delayed preemption, then the performance benefits should be significant.
It defines some useful terms, which are expressed in our terms here:
For the special case in which the period of each task is a multiple of the period of each lower priority task, the least upper bound on processor utilization is 1.
(I wrote this out instead of using an equation because that doesn't work too well with HTML 2.0. Task utilization is the ratio of a task's execution time to its period.)
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.
It isn't directly relevant to our problem because:
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?
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).
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.
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.
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.
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.
| 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 | |
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.