Directional buffers

Directional buffers

If you sit down and start playing with buffers, it quickly becomes apparent that there is more to buffer design than first meets the eye. For example, the data must be kept in the same order in which it was placed to preserve the chronological order. This is especially important for signal data or data that is sampled periodically. With an infinitely long buffer, this is not a problem. The first data is placed at the top of the buffer and new data is inserted underneath. The data in and out pointers then simply move up and down as needed. The order is preserved because there is always space under the existing data entries for more information. Unfortunately, such buffers are rarely practical and problems can occur when the end of the buffer is reached. The previous paragraphs have described how water marks can be used to trigger when these events are approaching and thus give some time to resolve the situation.

The resolution is different depending on how the buffer is used, i.e. is it being used for inserting data, extracting data or both. The solutions are varied and will lead onto the idea of multiple buffers and buffer exchange. The first case to consider is when a buffer is used to extract and insert data at the same time.

Single buffer implementation

In this case the buffer is used by two software tasks or routines to insert or extract information. The problem with water marks is that they have data above or below them but the free space that is used to fill the buffer does not lie in the correct location to preserve the order.

One solution to this problem is to copy the data to a new location and then continue to back-fill the buffer. This is the method shown in the next three diagrams.

It uses a single low water mark and a next data pointer. The next data pointer is used to access the next entry that should be extracted. Data is not inserted into the buffer until the next data pointer hits the low water mark. When that happens, the data below the low water mark is copied to the top of the buffer and the next data pointer moved to the top of the buffer. A new pointer is then created whose initial value is that of the first data entry below the copied data. This is chronologically the correct location and thus the buffer can be filled by using this new pointer. The original data at the bottom of the buffer can be safely overwritten because the data was copied to the top of the buffer. Data can still be extracted by the next data pointer. When the temporary pointer reaches the end of the buffer, it stops filling. The low water mark  — or even a different one — can be used to send a message to warn that filling must stop soon. By adding more pointers, it is possible to not completely fill the area below the low water mark and then use this to calculate the number of entries to move and thus the next filling location.

This method has a problem in that there is a delay while the data is copied. A more efficient alternative to copying the data, is to copy the pointer. This approach works by still using the low water mark, except that the remaining data is not copied. The filling will start at the top of the buffer and the next data pointer is moved to the top of the buffer when it hits the end. The advantage that this offers is that the data is not copied and only a pointer value is changed.

Both approaches allow simultaneous filling and extraction. However, care must be taken to ensure that the filling does not overwrite the remaining entries at the bottom of the buffer with the pointer copying technique, and that extracting does not access more data than has been filled. Additional pointer checking may be needed to ensure this integrity in all circumstances and not leave the integrity dependent on the dynamics of the system, i.e. assuming that the filling/extracting times will not cause a prob-lem.