Thread safe array class

Discussion in 'C++' started by andreas.zetterstrom@gmail.com, Sep 12, 2008.

  1. Guest

    I'm implementing some different c++ classes which I want to be thread
    safe. All these classes contain lists or arrays of some kind.
    I'm using protected sections to make them thread safe.

    The question then is: how do you in a nice safe way pick values out of
    the list? The easiest way is to have a pair of Lock, Unlock functions,
    but this also presents a lot of ways of doing a misstake.

    Say the list class has 5 functions, one to get the number of items,
    one to get items one by one and 3 other functions. The 3 functions
    have their locks internally as per c++ design you don't want other
    classes need to know anything about internal structure of another
    class. The 2 other functions is the problem. I would have to have
    external locks to lock them as the number of items might change while
    going through the list otherwise. 3 problems arise with that solution:
    you might forget (or don't know that it's needed) to lock the list
    before using it, you might forget to unlock the list while done and
    you might deadlock against other list functions that you didn't know
    were blocking too (or because you thought external locks were needed
    there as well).

    How to solve this in a nice way? I've been thinking of perhaps
    supplying a list to a special function in the list class that then
    transfers all the list data in the class to the supplied list and thus
    having a copy that won't risk changing. This will take double the
    memory and will require an extra loop through the data though.
    , Sep 12, 2008
    #1
    1. Advertising

  2. mqrk Guest

    On Sep 12, 12:52 am, wrote:

    > Say the list class has 5 functions, one to get the number of items,
    > one to get items one by one and 3 other functions. The 3 functions
    > have their locks internally as per c++ design you don't want other
    > classes need to know anything about internal structure of another
    > class. The 2 other functions is the problem. I would have to have
    > external locks to lock them as the number of items might change while
    > going through the list otherwise. 3 problems arise with that solution:
    > you might forget (or don't know that it's needed) to lock the list
    > before using it, you might forget to unlock the list while done and
    > you might deadlock against other list functions that you didn't know
    > were blocking too (or because you thought external locks were needed
    > there as well).


    The short answer is: I don't know. Since nobody has replied though I
    might as well share my thoughts on the matter.

    Let's call those other three functions f(), g(), and h(). Does your
    design allow f() to be called by one thread while g() is called by
    another? If f(), g(), and h() all potentially modify the data
    structure they should all lock together.

    Assuming you've already handled that, then you can have an iterator
    handle the locking. Let's say you decide that while one thread is
    iterating through the list, no other thread can access the data
    structure. Then, you can have the iterator's constructor lock the
    structure, and have the iterator's destructor unlock it. If you do
    this though, you have to worry about the copy semantics of the
    iterator. I think auto_ptr provides a good analog for this. You also
    have to assume that the client-programmer has the good sense not to
    hang on to an iterator.

    You could also have the iterator just lock on access and increment,
    but then you have to worry about the iterator going bad mid-
    iteration. Perhaps the iterator could keep the pointed-to item cached
    internally to prevent this, and throw an exception if it gets
    incremented after another thread just cleared the list or something.

    In any event, I don't envy you a bit.

    Regards,
    Mark McKenna
    mqrk, Sep 12, 2008
    #2
    1. Advertising

  3. James Kanze Guest

    On Sep 12, 9:52 am, wrote:
    > I'm implementing some different c++ classes which I want to be
    > thread safe. All these classes contain lists or arrays of some
    > kind. I'm using protected sections to make them thread safe.


    Just to be 100% clear: what do you mean by "protected" sections?
    ("Protected" has a very definite meaning in C++, which has
    nothing to do with threading. I presume you mean something to
    do with locks or mutexs. The word "synchronization" would be a
    better choice in that case, if only because it avoids the
    ambiguity with the C++ concept.)

    > The question then is: how do you in a nice safe way pick
    > values out of the list?


    What do you mean by "pick values out of the list"? You need a
    lock to read or access the values in the list, at least if there
    is a thread anywhere else which may access the list. The
    simplest rule is to never allow a pointer, a reference or an
    iterator to something in the list to escape a synchronized
    block. This is extrodinarily constraining, but the actual rules
    are complex (and depend on the container).

    > The easiest way is to have a pair of Lock, Unlock functions,
    > but this also presents a lot of ways of doing a misstake.


    > Say the list class has 5 functions, one to get the number of
    > items, one to get items one by one and 3 other functions. The
    > 3 functions have their locks internally as per c++ design you
    > don't want other classes need to know anything about internal
    > structure of another class. The 2 other functions is the
    > problem. I would have to have external locks to lock them as
    > the number of items might change while going through the list
    > otherwise. 3 problems arise with that solution: you might
    > forget (or don't know that it's needed) to lock the list
    > before using it, you might forget to unlock the list while
    > done and you might deadlock against other list functions that
    > you didn't know were blocking too (or because you thought
    > external locks were needed there as well).


    There are two distinct problems here. The first is accessing
    individual members in the container. You can't return a
    reference or a raw pointer to the element, since this would
    allow unlocked access to it; in addition, some other actions on
    the container (in another thread) might invalidate the pointer
    or reference. For read only access, returning a copy is often a
    valid solution. I've also used smart pointers in this case:
    return a reference counting smart pointer to the element, which
    frees the lock when the last reference disappears. (You can use
    boost::shared_ptr for this---just provide an appropriate
    deleter.)

    The second problem is race conditions outside of the container.
    The size() function returns the number of elements at the moment
    it is called, but this can change at any point outside of the
    function. The granularity of the locks the container can
    provide is too low to be really useful. (This is, of course,
    why the standard containers don't lock.) You could provide a
    nested class which manages some sort of scoped lock for the
    container, and require the client code to use this. If you
    wanted to be double sure, you could even have the scoped lock
    inform the container of its existance, and which thread held it,
    and assert() in each function that it was called by this thread.

    > How to solve this in a nice way? I've been thinking of perhaps
    > supplying a list to a special function in the list class that then
    > transfers all the list data in the class to the supplied list and thus
    > having a copy that won't risk changing. This will take double the
    > memory and will require an extra loop through the data though.


    There are really only two choices if client code needs to call
    more than one function with a consistent state: either the
    client code uses a private copy, or it holds a lock for the
    entire duration. Since only the client code can know the
    appropriate granularity of locking, only the client code can
    manage the locks. There are very, very few cases where it makes
    any sense to have the container itself manage locking.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Sep 14, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marc Twain
    Replies:
    2
    Views:
    961
    Marc Twain
    Nov 14, 2003
  2. Adam Warner
    Replies:
    13
    Views:
    793
    Patricia Shanahan
    Mar 28, 2006
  3. Gabriel Rossetti
    Replies:
    0
    Views:
    1,310
    Gabriel Rossetti
    Aug 29, 2008
  4. Thread safe array

    , Sep 12, 2008, in forum: C Programming
    Replies:
    6
    Views:
    349
    Chris M. Thomasson
    Sep 14, 2008
  5. John Nagle
    Replies:
    5
    Views:
    463
    John Nagle
    Mar 12, 2012
Loading...

Share This Page