UART is a great transmission protocol for both hobby and professional projects but, in time-critical systems, UART can be tricky.

UART (Universal Asynchronous Reception Transmission), is a popular protocol for microcontrollers to interface between other microcontrollers and computers. Low baud rate designs using high-speed microcontrollers typically do not have issues with UART. However, at higher speeds or if the micro is performing many tasks (such as in the ZBM project), serious issues can arise including missed bytes and the order of those bytes. Even in an interrupt driven system, the order can be very difficult to preserve. This article will explain a technique recently developed for this type of issue called UART double buffering.

Note: Technical Jargon (Push and Pop)

For those who are unfamiliar with stacks, pushing data means to put data onto the buffer and popping refers to removing data off the buffer.

 

The Problem Explained

Imagine an interrupt routine that does one task: Upon receiving a byte over UART, it stores the byte into the buffer array and increments the totalBytes counter.

 

                    isr_routine()
{
	if(UART_RECEIVE)
	{
		buffer[totalBytes] = UART_GET;
		totalBytes ++;
	}
}

                  

So as this array is filling up with data, our main program will take bytes off this buffer and then subtract from the totalBytes counter.

 

                    program()
{
	do{
	
		if(totalBytes >	0)
		{
			cout << buffer[totalBytes];
			totalBytes --;		
		}

	}while(1);
}
                  

So long as the main program takes bytes off the buffer faster than the bytes are being sent, then the order of the bytes is preserved. However, if the program cannot take the bytes off fast enough and bytes are added midway through this loop (remember, the interrupt has priority over the main loop), then the order of the bytes will be lost.​ But what is the “order of the bytes”?

 

Order of Bytes

The order of the bytes can be thought of as a timeline whereby the bytes are ordered chronologically. The first byte received must be the first piece of data to be processed and the last byte received must be the last to be processed. So in this example, if a device sends “Hello” over UART and our main program is quick enough, the output from cout (assuming we have a display) should also be “Hello” and not “elHlo” or some other combination.

 

 

So with the order of bytes considered, let us now see how this “order” is lost if the main program cannot pop data off the buffer faster than the ISR is putting data on. For the sake of example, we will assume that in the time it takes for our program to get one byte from the buffer, the ISR will have pushed two bytes sent over UART. What would the cout output look like? The output would spell “elolH”. How has this happened?

  • UART sends the first two bytes quickly, “He”
  • The main program takes one byte located at the end “e”
  • By this time the UART has sent a further two bytes “ll”
  • The main program takes the last byte again, “l”
  • The UART sends the last byte “o”
  • The main program then takes the data out of the array starting from the end to the start “lH”
  • The result is “elolH”

Not only has the data lost its order but it is not even in reverse! Reading the bytes backwards DOES NOT solve the issue. Even if you read from the first element to the last, you cannot adjust the value of totalBytes because the ISR could stop the program just before the value change, place the byte at the end of the array and then, upon returning, the main program could reset the value of totalBytes (thereby losing that sent byte). If the program does not alter the value of totalBytes because of a potential problem with interfering with the ISR, the buffer could overflow.

There are workarounds such as using circular buffers, multiple counters, and array sorting— but the easiest option (and one of the best) is the use of a double buffer.

 

The Double Buffer

The double buffer can be thought of as two completely separate units where the interrupt routine works with one unit and the program works with another unit. For the sake of modelling, the interrupt routine will be referred to as the “Kernel” and functions + programs that do not make up the interrupt routine will be referred to as the “User” (they use the data, the Kernel handles the hardware).

 

 

Each unit has two variables: an array called buffer[] and a counter called bufferCount. The buffer holds the UART data as it streams in and the bufferCount holds how much data has been sent. This counter can be used in two ways:

  1. Find how much data is present on the buffer
  2. Decide where to push / pop data to / from the buffer

Note: The simplest way to program the units and multiplexer is by using a multidimensional buffer and a multidimensional counter buffer.

 

                    // Each multi-array element is a unit
