[LC++]Threading and shared STL containers.

George T. Talbot george at phat.com
Fri Sep 7 03:07:05 UTC 2001


At my last job we followed the following rules:

1)  Protect all accesses to a shared container with a reader-writer lock.
2)  Only those operations that change the structure of the container itself
(insertion, removal, erase all elements, etc.) get the writer lock,
everything else gets the reader lock.
3)  When the writer locks the container, all live iterators referencing that
container should be considered invalid when the writer releases the lock.

Think about number three for a second.  It is possible to imagine a list
implementation that would leave a live iterator dangling after an insertion
or removal.  A possible solution to this is that a const_iterator acquires
the reader lock at creation, and releases it at destruction.

--George

P.S.  I assume you've read these:

http://gcc.gnu.org/onlinedocs/libstdc++/17_intro/howto.html#3
http://www.sgi.com/tech/stl/thread_safety.html
http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html   (scroll
down)

-----Original Message-----
From: Carlo Wood <carlo at alinoe.com>
To: tuxcpprogramming at lists.linux.org.au
<tuxcpprogramming at lists.linux.org.au>
Date: Thursday, September 06, 2001 12:00 PM
Subject: [LC++]Threading and shared STL containers.


>Does anyone know a tutorial, howto or even a white-paper
>on this topic?  It must have been done before :/
>
>I am mostly interested in the locking strategies
>for containers where iterators are not invalidated
>by insertion or erasure (for example a map<> or list<>).
>
>There seem to be four types of operations in this case:
>1) Changing the internal structure of the container
>   (1a) insertion or 1b) erasure).
>2) Reading the internal structure of the container
>   (for example doing a find()).
>3) Writing to elements (iterator).
>4) Reading elements (const_iterator).
>
>Obviously, the best thing to use for 1) and 2) are
>read/write locks.  Also, 2) reading the internal
>structure of a container, doesn't inhibit 4).
>
>Moreover, 3) writing to elements, is already implemented
>in a way that protects the internal tree structure of
>the STL containers: For example, a map<>::iterator
>doesn't allow you to change the key (the key is const).
>Hence, operations 3) and 4) do not need to inhibbit
>operation 1) or 2).  Finding elements involves reading
>elements however, so 2) finding elements, also blocks
>whatever operator 4) does block.
>
>Insertion of a new element always involves a different
>element then elements that we might already have iterators
>for.
>
>This "analysis" seems to give me the following demands:
>
>1a) insertion blocks:
> 1a) other insertions
> 1b) erasures
> 2)  find
>1b) erasure blocks:
> 1a) insertions
> 1b) other erasures
> 2) find
> Note: it makes no sense to block
> concurrent reads of iterators (to this
> element) because that block would be lifted
> directly after erasure completes and the program
> would still crash (since the assumed iterator
> would point to cyber space).
>2) finding elements blocks:
> 1) insertion or erasure of elements
> 3) writing to elements
>3) writing to iterators blocks:
> 3) writing to the same element
> 4) reading the same element
>4) reading iterators blocks:
> 3) writing to the same element
>
>This seems therefore to involve one rwlock per element,
>one global lock for 'writing to elements' and one global
>rwlock per container.
>
>I'd like to have comments on this analysis.
>
>--
>Carlo Wood <carlo at alinoe.com>
>_______________________________________________
>This is the Linux C++ Programming List
>: http://lists.linux.org.au/listinfo/tuxcpprogramming List
>




More information about the tuxCPProgramming mailing list