Scalable RWLock and FIFO fairness

[aminer]

Hello...

Please read this about the Windows event object:

http://msdn.microsoft.com/en-us/library/windows/desktop/ms682655(v=vs.85).aspx

It says: "Do not assume a first-in, first-out (FIFO) order"


So i have thought more about this, and if you have noticed i have
designed and implemented  two variations of my scalable RWLock, one that is called LW_RWLOCK that scales and that is not starvation free and that uses more CPU ressources, and another one that is called RWLock that scales and that is not stavation free on the reader side and  that uses less CPU ressources, so i have thought more about the second one that is called RWLock that uses my SemMonitor on the writer side and that uses a portable event object on the reader side, and i think it is not starvation free on the reader side cause the Windows event object that i am using on the reader side of my scalable RWLock is not FIFO fair, so i have thought more about this and i think that i have to upgrade my SemaMonitor to support the set() and reset() methos as in the Windows event object but my SemaMonitor will be FIFO fair so
it will be starvation free , the windows event object is not,
after that i will enhanced and upgrade my new SemaMonitor on the reader side of my
scalable RWLock so that it supports many requirements such us:

1- it will use my new SemaMonitor on both the reader and writer side
so it will use less CPU ressources.

2- It will scale on multicores

3- It will be FIFO fair on both the reader and the writer side
   so it will be starvation free.


So i will soon upgrade my SemaCondVar and SemaMonitor and my scalable RWLock so stay tuned.



Thank you,

Amine Moulay Ramdane.

[aminer]

Hello,


I have thought more about my scalable RWLock , i mean my second variation that scales and that is not FIFO fair and starvation free on the reader side, if you use the Windows manual event object and call the Setevent()  and Resetevent() methods  it will not be starvation free, so i will not use the Windows manual event object, so i have to implement this Setevent() and Resetevent methods inside my SemaMonitor and SemaCondvar objects so that my scalable RWLock be FIFO fair , but i have thought more and if you let my RWLock algorithm as it is, it will not be starvation free cause i am looping back inside my scalable RWLock and entering again my SemaMonitor but even if my SemaMonitor is FIFO fair my RWLock will not be FIFO fair cause i am looping back and
entering again my SemaMonitor, so the solution is that i have to change the following code:

if (FCount3^.fcount3 = 0)
then break
else
 begin
   LockedExchangeAdd(FCount1^[myid].fcount1,-1);
 end;


with:

if (FCount3^.fcount3 = 0)
then break

So i have to not decrement and looping back.

Look here at my LW_RWLOCK algorithm:

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


But with this change in my code my scalable RWLock algorithm will favor more the reader threads than the writer threads, but it will be FIFO fair and starvation free and this variation of my scalable RWLOCK will support the all following requirements:

1- it will use my new SemaMonitor on both the reader and writer side
so it will use less CPU ressources.

2- It will scale on multicores

3- It will be FIFO fair on both the reader and the writer side
   so it will be starvation free.



So i will upgrade soon my SemaMonitor and my SemaCondvar
and my scalable RWLock to support all those requirements.
 

Thank you,


Amine Moulay Ramdane.

[aminer]

Hello all,

I have to be smart more than that, so be smart with me...

In my previous post i have told you that i have to upgrade my
SemaCondvar and SemaMonitor objects, but i have thought more
and i think i have to not upgrade it, the solution is that i
have to delete the following code inside my TRWLOCK.RLock() method:

if (FCount3^.fcount3 = 0)
then break
else
 begin
   LockedExchangeAdd(FCount1^[myid].fcount1,-1);
 end;


look here at my LW_RWLOCK algorithm:

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


But that's not all and that's not enough, i have to avoid the enhancement of my previous post so that my scalable RWLock algorithm will not favor more the reader side , cause if it  favor more the reader side the write side can starve for a long time and this is bad , so i have thought more and i think i have found a solution for that , if you look at the interface of  my SemaCondvar and SemaMonitor objects look here: http://pages.videotron.com/aminer/

I have implemented a method called  "function WaitersBlocked:integer"
this WaitersBlocked() method will return how many waiters are blocked and this is enough to implement a much clever algorithm that do not
favor more the reader side, so i have to use my SemaMonitor on
both the reader side and the writer side of my scalable RWLock and on the reader side i have have also to look at how much Waiters there is Waiters Blocked on both the reader side and writer side by calling on
both the reader and the write side, if there is no writers threads on the writer side i will call the SignalAll() method of my SemaMonitor to wake up all the waiters on the reader side, but if  the there is more than 1 waiter threads on the writer side i will signal only one thread of the waiters on the reader side, so that i give a chance to the other writer threads to run, and by using this new algorithm the writers side will not starve for a long time, and my new scalable RWLock algorithm will support all the following requirements:


1- it will use my new SemaMonitor on both the reader and writer side
so it will use less CPU ressources.

2- It will scale on multicores

3- It will be FIFO fair on both the reader and the writer side
   so it will be starvation free.



So i will upgrade soon my scalable RWLock to support all those requirements.


Thank you,


Amine Moulay Ramdane.









 

[aminer]

Hello all,


I was reading and reading again my algorithm of  my scalable RWLock,
and i have discovered what is intelligence and what is to be smart..
if you look at my algorithm here: http://pages.videotron.com/aminer/rwlock1.html

you will notice that this algorithm  consists of different parts
that you have to assemble to make this scalable RWLock algorithm, and the action and it's speed to assemble those parts constitutes what we call intelligence , so i think a man that is smart is only a machine that is faster and that finds the parts of the algorithm faster and that assemble the final algorithm from those parts faster.


So i think intelligence and also conscience is in fact a faster machine with some data in it that organizes data in a form that is smart, but how life have evolved in a more intelligent and smart form as to be human ? i think it is just a long and dumb process, so to create intelligence and conscience we have first to be inspired by the laws of our mother nature and to create a more faster machines.



Thank you,
Amine Moulay Ramdane. 

[aminer]

Hello,

To support the FIFO fairness inside my RWLock i have
found a solution but unfortunatly this solution
is not optimal, cause i have to use two SemaMonitor objects
on the reader side of my RWLock algorithm, but unfortunatly
since my SemaMonitor is using a FIFO queue, the head and tail of this
FIFO queue is always updated by multiple threads so there values has
to move from a L2 cache to L2 cache so this is expensive and
since it's expensive this will make my RWLock not scalable friendly
so i can not use my SemaMonitor in the reader side and since
i can not use my Semamonitor so i think that bringing FIFO fairness
is too hard or even impossible to realize.


That's sad but it's as it's...

So i will let my scalable RWLock as it's now.



Amine Moulay Ramdane.