Hi Would there be any interest in a lock free implmentation of common data structures. The goal would be to preserve the integrity of the data in a multi-threaded environment without the use of locks. See http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms for more information. Perhaps a lock-free implementation of the STL might be a good idea?
I'd be interested. Some good cross-platform lock free containers would be great to have. On 9/16/05, Sashan Govender <sashang@gmail.com> wrote:
Hi
Would there be any interest in a lock free implmentation of common data structures. The goal would be to preserve the integrity of the data in a multi-threaded environment without the use of locks. See http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms for more information.
Perhaps a lock-free implementation of the STL might be a good idea? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Cory Nelson http://www.int64.org
"Sashan Govender" wrote:
Would there be any interest in a lock free implmentation of common data structures. The goal would be to preserve the integrity of the data in a multi-threaded environment without the use of locks. See http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms for more information.
Perhaps a lock-free implementation of the STL might be a good idea?
There would be lot of interest, for sure. Recently, comp.programming.threads have had several discussions on this topic as well as links to existing libraries. (One example: http://appcore.home.comcast.net/) /Pavel
Sashan Govender schrieb:
Perhaps a lock-free implementation of the STL might be a good idea?
I am afraid that it will be very hard to push it that far. Also I am not sure if I would want that at all. Isn't it the case that lock-free algorithms are much slower in the uncontended case? But having a bag of lockfree algorithms would definitely be a big win. BTW.: As I have stumbled over "lock-free " and "wait-free". Is it true that the use of a user space "spin lock" despite its name belongs to the class of lock-free but not wait free algorithms? Regards, Roland
BTW.: As I have stumbled over "lock-free " and "wait-free". Is it true that the use of a user space "spin lock" despite its name belongs to the class of lock-free but not wait free algorithms?
I don't know. These lock free algorithms are new to me and aren't my forte. I stumbled across it after watching the interview with Herb Sutter here http://channel9.msdn.com/Showpost.aspx?postid=39463. According to some papers I've been reading an algorithm is lock free if it guarantees that forward progress is made. So according to that definition you could technically qualify a user space 'spin lock' as lock free. I might be wrong. Maybe I read the wrong definition for lock free. I do know that they rely on CAS (compare and swap) being an atomic instruction at the processor level and can see how the lock free algorithms use CAS to implement lock free behaviour. -- sashan http://sashang.orcon.net.nz/code/code.htm
participants (4)
-
Cory Nelson -
Pavel Vozenilek -
Roland Schwarz -
Sashan Govender