Topic: hard real time systems

topics > computer science > Group: parallel processing

process control

action chunks
for loop
interrupt handler
non-preemptive task scheduling
plan-based task scheduling
programming without errors
proving concurrent programs
real time systems
safety critical systems
safety, liveness, and system properties
synchronized processing
task scheduling

Subtopic: control systems up

Quote: acyclic, embedded control systems do not have zero-delay loops; e.g., sample-driven, compute outputs on each clock tick [»benvA1_2003]
Quote: fixpoint control treats each reaction as the unique fixpoint for 'state+input -> state+output'; e.g., Esterel; difficult to prove unique [»benvA1_2003]
Quote: constrained control systems may allow blocked reactions or multiple, nondeterministic reactions; proving uniqueness is difficult; e.g., Signal and Sildex [»benvA1_2003]
Quote: for digital flight-control use synchronous channels, sensor data to all channels, and exact-match majority voting; needs fault-tolerant clock synchronization, etc. [»rushJ12_1991]
Quote: 17 man-months to write requirements for a working A-7 flight program with tight memory and time constraints [»heniKL1_1980]

Subtopic: hard real time up

Quote: for hard-real-time systems, predictability is most important; pre-run-time scheduling is often necessary [»xuJ1_1993]
Quote: performance guarantees required for controlling physical systems [»donnMD_1987]
Quote: a hard real time system must supply information within specified limits, neither too early nor too late; e.g., safety-critical systems [»faulSR3_1988]
Quote: all kernel operations are atomic; either complete within a deadline or no observable effect [»shapJS1_2002]
Quote: for hard real time synchronization uses a counting semaphore, up/down/pass; same as Dijkstra's V operation [»faulSR3_1988]

Subtopic: overload up

Quote: in HI-Pearl, can handle overload by degrading system performance with alternate task bodies; e.g., use extrapolation [»stoyAD7_1993]
Quote: measure real-time systems by schedulability and stability under transient overload; resource utilization with deadline guarantees, especially critical tasks [»shaL6_1991]

Subtopic: communication up

Quote: use wait-free, allocation-free channels to transfer data between high and low frequency tasks; wait-free for reader or writer [»spooD6_2006]

Subtopic: weakly-hard up

Quote: a weakly-hard real-time system limits the percentage of missed deadlines during a time interval [»bernG12_2001]
Quote: weakly-hard constraint, (n over m); a task meets n deadlines in any m consecutive invocations [»bernG12_2001]
Quote: use bi-modal scheduler for weakly-hard real-time; panic mode guarantees tasks will meet scheduability constraints [»bernG12_2001]

Subtopic: periodic process up

Quote: a periodic process can be described by its period, worst case computation time, deadline, and release time [»xuJ1_1993]

Subtopic: asynchronous process up

Quote: an asynchronous process can be described by its worst case computation time, deadline, and minimum time between consecutive requests [»xuJ1_1993]
Quote: can replace an asynchronous with a periodic one with a period shorter than the minimum request interval
Quote: only independent, periodic, regular tasks can have hard deadlines; no hard deadlines for nonperiodic tasks such as initialization and failure recovery [»liuCL1_1973]

Subtopic: single-assignment value flows up

Quote: treat control variables as a flow of values, one per clock tick; system of equations or dataflow network; each variable defined exactly once [»benvA1_2003]
Quote: Lustre extends the usual operators to operate pointwise on flows of values
Quote: a node in Lustre is a function of typed input flows; defined by a system of equations and local flows; exactly one definition for each output or local flow [»benvA1_2003]

Subtopic: logical execution time up

Quote: logical execution time (LET) separates the observable real-time behavior from its physical execution; execute between logical release and terminate events; outputs have the value of the previous execution [»farcE6_2005]
Quote: Timing Definition Language (TDL) is the parallel composition of modules; each module consists of modes; a mode is a set of periodically executed activities, having independent rates of execution and conditions [»farcE6_2005]
Quote: logical execution time and TDL allow any module to run on any node; a bus schedule is statically defined that specifies when a node sends packages [»farcE6_2005]
Quote: a Giotto program executes a periodic set of Logical Execution Time tasks (LET); a mode switch changes the set of tasks or their periods [»henzTA6_2005]
Quote: assign a release and a termination time for tasks; inputs available at release, outputs available at termination; the actual timing does not matter; avoids race conditions [»henzTA6_2005]

Subtopic: rate monotonic scheduling up

Quote: generalized rate monotonic scheduling gives predictable response time, schedulability, and stable overload; models aperiodic as periodic [»shaL9_1993]
Quote: the rate-monotonic scheduling algorithm assigns periodic task priorities in inverse relation to task period; good for real-time [»kleiMH1_1994]
Quote: use rate-monotonic priority assignment for optimal, static priorities; highest priority given to task with highest request rate [»liuCL1_1973]
Quote: combining rate-monotonic with deadline driven scheduling may be best for hard read-time applications [»liuCL1_1973]
Quote: use constant-ratio grid with rate-monotonic scheduling and ratio <2; e.g., 256 priority levels from 1 msec to 100 seconds has a schedulability loss of 0.0014 [»shaL6_1991]

