Cyclic Executive

Real-Time schedulers and concurrency

Concurrent programs do not exactly specify the ordering of process execution. Ordering constraints for IPC and synchronization provider ensure the the expected output is achieved; unfortunately, this does not eliminate nondeterminism--processes interleaving may satisfy ordering constraints, and remain nondeterministic.

Consider an example where some process A produces output that can be used by some process B or C. Assume there is another process D that produces the final (expected) output. Also assume that both process B and C transition directly to D. This clearly shows nondeterminism, because the output from A can take branch B or C to reach D. Since both transition options (B or C) satisfy ordering constraints that only guarantee successful output (e.g., A cannot transition directly to D), we have a nondeterministic algorithm. Although a state transition to B or C, and consequently, D, will produce the expected output, it is unlikely that the timing of of each path is equal.

Real-time schedulers are concerned with ordering and timing. Since determinism impacts timing, it is imperative that real-time scheduling algorithms optimize determinism.

If a process in a concurrent program has a tight deadline on completion time, only some of the interleavings that are acceptable from the concurrent programming perspective will also be adequate from the real-time execution point-of-view.

Process Models

Scheduling models are used to ensure correct output and timings in concurrent programs. A scheduling model consists of two main elements:

1. A scheduling algorithm

2. A way to analyze the system and evaluate worst-case behavior with respect to timings.

General-purpose scheduling algorithms are typically less concerned with determinism; instead, they emphasize:

• Fairness: Each process is given a fair share of the available processor time. (e.g., Time-sharing operating system). The amount of time given to each process is small (i.e., microseconds), creating an appearance of concurrent execution.

• Efficiency: Frequent invocation of the scheduling algorithm; the scheduling algorithm operation itself is considered overhead--the system is not doing anything useful from an application standpoint. Consequently, most general-purpose OS's require constant time-complexity [ O(1) ], if time-complexity depends on the number of processes running on a system, the speed of the scheduling algorithm would likely be inversely proportion to that number. This is not ideal for obvious reasons.

• Throughput: Referring to the number of jobs completed in a given interval, general-purpose schedulers are primarily concerned with maximizing the number of jobs completed, while paying little to no regard for time-related requirements.

Real-time scheduling algorithms emphasize timing requirements of each individual process being executed. Real-time systems typically provide a sufficient amount of information required to make scheduling decisions; however, general-purpose systems do not have this information available and must infer based on past performance.

Consider an arbitralily complex concurrent program such as a web browser where the interval between execution bursts and the processing time required to process these operations, depends on what the user is doing.