Introduction to Queues and Overview of STM32 Advanced Serial Ring Ring Buffers Using Ring Queues

Queue concept

Before that, let's review the basic concept of queues: Queue: A First In First Out (FIFO) linear table that only allows insertion (into the queue) at one end, at the other end Delete (dequeue).

The characteristics of the queue

Similar to the ticket queuing window, first-timers can see that they can buy tickets first, and then go first. Later people can only buy tickets later.

Two common forms of queues

Regular queue

In a computer, each piece of information is stored in a storage unit. For instance, some of the small square grids in the figure above are storage units. You can understand them as common arrays and store our information one by one.

When there is a lot of data, we can not store all the data, then when the computer processes data, it can only deal with the first, then after processing, it will release the data, and then deal with the next one. Then, the memory of the processed data is wasted. Because later data can only be queued back, if you want to move the remaining data forward one time, then the efficiency will be low, certainly not realistic, so the ring queue appears.

Ring Queue

Its queue is a ring, it avoids the shortcomings of the ordinary queue, it is a bit difficult to understand it, in fact it is a queue, the same as the head of the queue, the end of the queue, the same as the first-in first-out (FIFO). We use a clockwise method to sort the queue.

Head: The end that is allowed to be deleted is called the head of the team. Tail: The end that allows insertion is called the tail.

The realization of the ring queue: In the computer, there is no ring of memory, but we are dealing with the order of memory, so that a section of memory into a ring, so that they end to end, in simple terms, this is actually an array, only However, there are two pointers, one pointing to the queue leader and one pointing to the end of the queue. Pointer to the queue head (Head) is the buffer readable data, the pointer to the end of the queue (Tail) is the buffer can write data, by moving the two pointer (Head) & (Tail) to the buffer The data is read and written until the buffer is full (head-to-tail). After the data is processed, the data can be released and new data can be stored.

The principle of implementation: During initialization, both the head of the queue and the end of the queue point to 0. When there is data storage, the data is stored in the address space of '0', the tail of the queue points to the next place where data can be stored, and then there is When data arrives, the data is stored at address '1', and the end of the queue points to the next address '2'. When the data is to be processed, it is sure to first process the data of the '0' space, that is, the data of the queue heads. After processing the data, the data of the '0' address space is released, and the queue head points to the next data that can be processed. Address 1'. In order to achieve the entire ring buffer data read and write.

Looking at the chart, the head of the queue is pointing to the data that has been stored, and this data is pending. The data processed by the next CPU is 1; the end of the queue points to the address where data can be written. When 1 is processed, 1 is released. And point the head of the queue to 2. When a data 6 is written, the pointer at the end of the queue points to the next address that can be written.

If you understand the circular queue, follow the song and follow the code step by step:

Implementation from queue to serial buffer

Serial port ring buffer transceiver: In many entry-level tutorials, we know the serial port to send and receive are: receive a data, trigger an interrupt, and then send the data back. This kind of processing is not buffered. When the quantity is too large, or when the data is received too fast, we have no time to process the received data. Then, when the data is received again, it will be returned before. Unprocessed data is overwritten. Then the phenomenon of packet loss will appear and it will be a fatal wound to our program.

So how to avoid this situation, it is clear that the characteristics of some queues mentioned above can easily help us achieve the situation we need. Cache the accepted data, and let the processing speed be a bit buffered, making the processing speed faster than the receiving speed. We have already analyzed the advantages and disadvantages of the ordinary queue and the ring queue. Then we must use the ring queue to achieve . The following is the code implementation:

1 define a structure:

1typedef struct2{3 u16 Head; 4 u16 Tail;5 u16 Lenght;6 u8 Ring_Buff[RINGBUFF_LEN];7}RingBuff_t;8RingBuff_t ringBuff;//Create a ringBuff buffer

2 initialize the structure of the relevant information: Make our ring buffer is connected head and tail, and there is no data, which is an empty queue.

1/** 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author JJ 6* @date 2018 7* @version v1.0 8* @note Initialize ring buffer 9*/10void RingBuff_Init (void)11{12 // initialization related information 13 ringBuff.Head = 0;14 ringBuff.Tail = 0;15 ringBuff.Lenght = 0;16}

The initialization effect is as follows:

The code written into the ring buffer implements:

1/** 2* @brief Write_RingBuff 3* @param u8 data 4* @return FLASE: ring buffer is full, write failure; TRUE: write success 5* @author JJ 6* @date 2018 7* @ Version v1.0 8* @note writes u8 type data to ring buffer 9*/10u8 Write_RingBuff(u8 data)11{12 if(ringBuff.Lenght >= RINGBUFF_LEN) //determines if the buffer is full 13 {14 Return FLASE;15 }16 ringBuff.Ring_Buff[ringBuff.Tail]=data;17// ringBuff.Tail++;18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//prevent cross-border illegal access 19 ringBuff.Lenght++; 20 return TRUE;21}

The code implementation for reading the buffer's data:

1/** 2* @brief Read_RingBuff 3* @param u8 *rData, used to save the read data 4* @return FLASE: ring buffer no data, read failed; TRUE: read successfully 5* @author Jie Jie 6* @date 2018 7* @version v1.0 8* @note Read a u8 type data from the ring buffer 9*/10u8 Read_RingBuff(u8 *rData)11{12 if(ringBuff.Lenght == 0) //Judge non-empty 13 {14 return FLASE;15 }16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//First-in, first-out FIFO, out of buffer header 17// ringBuff.Head++;18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//prevents cross-border illegal access 19 ringBuff.Lenght--;20 return TRUE;21}

There are two things to note about read and write operations:

1: Determine if the queue is empty or full. If it is empty, it is not allowed to read data. Return FLASE. If it is full, it is also forbidden to write data, and to avoid overwriting existing data. Then, if the processing speed cannot keep up with the receiving speed, increase the size of the buffer and use the space for time.

2: To prevent illegal cross-border pointer access, the program has instructions that require the user to grasp the size of the entire buffer.

Then in the serial receiver function:

1void USART1_IRQHandler(void) 2{3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //Receive interrupt 4 {5 USART_ClearITPendingBit(USART1, USART_IT_RXNE); //Clear flag bit 6 Write_RingBuff(USART_ReceiveData(USART1)); // Read the received data 7 } 8} Test effect

No packet loss occurred in the test data.

supplement

For the current stage, JJ I also slowly learned to code. All code snippets are very readable and very portable. I used the macro definition to determine whether to enable ring buffers to send and receive data. Transplanting everyone's code does not have other side effects. I only need to enable the macro definition to use it.

1#define USER_RINGBUFF 1 //Receive data in the form of a ring buffer 2#if USER_RINGBUFF 3/** If the ring buffer is used to receive serial data ***/ 4#define RINGBUFF_LEN 200 //Define the maximum number of bytes received 200 5# Define FLASE 1 6#define TRUE 0 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData);10#endif

Of course, we can use idle interrupts and DMA transfers to be more efficient. However, some microcontrollers do not have free interrupts and DMAs. This type of ring buffer is very useful and easy to transplant. At the same time, we can also refer to the following source code analysis of Gokit3.0 STM32. We will understand this mechanism more deeply.