buffer[2][32]
bufferCounter[2][1]

// Unit A Variables
buffer[0][x]
bufferCounter[0][x]

// Unit B Variables
buffer[1][x]
bufferCounter[1][x]
                  

The User and Kernel unit selectors are done using two variables: uartKernel and uartUser. Each of these values is always the opposite. Below is a truth table for these values:

 

uartUser uartKernel
1 0
0 1

 

The multiplexer decides which unit will be routed to the Kernel and User (the multiplexer can only be in two states).

  • State A results in the Kernel using Unit A and the User using Unit B
  • State B results in the Kernel using Unit B and the User using Unit A

The multiplexer can be switched by calling the function switchBuffers(). This is not called every time a byte is read off the buffer, only once all the data in that buffer has been dealt with and the program is ready for more information from UART.

When the User reads off the array using the following code the bytes will be in the correct order.

 

                    for(int i = 0; i <= bufferCounter[uartUser]; i++)
{
	cout << buffer[uartUser][i];
}
                  

The Kernel uses the following code to place data into the buffer:

 

                    isr_routine()
{
	if(UART_RECEIVE)
	{
		buffer[uartKernel][bufferCounter[uartKernel]] = UART_GET;
		bufferCounter[uartKernel] ++;
	}
}
                  

As the uartUser and uartKernel values are always different (1 and 0), this means that the User and Kernel will always be accessing different buffers and counters. So how do we get the information from the Kernel to the User? All we have to do is switch the values of uartUser and uartKernel so that they point to each other's buffers and counters. Therefore, as the User is reading from the new data, the Kernel can carry on writing into the unused buffer. To make this switch, all the User has to do (before it processes new data), is call switchBuffers().

 

                    SwitchBuffers()
{
	uartUser = (!uartUser) & 0x01;
	uartKernel = (!uartKernel) & 0x01;
	
	// Need to reset the counter for the ISR
	bufferCounter[uartKernel] = 0;
}

                  

So let's see this double buffering technique in a scenario where the microcontroller is under heavy load and the UART is streaming data at twice the speed at which the program can deal with it. Like before, the UART will stream “Hello” and the User program will print the characters.

  • UART streams in “He” into Kernel – Places into Unit A
  • Program calls switchBuffers. Program prints “H” from Unit A
  • UART streams in “ll” into Kernel – Places into Unit B
  • Program is still processing the array and prints “e” from Unit A
  • UART streams in “o” into Kernel – Places into Unit B
  • Program has processed Unit A and switches Buffers – Program prints “l”
  • Program is still processing the array and prints “l” from unit B
  • Program is still processing the array and prints “o” from unit B

The double buffering technique has kept the ISR and main program entirely separate, enabled us to preserve the order, AND has generated very simplistic code with the opportunity for large buffers. No array sorting was needed, the ISR did not need to move elements around to preserve order, and no complicated circular buffering was needed either.

 

Comments

