Prev: Final call for papers
Next: Fundamental terms, question (Object Thinking)
From: Christopher Pisz on 12 Jan 2008 12:28
If I am OT here, please refer me. This NG was my best guess. I didn't see
any "Multithreading" groups and my questions do after all pertain to OO
design.

I discovered a few catch phrases that may point to the information I need.
Those phrases are "Object Level Locking", "Class Level Locking", and "RCU",
all of which I don't really understand and would love to see some code
examples and better references for. In the book "C++ Modern Design", the
author talks a little about the subject, but an implementation outside of
his own "Loki Library" is not shown and leaves my mind full of question
marks.

I am trying to solve a real world problem. This problem has come up in more
than one more domain. The problem is that there is a need for a C++:

1) Dynamic sized container, for example a class that has a std::map member.
A) multiple threads can make method calls that find, insert, and erase
elements from the map.
B) multiple threads can grab references and mutate elements from the
container.

I understand that 1A can be achieved using a static mutex in the class that
has the map member. I can use that mutex in every public member that
accesses the map. However, I have no clue how to achieve 1B, even in
psuedocode. 1B has come up at my workplace and in my hobby projects and I
want to be the hero who tackles it!

Please help with any info, references, or psuedocode you can. Thanks!





From: Daniel T. on 12 Jan 2008 13:19
"Christopher Pisz" <someone(a)somewhere.net> wrote:

> If I am OT here, please refer me. This NG was my best guess. I didn't see
> any "Multithreading" groups and my questions do after all pertain to OO
> design.
>
> I discovered a few catch phrases that may point to the information I need.
> Those phrases are "Object Level Locking", "Class Level Locking", and "RCU",
> all of which I don't really understand and would love to see some code
> examples and better references for. In the book "C++ Modern Design", the
> author talks a little about the subject, but an implementation outside of
> his own "Loki Library" is not shown and leaves my mind full of question
> marks.
>
> I am trying to solve a real world problem. This problem has come up in more
> than one more domain. The problem is that there is a need for a C++:
>
> 1) Dynamic sized container, for example a class that has a std::map member.
> A) multiple threads can make method calls that find, insert, and erase
> elements from the map.
> B) multiple threads can grab references and mutate elements from the
> container.
>
> I understand that 1A can be achieved using a static mutex in the class that
> has the map member. I can use that mutex in every public member that
> accesses the map. However, I have no clue how to achieve 1B, even in
> psuedocode. 1B has come up at my workplace and in my hobby projects and I
> want to be the hero who tackles it!
>
> Please help with any info, references, or psuedocode you can. Thanks!

You do it the same way. Any thread that is using an element from the
container must lock the container, so that the element can't be deleted
by another thread.

Of course you want to minimize such locking as much as possible. You say
that the map is contained in a class and presumably there is a mutex
associated with each object of the class which is locked whenever the
class is in one of its functions. The first thing you need to do is
remove any possibility of accessing the map except by objects of that
class. Make the map private, and don't provide any getters that provide
a reference or pointer to the map *or any of its contents*. Also make
sure that no iterators into the map are accessible to objects that are
not of this class.

Just a quick note, the above advice is standard OO practice (i.e., data
hiding/LoD.)
From: Dmitry A. Kazakov on 12 Jan 2008 13:24
On Sat, 12 Jan 2008 11:28:26 -0600, Christopher Pisz wrote:

> I am trying to solve a real world problem. This problem has come up in more
> than one more domain. The problem is that there is a need for a C++:
>
> 1) Dynamic sized container, for example a class that has a std::map member.
> A) multiple threads can make method calls that find, insert, and erase
> elements from the map.
> B) multiple threads can grab references and mutate elements from the
> container.
>
> I understand that 1A can be achieved using a static mutex in the class that
> has the map member. I can use that mutex in every public member that
> accesses the map. However, I have no clue how to achieve 1B, even in
> psuedocode. 1B has come up at my workplace and in my hobby projects and I
> want to be the hero who tackles it!

The references have types and if they are concurrently accessed then you
need locking at the level of these types and objects of. In general you
have (all mutable):

1. Container type

2. Element type

3. Reference type (a proxy to an element in the container)

4. Pointer type (same as 3, but lower-level)

Each one object of the types 1..4 must be locked upon mutation. The choices
are between:

A. Per object (instance) locks

B. Per type locks

C. Global lock

The problem is that pointers and built-in references aren't proper abstract
types in C++, so you have to avoid them altogether when concurrency is in
question. I don't even consider 4. Under 3 a smart reference is meant.

The choice between A, B, C is determined by each concrete case. A is
preferable when you have to lock things for a long time. C is on the other
end of the scale. B is in between. The problem with A is that you have to
handle cross operations (like swapping elements of different containers)
and you can easily run into a deadlock if you do not apply some policy of
locking.

