Open Source Automation Development Lab
You are here: Home / Science / RTLWS Submitted Papers / 
2016-06-30 - 08:52
Details of the Real Time Linux Foundation Working Group Project

OSADL Project: Real Time Linux Workshops

Real Time Linux Foundation Workshops since 1999

Real Time Linux Workshops

1999 - 2000 - 2001 - 2002 - 2003 - 2004 - 2005 - 2006 - 2007 - 2008 - 2009 - 2010 - 2011 - 2012 - 2013 - 2014 - 2015

Eleventh Real-Time Linux Workshop on September 28 to 30, in Dresden, Germany


Analysis of inherent randomness of the Linux kernel

Nicholas Mc Guire, DSLab, SISE, Lanzhou University, Gansu, China
Peter Odhiambo Okech, Faculty of Information Technology Strathmore University, Nairobi Kenya
Qingguo Zhou, DSLab, SISE, Lanzhou University, Gansu, China

While analyzing latency data from real-time Linux variants, we found that there are distinct parts to the system jitter - those that can be attributed to software constructs and those that are inherent in complex software systems running on non-deterministic hardware.

Essentially hunting for the maxima of latency, which was the common initial approach, only can detect grave latency issues, like excessively long holding of locks - but it is not able to detect low-level latency causes like miss-alignments, or short term locks that are in a hot path and thus contribute significantly to the systems overall latency and jitter. Further the maxima - if the assumption of inherent randomness hold - are not associated with a specific code-path but rather with the code-path being executed in a specific, system level, context - thus we believe that a statistic approach to tracing latency is needed.

Basic analysis of real time behavior in complex software systems can be split roughly into the following parts:

  • Timestamp precision - how precisely can an event be associated with a timestamp from a specific clock-source
  • Inherent randomness - how non-predictable is the execution of functionally deterministic code

The first can be quite nicely measured (or rather estimated based on measurements) - the second is a bit more complicated as there currently is not even a well accepted definition, nor a practically meaningful metric.

These two factors, we believe, can form a useful constraint for the lower-bounds of timing behavior that can be achieved in complex software systems - be that scheduling jitter, interrupt latency, or bandwidth variance.

In this paper, we will present the current state of our assessment along with an argument why we believe that inherent randomness is present and of what quality this randomness actually is based on preliminary evaluation of a random number generator (RNG) derived from our timestamp measurement code.