Lock-free buffer
allan
Lock-free queue, lock-free list, etc. are there, but is there the
algorithm for the lock-free buffer?
Lock-free queue is not sufficient for my case, because in the case
where three readers try to read a data and the lock-free queue has
only one data, only one of readers would get data with dequeue()
operation and the other two should wait until writers fill data into
the queue with enqueue() operation. In short, all readers should be
guaranteed to get the latest updated data all the time.
If anybody advices me, it would be deeply appreciated.
David Schwartz
"allan" <hj...@vt.edu> wrote in message
news:8f173f5e.05030...@posting.google.com...
If you only have one writer and writes are infrequent, why not just do
the following:
1) Allocate a new buffer.
2) Write the data into the buffer.
3) Save the pointer to the buffer that the readers use.
4) Atomically replace the pointer with the pointer to the new buffer.
5) Set a timer to free the old buffer later.
If writes are frequent, the timers to free the old buffers might get
ugly. In that case, you probably want an atomic reference count.
DS
Joe Seigh
It sounds like you want a shared buffer. A queue is a totally different
thing.
Yes, you can do it with COW (copy on write) which will allow lock-free
reads of the buffer. atomic_ptr, RCU (Read, Copy, Update), SMR hazard
pointers, Boehm style GC, etc... will let you do that. Updating the
buffer lock-free will require compare and swap or some other interlocked
primative.
--
Joe Seigh
Markus Elfring
> where three readers try to read a data and the lock-free queue has
> only one data, only one of readers would get data with dequeue()
> operation and the other two should wait until writers fill data into
> the queue with enqueue() operation. In short, all readers should be
> guaranteed to get the latest updated data all the time.
Does this algorithm and technique fit to your needs?
- Asynchronous Data Sharing in Multiprocessor Real-Time Systems Using Process Consensus
http://citeseer.ist.psu.edu/114960.html
- German description
http://www.carrara.ch/fachbeitraege/Consensus.pdf
Regards,
Markus
SenderX
I would advise you to take a long deep look at atomic_ptr:
http://atomic-ptr-plus.sourceforge.net/
It gets the job done.
Also, I am about ready to post a full blown hazard-pointer implementation to
my site. You can use that for all sorts of stuff. The docs will be a bit
scarce for a while, I have not really worked on them in the past week or
so... I am suffering from a bad case of the brain-burn.
;)
--
http://appcore.home.comcast.net/
(portable lock-free data-structures)
SenderX
>
> 2) Write the data into the buffer.
>
> 3) Save the pointer to the buffer that the readers use.
>
> 4) Atomically replace the pointer with the pointer to the new buffer.
>
> 5) Set a timer to free the old buffer later.
How would the timer know how long to wait?
David Schwartz
"SenderX" <x...@xxx.com> wrote in message
news:loWdndvDk4v...@comcast.com...
>> 1) Allocate a new buffer.
>>
>> 2) Write the data into the buffer.
>>
>> 3) Save the pointer to the buffer that the readers use.
>>
>> 4) Atomically replace the pointer with the pointer to the new buffer.
>>
>> 5) Set a timer to free the old buffer later.
>
> How would the timer know how long to wait?
There are several techniques and it depends upon the application. One
way is to wait until all threads that could have used the buffer pass a
neutral point.
DS
SenderX
>> How would the timer know how long to wait?
>
> There are several techniques and it depends upon the application. One
> way is to wait until all threads that could have used the buffer pass a
> neutral point.
That's sounds like RCU, but RCU is not based on timers. How could you
possibly calculate how long the timer should wait before freeing the data?
Using timers for this kind of stuff creates a race-condition.
SenderX
> way is to wait until all threads that could have used the buffer pass a
> neutral point.
But you said set a timer, that means that you need the time before the
reader threads could get into a quiescent state. How could you possibly
predict the correct amount of time?
David Schwartz
It depends upon the application. There are definitely applications where
you can predict the amount of time and applications where you can't.
DS