Avoiding Data Loss in Thread Communication

Contents

• 1 - Problem
• 2 - Solution
• 3 - Program
• 3.1 - Buffer
• 3.2 - Development
• 3.2.1 - Buffer Creation
• 3.2.2 - Write in the Buffer
• 3.2.3 - Read from the Buffer
• 3.2.4 - Create Nodes
• 3.2.5 - Delete the Buffer
• 4 - Test
• 5 - Makefile

1 - Problem

Suppose you have a device that makes readings and sends them to a computer through, for instance, a socket. If between two readings the computer has to do some calculations it is possible that, when the rate of the communication is higher, some data will be lost on the computer side.

2 - Solution

To solve this situation, you can create a thread in the computer side witch only task is to take the data out of the socket and put it in a buffer where the main program will go read it as soon as he is able to. Besides, as you don't know witch is the best length for the buffer, it will be even better if the buffer can grow as it is needed.

3 - Program

3.1 - Buffer

The buffer is a ring of a variable number of nodes each one with the following constitution:

• A pointer to the next node in the ring

• A pointer to a cell of fixed length where an item of data is stored

• A character witch indicates the last operation done in the cell, a reading or a writing

Besides the nodes it also has a control structure, called "Ring", witch has the following constitution:

• A pointer to the last read node

• A pointer to the last wrote node

• The number of nodes in the buffer

• The size in bytes of the cell

3.2 - Development

The program developed consists of the necessary functions to:

• Create the buffer
• Write in the buffer
• Read from the buffer
• Add more space to the buffer
• Delete the buffer

3.2.1 - Buffer Creation

To create the buffer you use the following function:

void ring_init(ring_struct *ring, int cell_size)
{
    node_struct *fst = NULL, *lst = NULL;
    ring_create_nodes(NODES_ON_INIT, cell_size, &fst, &lst);
    ring->r = ring->w = lst->nxt = fst;
 
    ring->node_num = 
NODES_ON_INIT;
    ring->cell_size = cell_size;
}

It begins by allocating NODES_ON_INIT nodes, then adjusts the pointers in the ring structure and makes the last created node to point at the first and finally fills the remaining of the ring structure.

3.2.2 - Write in the Buffer

The following function is used when it is needed to write in the buffer:

int ring_write(ring_struct *ring, void *cell_source)
{
    node_struct *fst = NULL, *lst = NULL;
    if(ring->w->nxt->status == 'r')
    {
        ring->w = ring->w->nxt;
        memmove(ring->w->cell, cell_source, 
ring->cell_size);
        ring->w->status = 'w';
    }
    else
    {
        ring->node_num += NODES_ON_ADD;
        if((NODES_MAX_NUM != 0) && (ring->node_num 
> NODES_MAX_NUM))
            return(-1);
        ring_create_nodes(NODES_ON_ADD, 
ring->cell_size, &fst, &lst);
        lst->nxt = ring->w->nxt;
        ring->w->nxt = fst;
        ring_write(ring, cell_source);
    }
    return(0);
}

Here you can find two situations, the next node is marked as read or it is marked as wrote. In the former case there is no problem of writing over it, in the second case if you write over it you are loosing data because that node was not read yet.

As sought, in the former case you point to the next node, copy the data into the cell and mark the node as wrote. In the second case there are a few more steps to take. In order to write more data you are going to make the buffer bigger by adding to it some mode nodes. First because the buffer could be configured with a maximum size you ask if with the nodes you are about to add you don't reach that size yet. If it is ok you call the function that creates the nodes to add more NODES_ON_ADD nodes witch are created with the read flag, adjust the pointers and the function call itself because now the next node is already marked as read.

3.2.3 - Read from the Buffer

To read from the buffer you use the following function:

int 
ring_read(ring_struct *ring, void *cell_dest)
{
    if(ring->r->nxt->status == 'r')
        return(0);
    else
    {
        ring->r = ring->r->nxt;
        memmove(cell_dest, ring->r->cell, 
ring->cell_size);
        ring->r->status = 'r';
        return(1);
    }
}

Here you ask again if the next node is marked as read or as wrote. In the former case there is nothing to read because all cells are marked with read. If it is marked as wrote then you can make a reading by copying the contents of the cell, adjusting the pointers and marking the node as read.

3.2.4 - Create Nodes

The simple but more complex function is to create nodes. The code to do that is:

void ring_create_nodes(int n, int cell_size, node_struct **fst, 
node_struct **lst)
{
    int i;
    node_struct *node = NULL, *ptr = NULL;
    for(i = 0; i < n; i++)
    {
        node = (node_struct *) 
malloc(sizeof(node_struct));
        if(!node)
            
ring_error_and_exit((char *) "Error in 'malloc' for 'node'");
        node->status = 'r';
        node->cell = malloc(cell_size);
        if(!node->cell)
            
ring_error_and_exit((char *) "Error in 'malloc' for 'cell'");
        if(!i)
        {
            *lst = node;
            node->nxt = 
NULL;
        }
        else
            node->nxt = 
ptr;
        ptr = node;
    }
    *fst = node;
}

The goal here is to create a finite number of nodes connected between them and with the first and last node opened. For that you create a cycle that, for the number of nodes that you want to create, begins by allocating space for the node, for the cell, marking the node as read and connecting it to the last created node. If it is the first node to be created (it will be the last in the queue because the queue grows to the back) it will point to NULL and the argument LST witch must points to the last node, will point to it. Finally the argument FST, that must point to the first node in the queue, points to the last created node.

3.2.5 - Delete the Buffer

When there is no more need for the buffer you must delete it. To do so you use the following code:

void ring_free(ring_struct *ring)
{
    node_struct *fst = NULL, *del = NULL;
    fst = ring->w;
    while(1)
    {
        del = ring->w;
        ring->w = del->nxt;
        free(del->cell);
        free(del);
        if(ring->w == fst)
            break;
    }
}

You begin by any node in the buffer, you take note of it and then you go by all nodes in the buffer freeing the space allocated to the cell and then the space allocated to the node until you reach the first node.

4 - Test

In order to test the program it was developed an application witch creates a thread that writes data to the buffer and the main program reads it and shows it on the screen. It was included a delay in the writing and a bigger one in the reading. This way the buffer gets full and it is possible to test it's growing. It was also included a maximum dimension for the buffer that when it is reached makes the application to end.

5 - Makefile

To build and test the whole application it was created a makefile that compiles all the modules. The application was tested under Cygwin environment but it will run as well under any Linux or Unix environment.