Re: [Boost-users] [thread] Locking Problem (App Level)

Subject: Re: [Boost-users] [thread] Locking Problem (App Level)
From: Richard Damon (Richard_at_[hidden])
Date: 2011-11-14 20:56:56

On 11/14/11 8:43 PM, U.Mutlu wrote:
> Peter Dimov wrote, On 2011-11-15 01:54:
>> U.Mutlu wrote:
>>> Hi,
>>> in my current project I'm confronted with an IMO challenging
>>> real-world problem, and am looking for an optimal or near-optimal
>>> solution for it:
>>>
>>> There is a standard vector (std::vector) of structs
>>> (ie. data records), and 3 threads working on that vector:
>>> thread 1: about every 10 seconds appends a new record
>>> to the vector, or updates an existing record,
>>> there are no deletions done.
>>> thread 2: walks over all records in a read-only manner
>>> and generates a list; it takes about 60 seconds.
>>> thread 3: walks over all records in a read-only manner
>>> and generates a different list; it takes about 90 seconds.
>>>
>>> Of course all threads are running simultanously, but thread 2 fires
>>> its job every 3 minutes, thread 3 every 5 minutes, and thread 1 is
>>> permanently working (reacting on external events).
>>>
>>> The problem is this: when thread 2 or 3 are running (remember 60 or
>>> 90 seconds)
>>> then using the usual shared locking schemes thread 1 cannot do its job,
>>> although it is the most important thread and its job is
>>> time-critical (recording external events).
>>>
>>> Is there a better locking solution to this problem?
>>
>> It depends. How long does it take to make a copy of the vector?
>
> Hmm. let's say it takes 35 seconds, but this method consumes
> very much memory, eventually tripling the memory consumption
> (when thread2.job and thread3.job run in parallel).
> Other, resource-efficient, alternatives?
>
>> // thread 1
>> lock mutex;
>> update vector;
>> unlock mutex;
>>
>> // thread 2
>> lock mutex;
>> make a copy of the vector;
>> unlock mutex;
>> walk over copy;
>>
>> // thread 3: see thread 2
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
Have you thought of using a list instead of a vector. Since you never
delete, then thread 2 and thread 3 never have their iterator into the
list invalidated. They then only need to lock the mutex while they are
actually accessing a node/walking the list, and can give up the mutex
while processing the contents of the node (perhaps making a copy of just
that node).

If you are only adding to the end of the vector, you can do something
similar with the vector, if you iterate through it with an index as
opposed to a iterator, since even if the vector reallocates the nth
element is still the nth element.

-- 
Richard Damon