Sporadic Scheduling

Peter Dibble
9 July 2005

Under RTSJ, release parameters tell the scheduler when it should expect a task to run. For instance, periodic parameters tell the scheduler that a task will run once per period, and aperiodic parameters tell the scheduler that the task may start running at unpredictable times.

The scheduler has two uses for release parameters:

Analysis

Rate Monotonic Analysis can determine whether a system of periodic tasks can all meet their deadlines; e.g., the system is feasible. RTSJ's online analysis only works well if the tasks never block, but given that, it's reasonably easy to determine whether a system is feasible from the cost, period, and deadline of each task.

The world is full of non-periodic events. There is no real period for the water level in a municipal water tower. What would you use as the period of smoke alarms, the period of key presses on a computer keyboard, or the period of detection of defective parts on an assembly line. The usual way to handle this type of event is to force it to behave periodic by polling for the event, but that leaves you with an uncomfortable choice: poll fast and waste resources checking for an event isn't happening, or poll slowly and live with the possibility that a long time will pass between the event and the polling loop noticing it.

One could classify non-periodic events as aperiodic, but aperiodic tasks make formal real-time analysis much less useful. Since an aperiodic task runs at unpredictable intervals the only ways to bound its resource utilization are to keep its priority low or use processing group parameters. Ignoring locks, those techniques prevent an aperiodic task from shutting out other tasks. A low priority or processing group keeps the aperiodic tasks from shutting down other tasks, but I don't know of any way to guarantee that aperiodic tasks will meet their deadlines. From the simple analysis point of view, no system with an aperiodic task in the feasibility set is feasible.

Sporadic parameters make aperiodic tasks "work" in a real-time system. Sporadic parameters are a sub-class of aperiodic parameters that puts aperiodic tasks on a budget. Sporadic parameters say to the scheduler, "I don't know how often this task will run, but assume it will be at least this minimum interarrival time, or MIT, between releases. If it tries to run more often that that, don't let it." Given this commitment, the scheduler can analyze sporadic tasks as if they were periodic.

Say you'd like the system to watch the water level in a water tower. The water level can't change fast, so give the async event handlers for the high and low triggers sporadic parameters with a MIT of 100 seconds, a deadline of 100 seconds, and a cost of 50 milliseconds. A system with such long minimum interarrival times sounds boring, but say the system has more than 10,000 sensors and some of them need sporadic parameters with a MIT as short as ten seconds. That is not obviously feasible.

Analysis will treat the system as if it were polling all 10,000 sensors with the period, cost and deadline of their respective sporadic parameters, but the application doesn't poll. Each handler will run strictly on demand. This greatly reduces the typical load on the system because events with an MIT measured in seconds may go days between actual occurrences and during those inactive days the handler uses no CPU time.

Execution

Telling the scheduler to just "not let" a handler run too soon sounds too simple to be the whole story. It is.

Starting with the invariant that the scheduler must leave an interval of MIT between the times that it releases a sporadic task for execution, what can it do when the task tries to run too soon? It can:

Take a concrete example. We're building a typewriter. We believe that nobody can type more then ten characters per second, so we design the hardware to be able to print fifteen characters per second. If we try to print more than fifteen characters per second the hardware will break.

It turns out that people do type faster than fifteen characters per second. Some type short bursts faster than 15 characters per second, others have been known to pound their hands on the keyboard pressing more than a dozen keys within a few milliseconds.

Let's attack the problem with the sporadic scheduling policy's MIT violation policy. Choose an MIT of 68 milliseconds—which is roughly a fifteenth of a second. What options are offered by sporadic scheduling?

Any of the first three MIT violation policies might prevent some errors that could be provoked when the typist inadvertently strikes several keys at nearly the same time, but in general I'd say that a typewriter that drops characters would be a vile thing, and I'd select the SAVE policy. The SAVE policy is the default for sporadic release parameters, so this would not take any work.

A practical detail: the RTSJ doesn't provide a way to pass a character from fire() to the async event handler, so the application will have to maintain a separate queue of characters. On the input side:

characterQueue.add(c);
inputEvent.fire();

In the async event handler's handleAsyncEvent() method

c = characterQueue.get();
printer.type(c);

The save policy works like this

Image

on bursty input.

Try another example, the smoke alarm. We don't expect smoke alarms to "fire" except when they are tested, but unfortunately (from the narrow viewpoint of control software) once they fire they don't shut up. We want to give a smoke alarm very high priority in the computer that services it, but we want the computer to be able to do other things once it has seen the alarm. Sporadic scheduling addresses this problem.

A smoke alarm might have an MIT of 5000 ms, a cost of 10 ms, and a deadline of 1000 ms. When the smoke alarm panics and starts firing every 5 ms we can ignore all but the first alarm. The IGNORE policy will see the first alarm in each 5-second interval and ignore all the others. That discards 99.9% of the load.

Deadlines

The key distinction between the IGNORE policy and the REPLACE policy is the handling of the deadline.

The deadline for a sporadic event is measured from the invocation of fire. When the MIT is respected, deadlines are easy to follow. When the MIT is violated, deadline handling gets interesting:

In the case of the smoke alarm (above), the REPLACE policy would have been a poor choice. The flurry of alarms would push the deadline to 6 seconds instead of the intended 1 second.