[LC++]Threading and shared STL containers.

[George T. Talbot]

-----Original Message-----
From: Carlo Wood <carlo at alinoe.com>
To: tuxcpprogramming at lists.linux.org.au
<tuxcpprogramming at lists.linux.org.au>
Date: Friday, September 07, 2001 12:01 AM
Subject: Re: [LC++]Threading and shared STL containers.


>On Thu, Sep 06, 2001 at 01:05:57PM -0400, George T. Talbot wrote:
>> 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.
>
>To recall, I had:
>
>1 == operations that change the structure of the container itself.
>2 == operations that read the structure of the container itself.
>3 == operations that write to elements pointed to by iterators.
>4 == operations that read elements pointed to by iterators.
>
>and a locking sheme:
>
>1 -> lock 1,2
>2 -> lock 1,3(all)
>3 -> lock 3(same),4(same)
>4 -> lock 3(same)
>
>where 3(all) means all elements and 3(same) means the same
>element as the current operation works on.
>
>You have:
>
>1 -> lock 1,2,3(all),4(all)
>2 -> lock 1,3(all)
>3 -> lock 1,3(all)
>4 -> lock 1,3(all)
>
>You miss a lock on 4(same) for operation 3 thus...
>That means your solution is not thread safe as one
>thread could be changing an element while another thread
>is reading it!


I wasn't trying to solve that problem--I was only concerned with protecting
the integrity of the container itself.  Protecting the integrity of the
individual elements is another issue.  It's hard to come up with a good
solution that covers all cases in a CPU-time and memory efficient manner.
Rather solutions for doing this kind of locking depend upon access patterns,
how often individual elements are modified, and how many elements there are.

o  If individual elements are modified infrequently, one could efficiently
use the same reader-writer lock as the container--take the write lock for
the container when writing to an element, otherwise take the reader lock.
The advantage here is that you can hold the single lock over the
modification of multiple elements, thus avoiding paying the cost of locking
at each element.

o  If individual elements are modified often, then each one probably needs
its own lock--which'll cost a lot more in memory.

o  Locking often happens at a higher level than containers and elements.
Certain operations in the program, composed of multiple operations on STL
structures and elements will often need to be atomic.  In that sort of
situation, locks on individual structures and elements probably don't make a
lot of sense anyway.

>> 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.
>
>I don't understand this, when inserting a new element in a container
>doesn't invalidate the live iterators - then why would that happen
>with multi threading?

Doesn't this depend upon which container and the particular implementation
of that container?  My STL book is at work--I seem to remember that there
wasn't a guarantee on all containers that iterators remain valid after
insertion/removal, but I could be wrong.

--George


>>
>> --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)
>
>Yes, thanks :).
>
>--
>Carlo Wood <carlo at alinoe.com>
>_______________________________________________
>This is the Linux C++ Programming List
>: http://lists.linux.org.au/listinfo/tuxcpprogramming List
>