Priority Levels

The figures below show the bitmap of priorities that are ready. The “width” of the table depends on the data type CPU_DATA (see cpu.h), which can either be 8-, 16- or 32-bits. The width depends on the processor used.

µC/OS-III allows up to OS_CFG_PRIO_MAX different priority levels (see os_cfg.h). In µC/OS-III, a low-priority number corresponds to a high-priority level. Priority level zero (0) is thus the highest priority level. Priority OS_CFG_PRIO_MAX-1 is the lowest priority level. µC/OS-III uniquely assigns the lowest priority to the idle task and thus, no other tasks are allowed at this priority level. If there are tasks that are ready-to-run at a given a priority level, then its corresponding bit is set (i.e., 1) in the bitmap table. Notice in the figures below that “priority levels” are numbered from left to right and, the priority level increases (moves toward lower priority) with an increase in table index. The order was chosen to be able to use a special instruction called Count Leading Zeros (CLZ), which is found on many modern processors. This instruction greatly accelerates the process of determining the highest priority level.

os_prio.c contains the code to set, clear, and search the bitmap table. These functions are internal to µC/OS-III and are placed in os_prio.c to allow them to be optimized in assembly language by replacing os_prio.c with an assembly language equivalent os_prio.asm, if necessary.

To determine the highest priority level that contains ready-to-run tasks, the bitmap table is scanned until the first bit set in the lowest bit position is found using OS_PrioGetHighest(). The code for this function is shown in the listing below.

          OS_PRIO  OS_PrioGetHighest (void)
          {
              CPU_DATA  *p_tbl;
              OS_PRIO    prio;
              
              
              prio  = (OS_PRIO)0;
              p_tbl = &OSPrioTbl[0];
              while (*p_tbl == (CPU_DATA)0) {               (1) 
                  prio += DEF_INT_CPU_NBR_BITS;             (2) 
                  p_tbl++;
              }
              prio += (OS_PRIO)CPU_CntLeadZeros(*p_tbl);    (3) 
              return (prio);
          }

The function CPU_CntLeadZeros() simply counts how many zeros there are in a CPU_DATA entry starting from the left (i.e., most significant bit). For example, assuming 32 bits, 0xF0001234 results in 0 leading zeros and 0x00F01234 results in 8 leading zeros.

At first view, the linear path through the table might seem inefficient. However, if the number of priority levels is kept low, the search is quite fast. In fact, there are several optimizations to streamline the search. For example, if using a 32-bit processor and you are satisfied with limiting the number of different priority levels to 64, the above code can be optimized as shown in the listing below. In fact, some processors have built-in “Count Leading Zeros” instructions and thus, the code can even be written with just a few lines of assembly language instead of C. Remember that with µC/OS-III, 64 priority levels does not mean that the user is limited to 64 tasks since with µC/OS-III, any number of tasks are possible at a given priority level (except 0 and OS_CFG_PRIO_MAX-1).

          OS_PRIO  OS_PrioGetHighest (void)
          {
              OS_PRIO  prio;
              
           
              if (OSPrioTbl[0] != (OS_PRIO_BITMAP)0) {
                  prio = OS_CntLeadZeros(OSPrioTbl[0]);
              } else {
                  prio = OS_CntLeadZeros(OSPrioTbl[1]) + 32;
              }
              return (prio);
          }