Follow+Star Public Account Number, don’t miss exciting content
Author | strongerHuang
WeChat Public Account | Embedded Column
During the development process of microcontrollers, “message queues” are often used, and there are various methods of implementation.This article shares the principles and mechanisms of queue implementation.
First, I would like to recommend a platform for embedded job information:
The circular queue is a very useful data structure in actual programming. It is a FIFO data structure that connects the head and tail, using linear space of an array, with simple data organization, allowing quick determination of whether the queue is full or empty, and enabling fast data access.
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 wraps back to position 0 for processing.
Thus, the logic of the circular queue is: connect the array elements q[0] and q[MAXN-1] to form a circular space for storing the queue.
For convenient reading and writing, array indices are 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 determining 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. However, to know who catches up with whom, some auxiliary means are needed for judgment.
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 from catching up with head, i.e., leave at least one element space between the tail node and the head node.
-
-
Queue full: (tail+1)% MAXN ==head
2. Implementation Principle with Additional Flag
a. The first circular queue has the following structure:
typedef struct ringq{ int head; /* head, dequeue direction*/ int tail; /* tail, enqueue direction*/ 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, dequeue direction*/ int tail; /* tail, enqueue direction*/ 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 for empty, tag = 1 for 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 ;}
Looking at the source code, I believe everyone understands the principles involved. In fact, there are methods that do not use tags or other markers; here we will not elaborate further, interested readers can study it themselves.
In RTOS, there is usually a message queue component, and it is one of the most commonly used components.
1. Basic Concept of Message Queue
A message queue is a data structure commonly used for inter-task communication. It allows messages of variable lengths to be sent between tasks or between interrupts and tasks.
Through the message queue service, tasks or interrupt service programs can place one or more messages into the message queue. Similarly, one or more tasks can receive messages from the message queue.
Using the message queue data structure can achieve asynchronous communication between tasks.
2. Characteristics of Message Queue
RTOS message queues have common characteristics:
-
Messages support first-in-first-out (FIFO) queuing and asynchronous read/write operations.
-
Both read and write queues support timeout mechanisms.
-
Messages support last-in-first-out (LIFO) queuing, sending messages to the head of the queue.
-
Messages of any type with varying lengths (not exceeding the maximum node size of the queue) are 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 using the delete queue function.
3. Principles of Message Queue
Here, we will use FreeRTOS as an example for explanation. The message queue control block of FreeRTOS consists of multiple elements. When a message queue is created, the system allocates corresponding memory space for the control block to save some information about the message queue, such as the storage location of the message, head pointer pcHead, tail pointer pcTail, message size uxItemSize, and queue length uxLength, etc.
For example, creating a message queue:
xQueue = xQueueCreate(QUEUE_LEN, QUEUE_SIZE);
Both tasks and interrupt service programs 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 continues not to allow enqueuing, the task will remain in a blocked state waiting for the queue to allow enqueuing. When other tasks read data from the waiting queue (the queue is not full), the task will automatically transition from the blocked state to the ready state. If the waiting time exceeds the specified blocking time, even if the queue still does not allow enqueuing, the task will automatically transition from the blocked state to the ready state, at which point the sending task or interrupt program will receive an error code errQUEUE_FULL.
Sending urgent messages is almost the same as sending messages, with the only difference being 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 and handle them in a timely manner.
When a task attempts to read 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 in the queue. When other tasks or interrupt service programs write data to the waiting queue, the task will automatically transition from the blocked state to the ready state. If 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 operational process of the message queue is illustrated in the following diagram:
4. Blocking Mechanism of Message Queue
Blocking on Dequeue: Tasks can only read data when there is data in the message queue, and the blocking time for waiting for data can be specified.
Blocking on Enqueue: Tasks can only successfully send messages when the queue allows enqueuing; if there is no available message space in the queue, it indicates that the message queue is full, and at this 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 that there are many common points between the “circular queue” and the “message queue”:
1. They are both data structures that contain information such as head, tail, and flags;
2. They both allocate a block of contiguous memory space and can allocate multiple queues.
3. Similar application scenarios, under circumstances with 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 an operating system, while the message queue relies on RTOS (some parameter information of RTOS).
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 delayed and interrupt data transmission, etc.
In conclusion, both types of queues have wide applications, and it is recommended to take the time to study both.
———— END ————
● Column “Embedded Tools”
● Column “Embedded Development”
● Column “Keil Tutorial”
● Selected Tutorials from Embedded Column
Follow the public account and reply “Add Group” to join the technical exchange group according to the rules, reply “1024” to see more content.
Click “Read the Original” to see more shares.
