Hello, Is there an implementation of a multi-writer, multi-reader FIFO queue for 32-bit PowerPC multiprocessors with the following characteristics: (1) the...
... Well it seems obvious to me.. Assuming that we'll never have devices with infinite memory, there will always be a limit on the number and size of elements....
... The requirement was that the *implementation of the FIFO* would not limit the number and size of elements. Not that lack of memory would not limit it. ... ...
Simon Jenkins
sjenkins@...
Feb 7, 2007 12:35 pm
223
... Eric was referring to garbage collection schemes, not memory allocation. Basically, if you can't free up memory easily, but instead need to wait for some...
... What makes the memory management internal vs external? The distinction is irrelevant. If it requires allocation it requires access to space. If that space...
A few years ago I emailed with Maged Michael, and he told me that it is possible to write a FIFO that has no interleaved LL/SC pairs. Since LL/SC is immune to...
... If you want access to unlimited space then you are going to need a non trivial memory management scheme. He even rules out the number one and two most...
... allocation. ... wait for ... via a ... counting ... "memory ... Chris is correct regarding my reference to "memory management." I apologize for any lack...
... A system is a whole. A lock free FIFO which requires calling a non-lock free memory manager to alloc/free space for the queue elements is not a lock free...
... No I'm sorry, what he meant is not established. You cannot say that memory management is external if it is required in order to enqueue an element. thonk...
Given that I can swap one lock-free memory allocator for another, yet still use the same FIFO algorithm, and one can reuse the same lock-free memory allocator...
... I think you're missing the point James. I think the essential characteristic Eric is getting at is: how much of the memory management system can be...
I'm having trouble understanding these two statements from this paper: http://www.cs.utah.edu/~eeide/compilers/papers/pldi04-michael.pdf "This paper presents a...
At some point you have to accept that you're constrained by the system you're running on. Michael's allocator is internally entirely lock-free, which means you...
... yes of course. ... Yes I would. Or I would think that the allocator should have been written to allocate from a fixed pool so that the claim would be ...
... That's a valid point. However, then you could *still* claim the algorithm was broken, because it needs to know how much memory it will require! A Catch-22,...
Hello again, As promised, I offer two implementations of the subject queue. As suggested by my first post, each implementation is a singly-linked list. In...
... At this link, http://www.eric-grant.com/archive/GQueue_Chart.pdf you can download a one-page PDF document containing a "flow chart" of the state of the...
Hey all, Just wondering if anyone has successfully used a back-off strategy to reduce contention with lock-free algorithms? If so, how did you do it? *...
hi all, thomas grill and i were working on c++ implementations of two lockfree data structures, the scott&michael queue and michael's list-based set. they are...
hi chris, i haven't implemented any memory management, this would have to be done from the user of the data structures ... i'm guess, this is no problem, if...
Yes. The algorithm doesn't work without memory management, as it's not safe to free an element of the list until all concurrent readers have stopped looking at...
New poster here... Has anyone checked out Intel's Thread Building Blocks? I understand it's not open source but it looks pretty cheap. I would love to see an...
Hey all, I know I can't malloc data in the audio thread of my app (since it is unbounded in time), but can I call free? It would simplify my implementation if...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
