[clam-devel] [Fwd: [ liblf-dev] [Fwd: Re: [Orocos-Dev] portable rtt]]

[Pau Arumi]

yep! i sent this to the old list some days ago.

interesting lock-free data structures library. i think it might be worth 
study its applicability for clam.
i found the linked pdf very informative (and fun). it remind me the 
lock-free approach we took for port-monitors

pau


>
> Assumpte:
> [liblf-dev] [Fwd: Re: [Orocos-Dev] portable rtt]
> De:
> Tim Blechmann <TimBlechmann at gmx.net>
> Data:
> Thu, 04 Jan 2007 12:53:43 +0100
> Per a:
> liblf-dev <liblf-dev at yahoogroups.com>
>
> Per a:
> liblf-dev <liblf-dev at yahoogroups.com>
>
>
> hi all, 
>
> i've been in contact with the developers of orocos (Open Robot Control
> Software), who wrote a real-time toolkit, which provides hard-realtime
> capable c++ implementations of several lockfree data structures. it's
> currently running on linux/rtai/xenomai, but i'm trying to make the data
> strucutes more portable, to make them run on windos and osx.
>
> in the attached mail, peter soetens gives a brief overview ...
> maybe it makes sense to spend our effort on orocos's rtt, instead of
> writing a liblfds ...
>
> cheers ... tim
>
> -------- Forwarded Message --------
> From: Peter Soetens <peter.soetens at fmtc.be>
> To: orocos-dev at lists.mech.kuleuven.be
> Subject: Re: [Orocos-Dev] portable rtt
> Date: Thu, 4 Jan 2007 10:37:12 +0100
>
> On Wednesday 03 January 2007 15:23, Tim Blechmann wrote:
>   
>> there is a guy, Ross Bencina, who proposed to write a library of
>> lockfree datastructures (http://tinyurl.com/sor7u). the project hasn't
>> started, yet, but a lot of audio developers have subscribed to the
>> mailinglist. however this project got stuck a bit and after seeing rtt i
>> guess, it would be better to put the efforts into making rtt portable
>> and maybe adding implementations of new data structures, instead of
>> reinventing the wheel ...
>>     
>
> Interesting link. I recognise a lot in it and I'll add it to the related 
> projects page on Orocos.org. 
>
> Now, for the whole lock-free issue in the Real-Time Toolkit. Should it be 
> portable ? Yes. Take a look at the front page of Orocos.org, vote and see the 
> statistics: the top winners are Linux, RTAI and Windows. 
> Should it become the reference for lock-free programming ? I don't know. I'm a 
> bit surprised that the (academic) 'big shots' have not yet published a free 
> library using their algorithms. Mine are not published (by anyone!) and they 
> work very well. They have been heavily stress tested and measured on a 
> real-time operating system.
>
> This is how I designed my algorithms:
> 1. The key of all algorithms is the 'AtomicQueue'. It is a fast, fixed size 
> many readers many writers queue. It is a 100% pure lock-free algorithm. The 
> access time is in (or under) the micro seconds range, even under very heavy 
> stressing[1]. It's memory use is constant (and very low) under any number of 
> accessing threads.(See 
> <http://www.orocos.org/stable/rtt/current/api/html/classRTT_1_1AtomicQueue.html>)
>
> 2. Built on top of the AtomicQueue, is the MemoryPool. It is a fast, many 
> readers/many writers re-sizable heap of blocks which safely allocates any 
> number of objects while in use. This means that the pool can grow while 
> elements are allocated/deallocated. It is a partially 'wait-free'/'lock-free' 
> algorithm as the search for free blocks is a wait-free algorithm. (See 
> <http://www.orocos.org/stable/rtt/current/api/html/classRTT_1_1MemoryPool.html>)
>
> 3. Built on top of (1) and (2) is the BufferLockFree, a wait-free/lock-free 
> many readers/many writers fixed-size FIFO. It basically manages the memory 
> allocation using a MemoryPool and enqueues objects using an AtomicQueue. 
> Users don't notice this in the API however.
> (See 
> <http://www.orocos.org/stable/rtt/current/api/html/classRTT_1_1BufferLockFree.html>)
>
> 5. The ListLockFree is similar to the BufferLockFree but is an iterable (!) 
> linked list where concurrent inserts/removals may happen. It is used by the 
> Orocos Event.
> (See 
> <http://www.orocos.org/stable/rtt/current/api/html/classRTT_1_1ListLockFree.html>)
>
> 4. Finally, we have the DataObjectLockFree. It is the only algorithm that is 
> single writer/many readers. It makes data accessible for other readers, while 
> concurrent writes are happening.
> (See 
> <http://www.orocos.org/stable/rtt/current/api/html/classRTT_1_1DataObjectLockFree.html>)
>
> I have _none_ of the above algorithms found in a publication. Most 
> publications I saw were not real-time to start with, or just way to hard to 
> implement portably (Hazard pointers IIRC). In this way, the Orocos primitives 
> are very unique : they are _hard_ real-time *and* being used in a realistic 
> and demanding application. No academic mambo jumbo here (DCAS ?? anyone ??) 
> My favourite is the AtomicQueue, it's so damn fast and memory efficient that 
> it should be used in any multi-threaded application for exchanging pointers 
> to objects.
>
> See also my FOSDEM presentation about lock-free algorithms here:
> <http://people.mech.kuleuven.be/~psoetens/doc/Lock-Free-FOSDEM.pdf>
>
> If you'd like to share this info on another list, feel free to spread the 
> word.
>
> Peter
>
> [1]AtomicQueue: That is, for the highest priority thread, the access time is 
> constant and minimal. For lower priority threads, the access time is bounded, 
> but no longer minimal, and will be in the microsecond range.
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> CLAM-devel mailing list
> CLAM-devel at iua.upf.es
> http://iua-mail.upf.es/mailman/listinfo/clam-devel


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.