source: rtems/doc/porting/prioritybitmap.t @ bb4b574

4.104.114.84.95
Last change on this file since bb4b574 was bb4b574, checked in by Joel Sherrill <joel.sherrill@…>, on Apr 25, 2000 at 1:15:14 PM

Merged changes from 4.5 branch and removed that branch.

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