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

Subject: Re: [Boost-users] [thread] Locking Problem (App Level)
From: Arun Ramasamy (aramasamy_at_[hidden])
Date: 2011-11-15 10:28:06

On 11/15/2011 4:12 AM, Vicente Botet wrote:
> 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
>>
> Hi,
>
> If you have just a writer thread and two (or more) reader threads, you could
> split your application in two parts. The writer part writes directly to his
> vector without using any mutex and in addition log some updates that need to
> be done on the reader part (using a mutex or any lock-free available
> algorithm).
> Any thread in the reader part starts by updating the reader vector by taking
> in account the updates in the log.
>
> The space required is 2 copies of the data and the temporary queue of
> commands to be updated.
> The synchronization time is reduced to the writing/reading of a command in
> the queue command.
>
> This is a little bit more complex, but scales well when you need to add more
> readers.
>
> Best,
> Vicente
I'd to deal with something very similar - with one writer thread and 
multiple readers. But my time scale were prettty diffferent - in the 
scale of milli seconds. Some of the modifications/options I'd tried in 
my app:
Opt 1. Using a fixed size lock-free list  - some info here on it
http://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c
Opt 2. All the records were stored as shared pointers and had a unique 
id associated (from a generator). The writer had a copy of the list and 
the reader had another copy. The writer will lock and update the list 
(modify was implemented as delete/add). The reader will readlock and 
read a copy of the list. The only time there was a contest was when both 
the writer and one of the readers want access to the list. Since these 
were fast operations (esp since the reader has to just copy a bunch of 
shared pointers(around 5000-10000)), there was very minimal conflict in 
access to lock. So the readers get their own copy to do whatever they 
wants in their time and the writer can change the dataset however he wants.

Hope this helped :)
best arun

> --
> View this message in context: http://boost.2283326.n4.nabble.com/thread-Locking-Problem-App-Level-tp4041317p4042305.html
> Sent from the Boost - Users mailing list archive at Nabble.com.
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

--