A little confused about this. If I speed up the processor, wouldn't it take less time to do a task and therefore lead to making the deadline sooner?
thanks
A little confused about this. If I speed up the processor, wouldn't it take less time to do a task and therefore lead to making the deadline sooner?
thanks
The answer is that there may be new resource conflicts due to the faster speed. This is known as Graham’s anomaly: If a task set is scheduled on a multiprocessor such that schedule length is minimized, then increasing processors, reducing execution times, or weakening precedence constraints can increase schedule length. Note the objective (minimize schedule length). But the anomaly can easily be shown to be true if tasks have deadlines and the objective is to meet all task deadlines. This is well-documented with illustrations of examples in a number of books on operating systems.
See also:
These kind of things happen, and Douglas already explained Grahams anomaly. I'll try to explain it with a little example. I hope this makes it easier to understand what is going on:
The anomaly arises if you are dealing with multiple concurrent tasks and a shared resource of fixed speed, such as a communication channel.
A good example for this in the context of a real-time system is data acquisition. If you have to read x milliseconds of data from an analog-to-digital converter it will always take x milliseconds, regardless of the CPU speed. In my example I call this 'IO-time' or 'io-task'.
Now consider the following scenario:
You have one task (A) which consists of:
A second task (B) will get started by a hardware event consists of:
The second task gets started at millisecond 3.
IO and CPU are shared resources. They can run in parallel, but either IO or CPU can only process a single job at a time.
One possible schedule for this could look like this:
timestamp: cpu/io job:
---------------------------------------------
t=0 event <--- hardware event triggers task-a
t=0 cpu start of task-a (4 ms)
t=3 event <--- hardware event triggers task-b
t=3 io start of task-b (4 ms)
t=4 cpu task-a done
t=7 io task-b done
t=7 io start of task-a (4 ms)
t=7 cpu start of task-b (2 ms)
t=9 cpu task-b done
t=10 io task-a done
Now we double the cpu power, so that the cpu will run twice as fast:
timestamp: cpu/io job:
---------------------------------------------
t=0 event <--- hardware event triggers task-a
t=0 cpu start of task-a (2 ms)
t=2 cpu task a done
t=2 io start of task a (4 ms)
t=3 event <--- hardware event triggers task-b, but can't start
because io-bus is busy. Must wait.
t=6 io task a done
t=6 io start of task b (4 ms)
t=10 io task b done
t=10 cpu start of task b (1 ms)
t=11 cpu task b done
As you can see, the improvement in CPU speed caused the two tasks to finish one millisecond later compared to the slower cpu scenario. This is because the fixed speed shared resource was busy while the hardware event occurred.
This is just a single millisecond, but these things can add up and may cause missed deadlines.
Depends... speeding up the processor doesn't impact other parts of the system (memory access times, propagation delays, etc.). Increasing the processor speed makes these things take up a greater portion of the processing time for a task.
If the processor speed is increased, propagation can cross over a clock cycle, possibly causing a delay due to retrying, depending on how your system is set up.
If a deadline is tied to a counter or timer based on the processor, it will increase as well, by a proportionally greater amount, since there are not main memory accesses for the counter.
Either of these could possibly be among the factors, depending on your particular setup.
Maybe -- but many techniques used to speed up processors (e.g., caching) also make them less predictable. Most of these techniques improve the average case (often quite a lot) at the expense of the worst case -- e.g., with a cache, in the worst case a fetch from memory can be slower than without a cache because in addition to the time to fetch from memory, there's some time taken to search the cache to see if the data is present.
Unfortunately, for real-time scheduling, your concern is primarily with the worst case, not the average case, so even though such an optimization makes most code faster most of the time, it can still lead to missing a deadline in a real-time system.