Queues: utility services and data structures

This article continues our look at queues.

Queue Utility Services

Nucleus RTOS has four API calls which provide utility functions associated with queues: reset queue, return information about a queue, return number of queues in the application and return pointers to all queues in the application. The first three of these are implemented in Nucleus SE.

Resetting a Queue

This API call restores the queue to its initial, unused state. Any messages stored in the queue are lost. Any tasks which were suspended on the queue are resumed and receive a return code of NUSE_QUEUE_WAS_RESET .

Nucleus RTOS API Call for Resetting a Queue

Service call prototype:

STATUS NU_Reset_Queue(NU_QUEUE *queue;

Parameters:

queue – pointer to user-define queue control block

Returns:

NU_SUCCESS – the call was completed successfully
NU_INVALID_QUEUE – the queue pointer is not valid

Nucleus SE API Call for Resetting a Queue

This API call supports the key functionality of the Nucleus RTOS API.

Service call prototype:

STATUS NUSE_Queue_Reset(NUSE_QUEUE queue);

Parameters:

queue – the index (ID) of the queue to be reset 

Returns:

NUSE_SUCCESS – the call was completed successfully
NUSE_INVALID_QUEUE – the queue index is not valid

Nucleus SE Implementation of Queue Reset

The initial part of the code of the NUSE_Queue_Reset() API function – after parameter checking – is quite straightforward. The head and tail indexes and the queue’s message count are all set to zero.

When blocking is enabled, additional code takes care of waking up any suspended tasks, thus:

while (NUSE_Queue_Blocking_Count[queue] != 0){   U8 index;             /* check whether any tasks are blocked */                         /* on this queue */   for (index=0; index<NUSE_TASK_NUMBER; index++)   {      if ((LONIB(NUSE_Task_Status[index]) == NUSE_QUEUE_SUSPEND)           && (HINIB(NUSE_Task_Status[index]) == queue))      {         NUSE_Task_Blocking_Return[index] = NUSE_QUEUE_WAS_RESET;         NUSE_Task_Status[index] = NUSE_READY;         break;      }   }   NUSE_Queue_Blocking_Count[queue]--;}#if NUSE_SCHEDULER_TYPE == NUSE_PRIORITY_SCHEDULER   NUSE_Reschedule(NUSE_NO_TASK);#endif

Each task suspended on the queue is marked as “ready” with a suspend return code of NUSE_QUEUE_WAS_RESET . After this process is complete, if the Priority scheduler is in use, a call is made to NUSE_Reschedule() , as one or more higher priority tasks may have been readied and needs to be allowed to run.

Queue Information

This service call obtains a selection of information about a queue. The Nucleus SE implementation differs from Nucleus RTOS in that it returns less information, as object naming, variable message size and suspend ordering are not supported and task suspend may not be enabled.

Nucleus RTOS API Call for Queue Information

Service call prototype:

STATUS NU_Queue_Information(NU_QUEUE *queue, CHAR *name,
VOID **start_address,UNSIGNED *queue_size, UNSIGNED *available,
UNSIGNED *messages, OPTION *message_type,
UNSIGNED *message_size, OPTION *suspend_type,
UNSIGNED *tasks_waiting, 
NU_TASK **first_task);

Parameters:

queue – pointer to the user-supplied queue control block
name – pointer to an 8-character destination area for the message-queue’s name
start_address – a pointer to a pointer, which will receive the address of the start of the queue’s data area
queue_size – a pointer to a variable for holding the total number of UNSIGNED data elements in the queue
available – a pointer to a variable for holding the number of available UNSIGNED data elements in the queue
messages – a pointer to a variable for holding the number of messages currently in the queue
message_type – pointer to a variable for holding the type of messages supported by the queue; valid message types are NU_FIXED_SIZE and NU_ VARIABLE_SIZE
message_size – pointer to a variable for holding the number of UNSIGNED data elements in each queue message; if the queue supports variable-length messages, this number is the maximum message size
suspend_type – pointer to a variable for holding the task suspend type. Valid task suspend types are NU_FIFO and NU_PRIORITY
tasks_waiting – a pointer to a variable which will receive the number of tasks suspended on this queue
first_task – a pointer to a task pointer; the pointer of the first suspended task is placed in this task pointer

Returns:

NU_SUCCESS – the call was completed successfully
NU_INVALID_QUEUE – the queue pointer is not valid

Nucleus SE API Call for Queue Information

This API call supports the key functionality of the Nucleus RTOS API.

Service call prototype:

STATUS NUSE_Queue_Information(NUSE_QUEUE queue,
ADDR *start_address, U8 *queue_size, U8 *available, U8 *messages, U8 *tasks_waiting, NUSE_TASK *first_task);

Parameters:

queue – the index of the queue about which information is being requested
start_address – a pointer to a variable of type ADDR , which will receive the address of the start of the queue’s data area
queue_size – a pointer to a variable of type U8 , which will receive the total number of messages for which the queue has capacity
available – a pointer to a variable of type U8 , which will receive the number of messages for which the queue has currently remaining capacity
messages – a pointer to a variable of type U8 , which will receive the number of messages currently in the queue
tasks_waiting – a pointer to a variable which will receive the number of tasks suspended on this queue (nothing returned if task suspend is disabled)
first_task – a pointer to a variable of type NUSE_TASK which will receive the index of the first suspended task (nothing returned if task suspend is disabled)

Returns:

NUSE_SUCCESS – the call was completed successfully
NUSE_INVALID_QUEUE – the queue index is not valid
NUSE_INVALID_POINTER – one or more of the pointer parameters is invalid

Nucleus SE Implementation of Queue Information

The implementation of this API call is quite straightforward:

*start_address = NUSE_Queue_Data[queue];*queue_size = NUSE_Queue_Size[queue];*available = NUSE_Queue_Size[queue] - NUSE_Queue_Items[queue];*messages = NUSE_Queue_Items[queue];#if NUSE_BLOCKING_ENABLE   *tasks_waiting = NUSE_Queue_Blocking_Count[queue];   if (NUSE_Queue_Blocking_Count[queue] != 0)   {      U8 index;      for (index=0; index<NUSE_TASK_NUMBER; index++)      {         if ((LONIB(NUSE_Task_Status[index]) ==            NUSE_QUEUE_SUSPEND)            && (HINIB(NUSE_Task_Status[index]) == queue))         {            *first_task = index;            break;         }      }   }   else   {      *first_task = 0;   }   #else      *tasks_waiting = 0;      *first_task = 0;   #endif

The function returns the queue status. Then, if blocking API calls is enabled, the number of waiting tasks and the index of the first one are returned (otherwise these two parameters are set to 0).

Obtaining the Number of Queues

This service call returns the number of queues configured in the application. Whilst in Nucleus RTOS this will vary over time and the returned value will represent the current number of queues, in Nucleus SE the value returned is set at build time and cannot change.

Nucleus RTOS API Call for Queue Count

Service call prototype:

UNSIGNED NU_Established_Queues(VOID);

Parameters:

None

Returns:

The number of created queues in the system.

Nucleus SE API Call for Queue Count

This API call supports the key functionality of the Nucleus RTOS API.

Service call prototype:

U8 NUSE_Queue_Count(void);
 

Parameters:

None

Returns:

The number of configured queues in the application

Nucleus SE Implementation of Queue Count

The implementation of this API call is almost trivially simple: the value of the #define symbol NUSE_QUEUE_NUMBER is returned.

Data Structures

Queues utilize five or six data structures – all in RAM and ROM – which, like other Nucleus SE objects, are a series of tables, included and dimensioned according to the number of queues configured and options selected.

I strongly recommend that application code does not access these data structures directly but uses the provided API functions. This avoids incompatibility with future versions of Nucleus SE and unwanted side-effects and simplifies porting of an application to Nucleus RTOS. The details of data structures are included here to facilitate easier understanding of the working of the service call code and for debugging.

Kernel RAM Data

These data structures are:

NUSE_Queue_Head[] – This is an array of type U8 , with one entry for each configured queue, which represents a pointer to the front of the queue of messages. It is used as an index off of the addresses in NUSE_Queue_Data[] (see below).

NUSE_Queue_Tail[] – This is an array of type U8 , with one entry for each configured queue, which represents a pointer to the end of the queue of messages. It is used as an index off of the addresses in NUSE_Queue_Data[] (see below).

NUSE_Queue_Items[] – This is an array of type U8 , with one entry for each configured queue, which represents a count of the current number of messages in the queue. This data is arguably redundant, as its value can be derived from the head and tail indexes, but storing the count simplifies the code.

NUSE_Queue_Blocking_Count[] – This type U8 array contains the counts of how many tasks are blocked on each queue. This array only exists if blocking API call support is enabled.

These data structures are all initialized to zeros by NUSE_Init_Queue() when Nucleus SE starts up. This is logical, as it renders every queue as being empty (unused). A future article will provide a full description of Nucleus SE start-up procedures.

Here are the definitions of these data structures in nuse_init.c file:

RAM U8 NUSE_Queue_Head[NUSE_QUEUE_NUMBER];RAM U8 NUSE_Queue_Tail[NUSE_QUEUE_NUMBER];RAM U8 NUSE_Queue_Items[NUSE_QUEUE_NUMBER];#if NUSE_BLOCKING_ENABLE   RAM U8 NUSE_Queue_Blocking_Count[NUSE_QUEUE_NUMBER];#endif

User RAM

It is the user’s responsibility to provide an area of RAM for data storage for each configured queue. The size of this RAM area must accommodate an array of type ADDR with one entry for each message in the queue.

ROM Data

These data structures are:

NUSE_Queue_Data[] – This is an array of type ADDR , with one entry for each configured queue, which represents a pointer to the data area (discussed in User RAM above) for each queue.

NUSE_Queue_Size[] – This is an array of type U8 , with one entry for each configured queue, which represents the number of messages that may be accommodated by each queue.

These data structures are all declared and initialized (statically, of course) in nuse_config.c , thus:

ROM ADDR *NUSE_Queue_Data[NUSE_QUEUE_NUMBER] ={   /* addresses of queue data areas ------ */};ROM U8 NUSE_Queue_Size[NUSE_QUEUE_NUMBER] ={   /* queue sizes ------ */};

Queue Data Footprint

Like all kernel objects in Nucleus SE, the amount of data memory required for queues is readily predictable.

The ROM data footprint (in bytes) for all the queues in an application may be computed thus:

NUSE_QUEUE_NUMBER * (sizeof(ADDR) + 1)

The kernel RAM data footprint (in bytes) for all the queues in an application, when blocking API calls is enabled, may be computed thus:

NUSE_QUEUE_NUMBER * 3

Otherwise it is:

NUSE_QUEUE_NUMBER * 4

The amount of user RAM (in bytes) required for the queue with index queue is:

NUSE_Queue_Size[queue] * sizeof(ADDR)

Unimplemented API Calls

Four queue API calls found in Nucleus RTOS are not implemented in Nucleus SE:

Create Queue

This API call creates a queue. It is not needed with Nucleus SE, as queues are created statically.

Service call prototype:

STATUS NU_Create_Queue(NU_QUEUE *queue, char *name,
VOID *start_address, UNSIGNED queue_size, OPTION message_type,
UNSIGNED message_size, OPTION suspend_type);

Parameters:

queue – pointer to a user-supplied queue control block; this will be used as a “handle” for the queue in other API calls
name – pointers to a 7-character, null-terminated name for the queue
start_address – starting address for the queue
message_type – type of message supported by the queue; may be NU_FIXED_SIZE or NU_VARIABLE_SIZE
message_size – if the queue supports fixed size messages, this parameter specifies the exact size of each message; otherwise, if the queue supports variable sized messages, this is the maximum message size
suspend_type – specifies how tasks suspend on the queue. Valid options for this parameter are NU_FIFO and NU_PRIORITY , which represent First-In-First-Out (FIFO) and priority-order task suspension, respectively

Returns:

NU_SUCCESS – indicates successful completion of the service
NU_INVALID_QUEUE – indicates the queue control block pointer is NULL or already in use
NU_INVALID_MEMORY – indicates the memory area specified by the start_address is invalid
NU_INVALID_MESSAGE – indicates that the message_type parameter is invalid
NU_INVALID_SIZE – indicates that either the message size is greater than the queue size, or that the queue size or message size is zero
NU_INVALID_SUSPEND – indicates that the suspend_type parameter is invalid

Delete Queue

This API call deletes a previously created queue. It is not needed with Nucleus SE, as queues are created statically and cannot be deleted.

Service call prototype:

STATUS NU_Delete_Queue(NU_QUEUE *queue);

Parameters:

queue – pointer to queue control block

Returns:

NU_SUCCESS – indicates successful completion of the service
NU_INVALID_QUEUE – indicates the queue pointer is invalid

Queue Pointers

This API call builds a sequential list of pointers to all queues in the system. It is not needed with Nucleus SE, as queues are identified by a simple index, not a pointer, and it would be redundant.

Service call prototype:

UNSIGNED NU_Queue_Pointers(NU_QUEUE **pointer_list,
UNSIGNED maximum_pointers);

Parameters:

pointer_list – pointer to an array of NU_QUEUE pointers; this array will be filled with pointers to established queues in the system
maximum_pointers – the maximum number of pointers to place in the array

Returns:

The number of NU_QUEUE pointers placed into the array

Broadcast to Queue

This API call broadcasts a message to all tasks waiting for a message from the specified queue. It is not implemented with Nucleus SE, as it would have added excessive complexity.

Service call prototype:

STATUS NU_Broadcast_To_Queue(NU_QUEUE *queue, VOID *message,
UNSIGNED size, UNSIGNED suspend);

Parameters:

queue – pointer to queue control block
message – pointer to the broadcast message
size – the number of UNSIGNED data elements in the message. If the queue supports variable-length messages, this parameter must be equal to or less than the message size supported by the queue. If the queue supports fixed-size messages, this parameter must be exactly the same as the message size supported by the queue
suspend – specifies whether or not to suspend the calling task if the queue is already full; valid options for this parameter are NU_NO_SUSPEND , NU_SUSPEND or a timeout value.

Returns:

NU_SUCCESS – indicates successful completion of the service
NU_INVALID_QUEUE – indicates the queue pointer is invalid
NU_INVALID_POINTER – indicates that the message pointer is NULL
NU_INVALID_SIZE – Indicates that the message size specified is not compatible with the size specified when the queue was created
NU_INVALID_SUSPEND – indicates that suspend attempted from a non-task thread
NU_QUEUE_FULL – indicates that there is insufficient space in the queue for the message
NU_TIMEOUT – indicates the queue is still full after the timeout has expired
NU_QUEUE_DELETED – queue was deleted while task was suspended
NU_QUEUE_RESET – queue was reset while the task was suspended

Compatibility with Nucleus RTOS

With all aspects of Nucleus SE, it was my goal to maintain as high a level of applications code compatibility with Nucleus RTOS as possible. Queues are no exception and, from a user’s perspective, they are implemented in much the same way as in Nucleus RTOS. There are areas of incompatibility, which have come about where I determined that such an incompatibility would be acceptable, given that the resulting code is easier to understand, or, more likely, could be made more memory efficient. Otherwise, Nucleus RTOS API calls may be almost directly mapped onto Nucleus SE calls. A future article will include further information on using Nucleus SE for users of Nucleus RTOS.

Object Identifiers

In Nucleus RTOS, all objects are described by a data structure – a control block – which has a specific data type. A pointer to this control block serves as an identifier for the queue. In Nucleus SE, I decided that a different approach was needed for memory efficiency, and all kernel objects are described by a number of tables in RAM and/or ROM. The size of these tables is determined by the number of each object type that is configured. The identifier for a specific object is simply an index into those tables. So, I have defined NUSE_QUEUE as being equivalent to U8 ; a variable – not a pointer – of this type then serves as the queue identifier. This is a small incompatibility, which is easily handled if code is ported to or from Nucleus RTOS. Object identifiers are normally just stored and passed around and not operated upon in any way.

Nucleus RTOS also supports naming of queues. These names are only used for target-based debug facilities. I omitted them from Nucleus SE to save memory.

Message Size and Variability

In Nucleus RTOS, a queue may be configured to handle messages which are comprised of any number of unsigned data elements. In Nucleus SE, queues are simplified and only single ADDR messages are supported. Pipes are a little more flexible in Nucleus SE and may offer a useful alternative to queues for some applications; pipes will be covered in the next two articles in this series.

Nucleus RTOS also supports queues with variable size messages, where only the maximum size is specified at creation time. Variable size messages are not supported by Nucleus SE.

Queue Size

The number of messages in a queue in Nucleus SE is limited to 256, as all the index variables and constants are type U8 . Nucleus RTOS is not limited in this way.

Unimplemented API Calls

Nucleus RTOS supports ten service calls to work with queues. Of these, four are not implemented in Nucleus SE. Details of these and of the decision to omit them may be found in Unimplemented API Calls earlier in this article.

The next RTOS Revealed article will look at pipes.


Colin Walls has nearly forty years’ experience in the electronics industry, largely dedicated to embedded software. A frequent presenter at conferences and seminars and author of numerous technical articles and two books on embedded software, Colin is an embedded software technologist with Mentor, a Siemens business, and is based in the UK. His regular blog is located at: http://blogs.mentor.com/colinwalls. He may be reached by email at colin_walls@mentor.com

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.