You are here: Home / RTLWS 1999-2017 / RTLWS Submitted Papers / 
2024-04-15 - 20:04

Dates and Events:

OSADL Articles:

2023-11-12 12:00

Open Source License Obligations Checklists even better now

Import the checklists to other tools, create context diffs and merged lists

2023-03-01 12:00

Embedded Linux distributions

Results of the online "wish list"

2022-01-13 12:00

Phase #3 of OSADL project on OPC UA PubSub over TSN successfully completed

Another important milestone on the way to interoperable Open Source real-time Ethernet has been reached

2021-02-09 12:00

Open Source OPC UA PubSub over TSN project phase #3 launched

Letter of Intent with call for participation is now available

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

Announcement - Hotels - Agenda - Paper Abstracts - Presentations - Registration - Abstract Submission - Xenomai User Meeting - Sponsors


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.