Thread safe array class

On Sep 12, 12:52 am, andreas.zetters t...@gmail.com 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

an************* ****@gmail.com kirjutas:

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.

Right. If I understand correctly one of the requirements is that the
list/array should not mutate while taking out different items. Then there
are some solutions, which might or might not work for you (most probably
there are other solutions):

1) Add a function returning a copy of the list or array. After the
function has returned you can iterate and process items without locking.
This approach reduces thread contention and may thus give the best
overall performance, especially on multicore systems.

2) Add a scanning function which takes a functor as an argument. The
scanning function locks the array/list and then calls the callback
functor for each item. For supporting any functor the scanning function
should either be a template function, or the functor should be
polymorphic.

hth
Paavo

On Sep 12, 9:52 am, andreas.zetters t...@gmail.com 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 "synchronizatio n" 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_p tr 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:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34