Subtopic: earliest deadline up

Quote: the earliest deadline scheduling algorithm assigns the highest priority to the ready task with the nearest deadline; good for real-time
Quote: define task priority as its deadline in microseconds; better than priority levels since easily understood [»clarDD12_1995]
Quote: deadline promotion -- a task with a short deadline can promote a task with a long deadline if it holds a locked monitor [»clarDD12_1995]
Quote: use deadline driven scheduling for optimal, dynamic priorities; highest priority to task with nearest deadline; no idle time prior to overflow; best schedulability [»liuCL1_1973]

Subtopic: critical instance up

Quote: a critical instance occurs when a task has the longest response time; i.e., when requested with higher priority tasks [»liuCL1_1973]

Subtopic: fixed scheduling up

Quote: a time-triggered system initiates all system activity at pre-determined points in time; used for Japan's bullet train [»kopeH1_1994]
Quote: with a time-triggered system, know which node must send what type of message at what time; can drop id information and quickly detect missing frames [»kopeH1_1994]
Quote: pre-run-time scheduling is necessary for large, complex hard-real-time systems [»xuJ12_1991]
Quote: pre-run-time scheduling reduces run-time scheduling costs and context switches; asynchronous requests are serviced by a periodic process [»xuJ1_1993]
Quote: a pre-run-time schedule can satisfy precedence and exclusion relations; e.g., for acquiring information or for sharing resources [»xuJ1_1993]
Quote: schedule hard-real-time systems by translating asynchronous processes into periodic processes and finding a pre-run-time schedule that meets deadlines [»xuJ12_1991]
Quote: executes simple tasks (boolean assignments only) once per scan for hard real-time processes [»weavAC_1978]
Quote: Real-Time Euclid is the first language to provide schedulability analysis
Quote: Real-Time Euclid requires timing constraints for programs, a real-time process model, and bounded-time constructs [»stoyAD7_1993]
Quote: each process is Real-Time Euclid has a frame; once activated, it must complete before the end of the frame; no reactivation in frame [»stoyAD7_1993]
Quote: in MicroTool, all control structures are single-entry, single-exit without recursion; only one level of interrupt with optional reset [»elshJL1_1991]
Quote: MicroTool measures min/max execution time and stack requirements from interrupt rates and min/max iteration counts; annotated flowchart [»elshJL1_1991]
Quote: MicroTool includes lower and upper limit operators to bound operations [»elshJL1_1991]
Quote: HI-Pearl lets you specify synchronization times for tasks and resources; system schedules times slots and checks for inconsistencies [»stoyAD7_1993]

Subtopic: event processing up

Quote: Eventrons provide safe, high frequency event processing while using a garbage collector; safety enforced with data-sensitive analysis and simple run-time checks [»spooD6_2006]
Quote: Eventrons can replace even the lowest system levels with safe, managed code
Quote: validate Eventrons at run-time before scheduling; no allocation or pointer modification; creates a data-specific call graph [»spooD6_2006]

Subtopic: loop bounds up

Quote: requiring a loop bound caught many design errors and was practical [»andeT_1985]
Quote: hard real-time requires constant-bounded loops per task activation; allows schedulability analysis [»stoyAD7_1993]
Quote: eliminate proofs of termination by avoiding loop forever constructs [»andeT_1985]

Subtopic: timer up

Quote: redesigned BSD timer facilities; constant time operations; scalable; bounded interrupt time [»costAM7_1998]

Subtopic: lock-free up

Quote: if assume upper bound for shared memory access can transform a sequential implementation of data structure primitives into a fast, wait-free concurrent implementation [»alurR12_1993]
Quote: lock-free objects with retry loops are useful for hard real-time; no priority inversion, minimal operating system support, upper bound on successful updates [»andeJH8_1995]

Subtopic: shared variables vs. message passing up

Quote: in hard real time systems need shared variables; message passing is too expensive and unpredictable [»faulSR3_1988]

Subtopic: exceptions up

Quote: the cost of an exception is hard to predict; depends on depth of stack and number of objects; not suitable for hard real time [»stroB12_2004]

Subtopic: problems with off-line schedules up

Quote: while off-line schedules are efficient, they do poorly with changes, aperiodic tasks, large task sets, and schedule overruns

Related Topics up

Group: process control   (13 topics, 106 quotes)

Topic: action chunks (6 items)
Topic: for loop (18 items)
Topic: interrupt handler (20 items)
Topic: non-preemptive task scheduling (16 items)
Topic: plan-based task scheduling (13 items)
Topic: programming without errors (28 items)
Topic: proving concurrent programs (37 items)
Topic: real time systems (14 items)
Topic: safety critical systems (32 items)
Topic: safety, liveness, and system properties (22 items)
Topic: synchronized processing (35 items)
Topic: task scheduling
(49 items)

Updated barberCB 10/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.