Alternatives:

A viable alternative is to avoid mutability. Scrap 3 and 4. Use by value
semantics for 2, and you will go with A when only 1 is left (and no
operations between containers allowed).

On this path you can switch to immutable containers. That is a sort of
transaction model when a thread dealing with the container becomes a copy
of it (opens transaction). Then it does what needed and commits changes
(closes transaction). This requires a higher level abstraction than just a
container.

You can switch from protected objects to monitors. A monitor is a thread
exclusively responsible for dealing with the container (resource in
general). Anybody who wants to do anything with the container and its
elements requests the monitor via rendezvous. This also requires a
higher-level model, because monitors are quite inefficient for fine
granularity concurrency.

In general case, there is no optimal design for concurrently accessed
containers. Typically, first when you constrain the container's
functionality to only things you need and glue individual operations into
larger ones, then you will be able to make some choices.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
From: Martin Vuille on 12 Jan 2008 13:38
"Christopher Pisz" <someone(a)somewhere.net> wrote in
news:4788f8ba$0$22634$4c368faf(a)roadrunner.com:

> I didn't see any "Multithreading" groups and my questions do

comp.programming.threads

MV

--
I do not want replies; please follow-up to the group.
From: Patrick May on 12 Jan 2008 19:54
"Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> writes:
> On Sat, 12 Jan 2008 11:28:26 -0600, Christopher Pisz wrote:
>> I am trying to solve a real world problem. This problem has come up
>> in more than one more domain. The problem is that there is a need
>> for a C++:
>>
>> 1) Dynamic sized container, for example a class that has a std::map
>> member.
>> A) multiple threads can make method calls that find, insert, and
>> erase elements from the map.
>> B) multiple threads can grab references and mutate elements from
>> the container.
[ . . . ]
> The references have types and if they are concurrently accessed then
> you need locking at the level of these types and objects of. In
> general you have (all mutable):
>
> 1. Container type
>
> 2. Element type
>
> 3. Reference type (a proxy to an element in the container)
>
> 4. Pointer type (same as 3, but lower-level)
>
> Each one object of the types 1..4 must be locked upon mutation. The
> choices are between:
>
> A. Per object (instance) locks
>
> B. Per type locks
>
> C. Global lock

Further, you may find that you need read-only and read-write
locks to reduce contention and improve concurrency. Then you'll need
transactional attributes to allow dirty reads. And so on and so on.
Here there be dragons.

> The problem is that pointers and built-in references aren't proper
> abstract types in C++, so you have to avoid them altogether when
> concurrency is in question. I don't even consider 4. Under 3 a smart
> reference is meant.
>
> The choice between A, B, C is determined by each concrete case. A is
> preferable when you have to lock things for a long time. C is on the
> other end of the scale. B is in between. The problem with A is that
> you have to handle cross operations (like swapping elements of
> different containers) and you can easily run into a deadlock if you
> do not apply some policy of locking.

Mr. Kazakov's advice is excellent. Here he hints at an important
point: Why do you need this functionality? If you're building tools
for other developers, you'll need this level of generality and can
justify the time and effort to address all these issues. If, on the
other hand, you're trying to solve a particular problem, this might be
a good time to take a step back and look at your real requirements.
Do you really need transactional collections or is that simply an
artifact of your proposed solution?

> A viable alternative is to avoid mutability. Scrap 3 and 4. Use by
> value semantics for 2, and you will go with A when only 1 is left
> (and no operations between containers allowed).
>
> On this path you can switch to immutable containers. That is a sort
> of transaction model when a thread dealing with the container
> becomes a copy of it (opens transaction). Then it does what needed
> and commits changes (closes transaction).

This obviously only works for relatively small collections of
objects, even if only references or smart pointers are copied. You
may also want to consider making the nodes in the collection
immutable, avoiding the complexity of allowing updates. Again, it
depends on your underlying requirements.

> In general case, there is no optimal design for concurrently
> accessed containers. Typically, first when you constrain the
> container's functionality to only things you need and glue
> individual operations into larger ones, then you will be able to
> make some choices.

More excellent commentary. If you're interested in a completely
different approach, you might want to look at JavaSpaces. The
reference implementation is in Java, but it's relatively
straightforward to apply the concepts to any language. A space can be
used as a shared collection and provides the transactional isolation
and concurrent access you require.

Regards,

Patrick

------------------------------------------------------------------------
S P Engineering, Inc. | Large scale, mission-critical, distributed OO
| systems design and implementation.
pjm(a)spe.com | (C++, Java, Common Lisp, Jini, middleware, SOA)
 |  Next  |  Last
Pages: 1 2
Prev: Final call for papers
Next: Fundamental terms, question (Object Thinking)