Peter Okech, Strathmore University, Nairobi, Kenya, and Nicholas Mc Guire, Distributed & Embedded System Lab, Lanzhou University, China

The determination of the upper bound of of execution time of a real time task involves considering the potential control flow path of the task and then the time spent in the instructions of this path on a given hardware platform. A commonly held assumption is that the execution time of an instruction is predictable. For contemporary computing systems with performance enhancing hardware components, the execution time of a given instruction or sequence of instructions shows a marked variance. The temporal indeterminism at instruction level can be attributed to the internal complexity of super scalar CPUs. We need to develop metrics to measure the inherent randomness associated with the complexity of the hardware/software system.

In this paper, we present the results of what we consider as the first step of the process of defining a suitable metric for inherent randomness. Our approach involves generating a random binary sequence based on the non-deterministic execution a fixed code sequence. We then perform a number of statistical tests, from a variety of test suites, to evaluate quality of the bit stream produced. It is our belief that these results can form a basis for an acceptable metric of system level randomness and could further provide a set of quantitative measures that can be used to compare real-time systems based on complex hardware/software like GNU/Linux with its real time extensions at system level.