![]() |
F´ Flight Software - C/C++ Documentation devel
A framework for building embedded system applications to NASA flight quality standards.
|
The ISF Os::Queue
provides a message queue interface for asynchronous ISF ports. Many operating systems provide their own inter-process communication (IPC) queues (ie. POSIX, VxWorks, SysV), which have traditionally been used as the underlying implementation for Os::Queue
. In contrast, this Pthreads implementation is hand coded C++ code tailored to the ISF Os::Queue
interface. Its only dependency on non-standard libraries is <pthread.h>
, which is used for access and control flow of the internal queue data structure (ie. pthread_mutex_lock
, pthread_cond_wait
, etc.). The Pthread implementation provides the following advantages over the operating system provided IPC queues:
Os::Queue
deconstructor has been called. ISF currently does not spread different threads of execution in different memory spaces on Darwin and Linux, so this is an acceptable solution.The Pthread queues can be configured in one of two ways depending on mission needs: first-in-first-out (FIFO) or priority. The FIFO queue is implemented using a circular buffer with O(log(1)) enqueue and dequeue time. The priority queue is implemented using a stable maximum binary heap with O(log(n)) enqueue and dequeue time. Note: A stable maximum binary heap has the property that items pulled off the queue are in order of decreasing priority. Items of equal priority are pulled off in FIFO order.
NOTE: POSIX queues use a dynamically sized red-black tree for the message queue data structure. This data structure also has an O(log(n)) enqueue and dequeue time.
Requirement | Description | Rationale | Verification Method |
---|---|---|---|
ISF-Q-001 | The Pthreads queue shall conform to the ISF Os::Queue interface. | Ensures the queue can be used for ISF components | Inspection |
ISF-Q-002 | The Pthreads queue shall not use dynamic memory, except at initialization. | Conform to flight software guidelines. | Inspection |
ISF-Q-003 | The Pthreads queue shall not use operating system parameters for size limits. | Ensure that the queue sizes can be changed by the user without changing kernel parameters. | Inspection |
The Pthreads queue uses the following constants, specified at instantiation:
The queue maintains the following state:
U8*
buffer of size: (Message Size + sizeof(NATIVE_UINT_TYPE)
) * Depthsizeof(NATIVE_UINT_TYPE)
* 3 * Depth.A maximum binary heap data structure is a binary tree with the following constraints:
The Pthreads heap implementation is also stable, which means it satisfies the following additional constraint:
This ensures that messages of equal priority are dequeued in FIFO order.
This section provides a summary of the code included in the C++ implementation files.
Queue.cpp
:** This is the implementation of the ISF Os::Queue
class. This file provides synchronization between threads reading and writing to the queue, and passes data to and from the underlying data structure.BufferQueue.hpp
:** This file outlines an interface to a generic queue data structure.FIFOBufferQueue.cpp
:** This file implements a first-in-first-out queue data structure, conforming to BufferQueue.hpp
.PriorityBufferQueue.cpp
:** This file implements a priority queue data structure, conforming to BufferQueue.hpp
. It uses files in MaxHeap/ to perform priority queueing.BufferQueueCommon.cpp
:** This file implements various common methods for BufferQueue.hpp
.MaxHeap/MaxHeap.hpp
:** This file outlines an interface to a generic maximum heap data structure, where NATIVE_INT_TYPE
is used for priority and a NATIVE_UINT_TYPE
is stored as data.MaxHeap/MaxHeap.cpp
:** This file implements a stable maximum heap conforming to MaxHeap/MaxHeap.hpp
.Note: To use the FIFO queue implementation, a user must include Queue.cpp
, FIFOBufferQueue.cpp
, and BufferQueueCommon.cpp
in the compilation. To use the priority queue implementation, the user must include Queue.cpp
, PriorityBufferQueue.cpp
, BufferQueueCommon.cpp
, and MaxHeap/MaxHeap.cpp
.
There are 3 unit tests used to validate the Pthreads queue implementation at different levels of abstraction.
The maximum heap unit tests are located in Os/Pthread/MaxHeap/test/ut
. These tests validate the functionality of the maximum heap data structure. Test names and descriptions are listed below:
The buffer queue unit tests are located in Os/Pthread/test/ut
. These tests validate the functionality of the underlying queue data structure. Note: These tests do NOT test any blocking behavior of the queue. Test names and descriptions are listed below:
The queue unit tests are located in Os/test/ut
. These tests validate the functionality of the queue as well as the blocking behavior at the component interface level. Test names and descriptions are listed below:
The performance results for tests 5.3.3 for the Pthreads queue and the Posix queue were run on a Virtual Box VM (hosted on a Mac) and given 4 execution cores (April 2016). The test results can be seen below:
Pthreads queue results:
Posix queue results:
The Pthreads queues are significantly faster than posix queues on a single core. The Pthreads queue is marginally slower in a multi-threaded environment, but its performance is still very similar to the Posix queue implementation. Based on these results the Pthreads queue is performant enough for single core flight systems. It also looks to have reasonable performance when multi-threaded. If we wanted better multi-core performance, we could look into implementing a lock-free concurrent max heap data structure.