4 Comments


  • john p 2016-05-28

    I’m very doubtful about whether this offers any improvement over a circular buffer. All you need is like this:


    // Global variables
    int put_in = 0, take_out = 0;
    char buffer[BUFFER_SIZE];

    isr_routine()
    {
    if (UART_RECEIVE)
    {
    buffer[put_in] = UART_GET;
    if (++put_in >= BUFFER_SIZE)
    put_in = 0;
    }
    }

    main()
    {
    ...
    if (take_out != put_in)
    {
    do_whatever_we_do_with_serial_data( buffer[take_out] );
    if (++take_out >= BUFFER_SIZE)
    take_out = 0;
    }
    }

    • Robin Mitchell 2016-05-29

      This is also an alternative method for UART handling. The only difference is that the user can in theory adjust all the values in the array which is being used by the ISR. By separating the two so that the user and ISR use different buffers the unprocessed incoming data can never be adjusted. Also, the system described in the article informs the user the size of data sitting in the buffers without interfering with counters in use by the ISR.

  • Siegex1 2016-06-10

    I believe this double-buffer implementation to be fundamentally flawed in two ways.

    #1) You have an off-by-one error in your unnamed user-read function.  You should change ‘<=’ to simply “<” because after the UART writes two bytes, the bufferCounter[uartKernel] will be set to 2 and since your loop starts at 0, the cout method will execute three times spitting out garbage on the third iteration.  Easy fix, not a big deal

    #2) In the single-buffer implementation you said “Even if you read from the first element to the last, you cannot adjust the value of totalBytes because the ISR could stop the program just before the value change.”

    Your implementation suffers from the same fundamental flaw in that the ISR could interrupt the SwitchBuffers() function right after you swapped uartUser and uartKernel but *before* you set bufferCounter[userKernel] to zero.

    Lets run through an example where the UART is going to receive the string “HELLO_WORLD” (and assume the off-bye-one error has been fixed)

    1) UART receives two bytes, “HE”
    uartKernel = 0, uartUser = 1
    bufferCounter[0]  = 0, bufferCounter[1] = 0
    buff0—> [ H ][ E ]
    buff1—> [ ?  ][ ? ]
    bufferCounter[0]  = 2, bufferCounter[1] = 0

    2) SwitchBuffers() is called and executed completely
    uartKernel = 1, uartUser = 0
    bufferCounter[0] = 2, bufferCounter[1] = 0

    3) userland outputs buff0 contents
    “HE”

    4) UART receives two bytes, “LL”
    uartKernel = 1, uartUser = 0
    bufferCounter[0] = 2, bufferCounter[1] = 2
    buff0—> [ H ][ E ]
    buff1—> [ L ][ L ]
    bufferCounter[0] = 2, bufferCounter[1] = 2

    5) SwitchBuffers() is called but halted by ISR right before bufferCounter[uartKernel] is set to 0
    uartKernel = 0, uartUser = 1
    bufferCounter[0] = 2, bufferCounter[1] = 2

    6) UART receives two bytes, “O_”
    uartKernel = 0, uartUser = 1
    bufferCounter[0]  = 2, bufferCounter[1] = 2
    buff0—> [ H ][ E ][ O ][ _ ]
    buff1—> [ L ][ L ]
    bufferCounter[0] = 4, bufferCounter[1] = 2

    7) SwitchBuffer() resumes and sets bufferCounter[uartKernel] = 0
    uartKernel = 0, uartUser = 1
    bufferCounter[0] = 0, bufferCounter[1] = 2

    8) userland code outputs buff1 contents
    “LL”

    9) SwitchBuffers() is called and executed completely
    uartKernel = 1, uartUser = 0
    bufferCounter[0] = 0, bufferCounter[1] = 0

    10) userland code outputs buff0 contents
    Oops, nothing to output as the bufferCounter says it’s zero

    11) UART receives five bytes, “WORLD”
    uartKernel = 1, uartUser = 0
    bufferCounter[0]  = 0, bufferCounter[1] = 0
    buff0—> [ H ][ E ][ O ][ _ ]
    buff1—> [ W ][ O ][ R ][ L ][ D]
    bufferCounter[0] = 0, bufferCounter[1] = 5

    12) SwitchBuffers() is called and executed completely
    uartKernel = 0, uartUser = 1
    bufferCounter[0] = 0, bufferCounter[1] = 5

    13) userland code outputs buff1 contents
    “WORLD”

    The final output of this will be “HELLWORLD”
    Kinda fitting actually

  • ci139 2016-07-11

    I’am sorry to ask a stupid question but : are you actually “virtually duplicating” a single Comm line so that at time of buffer.read the input of the physical Comm stays isolated (from the buffer being read) e.g. there is always an unbusy port read at each time (the port is read)

    + how such prevents a buffer overflow when the incoming bit-stream is/stays faster the ISR can handle
    OR otherwords ?what is the exact occasion such “COM setup” resolves