Changeset a17535d in rtems-docs

Jan 30, 2017, 12:51:57 PM (3 years ago)
Sebastian Huber <sebastian.huber@…>
5, master
Sebastian Huber <sebastian.huber@…> (01/30/17 12:51:57)
Sebastian Huber <sebastian.huber@…> (01/30/17 12:52:23)

c-user: Add timer and timeouts key concept

Update #2554.

3 edited


  • c-user/

    re23f46c ra17535d  
    44from conf import *
    6 extensions = ['sphinxcontrib.bibtex']
     6extensions = ['sphinx.ext.imgmath', 'sphinxcontrib.bibtex']
    88version = '4.11.99'
  • c-user/key_concepts.rst

    re23f46c ra17535d  
    290290.. index:: rtems_time_of_day
     292Timer and Timeouts
     295Timer and timeout services are a standard component of an operating system.
     296The use cases fall roughly into two categories:
     298* Timeouts -- used to detect if some operations need more time than expected.
     299  Since the unexpected happens hopefully rarely, timeout timers are usually
     300  removed before they expire. The critical operations are insert and removal.
     301  For example, they are important for the performance of a network stack.
     303* Timers -- used to carry out some work in the future. They usually expire
     304  and need a high resolution. An example use case is a time driven scheduler,
     305  e.g.  rate-monotonic or EDF.
     307In RTEMS versions prior to 4.12 the timer and timeout support was implemented
     308by means of delta chains.  This implementation was unfit for SMP systems due to
     309several reasons.  The new implementation present since RTEMS 4.12 uses a
     310red-black tree with the expiration time as the key.  This leads to
     311:math:`O(log(n))` worst-case insert and removal operations for :math:`n` active
     312timer or timeouts.  Each processor provides its own timer and timeout service
     313point so that it scales well with the processor count of the system.  For each
     314operation it is sufficient to acquire and release a dedicated SMP lock only
     315once. The drawback is that a 64-bit integer type is required internally for the
     316intervals to avoid a potential overflow of the key values.
     318An alternative to the red-black tree based implementation would be the use of a
     319timer wheel based algorithm :cite:`Varghese:1987:TimerWheel` which is used in
     320Linux and FreeBSD :cite:`Varghese:1995:BSDCallout` for example.  A timer wheel
     321based algorithm offers :math:`O(1)` worst-case time complexity for insert and
     322removal operations.  The drawback is that the run-time of the clock tick
     323procedure is unpredictable due to the use of a hash table or cascading.
     325The red-black tree approach was selected for RTEMS, since it offers a more
     326predictable run-time behaviour.  However, this sacrifices the constant insert
     327and removal operations offered by the timer wheel algorithms.  See also
     328:cite:`Gleixner:2006:Hrtimers`.  The implementation can re-use the red-black
     329tree support already used in other areas, e.g. for the thread priority queues.
     330Less code is a good thing for size, testing and verification.
    292332Memory Management
  • common/

    re23f46c ra17535d  
    1616    'amssymb'        : ['\\usepackage{amssymb}'],
    1717    'amstext'        : ['\\usepackage{amstext}'],
     18    'anyfontsize'    : ['\\usepackage{anyfontsize}'],
    1819    'array'          : ['\\usepackage{array}'],
    1920    'atbegshi'       : ['\\usepackage{atbegshi}'],
Note: See TracChangeset for help on using the changeset viewer.