Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2153

Bakery algorithm

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson

==

{ Queue Ops }
procedure producer(state:long);
     var ver:longword;
     var c:^cell;
begin
     ver := ATOMIC_XADD(@head, 1);
     c := @cells[ver and (N - 1)];
     while ATOMIC_LOAD(@c^.ver) <> ver do backoff;
     c^.state := state;
     ATOMIC_STORE(@c^.ver, ver + 1);
end;


function consumer():long;
     var ver:longword;
     var c:^cell;
begin
     ver := ATOMIC_XADD(@tail, 1);
     c := @cells[ver and (N - 1)];
     while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff;
     consumer := c^.state;
     ATOMIC_STORE(@c^.ver, ver + N);
end;


===


As you have noticed if i want to use this FIFO queue
inside my scalable FIFO fair lock, i don't need synchronization
on the pop() side , so even if i delete the  ATOMIC_XADD()
inside the consumer() method there will still be two cache-lines 
transfers ionside the consumer methoid,  one when you want to increment 
the "tail" and another one since the "@c^.ver" is changed every time and 
it will incur a cache-line transfer , so it will be slower than my array 
based queue and this has been confirmed on my benchmarks.




Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Bakery algorithm aminer <aminer@toto.net> - 2014-04-13 19:28 -0700
  Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:44 -0700
    Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:46 -0700
      Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 13:49 -0700

csiph-web