5

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

1
  • 3
    What makes you think that this is true? Is this a problem you have experienced, or something that you have been told or read? Citation required.
    – Clifford
    Commented Apr 11, 2012 at 20:45

4 Answers 4

6

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:

  • Andersson, B.; Jonsson, J.; , "Preemptive multiprocessor scheduling anomalies," Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM , vol., no., pp.12-19, 2002. doi: 10.1109/IPDPS.2002.1015483
  • Grahamm R. L., "Bounds on Multiprocessing Timing Anomalies", SIAM Journal on Applied Mathematics , Vol. 17, No. 2 (Mar., 1969), pp. 416-429.
5

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:

  • 4 milliseconds CPU computations
  • 4 milliseconds IO time (save data)

A second task (B) will get started by a hardware event consists of:

  • 4 milliseconds IO time (load data)
  • 2 milliseconds CPU time

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.

2

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.

1

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.

1
  • Also, if there are any resources shared between the CPU and the rest of the system and the resource contention grows with the CPU speed and becomes a bottleneck (perhaps with resource starvation), deadlines may be missed because of that. Commented Apr 11, 2012 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.