HI Yubin,
Please see below,
On Tue, Aug 8, 2017 at 10:12 AM, Yubin Ruan <ablacktshirt@xxxxxxxxx> wrote:
> 2017-08-08 0:57 GMT+08:00 Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>:
>> On Tue, Aug 08, 2017 at 12:48:08AM +0800, Yubin Ruan wrote:
>>> 2017-08-05 9:02 GMT+08:00 Yubin Ruan <ablacktshirt@xxxxxxxxx>:
>>> > 2017-08-05 3:50 GMT+08:00 Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>:
>>> >> On Fri, Aug 04, 2017 at 11:57:28PM +0800, Yubin Ruan wrote:
>>> >>> 2017-08-04 22:52 GMT+08:00 Yubin Ruan <ablacktshirt@xxxxxxxxx>:
>>> >>> > Hi,
>>> >>> > I am sure the subject explain my intention. I got two processes trying
>>> >>> > to modifying the same place. I want them to do it one after one, or,
>>> >>> > if their operations interleave, I would like to let them know that the
>>> >>> > content have been changed and polluted by the other so that the
>>> >>> > content should be given up. That is, I would rather give up the data,
>>> >>> > if polluted, than having a false one.
>>> >>> >
>>> >>> > I try to set a atomic ref counter, but it seems impossible to do that
>>> >>> > without a lock to synchronize.
>>> >>> >
>>> >>> > Note that I don't want a strict synchronization: the situation is a
>>> >>> > lot better. The data can be given up if that place has been polluted.
>>> >>>
>>> >>> Let's explain some of my reasoning: if process A use some flag to
>>> >>> indicate that it has entered the critical region, then if it crash
>>> >>> before it can reset the flag, all following processes cannot enter
>>> >>> that region. But if process A cannot use flag for indication, how to
>>> >>> other people know (how to synchronization)?
>>> >>
>>> >> The simplest approach is to guard the data with a lock.
>>> >
>>> > Indeed. But if a process get killed then it will have no chance to release
>>> > the lock...
>>> >
>>> > By the way, do you know whether there are any chances that a thread get
>>> > killed by another thread when doing some "small" things? I mean something
>>> > like this:
>>> >
>>> > lock();
>>> > some_mem_copying();
>>> > unlock();
>>> >
>>> > Are there any chance that a thread get killed by another thread before it
>>> > can "unlock()", without the entire process going down?
>>
>> Indeed, that is possible. The pthread_kill() system call if nothing
>> else.
>>
>>> pthread_mutexattr_setrobust(..) will help in this situation, although it is
>>> quite painful that nobody is maintaining the NPTL docs currently and you have
>>> to dive into the source code if you want to make sure the semantic is exactly
>>> what you want.
>>
>> True on all counts. But what exactly are you trying to achieve?
>
> What I am going to achieve is to allow multiple producer to place some content
> in some slots of a queue. The risk is that some producers might be in the same
> slot, so that it require some locking to synchronize them. But if you use lock,
It seems what you are looking for is a lock-free queue implementation,
which, by placing difference write requests on different queue slots,
immunes to the risk you mentioned. There are plenty of them. One
example (From "Fast concurrent queues for x86 processors", 2013):
enqueue(x : Object) {
while (true) {
t := F&A(&tail, 1)
if ( SWAP(&Q[t], x) =⊥ ) return OK
} }
dequeue() {
while (true) {
h := F&A(&head, 1)
x := SWAP(&Q[h], ?)
if x !=⊥ return x
if ( tail ≤ h+1) return EMPTY
} }
But as mentioned by Paul, "Doing "just a bit more" in this area
usually means incurring a huge amount more pain", the code snippet
above may suffer livelock problem. If you care about that, the authors
have addressed the problem and the code is free to download.
--Jason
> a thread holding the lock can get killed accidentally (for whatever reasons)
> before releasing it, causing all the other producers unable to acquire it
> therefore.
>
> Ideas of RCU can help here, except that I have a statically allocated
> array-based queue, where every slot is addressed by index rather than pointer,
> and because we can not dynamically allocate any space (malloc() not allowed),
> our choices are limited.
>
>> Note that killing a thread not holding any lock can be a problem, for
>> example, suppose the thread that is to place a new element gets killed
>> just before doing so. How do you intend to handle that situation?
>>
>>> Yubin
>>>
>>> >> But if you don't want to do that, another approach is to restrict the
>>> >> data to one machine word minus one bit, with zero saying that the location
>>> >> is (as you say) unpolluted. Then you can use a compare-and-swap loop
>>> >> to update the location only if it is unpolluted.
>>> >>
>>> >> But maybe you need more data. If so, you can have the data separately
>>> >> (perhaps dynamically allocated, perhaps not, your choice), and then use
>>> >> the compare-and-swap method above where NULL says unpolluted.
>>> >
>>> > Good suggestion... although I think it would be pretty painful.
>>
>> Well, if you are going for full-up fault tolerance, you are in for a
>> world of pain regardless. Fault tolerance is non-trivial any way you
>> look at it.
>>
>> Therefore, my advice is to very carefully work out what your users really
>> need, and implement exactly that. Doing "just a bit more" in this area
>> usually means incurring a huge amount more pain, often incurred later
>> in the project.
>
> Yes I agree. Designing a lock-free algorithm is full of fun, but nevertheless
> lock-free comes with price.
>
> Thanks,
> Yubin
> --
> To unsubscribe from this list: send the line "unsubscribe perfbook" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
