RTEMS Porting Guide
The RTEMS chain of ready tasks is implemented as an array of FIFOs with each priority having its own FIFO. This makes it very efficient to determine the first and last ready task at each priority. In addition, blocking a task only requires appending the task to the end of the FIFO for its priority rather than a lengthy search down a single chain of all ready tasks. This works extremely well except for one problem. When the currently executing task blocks, there may be no easy way to determine what is the next most important ready task. If the blocking task was the only ready task at its priority, then RTEMS must search all of the FIFOs in the ready chain to determine the highest priority with a ready task.
RTEMS uses a bitmap array to efficiently solve this problem. The state of each bit in the priority map bit array indicates whether or not there is a ready task at that priority. The bit array can be efficiently searched to determine the highest priority ready task. This family of data type and routines is used to maintain and search the bit map array.
When manipulating the bitmap array, RTEMS internally divides the
8 bits of the task priority into "major" and "minor" components.
The most significant 4 bits are the major component, while the least
significant are the minor component. The major component of a priority
value is used to determine which 16-bit wide entry in the
_Priority_Bit_map array is associated with this priority.
Each element in the _Priority_Bit_map array has a bit
in the _Priority_Major_bit_map associated with it.
That bit is cleared when all of the bits in a particular
_Priority_Bit_map array entry are zero.
The minor component of a priority is used to determine
specifically which bit in _Priority_Bit_map[major]
indicates whether or not there is a ready to execute task
at the priority.
RTEMS Porting Guide
Copyright © 1988-2008 OAR Corporation