http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* Lock-free Threadpool and lockfree_SPMC and forward progress... - 2 messages,
2 authors
http://groups.google.com/group/comp.programming.threads/t/da2248916ab05379?hl=en
* Strong thread safety and lock free? - 2 messages, 2 authors
http://groups.google.com/group/comp.programming.threads/t/ea65e0404880396f?hl=en
* Lock-free threadpool 1.03 and patch... - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/7a784a0ad7f4ce87?hl=en
* weird thread behavior on itanium/hp-ux with pthread - 4 messages, 3 authors
http://groups.google.com/group/comp.programming.threads/t/b2b5d744b99b760c?hl=en
* Lockfree_SPMC and the correctness - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/ef2ecb1f19720ec0?hl=en
==============================================================================
TOPIC: Lock-free Threadpool and lockfree_SPMC and forward progress...
http://groups.google.com/group/comp.programming.threads/t/da2248916ab05379?hl=en
==============================================================================
== 1 of 2 ==
Date: Tues, Jul 28 2009 12:04 am
From: "Dmitriy V'jukov"
On 28 июл, 06:40, Amine <ami...@colba.net> wrote:
> Hello all,
>
> I was thinking about my lockfree threadpool and lockfree_SPMC,
> and as you know lock-free does guaranty only global progress,
> so, if we have let say more than 100 cores, i think it will be a
> problem.. hence, what i am doing is using a queue for every worker
> thread this will lower the contention and *guaranty* forward progress
> for every worker thread.
> So, if you have read carefully the algorithms above, you will come to
> the
> conclusion that if we are in a system with let say over 100 cores we
> can
> go through a state where we will have a very high contention in the
> work-stealing
> process, this will guaranty forward global progress but not guaranty
> forward
> progress for every worker thread in the work-stealing process. And
> that's not good.
>
> So, one solution is to loop a bound number of times in the
> lockfree_SPMC pop()
> method and not loop infinitly.
>
> Have you any other ideads, suggestions ?
Hmmm... Leave as is.
IMHO distributed queues + lock-free guarantees is enough to reduce
contention to acceptable level. Thread fails IFF some other thread
succeeds, and if thread succeeds than he retires with significant
amount of work for some time.
--
Dmitriy V'jukov
== 2 of 2 ==
Date: Tues, Jul 28 2009 4:11 pm
From: "Chris M. Thomasson"
"Amine" <aminer@colba.net> wrote in message
news:50aba4cf-8713-46b0-9970-2b6b0b82bf64@d32g2000yqh.googlegroups.com...
> Hello all,
>
> I was thinking about my lockfree threadpool and lockfree_SPMC,
> and as you know lock-free does guaranty only global progress,
> so, if we have let say more than 100 cores, i think it will be a
> problem.. hence, what i am doing is using a queue for every worker
> thread this will lower the contention and *guaranty* forward progress
> for every worker thread.
> So, if you have read carefully the algorithms above, you will come to
> the
> conclusion that if we are in a system with let say over 100 cores we
> can
> go through a state where we will have a very high contention in the
> work-stealing
> process, this will guaranty forward global progress but not guaranty
> forward
> progress for every worker thread in the work-stealing process. And
> that's not good.
>
> So, one solution is to loop a bound number of times in the
> lockfree_SPMC pop()
> method and not loop infinitly.
>
> Have you any other ideads, suggestions ?
Ideally, stealing operations would not be all that frequent. I am not sure
how Clik performs its stealing operation. For instance, do they allow a
thief to attempt to steal from all workers, or do they allow a thief to
attempt to steal from a single random worker and if that fails, then it
waits for work to be explicitly queued to it.
==============================================================================
TOPIC: Strong thread safety and lock free?
http://groups.google.com/group/comp.programming.threads/t/ea65e0404880396f?hl=en
==============================================================================
== 1 of 2 ==
Date: Tues, Jul 28 2009 8:53 am
From: Marcel Müller
Hi,
Chris M. Thomasson wrote:
> I found the patent application:
>
> http://www.google.com/patents/about?id=cs6aAAAAEBAJ&dq=Lightweight+reference+counting+using+single-target+synchronization
thanks for the links. It was a long document with many stories about
'persons of ordinary skill' and the only really important fact is in
section 72 telling that there is an additional counter at any shared
reference. However, the idea is very useful.
Marcel
== 2 of 2 ==
Date: Tues, Jul 28 2009 10:26 pm
From: "Chris M. Thomasson"
"Marcel Müller" <news.5.maazl@spamgourmet.com> wrote in message
news:4a6f1f05$0$30227$9b4e6d93@newsspool1.arcor-online.net...
> Hi,
>
> Chris M. Thomasson wrote:
>> I found the patent application:
>>
>> http://www.google.com/patents/about?id=cs6aAAAAEBAJ&dq=Lightweight+reference+counting+using+single-target+synchronization
>
> thanks for the links. It was a long document with many stories about
> 'persons of ordinary skill'
;^)
> and the only really important fact is in section 72 telling that there is
> an additional counter at any shared reference. However, the idea is very
> useful.
The drawings basically explain everything as they show how Joes atomic-ptr
works.
==============================================================================
TOPIC: Lock-free threadpool 1.03 and patch...
http://groups.google.com/group/comp.programming.threads/t/7a784a0ad7f4ce87?hl=en
==============================================================================
== 1 of 1 ==
Date: Tues, Jul 28 2009 4:04 pm
From: "Chris M. Thomasson"
"Amine" <aminer@colba.net> wrote in message
news:6dff72c7-6d5a-4d29-952e-4907f71995cf@o6g2000yqj.googlegroups.com...
>
> Hello,
>
> I have added PushInQueue1() and PushInQueue2()
> to the Lockfree threadpool. If for example you have two
> super fast connection and you want to have more throuput
> and minimize contention you will use those two methods
> on each worker thread.
>
> Also, i have patched it and added in the destructor
> the following:
> SetLength(FThreads, 0);
> SetLength(Queues, 0);
>
> To free the memory of the dynamic arrays.
>
> Now it is working perfectly and version 1.03 is online now.
>
> Welcome: http://www.colba.net/~aminer/
How are you handling the case in which a queue is full/empty? It seems like
your busy-waiting. Unless I am missing something vital, this is a troubling
practice indeed...
==============================================================================
TOPIC: weird thread behavior on itanium/hp-ux with pthread
http://groups.google.com/group/comp.programming.threads/t/b2b5d744b99b760c?hl=en
==============================================================================
== 1 of 4 ==
Date: Tues, Jul 28 2009 6:07 pm
From: Jeremy
we have a code snippet where one thread wakes up the other thread
whenever necessary:
thread 0 thread 1
loop loop
do_something(); if
(somethingelse_happened) {
mutex.lock(); mutex.lock();
if ( !signaled) { if
(sleeping) {
sleeping = true; sleep =
false;
while (sleeping)
condition.signal();
condition.timedwait(1); }
} else { signaled
= true;
sleeping = false; mutex.unlock();
} }
mutex.unlock
however, using tusc, we observed that thread 0 did go to sleep first,
and 'something else' did happen afterwards, but thread 0 did not wake
up until it timed out.
could anybody explain why this can happen, or I simply missed
something?
Thanks,
Jeremy
== 2 of 4 ==
Date: Tues, Jul 28 2009 6:15 pm
From: Jeremy
the pseudo code was totally messed up, here it is again:
thread 0
loop
mutex.lock();
do_something();
if ( !signaled) {
sleeping = true;
while (sleeping)
condition.timedwait(1);
} else {
sleeping = false;
}
mutex.unlock
thread 1 -----------------------
loop
if (somethingelse_happened) {
mutex.lock();
if (sleeping) {
sleep = false;
condition.signal();
}
signaled = true;
mutex.unlock();
}
== 3 of 4 ==
Date: Tues, Jul 28 2009 9:25 pm
From: Loïc Domaigné
Hi Jeremy,
> the pseudo code was totally messed up, here it is again:
>
> thread 0
>
> loop
> mutex.lock();
> do_something();
> if ( !signaled) {
> sleeping = true;
> while (sleeping)
> condition.timedwait(1);
> } else {
> sleeping = false;
> }
> mutex.unlock
>
> thread 1 -----------------------
>
> loop
> if (somethingelse_happened) {
> mutex.lock();
> if (sleeping) {
> sleep = false;
> condition.signal();
> }
> signaled = true;
> mutex.unlock();
> }
I guess, this should be "sleeping = false" in thread 1, right? It's
difficult to pinpoint problem using pseudo-code. Can you please post a
minimalistic example (which compiles) that shows your particular
problem?
TIA,
Loïc.
--
My Blog: http://www.domaigne.com/blog
"Computers are good at following instructions, but not at reading your
mind." – Donald Knuth
== 4 of 4 ==
Date: Tues, Jul 28 2009 10:03 pm
From: David Schwartz
On Jul 28, 6:15 pm, Jeremy <fc2...@gmail.com> wrote:
> the pseudo code was totally messed up, here it is again:
>
> thread 0
>
> loop
> mutex.lock();
> do_something();
> if ( !signaled) {
> sleeping = true;
> while (sleeping)
> condition.timedwait(1);
> } else {
> sleeping = false;
> }
> mutex.unlock
>
> thread 1 -----------------------
>
> loop
> if (somethingelse_happened) {
> mutex.lock();
> if (sleeping) {
> sleep = false;
> condition.signal();
> }
> signaled = true;
> mutex.unlock();
> }
Why do you have "while(sleeping)" when what you really want is "while(!
signaled)"? Your "sleeping" variable seems to serve no purpose but to
make this design at least twice as complex as it needs to be.
DS
==============================================================================
TOPIC: Lockfree_SPMC and the correctness
http://groups.google.com/group/comp.programming.threads/t/ef2ecb1f19720ec0?hl=en
==============================================================================
== 1 of 1 ==
Date: Tues, Jul 28 2009 11:55 pm
From: "Chris M. Thomasson"
"Amine" <aminer@colba.net> wrote in message
news:ec33d7b3-3680-437e-b88e-0ac3a524066a@y19g2000yqy.googlegroups.com...
On Jul 14, 11:52 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > "Amine" <ami...@colba.net> wrote in message
> >
> > news:55d911c7-de45-4131-a1b3-527edbf34b29@l31g2000vbp.googlegroups.com...
> > [...]
> >
> > > I have looked at the assembler code and it does not reorder
> > > the two operations.
> >
> > > Hence, my lockfree_SPMC and lockfree_priority_SPMC
> > > are safe and correct.
> >
> > Are you sure that any Pascal compiler will never reorder the operations?
> >
> > [...]
> No Chris, not for any Pascal compiler.
> I have just verified for Delphi and Freepascal.
Of course you can totally eliminate this "possibility" by coding your
`lockfree_SPMC' algorithm in pure assembly language; assemble and link to
the object file.
==============================================================================
You received this message because you are subscribed to the Google Groups "comp.programming.threads"
group.
To post to this group, visit http://groups.google.com/group/comp.programming.threads?hl=en
To unsubscribe from this group, send email to comp.programming.threads+unsubscribe@googlegroups.com
To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.programming.threads/subscribe?hl=en
To report abuse, send email explaining the problem to abuse@googlegroups.com
==============================================================================
Google Groups: http://groups.google.com/?hl=en
No comments:
Post a Comment