diff options
authorSebastian Huber <>2017-01-30 13:51:57 +0100
committerSebastian Huber <>2017-01-30 13:52:23 +0100
commita17535d222a1268542e97c7e6c1b2fdf045e46d8 (patch)
parente23f46c3b99f9ade28d8dba2a30761edcefac9ff (diff)
c-user: Add timer and timeouts key concept
Update #2554.
3 files changed, 42 insertions, 1 deletions
diff --git a/c-user/ b/c-user/
index 147fbf7..0afe6f8 100644
--- a/c-user/
+++ b/c-user/
@@ -3,7 +3,7 @@ sys.path.append(os.path.abspath('../common/'))
from conf import *
-extensions = ['sphinxcontrib.bibtex']
+extensions = ['sphinx.ext.imgmath', 'sphinxcontrib.bibtex']
version = '4.11.99'
release = '4.11.99'
diff --git a/c-user/key_concepts.rst b/c-user/key_concepts.rst
index 767e93f..e5c8cfd 100644
--- a/c-user/key_concepts.rst
+++ b/c-user/key_concepts.rst
@@ -289,6 +289,46 @@ time in RTEMS services. See :ref:`Time and Date Data Structures`.
.. index:: rtems_time_of_day
+Timer and Timeouts
+Timer and timeout services are a standard component of an operating system.
+The use cases fall roughly into two categories:
+* Timeouts -- used to detect if some operations need more time than expected.
+ Since the unexpected happens hopefully rarely, timeout timers are usually
+ removed before they expire. The critical operations are insert and removal.
+ For example, they are important for the performance of a network stack.
+* Timers -- used to carry out some work in the future. They usually expire
+ and need a high resolution. An example use case is a time driven scheduler,
+ e.g. rate-monotonic or EDF.
+In RTEMS versions prior to 4.12 the timer and timeout support was implemented
+by means of delta chains. This implementation was unfit for SMP systems due to
+several reasons. The new implementation present since RTEMS 4.12 uses a
+red-black tree with the expiration time as the key. This leads to
+:math:`O(log(n))` worst-case insert and removal operations for :math:`n` active
+timer or timeouts. Each processor provides its own timer and timeout service
+point so that it scales well with the processor count of the system. For each
+operation it is sufficient to acquire and release a dedicated SMP lock only
+once. The drawback is that a 64-bit integer type is required internally for the
+intervals to avoid a potential overflow of the key values.
+An alternative to the red-black tree based implementation would be the use of a
+timer wheel based algorithm :cite:`Varghese:1987:TimerWheel` which is used in
+Linux and FreeBSD :cite:`Varghese:1995:BSDCallout` for example. A timer wheel
+based algorithm offers :math:`O(1)` worst-case time complexity for insert and
+removal operations. The drawback is that the run-time of the clock tick
+procedure is unpredictable due to the use of a hash table or cascading.
+The red-black tree approach was selected for RTEMS, since it offers a more
+predictable run-time behaviour. However, this sacrifices the constant insert
+and removal operations offered by the timer wheel algorithms. See also
+:cite:`Gleixner:2006:Hrtimers`. The implementation can re-use the red-black
+tree support already used in other areas, e.g. for the thread priority queues.
+Less code is a good thing for size, testing and verification.
Memory Management
.. index:: memory management
diff --git a/common/ b/common/
index 7f2765c..9704486 100644
--- a/common/
+++ b/common/
@@ -15,6 +15,7 @@ package_tests = {
'amsmath' : ['\\usepackage{amsmath}'],
'amssymb' : ['\\usepackage{amssymb}'],
'amstext' : ['\\usepackage{amstext}'],
+ 'anyfontsize' : ['\\usepackage{anyfontsize}'],
'array' : ['\\usepackage{array}'],
'atbegshi' : ['\\usepackage{atbegshi}'],
'babel' : ['\\usepackage{babel}'],