source: rtems/doc/porting/prioritybitmap.t @ 0660b4f8

4.104.114.84.95
Last change on this file since 0660b4f8 was 0660b4f8, checked in by Joel Sherrill <joel.sherrill@…>, on Nov 16, 1999 at 7:50:56 PM

Changed copyright date to 1999.

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