Changes between Version 13 and Version 14 of FAQ/AlgorithmicComplexity
- Timestamp:
- 11/23/14 06:37:18 (9 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
FAQ/AlgorithmicComplexity
v13 v14 4 4 RTEMS 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. 5 5 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. 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 occurring during the execution of a call. 7 7 8 = SuperCore = 8 9 9 10 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. 11 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 behaviours. 12 11 13 = Message Queue Handler = 12 14 = Variable Length Messages = 13 15 14 16 Longer messages take longer to copy. 17 15 18 = Insertion of Message by Priority = 16 19 … … 18 21 == Pavel Pisa's Sugestion == 19 22 20 Posted to the RTEMS ML (http:// www.rtems.org/ml/rtems-users/2006/february/msg00099.html).23 Posted to the RTEMS ML (http://lists.rtems.org/pipermail/users/2006-February/014021.html). 21 24 22 25 GAVL can solve this