RTEMS Algorithmic Complexity

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.

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.

SuperCore?

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.

Message Queue Handler

Variable Length Messages

Longer messages take longer to copy.

Insertion of Message by Priority

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.

Message Broadcast

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.

Watchdog Timer

Insertion of a Timer

Timers are managed as a delta chain. Insertion is O(n) where n is the number of timers on the chain (e.g. active).

Heap

The heap is used for variable memory allocation.

Memory Allocation

The list of free blocks is managed as an unsorted listed. Allocating a memory block requires a linear search of all free blocks until one large enough to satisfy the request is located.

Classic API

The Classic API inherits the following non-constant time algorithms from the SuperCode?

• Variable length message support
• Message broadcast
• Timer insertion (timer manager, delays, and timeouts)
• Memory Allocation

Region Manager

Freeing Memory

Although freeing memory is O(constant), freeing a large block of memory may result in the outstanding requests of multiple blocked tasks being satisfied.

POSIX API

The POSIX API inherits the following non-constant time algorithms from the SuperCode?

• Variable length message support
• Priority based message insertion
• Timer insertion (timer manager, delays, and timeouts)

Message Queue Manager

mq_open

There is a linear search for the message queue name.= mq_unlink =

There is a linear search for the message queue name.

Semaphore Manager

sem_open

There is a linear search for the semaphore name.= sem_unlink =

There is a linear search for the semaphore name.

Timer Manager

Timer Id Management

There is a linear search of slots in a timer array.

FIX: This is a bad implementation which was originally submitted by a user who did not understand the standard pattern of object management. This pattern requires objects be preallocated at system initialization time and object creation only removes one from an inactive object list. Normally, RTEMS object Id to pointer translation is constant order so, this manager is fixable.

UPDATE: As of 1 Feb 2006, JoelSherrill? is testing a new implementation of POSIX timers which will not have O(n) object Id management.