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

Groups > comp.programming.threads > #2275 > unrolled thread

Starvation freedom and the two locks algorithm...

Back to article view | Back to comp.programming.threads

Contents

  Starvation freedom and the two locks algorithm... aminer <aminer@toto.net> - 2014-04-27 12:40 -0700
    Re: Starvation freedom and the two locks algorithm... aminer <aminer@toto.net> - 2014-04-27 12:51 -0700
    Re: Starvation freedom and the two locks algorithm... aminer <aminer@toto.net> - 2014-04-27 12:55 -0700

#2275 — Starvation freedom and the two locks algorithm...

Hello,


I have just updated my concurrent FIFO queue that uses
a two locks algorithm, before i was doing something like this
on the push() side:

==

  function TWQueue.push(tm : long):boolean;
begin

result:=true;
lock1.enter;
if getlength >= fsize
   then
       begin
           result:=false;
          lock1.leave;
          exit;
       end;

     setObject(head,tm);
     head:=(head+1);
    lock1.leave;
if fwait then sema.signal;
end;

==

But the above pop() method is not starvation-free , when the queue is 
full and the "if getlength >= fsize" becomes true , the threads
will loop back a, hence this is not starvation-free, to be fully 
starvation-free here is what look my updated pop() method:

==
function TWQueue.push(tm : long):boolean;
begin

result:=true;
lock1.enter;
if getlength >= fsize
   then
       begin
         while getlength >= fsize
          do sleep(0);
      end;

     setObject(head,tm);
     head:=(head+1);
    lock1.leave;
if fwait then sema.signal;
end;

===


When the a thread enters and the "if getlength >= fsize" is
true it will spin-wait inside the locked region until
"if getlength >= fsize" is false, and when you set
the wait parameter to true my concurrent FIFO queue will become
fully starvation-free on both the push() side and on the pop() side.


You can download my updated concurrent FIFO queue version 1.02 that uses 
the two locks algorithm from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.
algorithm

[toc] | [next] | [standalone]

#2276

Hello,


I have just updated my concurrent FIFO queue that uses
a two locks algorithm, before i was doing something like this
on the push() side:

==

  function TWQueue.push(tm : long):boolean;
begin

result:=true;
lock1.enter;
if getlength >= fsize
   then
       begin
           result:=false;
          lock1.leave;
          exit;
       end;

     setObject(head,tm);
     head:=(head+1);
    lock1.leave;
if fwait then sema.signal;
end;

==

But the above pop() method is not starvation-free , when the queue is 
full and the "if getlength >= fsize" becomes true , the threads
will loop backa, hence this is not starvation-free, to be fully 
starvation-free here is what look my updated push() method:

==
function TWQueue.push(tm : long):boolean;
begin

result:=true;
lock1.enter;
if getlength >= fsize
   then
       begin
         while getlength >= fsize
          do sleep(0);
      end;

     setObject(head,tm);
     head:=(head+1);
    lock1.leave;
if fwait then sema.signal;
end;

===


When the a thread enters and the "if getlength >= fsize" is
true it will spin-wait inside the locked region until
"if getlength >= fsize" is false, and when you set
the wait parameter to true my concurrent FIFO queue will become
fully starvation-free on both the push() side and on the pop() side.


You can download my updated concurrent FIFO queue version 1.02 that uses 
the two locks algorithm from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#2277

Hello,

You have to set the wait parameter of the constructor to "true"
and set the option inside the file "defines.inc" to TicketSpinlock
or AMLock, so that my concurrent FIFO queue becomes fully
starvation-free.


Please take a look a=t the source code here:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.


On 4/27/2014 12:40 PM, aminer wrote:
>
> Hello,
>
>
> I have just updated my concurrent FIFO queue that uses
> a two locks algorithm, before i was doing something like this
> on the push() side:
>
> ==
>
>   function TWQueue.push(tm : long):boolean;
> begin
>
> result:=true;
> lock1.enter;
> if getlength >= fsize
>    then
>        begin
>            result:=false;
>           lock1.leave;
>           exit;
>        end;
>
>      setObject(head,tm);
>      head:=(head+1);
>     lock1.leave;
> if fwait then sema.signal;
> end;
>
> ==
>
> But the above pop() method is not starvation-free , when the queue is
> full and the "if getlength >= fsize" becomes true , the threads
> will loop back a, hence this is not starvation-free, to be fully
> starvation-free here is what look my updated pop() method:
>
> ==
> function TWQueue.push(tm : long):boolean;
> begin
>
> result:=true;
> lock1.enter;
> if getlength >= fsize
>    then
>        begin
>          while getlength >= fsize
>           do sleep(0);
>       end;
>
>      setObject(head,tm);
>      head:=(head+1);
>     lock1.leave;
> if fwait then sema.signal;
> end;
>
> ===
>
>
> When the a thread enters and the "if getlength >= fsize" is
> true it will spin-wait inside the locked region until
> "if getlength >= fsize" is false, and when you set
> the wait parameter to true my concurrent FIFO queue will become
> fully starvation-free on both the push() side and on the pop() side.
>
>
> You can download my updated concurrent FIFO queue version 1.02 that uses
> the two locks algorithm from:
>
> http://pages.videotron.com/aminer/
>
>
>
> Thank you,
> Amine Moulay Ramdane.
> algorithm
>
>
>
>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web