Home > Software Design > WCP: Uncertain Times…

WCP: Uncertain Times…

Tuesday, September 20, 2011 Leave a comment Go to comments

Timing issues are often important in systems containing software but, ultimately, all timing is determined by hardware. Let’s pursue this by splitting a hypothetical system into (1) the software we’re designing and (2) the platform it’s intended to run on. We also need to consider (3) the toolchain. To be a little more precise:

  1. The software we’re designing (referred to just as the “Software” after I’m through with these definitions) is simply that. It is the software to which we are applying the WCP and which we are trying to make perfect. It does not include any third-party software (such as an OS), firmware, FPGA code or microcode which may exist in the Platform.
  2. The Platform obviously must contain at least one hardware processor. However, it will also have some peripherals and may include any of the other things mentioned in the last sentence of (1), above. For our present purpose, it doesn’t matter how simple or complex the platform is, or whether or not it includes its own “black box” software, as well as hardware, because I intend to use the simplest possible abstraction of it.
  3. The Toolchain’s job is to translate the source code we write (or, in some cases, draw) into executable code, without redesigning our Software in so doing. I am going to assume that the toolchain does its job perfectly – not because it necessarily will but because toolchain validation, although important, is outside the scope of this discussion. That said, I will ignore the Toolchain from now on.
Abstracting the Platform

Because it contains hardware, even if for no other reason, a real Platform is always at risk of failure. In striving for perfect Software, we aim not to increase this risk by introducing errors. The worst case abstract Platform for us, therefore, is – somewhat paradoxically – one which is functionally perfect and never fails! This is because such a Platform places the greatest pressure upon us to design our Software properly. For timing purposes, though, I’m going to assume a very bad thing: that we know nothing, from the Platform’s specification, about its timings! So – for this article only – I’m giving our hypothetical Software designer a really hard time, and following where that leads.

Even with no Platform specification to guide us we can still, with a little thought, come to some conclusions about its timings. Let us define an Operation, within our Software, as some particular finite sequence of instructions, as executed (i.e. with all branches, etc., resolved). An Operation could be a single instruction, a high-level statement or some execution path through an entire function; it doesn’t matter. What does matter is that the sequence, for any given Operation, is fixed. The execution time for a given Operation, if repeated, may vary, depending upon the state of the hardware each time (think “caches”), so the execution time, t, is a function of the actual Operation, O, and also of the machine state, S, at the time O begins to execute. We can now assert that:

0 < t(O, S) < ∞

This is not much to go on, but it is something! Firstly, it tells us that t is always positive and never (quite) zero, as dictated by the laws of physics. Secondly, the fact that t cannot be zero or less preserves our fundamental concept of sequence, thankfully! Thirdly, we have asserted that t cannot be infinite. We do not have to get into metaphysics to justify this last assertion: an infinite execution time for any finite Operation most certainly implies Platform failure, which is not allowed in our abstraction.

Software implications

(1) With such uncertain timings, we cannot calculate the worst-case execution time of any Operation. Therefore no Operation can be guaranteed to complete in time to meet any hard deadline. The term “hard real time” can never justifiably be used to describe any part of this system.

(2) For a real system approximating this hypothetical one, the only way to determine any timings is to measure them during testing. Measurement alone can never guarantee that the worst-case timings have been found. Such an approach can only ever yield statistically fuzzy results, with the fuzziness being expressible only in a fuzzy way, with a fuzzy level of confidence (fuzziness squared?). Such systems, exhaustively tested, are sometimes deemed “soft real time”, but “not real time” would be more meaningful and more honest.

(3) In designing Software for this system, it is clear that we cannot time anything at all by running in loops, but must invoke the services of at least one hardware timer to deal with time-related matters in the Software. Coding pure software loops for timing puposes is widely considered bad practice, anyway, but its inadequacy has been highlighted here and hopefully serves to remind us not to do it, even in systems where the timings are better known.

(4) More subtly, there is nothing in our timing assumptions which allows us to say anything like t(A, X) > t(B, Y), where A and B are two different operations and X and Y are two machine states (which are not necessarily different). We cannot say this even if A has many more machine instructions than B. This has an important implication for concurrent systems: we should never rely on execution timings to predict such things as the order in which threads might complete their work. Another known (but sometimes forgotten) bad practice to avoid, even when timings are more predictable.

Reality check

Do real systems ever have such unpredictable timings as the ones just described? Can such systems ever be useful? Yes, to both questions! Consider the following:

  1. You are a PC user, like the rest of us. With all the antivirus, Windows and other updates which might be in the pipeline, what will be the absolute maximum time between your turning the computer on tomorrow and your being able to use it? Don’t know? How long, then, will it have to take, and how often must it take that long, before you (a) upgrade to a faster processor and/or faster broadband or (b) buy a Mac, hoping it will be better?
  2. You’re writing an application in Java for an Android-based ‘phone. You want to know the worst-case execution time of a particular operation which allocates a new object (dynamically, as Java must). Can you, for a start, calculate the maximum time that allocation will take, given that the garbage collector may have to do an open-ended amout of work to find the space – assuming there is sufficient space available, of course? No, you can’t! So you do some testing and make the judgement that it’s “fast enough, most of the time”. You hope that most of your customers will be happy with what they get, but accept the risk that one or two might give your “App” bad reviews.

So such systems do exist and are useful to many of us every day. In each case, someone has made a judgement – maybe unconsciously – that sufficient numbers of customers will buy the product, in spite of the fact that some of its most basic parameters were unknown to (or just ignored by) the design team. The fact that such designs would not (and, I hope, never will) pass muster at, say, an aerospace company does not detract (much) from their saleability in their target market. But this does not mean that professional engineers should abandon their principles and succumb wholly to the test-and-hope paradigm of software development. Good WCP design and coding at least stops us from augmenting risks deliberately or inadvertently taken elsewhere, and thereby helps keep more enterprises afloat and more of us gainfully employed. Also, doing things properly is more fulfilling!

Next time, I’ll give timing a rest, before coming back to it later, and deal with other issues of predictability and worst-case design.

Advertisements
Categories: Software Design Tags: ,
  1. Peter Bushell
    Wednesday, September 21, 2011 at 15:38

    My Software Implication (3) is actually worse than stated above. Once a hardware timer has been started, the software has eventually to synchronise with it, by waiting for its expiry. As the Software timing is unpredictable, all we can be sure of is that the timer, once started, defines a minimum time before which the software cannot pass the synchronisation point.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: