- In feasibility analysis, the values in the release parameters are used to determine whether the system has enough resources to guarantee that it can meet all deadlines.
- During execution, release parameters may determine when each task is released for execution.
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 that 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 than 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:
- throw an exception from the
fire()that tried to release the sporadic task too soon, - silently ignore the attempt to release it (RTSJ has two subtly different flavors of this called IGNORE and REPLACE)
- or defer the release until enough time has passed that it won't violate the MIT invariant.
Take a concrete example. We're building a typewriter. We believe that nobody can type more than 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?
- EXCEPT, Every time the user types a key sooner than 68 ms after the previous character, sound a bell and reject the character that came too early
- IGNORE, silently ignore every keystroke that is entered too soon.
- REPLACE, When a key is pressed too soon, and the previous key has not yet been printed, tell the printing mechanism to discard the previous character and print the new one instead
- SAVE, Buffer the new character and print it 68 ms after the previous one.
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
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:
- EXCEPT and IGNORE, fires that violate the MIT have no effect on deadlines.
- REPLACE, if the previous release has not completed or missed its deadline, then the deadline for the previous release is replaced with the deadline the new fire would have.
- SAVE, releases that are delayed to prevent MIT violations keep deadlines relative to the time they were fired. Unless the deadline is greater than the MIT, the SAVE policy will cause missed deadlines every time it defers releases.
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.