TECHNOLOGY BACKGROUNDER

Algorithms and Protocols

This paper briefly describes several scheduling algorithms and prioritization protocols and indicates how they are used in RAPID RMA.

Descriptions of Algorithms

Rate Monotonic (RM)

A term applied to the method of assigning priorities to responses implemented by tasks according to the frequency or rate of the tasks. Tasks that execute at a higher rate are assigned a higher priority than tasks that execute at a lower rate.

Deadline Monotonic (DM)

A term applied to the method of assigning priorities to tasks according to the deadline of the responses implemented by tasks. Tasks with shorter deadlines are assigned higher priorities than tasks with longer deadlines.

Earliest Deadline First (EDF)

RM scheduling generally prioritizes tasks by the length of time it takes to complete them, with the shortest task having the highest priority. EDF allows designers to evaluate their model based on task deadlines and ensures that tasks whose deadlines are coming up first have priority in the design sequence. EDF provides designers with a more dynamic analysis that allows them to evaluate whether their design can execute in a timely manner. It provides a way to validate a system's architecture, instead of its functionality, in either single-node or end-to-end scenarios.

Cyclic Executive (CE)

While RMA uses strict mathematical approaches to determine a design's worst case performance, CE Analysis allows developers to validate their designs using simulation techniques and round-robin scheduling paradigms.

HKL, SGL

Algorithms especially tuned for single instance tasks that have explicit dependencies between them.

Descriptions of Protocols

Priority Ceiling Protocol (PCP)

A synchronization protocol that avoids deadlocks and ensures that a task will be blocked once (at most) by the duration of a single critical section. PCP can be used in Single Node, Multi-Node, and End-to-End analysis.

Stack Based Protocol (SBP)

When used with rate monotonic, deadline monotonic, and earliest deadline first algorithms, this protocol assigns a fixed preemption level to every task based on its relative deadline. The smaller the deadline, the higher the preemption level. Note that the preemption level of a task is not related to the priority of the task. Like PCP, this protocol avoids deadlocks and multiple blocking; SBP blocks a task earlier, at the start of the execution. Once the task starts executing, it will never be blocked (but it can be preempted). This protocol is only applicable to Single Node systems. SBP cannot be used in Multi-Node analysis.

Basic Interitance Protocol (BIP)

This protocol is identical to PCP modulo the guarantee for deadlock avoidance and blocked-at-most-once. This algorithm can produce chained blocking. It has been implemented in a great many real time systems, and is the default resource sharing protocol in Wind River's VxWorks real-time operating system.

Combinations Used in RAPID RMA

RM + PCP

Rate Monotonic with Priority Ceiling Protocol scheduling

RM + SBP

Rate Monotonic with Stack Based Protocol scheduling (not for Multi-Node systems)

RM + BIP

Rate Monotonic with Basic Interitance Protocol scheduling

DM + PCP

Deadline Monotonic with Priority Ceiling Protocol scheduling

DM + SBP

Deadline Monotonic with Stack Based Protocol scheduling (not for Multi-Node systems)

DM + BIP

Deadline Monotonic with Basic Inheritance Protocol scheduling

EDF + SBP

Earliest Deadline First with Stack Based Protocol scheduling (only for Single Node systems)

CE

Cyclic Executive (only for Single Node systems)

HKL

Single instance tasks with dependencies (only for Single Node systems)

SGL

Single instance tasks with dependencies (only for Single Node systems)