RTOS: The new wide priority range leads to implementation inefficiencies

[ilg-ul]

In CMSIS RTOS 1.x, priorities ranged from -3 to +3, which sometimes was a bit to little.

In the new proposal, the range was extended to -48 to +48, which is a bit too much.

The problem is not the size of the variable required to store the value, but the implications in the scheduler implementation.

Although the specifications of the CMSIS RTOS should not be made with specific implementations in mind, they should also not prevent common implementations.

The problem is related to the implementation of the READY list.

For very small systems, with only 2-3 threads, it is not a problem to keep a single list, with all threads ordered by priority.

But for medium to large size applications iterating through this list starts to matter, and a common solution is to use a two layer structure, with threads grouped by priorities.

For fast access, the first layer is usually implemented as an array, with each element pointing to a list of threads.

Mandating for almost 100 priorities means this array should have 100 elements, each with two pointers and a counter, which means 4*3 = 12 bytes, with a total of more than 1 KB, spent only on this array.

The alternative to the array is a list of priorities, but if there are many priorities used at the same time, iterating throughout this list is again expensive in time.

So, mandating for a large number of priorities is either expensive in memory or in time.

My approach to this problem was a flexible one, allowing the user to decide how many levels are really needed for each application, and to decide on memory size vs speed compromises.

As such, the definitions use a custom scaler value, defined in the project configuration.

#if !defined(OS_INTEGER_RTOS_PRIORITY_SCALE)
#define OS_INTEGER_RTOS_PRIORITY_SCALE (0)
#endif

      namespace priority
      {
        // This gives a basic range of 16 priorities, easily extensible
        // to 32, 64, 128.
        constexpr uint32_t shift = OS_INTEGER_RTOS_PRIORITY_SCALE;

        enum
          : priority_t
            {
              //
          none = 0, // undefined, thread not initialised
          idle = 1, // system reserved for IDLE thread
          lowest = 2, // lowest available for user code
          low = (2 << shift),
          below_normal = (4 << shift),
          normal = (6 << shift), // default
          above_normal = (8 << shift),
          high = (10 << shift),
          realtime = (12 << shift),
          highest = ((16 << shift) - 3), // highest available for user code
          isr = ((16 << shift) - 2), // system reserved for ISR deferred task
          error = ((16 << shift) - 1) // error
        };
      } /* namespace priority */

As the comment says, the basic range has 16 priorities, with 2-14 available to the user, quite enough for the majority of applications.

Increasing the scaler to 1 extends the range to 32 priorities, 2 gives 64 priorities, 3 gives 128 priorities, and so on.

The scheduler has access to the scaler definition and can statically or dynamically allocate the priorities array or any other memory structures it needs.

My suggestion is to analyse such a scheme for CMSIS RTOS v2.x.

Regards,

Liviu

[RobertRostohar]

The range of priorities can be reduced to more or less the actual number of named priorities in the enum.

The approach with configurable number of priorities sounds interesting. However configuring the actual priority values at the project level is a problem when using library binaries which also use RTOS but with different priority definitions.

Possible solution is to define only the configurable number of priorities (sub priority bits) at the project level where the actual priority values are defined for all available priorities.

Proposal for osPriority:

typedef enum  {
  osPriorityNone          =  0,          ///< no priority (thread not initialized)
  osPriorityIdle          =  1,          ///< priority: idle (system reserved for Idle thread)
  osPriorityLowest        =  8,          ///< priority: lowest (available to user)
  osPriorityLow           =  8,          ///< priority: low
  osPriorityLow1,                        ///< priority: low + 1
  osPriorityLow2,                        ///< priority: low + 2
  osPriorityLow3,                        ///< priority: low + 3
  osPriorityLow4,                        ///< priority: low + 4
  osPriorityLow5,                        ///< priority: low + 5
  osPriorityLow6,                        ///< priority: low + 6
  osPriorityLow7,                        ///< priority: low + 7
  osPriorityBelowNormal   = 16,          ///< priority: below normal
  osPriorityBelowNormal1,                ///< priority: below normal + 1
  osPriorityBelowNormal2,                ///< priority: below normal + 2
  osPriorityBelowNormal3,                ///< priority: below normal + 3
  osPriorityBelowNormal4,                ///< priority: below normal + 4
  osPriorityBelowNormal5,                ///< priority: below normal + 5
  osPriorityBelowNormal6,                ///< priority: below normal + 6
  osPriorityBelowNormal7,                ///< priority: below normal + 7
  osPriorityNormal        = 24,          ///< priority: normal
  osPriorityNormal1,                     ///< priority: normal + 1
  osPriorityNormal2,                     ///< priority: normal + 2
  osPriorityNormal3,                     ///< priority: normal + 3
  osPriorityNormal4,                     ///< priority: normal + 4
  osPriorityNormal5,                     ///< priority: normal + 5
  osPriorityNormal6,                     ///< priority: normal + 6
  osPriorityNormal7,                     ///< priority: normal + 7
  osPriorityAboveNormal   = 32,          ///< priority: above normal
  osPriorityAboveNormal1,                ///< priority: above normal + 1
  osPriorityAboveNormal2,                ///< priority: above normal + 2
  osPriorityAboveNormal3,                ///< priority: above normal + 3
  osPriorityAboveNormal4,                ///< priority: above normal + 4
  osPriorityAboveNormal5,                ///< priority: above normal + 5
  osPriorityAboveNormal6,                ///< priority: above normal + 6
  osPriorityAboveNormal7,                ///< priority: above normal + 7
  osPriorityHigh          = 40,          ///< priority: high
  osPriorityHigh1,                       ///< priority: high + 1
  osPriorityHigh2,                       ///< priority: high + 2
  osPriorityHigh3,                       ///< priority: high + 3
  osPriorityHigh4,                       ///< priority: high + 4
  osPriorityHigh5,                       ///< priority: high + 5
  osPriorityHigh6,                       ///< priority: high + 6
  osPriorityHigh7,                       ///< priority: high + 7
  osPriorityRealtime      = 48,          ///< priority: real-time
  osPriorityRealtime1,                   ///< priority: real-time + 1
  osPriorityRealtime2,                   ///< priority: real-time + 2
  osPriorityRealtime3,                   ///< priority: real-time + 3
  osPriorityRealtime4,                   ///< priority: real-time + 4
  osPriorityRealtime5,                   ///< priority: real-time + 5
  osPriorityRealtime6,                   ///< priority: real-time + 6
  osPriorityRealtime7,                   ///< priority: real-time + 7
  osPriorityHighest       = 55,          ///< priority: highest (available to user)
  osPriorityISR           = 56,          ///< priority: ISR (system reserved for ISR deferred thread)
  osPriorityError         = 0xFF,        ///< system cannot determine priority (invalid thread)
  os_priority_reserved    = 0x7FFFFFFF   ///< prevent from enum down-size compiler optimization.
} osPriority;

Each priority available to user code (Low, BelowNormal, Normal, AboveNormal, High, Realtime) is extended with a 3-bit sub priority.

Maximum number of priority levels for user code is 48.

When RTOS implementation is sensible to the number of priority levels it can implement the actual number of different levels according to user configurable number of sub priorities (1,2,4 or 8).

[ilg-ul]

The approach with configurable number of priorities sounds interesting. However configuring the actual priority values at the project level is a problem when using library binaries which also use RTOS but with different priority definitions. ... When RTOS implementation is sensible to the number of priority levels it can implement the actual number of different levels according to user configurable number of sub priorities (1,2,4 or 8).

in this case why not make the default range the widest available on 1 byte, and let the implementation scale it down if necessary.

