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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.