Follow+Star Public Account Number, don’t miss exciting content
Author | strongerHuang
WeChat Public Account | Embedded Column
In the process of microcontroller development, the “message queue” is often used, and there are various implementation methods.This article shares the principles and mechanisms of queue implementation.
The circular queue is a very useful data structure in actual programming, it is a FIFO data structure with a connected head and tail, using linear space of an array, data organization is simple, can quickly know whether the queue is full or empty, and can access data at high speed.
The circular queue is usually used in communication fields, such as UART, USB, CAN, networks, etc.
1. Principle of Circular Queue Implementation
There is no circular structure in memory, so the circular queue is actually implemented using the linear space of an array. When data reaches the end, it will return to position 0 for processing.
Thus, the logic of the circular queue: connect array elements q[0] and q[MAXN-1] to form a circular space for storing the queue.
To facilitate read and write, array indices are also used to indicate the read and write positions of the queue: head/tail. Here, head points to the readable position, and tail points to the writable position.
The key to the circular queue is to determine whether the queue is empty or full. When tail catches up with head, the queue is full; when head catches up with tail, the queue is empty. But how to know who is catching up with whom requires some auxiliary means to judge.
There are two methods to determine whether the circular queue is empty or full:
a. Add a flag variable tag
-
When head catches up with tail, the queue is empty, set tag=0
-
When tail catches up with head, the queue is full, set tag=1
b. Restrict tail catching up with head, that is, at least one element space must be left between the tail node and the head node.
-
-
Queue full: (tail+1)% MAXN ==head
2. Principle of Additional Flag Implementation
a. The first circular queue has the following structure:
typedef struct ringq{ int head; /* head, direction of dequeuing */ int tail; /* tail, direction of enqueuing */ int tag ; int size ; /* total size of the queue */ int space[RINGQ_MAX]; /* queue space */}RINGQ;
q->head = q->tail = q->tag = 0;
( q->head == q->tail) && (q->tag == 0)
((q->head == q->tail) && (q->tag == 1))
Enqueue operation, if the queue is not full, then write:
q->tail = (q->tail + 1) % q->size ;
Dequeue operation, if the queue is not empty, read from head.
The next readable position is:
q->head = (q->head + 1) % q->size
#ifndef __RINGQ_H__#define __RINGQ_H__
#ifdef __cplusplus
extern "C" {
#endif
#define QUEUE_MAX 20
typedef struct ringq{ int head; /* head, direction of dequeuing */ int tail; /* tail, direction of enqueuing */ int tag ; /* flag for empty or full */ int size ; /* total size of the queue */ int space[QUEUE_MAX]; /* queue space */}RINGQ;
/* First design method: When head == tail, tag = 0 means empty, equals 1 means full.*/
extern int ringq_init(RINGQ * p_queue);
extern int ringq_free(RINGQ * p_queue);
/* Add data to the queue */
extern int ringq_push(RINGQ * p_queue,int data);
/* Get data from the queue */
extern int ringq_poll(RINGQ * p_queue,int *p_data);
#define ringq_is_empty(q) ( (q->head == q->tail) && (q->tag == 0))
#define ringq_is_full(q) ( (q->head == q->tail) && (q->tag == 1))
#define print_ringq(q) printf("ring head %d,tail %d,tag %d\n", q->head,q->tail,q->tag);
#ifdef __cplusplus}
#endif
#endif /* __RINGQ_H__ */
#include <stdio.h>
#include "ringq.h"
int ringq_init(RINGQ * p_queue){ p_queue->size = QUEUE_MAX ;
p_queue->head = 0; p_queue->tail = 0;
p_queue->tag = 0;
return 0;}
int ringq_free(RINGQ * p_queue){ return 0;}
int ringq_push(RINGQ * p_queue,int data){ print_ringq(p_queue);
if(ringq_is_full(p_queue)) {
printf("ringq is full\n"); return -1; }
p_queue->space[p_queue->tail] = data;
p_queue->tail = (p_queue->tail + 1) % p_queue->size ;
/* At this point, the queue must be full */ if(p_queue->tail == p_queue->head) { p_queue->tag = 1; }
return p_queue->tag ; }
int ringq_poll(RINGQ * p_queue,int * p_data){ print_ringq(p_queue); if(ringq_is_empty(p_queue)) {
printf("ringq is empty\n"); return -1; }
*p_data = p_queue->space[p_queue->head];
p_queue->head = (p_queue->head + 1) % p_queue->size ;
/* At this point, the queue must be empty */ if(p_queue->tail == p_queue->head) { p_queue->tag = 0; } return p_queue->tag ;}</stdio.h>
Seeing the source code, I believe everyone understands the principles involved. In fact, there are methods that do not use tags or other flags, which will not be discussed further here. Interested readers can study it themselves.
In RTOS, there is basically a message queue component, which is also one of the most commonly used components.
1. Basic Concept of Message Queue
Message queues are a data structure commonly used for inter-task communication, allowing tasks and interrupts to pass information between each other, enabling tasks to receive variable-length messages from other tasks or interrupts.
Through the message queue service, tasks or interrupt service routines can place one or more messages into the message queue. Similarly, one or more tasks can obtain messages from the message queue.
Using the message queue data structure allows asynchronous communication between tasks.
2. Characteristics of Message Queues
RTOS message queues have common characteristics:
-
Messages support first-in-first-out queuing and asynchronous read/write operations.
-
Both read and write queues support timeout mechanisms.
-
Messages support last-in-first-out queuing, sending messages to the front of the queue (LIFO).
-
Messages of any type with different lengths (not exceeding the maximum node value of the queue) can be allowed.
-
A task can receive and send messages from any message queue.
-
Multiple tasks can receive and send messages from the same message queue.
-
When the queue is no longer in use, it can be deleted through the deletion function.
3. Principles of Message Queue
Taking FreeRTOS as an example for explanation. The message queue control block in FreeRTOS consists of multiple elements, and when the message queue is created, the system allocates corresponding memory space for the control block to store some information about the message queue, such as the storage location of messages, head pointer pcHead, tail pointer pcTail, message size uxItemSize, and queue length uxLength, etc..
For example, to create a message queue:
xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);
Tasks or interrupt service routines can send messages to the message queue. When sending a message, if the queue is not full or allows overwriting, FreeRTOS will copy the message to the tail of the message queue; otherwise, it will block according to the user-specified blocking timeout. During this time, if the queue does not allow enqueueing, the task will remain in a blocked state waiting for the queue to allow enqueueing. When other tasks read data from their waiting queue (the queue is not full), the task will automatically transition from the blocked state to the ready state. When the waiting time exceeds the specified blocking time, even if the queue still does not allow enqueueing, the task will automatically transition from the blocked state to the ready state, at which point the sending task or interrupt will receive an error code errQUEUE_FULL.
The process of sending urgent messages is almost the same as sending regular messages, the only difference is that when sending urgent messages, the sending position is the head of the message queue rather than the tail, so that the receiver can prioritize receiving urgent messages for timely processing.
When a task attempts to read from a queue, it can specify a blocking timeout. During this time, if the queue is empty, the task will remain in a blocked state waiting for valid data from the queue. When other tasks or interrupt service routines write data into its waiting queue, the task will automatically transition from the blocked state to the ready state. When the waiting time exceeds the specified blocking time, even if there is still no valid data in the queue, the task will automatically transition from the blocked state to the ready state.
When the message queue is no longer in use, it should be deleted to free system resources. Once the operation is complete, the message queue will be permanently deleted.
The operation process of the message queue is shown in the figure below:
4. Blocking Mechanism of Message Queue
Blocking on Dequeue: A task can only read data when the message queue has data, and it can specify the blocking time to wait for data.
Blocking on Enqueue: A sender can only successfully send a message when the queue allows enqueueing; when there is no available message space in the queue, it indicates that the message queue is full, at which point the system will block the task according to the user-specified blocking timeout.
If multiple tasks are blocked on a message queue, these blocked tasks will be sorted according to task priority, with higher-priority tasks gaining access to the queue first.
Similarities and Differences between Circular Queue and Message Queue
Through the above analysis, you will find many common points between the “circular queue” and “message queue”:
1. They are both a type of data structure, containing information such as head, tail, and flags;
2. They both allocate a contiguous block of memory space and can allocate multiple queues.
3. Similar application scenarios, in cases of large data throughput, such as in communication fields.
Of course, they also have some differences:
1. The “circular queue” can be used independently or in conjunction with the operating system, while the message queue relies onRTOS (some RTOS parameter information).
2. The “circular queue” occupies fewer resources and is more suitable for systems with limited resources.
3. The “message queue” is more flexible in RTOS applications, such as delay, interrupt data transmission, etc.
Finally, both types of queues have broad applications, and I recommend studying both when you have time.
The seven essential components of power circuits for hardware
2025-01-08
How long will it take to read the Linux kernel source code?
2025-01-03
Recommended books on power integrity for embedded hardware
2024-12-25
This book tells you what knowledge chain is needed to learn embedded C language
Click here if you like the article