using the configurable number of priorities algorithm, that would translate to:

        constexpr uint32_t shift = 4;

        enum
          : priority_t
            {
              //
          none = 0, // undefined, thread not initialised
          idle = 1, // system reserved for IDLE thread
          lowest = 2, // lowest available for user code
          low = (2 << shift),
          below_normal = (4 << shift),
          normal = (6 << shift), // default
          above_normal = (8 << shift),
          high = (10 << shift),
          realtime = (12 << shift),
          highest = ((16 << shift) - 3), // highest available for user code
          isr = ((16 << shift) - 2), // system reserved for ISR deferred task
          error = ((16 << shift) - 1) // error
        };

which will result in the following:

          none = 0,
          idle = 1,
          lowest = 2,
          low = 32,
          below_normal = 64,
          normal = 96,
          above_normal = 128,
          high = 160,
          realtime = 192,
          highest = 253,
          isr = 254,
          error = 255,

to me this seems like a fairly uniform distribution.

I can also make this the default in CMSIS++, however allowing the user to reduce the scale if no binary libraries are used.

[ilg-ul]

osPriorityNormal1 ... osPriorityNormal7

as for defining all these intermediate levels, I would not do it; instead I would suggest the user to define specific priorities for each specific thread:

#define CONFIG_THREAD_ALPHA_PRIORITY (osPriorityNormal + 1)
#define CONFIG_THREAD_BRAVO_PRIORITY (osPriorityLow + 3)
#define CONFIG_THREAD_CHARLIE_PRIORITY (osPriorityHigh + 7)

[ilg-ul]

for completeness, here are the CMSIS++ files that define the priorities:

• the C++ definition: cmsis-plus/rtos/os.h
• the C definitions: cmsis-plus/rtos/os-c-decls.h - not used directly, but included via cmsis-plus/rtos/os-c-api.v

(I already updated the CMSIS++ priorities to use the full byte range by default)

[ilg-ul]

a problem when using library binaries which also use RTOS but with different priority definitions.

while thinking more about this, I discovered another weakness of the current CMSIS RTOS specifications: it can be safely used only to build applications from source code; distributing binary libraries is possible only if the libraries and the final application are built using exactly the same <cmsis_os.h>, otherwise behaviour is undefined.

the reason for this is the heavy reliance on macros, to define RTOS implementation.

in other words, if you build a library with the RTX customised <cmsis_os.h>, I have little chance to link it with an application built with my own customised <cmsis_os.h>, because I have different definitions for the osXyzDef() macros.

so your concern about priorities, although correct in principle, no longer matters since building binary libraries is problematic.

[RobertRostohar]

as for defining all these intermediate levels, I would not do it; instead I would suggest the user to define specific priorities for each specific thread.

Would be nice however mixing enums with ints causes compiler and MISRA warnings.

osPriority priority;

priority = (osPriorityNormal + 1);
// compiler warning: enumerated type mixed with another type
// MISRA warning: Converting enum 'osPriority' to 'int'

This is the reason for defining all possible levels.

why not make the default range the widest available on 1 byte, and let the implementation scale it down if necessary.

This goes towards having a large number of priority levels which we wanted to avoid in the first place. It also defeats the named levels concept.

6 group priorities with 3-bit sub priority provides 48 levels which seems to be an acceptable compromise.

We could consider a 4-bit sub priority with 96 levels (all defined in the enum). Going over 100 levels doesn't make sense.

distributing binary libraries is possible only if the libraries and the final application are built using exactly the same

Correct. There is only one definition for osPriority values (with all levels defined).

RTOS implementation however can be configured to use less sub levels by accepting all values but scaling them internally. For example when RTOS is configured to use only 2-bit sub priority than priorities Normal and Normal+1 would be effectively the same.

The user needs to know how many sub levels the library requires and also the application in order to configure the number of sub levels for RTOS implementation which supports this.

This should help specific RTOS implementations which have configurable number of priorities. Typically the number of priorities is fixed.

The recommendation for the user would be to still use group priorities and the sub priorities only if really needed. Libraries typically won't use threads or only a few and the expectation would anyway be that they only use group priorities.

Note: osPriorityError is not a real thread priority and the value can be outside the real priority range. It is only used as an error indicator for GetPriority function.

