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

Groups > comp.programming.threads > #2276

Re: Starvation freedom and the two locks algorithm...

Cross-posted to 2 groups.

Show all headers | View raw

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.

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

Thread

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

csiph-web