[rtems-docs commit] c-user: Add timer and timeouts key concept

[Sebastian Huber]

Module:    rtems-docs
Branch:    master
Commit:    a17535d222a1268542e97c7e6c1b2fdf045e46d8
Changeset: http://git.rtems.org/rtems-docs/commit/?id=a17535d222a1268542e97c7e6c1b2fdf045e46d8

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Mon Jan 30 13:51:57 2017 +0100

c-user: Add timer and timeouts key concept

Update #2554.

---

 c-user/conf.py          |  2 +-
 c-user/key_concepts.rst | 40 ++++++++++++++++++++++++++++++++++++++++
 common/latex.py         |  1 +
 3 files changed, 42 insertions(+), 1 deletion(-)

diff --git a/c-user/conf.py b/c-user/conf.py
index 147fbf7..0afe6f8 100644
--- a/c-user/conf.py
+++ b/c-user/conf.py
@@ -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/latex.py b/common/latex.py
index 7f2765c..9704486 100644
--- a/common/latex.py
+++ b/common/latex.py
@@ -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}'],