| 18 | == GAVL=== |
| 19 | |
| 20 | From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html). |
| 21 | |
| 22 | GAVL can solve this |
| 23 | |
| 24 | insert = search O(log(n)), |
| 25 | max one re-ballance O(1) with max O(log(n)) heights update. |
| 26 | |
| 27 | cut first = O(log(n)) find first and O(1) cut, zero re-balances |
| 28 | O(log(n)) heights update |
| 29 | First Last Enhanced Speed (FLES) alternative |
| 30 | O(1) find first and O(1) cut, zero rebalance |
| 31 | O(log(n)) heights update and next prepare |
| 32 | |
| 33 | premature delete = O(1) detach, O(log(n)) heights update |
| 34 | and max O(log(n)) updates and re-balances, |
| 35 | may be, it is possible to prove, that count of re-balances |
| 36 | is lower or can be decreased. It is possible to omit |
| 37 | re-balances at all, but AVL tree properties would be lost |
| 38 | => height is not in range from |
| 39 | log2(n+1)+1 to 1.44*log2(n+2)-0.328+1. |
| 40 | The +1 one in GAVL is cost for zero re-balanced |
| 41 | cut first operation. |
| 42 | |
| 43 | More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut |
| 44 | |
| 45 | There is no problem with RTEMS compatible license, in the fact uLUt is extensively used in our RTEMS based application for drivers and GUI code. |
| 46 | |
| 47 | Code is used in more components from OCERA project http://www.ocera.org |
| 48 | and proven to be extremely stable. |
| 49 | It is used even in http://ulan.sourceforge.net/ and SuiTk sources. |
| 50 | GAVL code doesnot need any dynamic memory allocations and it |
| 51 | significantly outperforms even heap-tree algorithm with preallocated |
| 52 | array for all elements (Heap tree is suggested solution |
| 53 | for priority queues in the classic theory texts). |
| 54 | |
| 55 | GAVL is result of my personal rethinking of AVL algorithm. |
| 56 | My C implementation can even ensure type safety, but macro magic |
| 57 | can be too much for you. Base of algorithm can be rewritten from |
| 58 | generic code to one purpose one. In the fact "gcc -E" does the work |
| 59 | and I have ported this way with some manual simplifications |
| 60 | some uLUt code even on 8051 based chips. |
| 73 | The list of free blocks is managed as an unsorted listed. Allocating a memory block requires a linear search of a ==MS 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. |
| 74 | |
| 75 | 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. |
| 76 | = SuperCore = |
| 77 | |
| 78 | |
| 79 | 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. |
| 80 | = Message Queue Handler = |
| 81 | = ==Variable Length Messages=== |
| 82 | |
| 83 | Longer messages take longer to copy. |
| 84 | |
| 85 | ===Insertion of Message by Priority=== |
| 86 | |
| 87 | When priority ordering of messages is used, the insertion is into a simple list and is O(n) where n is the number of messages pending. |
| 88 | |
| 89 | ====GAVL=== |
| 90 | |
| 91 | From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html). |
| 92 | |
| 93 | GAVL can solve this |
| 94 | |
| 95 | insert = search O(log(n)), |
| 96 | max one re-ballance O(1) with max O(log(n)) heights update. |
| 97 | |
| 98 | cut first = O(log(n)) find first and O(1) cut, zero re-balances |
| 99 | O(log(n)) heights update |
| 100 | First Last Enhanced Speed (FLES) alternative |
| 101 | O(1) find first and O(1) cut, zero rebalance |
| 102 | O(log(n)) heights update and next prepare |
| 103 | |
| 104 | premature delete = O(1) detach, O(log(n)) heights update |
| 105 | and max O(log(n)) updates and re-balances, |
| 106 | may be, it is possible to prove, that count of re-balances |
| 107 | is lower or can be decreased. It is possible to omit |
| 108 | re-balances at all, but AVL tree properties would be lost |
| 109 | => height is not in range from |
| 110 | log2(n+1)+1 to 1.44*log2(n+2)-0.328+1. |
| 111 | The +1 one in GAVL is cost for zero re-balanced |
| 112 | cut first operation. |
| 113 | |
| 114 | More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut |
| 115 | |
| 116 | There is no problem with RTEMS compatible license, in the fact uLUt is extensively used in our RTEMS based application for drivers and GUI code. |
| 117 | |
| 118 | Code is used in more components from OCERA project http://www.ocera.org |
| 119 | and proven to be extremely stable. |
| 120 | It is used even in http://ulan.sourceforge.net/ and SuiTk sources. |
| 121 | GAVL code doesnot need any dynamic memory allocations and it |
| 122 | significantly outperforms even heap-tree algorithm with preallocated |
| 123 | array for all elements (Heap tree is suggested solution |
| 124 | for priority queues in the classic theory texts). |
| 125 | |
| 126 | GAVL is result of my personal rethinking of AVL algorithm. |
| 127 | My C implementation can even ensure type safety, but macro magic |
| 128 | can be too much for you. Base of algorithm can be rewritten from |
| 129 | generic code to one purpose one. In the fact "gcc -E" does the work |
| 130 | and I have ported this way with some manual simplifications |
| 131 | some uLUt code even on 8051 based chips. |
| 132 | |
| 133 | ===Message Broadcast=== |
| 134 | |
| 135 | Broadcasting a message results in every task currently blocking on a particular message queue waiting for a message to receive the same message. The time required to execute this service is O(n) where n is the number of blocked tasks. |
| 136 | |
| 137 | ==Watchdog Timer== |
| 138 | |
| 139 | ===Insertion of a Timer=== |
| 140 | |
| 141 | Timers are managed as a delta chain. Insertion is O(n) where n is the number of timers on the chain (e.g. active). |
| 142 | |
| 143 | ==Heap== |
| 144 | |
| 145 | The heap is used for variable memory allocation. |
| 146 | |
| 147 | ===Memory Allocation=== |
| 148 | |