Real-time scheduling in practice
In one of our previous items we talked about Real-time scheduling. Now, we want to show how priorities could be assigned in practice and how deterministic system response can be designed.
Deterministic response needs to take into account the worst case scenario: everything is happening at once, at the worst possible time (usually the beginning): the system must respond within a given time frame. The system could react faster, but – in order to be a hard-real-time system – it should never miss the dead-line.
Periodic events on which the system must respond are defined by their maximum frequency, i.e. the shortest time between two events transformed in the number of times per second the event could occur: For example, the event fires, and the fastest time the next similar event could occur is 10ms later, this means the worst case frequency is 100Hz (100 times per second). It does not matter if this only happens in one in ten cases. At that time, the system must be able to handle it.
Event processing time
The second important parameter linked to the occurrence of a ‘trigger’ event, is the time it takes to respond to it: this can be defined as the entire reaction plus processing time related to the response, which is “as long as it takes to formulate an adequate answer plus the time it takes for the system to become ready again to respond to another event.”
Timely system response
We need those two parameters to successfully model the deterministic system response. Frequency is usually the easy one. For example, receive RS232 serial communication data with a single BYTE reception register (without FIFO/DMA) at 9600 baud, will give you 9600/(8 bits + 1 start bit + 1 stop bit) or 960 ‘there-is-a-byte-in-the-reception-register’ events per second. If a single byte must not be lost, the system must read the receive register before the next byte arrives (and overwrites the previous content).
So, – unrealistically – if the system has nothing else to do, it can take 1/960 seconds to read the data from the reception register. Hopefully, it takes less time to respond to the event, so the system can also do something useful with the data :). But “to measure is to know” or “the numbers tell the tale” or whatever. So in order to know the response time, you need to measure the time it takes to execute the required code. That might be tricky if you know the processor or micro-controller you will be using, but it might be guesswork if the platform selection has not been made yet. In that case, one might revert to known similar processors and acquire the data there, and try to extrapolate with a large error margin. At a later stage in development, it needs to be checked and re-evaluated. So in short: determine the processing time without cache impact by measuring code execution of isolated tasks (thus without other higher priority tasks running). This will be easier if the code does not contain complicated branches or loops. Always go for the worst case execution path.
Another caveat in code execution measurement is the cache issue. To measure the worst case behaviour, data and code cache on the processor or micro-controller must be disabled (or poisoned)! Embedded processors usually do not have a huge cache, so at a time the ‘event’ occurs, chances are that the cache is filled with other code and data than is required to perform the response. If one cannot disable the cache, a low priority task can be used to poison the cache and flush out code and data referenced by the task under scrutiny.
We simply define ‘System load’ as the percentage of the time the system is busy processing; or in other words, the percentage of time, the system is NOT idle. Even systems with very little load could miss deadlines and then these cannot be categorized as ‘real-time systems’. It is difficult – but not impossible – to have or design heavily loaded real-time systems.
Assigning priorities: example
Things will get clearer with an example.
Three events. A, B and C.
A – frequency 10Hz (every 100ms), it takes 90ms to respond; if it were the only task, it would lead to 90% load on the system.
B – frequency 500Hz (every 2ms), it takes 150µs to respond; 7.5% load
C – frequency 100Hz (every 10ms), it takes 100µs to respond; 1% load
Which one is more important? Which of the events should get the highest priority? Rate Monotonic Scheduling (RMS) and Earliest Deadline First (EDF) e.g. each will provide an answer and can give some insight in the matter. E.g. with RMS, the task with the highest occurrence rate gets the highest priority: B, then C and then A. For more theoretical detail, look here.
If it is still unclear whether the system is ‘schedulable’, you can try the following heuristic:
All events A, B and C occur at the same time, t0.
Since B is regarded by the developer as the most important task, it gets the highest priority. C gets the second highest priority. It is clear that A cannot get the highest priority since then the other tasks would miss there deadline very soon.
A gets priority 3 (lowest), B gets priority 1 (highest), C gets priority 2 (middle).
At time t1 = t0 + 150µs = 150µs, B is finished, C is scheduled to run.
At time t2 = t0 + 150µs + 100µs = 250µs, C is finished, A is scheduled to run.
At time t3 = t0 + 2000µs , A is not yet finished but B needs to run and is scheduled.
At time t4 = t0 + 2150µs = 2150µs, B is finished, A is scheduled to run and continues (already done 2000 – 250 µs = 1750 µs of the 90000µs it needs to complete it) processing…
At time … and so on. You make a nice drawing of it and visually see of this system meets all deadlines.
More to come
These scheduling and priority schemes depends on the fact that tasks have no (b)locking inter-dependencies, thus no priority inversion problems or deadlocks. In a next episode, we will demonstrate how this can be achieved.