 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 07/08/2012 04:55 PM, Warp wrote:
> Invisible<voi### [at] dev null> wrote:
>> Does anyone know of somewhere I can find a description of how to
>> implement a lock-free work queue? I'm curious to see how it's done.
>
> Have you tried a google search. I didn't, but I'm pretty sure that there
> should be plenty of material out there.
I had thought this, but I didn't manage to find anything. (Other than
several Wikipedia pages saying that "algorithms exist to do this".)
> AFAIK lock-free algorithms cannot be implemented without proper hardware
> support.
Yeah, I figured that would be the case.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 07/08/2012 14:48, Invisible nous fit lire :
> On 07/08/2012 01:42 PM, Le_Forgeron wrote:
>> Le 07/08/2012 13:00, Invisible a écrit :
>>> Does anyone know of somewhere I can find a description of how to
>>> implement a lock-free work queue? I'm curious to see how it's done.
>>
>>
>> I thinks there might be one in The Art of Multiprocessor Programming.
>
> This one?
>
> http://tinyurl.com/cfklrg2
>
>> The difficult part in all such algorithms is the "special" write
>> instruction. You cannot make it lock-free without the support at the
>> assembly level by the instruction set (at least in NUMA architecture)
>
> So that's, what, a CAS instruction or something?
Yes & Yes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8/7/2012 5:42, Le_Forgeron wrote:
> The difficult part in all such algorithms is the "special" write
> instruction. You cannot make it lock-free without the support at the
> assembly level by the instruction set (at least in NUMA architecture)
Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good write-up.)
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8/7/2012 8:55, Warp wrote:
> AFAIK lock-free algorithms cannot be implemented without proper hardware
Lamport actually surprised a lot of people when he came up with the bakery
algorithm.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/08/2012 12:48 AM, Darren New wrote:
> On 8/7/2012 5:42, Le_Forgeron wrote:
>> The difficult part in all such algorithms is the "special" write
>> instruction. You cannot make it lock-free without the support at the
>> assembly level by the instruction set (at least in NUMA architecture)
>
> Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good
> write-up.)
Why must all algorithms do to with multithreading have food in their names?
First the dining philosophers, and now this?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 10/08/2012 01:48, Darren New a écrit :
> On 8/7/2012 5:42, Le_Forgeron wrote:
>> The difficult part in all such algorithms is the "special" write
>> instruction. You cannot make it lock-free without the support at the
>> assembly level by the instruction set (at least in NUMA architecture)
>
> Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good
> write-up.)
>
The backery is lock free, but need either static threads or a global
registry (list, whatever) of all active threads. You cannot protect such
registry with backery (deadly recursion).
(
Other inherent issue is unlimited number: on rollover with an actual
implementation, you're stuck.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 8/10/2012 0:59, Invisible wrote:
> Why must all algorithms do to with multithreading have food in their names?
>
> First the dining philosophers, and now this?
The dining philosophers introduced "starvation" of resources.
The bakery algorithm is called that because you "take a number" just like at
the bakery.
--
Darren New, San Diego CA, USA (PST)
"Oh no! We're out of code juice!"
"Don't panic. There's beans and filters
in the cabinet."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/08/2012 06:37 PM, Darren New wrote:
> The bakery algorithm is called that because you "take a number" just
> like at the bakery.
You mean like this?
http://www.cad-comic.com/cad/20100326/
In all seriousness, I've never seen this in any bakery. But the
supermarkets tend to do it...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 10/08/2012 06:37 PM, Darren New wrote:
> The bakery algorithm is called that because you "take a number" just
> like at the bakery.
Maybe I missed it, but... how does the algorithm guarantee that no two
people take the same number?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 15.08.2012 13:17, schrieb Invisible:
> On 10/08/2012 06:37 PM, Darren New wrote:
>> The bakery algorithm is called that because you "take a number" just
>> like at the bakery.
>
> Maybe I missed it, but... how does the algorithm guarantee that no two
> people take the same number?
It doesn't.
"Due to the limitations of computer architecture, some parts of
Lamport's analogy need slight modification. It is possible that more
than one thread will get the same number when they request it; this
cannot be avoided. Therefore, it is assumed that the thread identifier i
is also a priority . A lower value of i means a higher priority and
threads with higher priority will enter the critical section first."
(from Wikipedia, which is one of your friends)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