[ilg-ul]

Would be nice however mixing enums with ints causes compiler and MISRA warnings.

yes, I know, but in CMSIS++ I solved the problem differently, I define os_thread_priority_t to be an uint, not an enum, and separately define the enum values, which can then be used freely in arithmetic expressions.

for reference, the definitions are in cmsis-plus/rtos/os-c-decls.h.

as for using priorities in libraries, if you want it to be portable, you need to pass the value via a run-time parameter.

binary libraries

I'm not sure you got the point related to the problems of distributing binaries.

hard-coding priorities is a minor nuisance compared to hardcoding the content of the osThreadDef(), osMutexDef(), etc definition structures, which, according to the documentation, "CAN BE CHANGED" in different CMSIS RTOS ports.

in other words, if you use a MessageQueue in your library, and you build it with the RTX specific <cmsis_os.h>, you expect the RTX to dynamically allocate the queue. If I have my own <cmsis_os.h> where I want to use statically allocated queues, I have different macros to define the queues, and my queue creation function expects exactly my definitions, if you call it with the RTX definitions it'll probably crash.

the conclusion is that any function that creates objects (osThreadCreate(), osTimerCreate(), osMutexCreate(), osSemaphoreCreate(), etc) cannot be used in a library, because it depends on a non-portable, implementation dependent macro.

[RobertRostohar]

hard-coding priorities is a minor nuisance compared to hardcoding the content of the osThreadDef(), osMutexDef(), etc definition structures, which, according to the documentation, "CAN BE CHANGED" in different CMSIS RTOS ports.

Yes, that is an issue and we will look into it, also in the light of dynamic objects.

the conclusion is that any function that creates objects (osThreadCreate(), osTimerCreate(), osMutexCreate(), osSemaphoreCreate(), etc) cannot be used in a library, because it depends on a non-portable, implementation dependent macro.

Not completely correct. "osObjectCreate" functions can be used since they only use a pointer to the definition structure. However the "osObjectDef" macros cannot be used in a binary library but rather in source module.

[ilg-ul]

"osObjectCreate" functions can be used since they only use a pointer to the definition structure.

yes, sure, they can be used, but the result is unpredictable.

otherwise what would be the point of passing a pointer to a structure that has a different definition, coming from a different header?

[RobertRostohar]

they can be used, but the result is unpredictable.

Not if the library consists of a binary (with RTOS functions) and a source module (with osObjectDef's).

pointer to a structure that has a different definition, coming from a different header?

Application and the library source is compiled with the same definitions coming from the same header.

[ilg-ul]

Application and the library source is compiled with the same definitions coming from the same header.

well, in this case all discussions of priorities definitions (and macro definitions, and generally cmsis_os.h definitions) are no longer relevant, since library writers can do nothing but choose a RTOS; it is the RTOS author who writes the cmsis_os.h, and that header may very well define priorities in any range, shape and colour, without having to care for compatibility with other RTOS implementations.

[RobertRostohar]

Let me clarify my previous post by an example:

Library consist of:

A. Modules which use CMSIS RTOS functions but no osObjectDef macros
Modules can be compiled with any CMSIS RTOS implementation.

B. Module with osObjectDef macros
Provided as source and is compiled together with the application.

Library is shipped with a prebuilt binary and a source module with osObjectDef macros.

User still decides which RTOS implementation to choose.

[ilg-ul]

this should probably work, although I would not consider it very elegant.

personally I would move everything non-portable out of the library and into the source file (object creation, use of priorities, etc)

as for the C++ API, the modern trend being towards constexpr, inlines and inline templates, to give the compiler the best chance to optimise, I would be very cautious to recommend binary libraries. but I can understand that there is life outside the open source world too.

[RobertRostohar]

Existing priorities available to user (Low, BelowNormal, Normal, AboveNormal, High, Realtime) are extended with a 3-bit sub priority. Priorities are encoded in a way that can be scaled down according to user configurable number of sub priorities (1,2,4 or 8).

f595671