source: rtems-docs/porting/priority_bitmap.rst @ 7497f5e

4.115
Last change on this file since 7497f5e was 7497f5e, checked in by Joel Sherrill <joel@…>, on 10/28/16 at 20:57:11

porting: Review and tidy up multiple formatting issues.

  • Property mode set to 100644
File size: 7.5 KB
Line 
1.. comment SPDX-License-Identifier: CC-BY-SA-4.0
2
3.. COMMENT: COPYRIGHT (c) 1988-2002.
4.. COMMENT: On-Line Applications Research Corporation (OAR).
5.. COMMENT: All rights reserved.
6
7Priority Bitmap Manipulation
8############################
9
10Introduction
11============
12
13The RTEMS chain of ready tasks is implemented as an array of FIFOs with
14each priority having its own FIFO.  This makes it very efficient to
15determine the first and last ready task at each priority.  In addition,
16blocking a task only requires appending the task to the end of the FIFO
17for its priority rather than a lengthy search down a single chain of all
18ready tasks.  This works extremely well except for one problem.  When the
19currently executing task blocks, there may be no easy way to determine
20what is the next most important ready task.  If the blocking task was the
21only ready task at its priority, then RTEMS must search all of the FIFOs
22in the ready chain to determine the highest priority with a ready task.
23
24RTEMS uses a bitmap array to efficiently solve this problem.  The state of
25each bit in the priority map bit array indicates whether or not there is a
26ready task at that priority.  The bit array can be efficiently searched to
27determine the highest priority ready task.  This family of data type and
28routines is used to maintain and search the bit map array.
29
30When manipulating the bitmap array, RTEMS internally divides the 8 bits
31of the task priority into "major" and "minor" components.  The most
32significant 4 bits are the major component, while the least significant
33are the minor component.  The major component of a priority value is
34used to determine which 16-bit wide entry in the``_Priority_Bit_map``
35array is associated with this priority.  Each element in the
36``_Priority_Bit_map`` array has a bit in the ``_Priority_Major_bit_map``
37associated with it.  That bit is cleared when all of the bits in a
38particular``_Priority_Bit_map`` array entry are zero.
39
40The minor component of a priority is used to determine
41specifically which bit in ``_Priority_Bit_map[major]``
42indicates whether or not there is a ready to execute task
43at the priority.
44
45_Priority_bit_map_Control Type
46==============================
47
48The ``_Priority_Bit_map_Control`` type is the fundamental data type of the
49priority bit map array used to determine which priorities have ready
50tasks.  This type may be either 16 or 32 bits wide although only the 16
51least significant bits will be used.  The data type is based upon what is
52the most efficient type for this CPU to manipulate.  For example, some
53CPUs have bit scan instructions that only operate on a particular size of
54data.  In this case, this type will probably be defined to work with this
55instruction.
56
57Find First Bit Routine
58======================
59
60The _CPU_Bitfield_Find_first_bit routine sets _output to the bit number of
61the first bit set in ``_value``.  ``_value`` is of CPU dependent type``Priority_bit_map_Control``.  A stub version of this routine is as follows:
62
63.. code-block:: c
64
65    #define _CPU_Bitfield_Find_first_bit( _value, _output ) \
66    { \
67      (_output) = 0;   /* do something to prevent warnings */ \
68    }
69
70There are a number of variables in using a "find first bit" type
71instruction.
72
73#. What happens when run on a value of zero?
74
75#. Bits may be numbered from MSB to LSB or vice-versa.
76
77#. The numbering may be zero or one based.
78
79#. The "find first bit" instruction may search from MSB or LSB.
80
81RTEMS guarantees that (1) will never happen so it is not a concern.
82Cases (2),(3), (4) are handled by the macros _CPU_Priority_mask() and
83_CPU_Priority_bits_index().  These three form a set of routines which must
84logically operate together.  Bits in the ``_value`` are set and cleared based
85on masks built by CPU_Priority_mask().  The basic major and minor values
86calculated by _Priority_Major() and _Priority_Minor() are "massaged" by
87_CPU_Priority_bits_index() to properly range between the values returned
88by the "find first bit" instruction.  This makes it possible for
89_Priority_Get_highest() to calculate the major and directly index into the
90minor table.  This mapping is necessary to ensure that 0 (a high priority
91major/minor) is the first bit found.
92
93This entire "find first bit" and mapping process depends heavily on the
94manner in which a priority is broken into a major and minor components
95with the major being the 4 MSB of a priority and minor the 4 LSB.  Thus (0
96<< 4) + 0 corresponds to priority 0 - the highest priority.  And (15 <<
974) + 14 corresponds to priority 254 - the next to the lowest priority.
98
99If your CPU does not have a "find first bit" instruction, then there are
100ways to make do without it.  Here are a handful of ways to implement this
101in software:
102
103- a series of 16 bit test instructions
104
105- a "binary search using if's"
106
107- the following algorithm based upon a 16 entry lookup table.  In this
108  pseudo-code, bit_set_table[16] has values which indicate the first
109  bit set:
110
111  .. code-block:: c
112
113      _number = 0 if _value > 0x00ff
114      _value >>=8
115      _number = 8;
116      if _value > 0x0000f
117        _value >=8
118        _number += 4
119        _number += bit_set_table[ _value ]
120
121The following illustrates how the CPU_USE_GENERIC_BITFIELD_CODE macro may
122be so the port can use the generic implementation of this bitfield code.
123This can be used temporarily during the porting process to avoid writing
124these routines until the end.  This results in a functional although lower
125performance port.  This is perfectly acceptable during development and
126testing phases.
127
128.. code-block:: c
129
130    #define CPU_USE_GENERIC_BITFIELD_CODE TRUE
131    #define CPU_USE_GENERIC_BITFIELD_DATA TRUE
132
133Eventually, CPU specific implementations of these routines are usually
134written since they dramatically impact the performance of blocking
135operations.  However they may take advantage of instructions which are not
136available on all models in the CPU family.  In this case, one might find
137something like this stub example did:
138
139.. code-block:: c
140
141    #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE)
142      #define _CPU_Bitfield_Find_first_bit( _value, _output ) \
143      { \
144        (_output) = 0;   /* do something to prevent warnings */ \
145      }
146    #endif
147
148Build Bit Field Mask
149====================
150
151The _CPU_Priority_Mask routine builds the mask that corresponds to the bit
152fields searched by _CPU_Bitfield_Find_first_bit().  See the discussion of
153that routine for more details.
154
155The following is a typical implementation when the
156_CPU_Bitfield_Find_first_bit searches for the most significant bit set:
157
158.. code-block:: c
159
160    #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE)
161      #define _CPU_Priority_Mask( _bit_number ) \
162        ( 1 << (_bit_number) )
163    #endif
164
165Bit Scan Support
166================
167
168The ``_CPU_Priority_bits_index`` routine translates the bit numbers
169returned by ``_CPU_Bitfield_Find_first_bit()`` into something
170suitable for use as a major or minor component of a priority.
171The find first bit routine may number the bits in a
172way that is difficult to map into the major and minor components
173of the priority.  For example, when finding the first bit set in
174the value 0x8000, a CPU may indicate that bit 15 or 16 is set
175based on whether the least significant bit is "zero" or "one".
176Similarly, a CPU may only scan 32-bit values and consider the
177most significant bit to be bit zero or one.  In this case, this
178would be bit 16 or 17.
179
180This routine allows that unwieldy form to be converted
181into a normalized form that is easier to process and use
182as an index.
183
184.. code-block:: c
185
186    #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE)
187      #define _CPU_Priority_bits_index( _priority ) \
188        (_priority)
189    #endif
Note: See TracBrowser for help on using the repository browser.