Static Cyclic Scheduling

The table is organized in micro-cycles (μC) with a fixed duration. This way it is possible to release tasks periodically.

The micro-cycles are triggered by a Timer.

Scanning the whole table repeatedly generates a periodic pattern, called macro-cycle (MC).

• Γ = {τi (Ci , ∅i , Ti , Di )}, i = {1...n}

• μC = GCD(Ti); MC = mCM(Ti)

Example

∅i = 0

T1 = 5ms; T2 = 10ms; T3 = 15ms.

Pros

Very simple implementation (timer+table).

Execution overhead very low (simple dispatcher).

Permits complex optimizations (e.g. jitter reduction, check precedence constraints).

Cons

Doesn’t scale (changes on the tasks may incur in massive changes on the table. In particular the table size may be prohibitively high).

Sensitive to overloads, which may cause the “domino effect”, i.e., sequence of consecutive tasks failing its deadlines due to a bad-behaving task.

Algorithm

How to build the table:

• Compute the micro and macro cycles (μC and MC).

• Express the periods and phases of the tasks as an integer number of micro-cycles.

• Compute the cycles where tasks are activated.

• Using a suitable scheduling algorithm, determine the execution order of the ready tasks.

• Check if all tasks scheduled for a give micro-cycle fit inside the cycle. Otherwise some of them have to be postponed for the following cycle(s).

• It may be necessary to break a task in several parts, so that that each one of them fits inside the respective micro-cycle.