Subject: Re: [linux-audio-dev] MidiShare Linux
From: Paul Barton-Davis (pbd_AT_Op.Net)
Date: Thu Jul 20 2000 - 14:26:36 EEST
>Actually i don't really understand the way your fifo (with ringbuffer) works.
>How can you garantee that the write operations works correctly in a
>multi-thread context?
>Can you explain the design ?
as the "designer" of the thread safe version, i'll push my way in here :)
you have an array, with two indexes: the read ptr and the write ptr.
only readers adjust the read ptr and only writers adjust the write
ptr. to figure out the date/space available for reading or writing,
you do a fairly simple subtraction:
size_t write_space () {
size_t w, r;
w = write_ptr;
r = read_ptr;
if (w > r) {
return ((r - w + size) & size_mask) - 1;
} else if (w < r) {
return (r - w) - 1;
} else {
return size - 1;
}
}
size_t read_space () {
size_t w, r;
w = write_ptr;
r = read_ptr;
if (w > r) {
return w - r;
} else {
return (w - r + size) & size_mask;
}
}
Now, access to read_ptr and write_ptr are not atomic with respect to
the operations of the other thread in the sense that they may change
during this computation. But the key things to notice are:
1) only the writer ever computes write_space(), so only the read_ptr
can move during this time.
2) only the reader ever computes read_space(), so only the write_ptr
can move during this time.
3) if the read_ptr moves during the computation of write_space(), it
means only that we under-estimate the amount of space available
to write into the ringbuffer.
4) if the write_ptr moves during the computation of read_space(), it
means only that we under-estimate the amount of data available
to read from the ringbuffer.
The net result is that these computations are always thread safe if
there is just one reader and one writer. The only detail is that its
possible to underestimate the data or space available, and thats
nearly always completely OK.
Note that I have a more efficient implementation of a lock-free FIFO
for use where the characteristics of a ringbuffer are not desired
(i.e. you really are always just pushing and popping elements from the
FIFO). The ringbuffer implementation allows it to be used to store
streaming data efficiently, but is not so quick for simple push/pop
operations.
--p
This archive was generated by hypermail 2b28 : Thu Jul 20 2000 - 15:00:21 EEST