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

Subject: Re: [Boost-users] [thread] Locking Problem (App Level)
From: Brian Budge (brian.budge_at_[hidden])
Date: 2011-11-15 11:35:59

On Tue, Nov 15, 2011 at 7:28 AM, Arun Ramasamy
<aramasamy_at_[hidden]> wrote:
> 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.
>>>>>

Someone already mentioned using a list, and someone else a deque.
Unless there are other reasons to use a vector (contiguous entries), I
think that these are excellent options.  It would likely require very
few changes, and would allow you to only hold a lock on the original.
If you need to perform an update, likely now you have an index.  Using
a deque would allow you to continue using an index.   Existing data is
not invalidated.

Some questions though:  What should happen in thread 2 or 3 when it
encounters an entry being updated by thread 1?  Should the thread wait
for thread 1 to finish it's update, and use the new data?  If so, you
should consider keeping a mutex with each entry.  There are more
complex lock-free options, but they would not ensure the case of
simultaneous update/read would result in the new data.

I'm guessing that the lists generated by threads 2 and 3 are smaller
than the original vector, and perhaps contain derived data?

  Brian