Boost logo

Boost :

Subject: Re: [boost] [intrusive] making a list safe for concurrent readers
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-09-16 15:10:29


Michael Marcin wrote:
> I have a program that protects an object containing a linked with what
> is essentially a shared_mutex. I'd like to take advantage of the logical
> constness of traversing a linked list with const iterators and allow
> concurrent traversal protected by the external shared_mutex.
> Unfortunately the standard makes no such guarantees on std::list so I've
> determined I'll have to write my own linked list with a slightly
> stronger guarantee that concurrent read access is safe.
>
> I remember reading during the review that intrusive could be used to
> make high quality non-intrusive data structures easily. Can I use
> intrusive to make a std::list like container that is safe to read
> concurrently?

Yes. Although the standard does not guarantee it, I think most (all?)
implementations offer read-only thread-safety. Intrusive offers similar
guarantees. Intrusive documentation says:

http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/thread_safety.html

Thread safety guarantees

Intrusive containers have thread safety guarantees similar to STL
containers.

     * Several threads having read or write access to different
instances is safe as long as inserted objects are different.
     * Concurrent read-only access to the same container is safe.

Some Intrusive hooks (auto-unlink hooks, for example) modify containers
without having a reference to them: this is considered a write access to
the container.

Other functions, like checking if an object is already inserted in a
container using the is_linked() member of safe hooks, constitute read
access on the container without having a reference to it, so no other
thread should have write access (direct or indirect) to that container.

Since the same object can be inserted in several containers at the same
time using different hooks, the thread safety of Boost.Intrusive is
related to the containers and also to the object whose lifetime is
manually managed by the user.

> Thanks,
>
> Michael Marcin

Regards,

Ion


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk