Changes between Version 13 and Version 14 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
Nov 23, 2014, 6:37:18 AM (5 years ago)
Author:
Chris Johns
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FAQ/AlgorithmicComplexity

    v13 v14  
    44RTEMS is composed of multiple software classes and is layered.  Each software class has its own execution characteristics.  Although every effort was made to ensure that after an instance of an object is created, that as many operations as possible execute in a fixed length of time.  In this light, the designers of RTEMS focused on the algorithms used and their algorithmic complexity.  Ideally, all algorithms in RTEMS would be O(constant) which is also know as stable.  However some algorithms have variations based upon what they are doing (e.g. blocking or non-blocking) or how many instances of an object are in the system.  If the algorithm varies in execution time based upon the number of instances of an object, it is said to be O(n) where n is the number of instances.
    55
    6 This page attempts to capture information regarding the algorithmic complexity of the algorithms in RTEMS with a focus on those that are not O(constant).  We do not include operations that create or delete objects.  We will ignore variations due to a particular call blocking instead of a non-blocking since it is obvious blocking takes longer.  We will also ignore variations caused by an interrupt occuring during the execution of a call.
     6This page attempts to capture information regarding the algorithmic complexity of the algorithms in RTEMS with a focus on those that are not O(constant).  We do not include operations that create or delete objects.  We will ignore variations due to a particular call blocking instead of a non-blocking since it is obvious blocking takes longer.  We will also ignore variations caused by an interrupt occurring during the execution of a call.
     7
    78= SuperCore =
    89
    910
    10 This section presents the non-constant order algorithms found in the SuperCore.  The SuperCore is used to implement all supported RTEMS APIs so they inherit these core hahaviors.
     11This section presents the non-constant order algorithms found in the SuperCore.  The SuperCore is used to implement all supported RTEMS APIs so they inherit these core behaviours.
     12
    1113= Message Queue Handler =
    1214= Variable Length Messages =
    1315
    1416Longer messages take longer to copy.
     17
    1518= Insertion of Message by Priority =
    1619
     
    1821== Pavel Pisa's Sugestion ==
    1922
    20 Posted to the RTEMS ML (http://www.rtems.org/ml/rtems-users/2006/february/msg00099.html).
     23Posted to the RTEMS ML (http://lists.rtems.org/pipermail/users/2006-February/014021.html).
    2124
    2225GAVL can solve this