C++ synchronization objects library
Author: Amine Moulay Ramdane
Description:
This library contains 9 synchronization objects, first one is my scalable SeqlockX that is a variant of Seqlock that eliminates the weakness of Seqlock that is "livelock" of the readers when there is more writers, and second is my scalable MLock that is a scalable lock , and third is my SemaMonitor that combines some of the characteristics of a semaphore and all the characteristics of an eventcount and all the characteristics of a windows Manual-reset event and also all the characteristics of a windows Auto-reset event , and if you want the signal(s) to not be lost, you can configure it by passing a parameter to the constructor, and fourth is my scalable DRWLock that is a scalable reader-writer lock that is starvation-free and it does spin-wait, and five is is my scalable DRWLockX that is a scalable reader-writer lock that is starvation-free and it doesn't spin-wait, but it waits on the Event objects and my SemaMonitor, so it is energy efficient, and six is my LW_Fast_RWLockX that is a lightweight scalable Reader-Writer Mutex that uses a technic that looks like Seqlock without looping on the reader side like Seqlock, and this has permited the reader side to be costless, it is FIFO fair on the writer side and FIFO fair on the reader side and it is of course Starvation-free and it does spin-wait, and seven is my Fast_RWLockX, a lightweight scalable Reader-Writer Mutex that uses a technic that looks like Seqlock without looping on the reader side like Seqlock, and this has permited the reader side to be costless, it is FIFO fair on the writer side and FIFO fair on the reader side and it is of course Starvation-free and it does not spin-wait, but waits on my SemaMonitor, so it is energy efficient.
And eight one is a scalable reader-writer lock using scalable counting networks called RWLock_cn, this scalable reader-writer lock is starvation-free and it does spin-wait, and nine one is a scalable reader-writer lock using scalable counting networks called RWLockX_cn, this scalable reader-writer lock is starvation-free and it doesn't spin-wait, but it waits on the Event objects and my SemaMonitor, so it is energy efficient.
If you take a look at the zip file , you will notice that it contains the DLLs Object pascal source codes, to compile those dynamic link libraries source codes you will have to download my SemaMonitor Object pascal source code and my SeqlockX Object pascal source code and my scalable MLock Object pascal source code and my scalable DRWLock Object pascal source code from here:
https://sites.google.com/site/aminer68/
I have compiled and included the 32 bit and 64 bit Windows and Linux Dynamic Link libraries inside the zip file, if you want to compile the dynamic link libraries for OSX on (x86) , please download the source codes of my SemaMonitor and my scalable SeqlockX and my scalable MLock and my scalable DRWLock and compile them yourself.
SemaMonitor is a new and portable synchronization object, SemaMonitor combines some of the characteristics of a semaphore and all the characteristics of an eventcount and all the characteristics of a windows Manual-reset event and also all the characteristics of a windows Auto-reset event , and if you want the signal(s) to not be lost, you can configure it by passing a parameter to the constructor, they only use an event object and and a very fast and very efficient and portable lock, so it is fast and it is FIFO fair and and it is portable to windows,Linux and OSX on x86 architecture, here is its C++ interface:
class SemaMonitor{
public:
SemaMonitor(bool state, long3 InitialCount1=0,long3 MaximumCount1=MaxInt1);
~SemaMonitor();
bool wait(signed long mstime=INFINITE);
void signal();
void signal_all();
bool signal(long1 nbr);
void setSignal();
void resetSignal();
long2 WaitersBlocked();
};
When you set the first parameter of the constructor to true, the signal will not be lost if the threads are not waiting for the SemaMonitor objects, but when you set the first parameter of the constructor to false, if the threads are not waiting for the SemaCondvar or SemaMonitor the signal will be lost..
the parameters InitialCount1 and MaximumCount1 is the semaphore InitialCount and MaximumCount.
The wait() method is for the threads to wait on the SemaMonitor
or SemaCondvar object for the signal to be signaled. If wait() fails, that can be that the number of waiters is greater than the maximum number of an unsigned long, if wait() returns true
that means it has been signaled, if wait() returns false that means it has not been signaled.
and the signal() method will signal one time a waiting thread on the SemaMonitor object.
the signal_all() method will signal all the waiting threads on the SemaMonitor object.
the signal(long2 nbr) method will signal nbr number of waiting threads
the setSignal() and resetSignal() methods behave like the windows Event object's methods that are setEvent() and resetEvent().
and WaitersBlocked() will return the number of waiting threads on
the SemaMonitor object.
As you have noticed my SemaMonitor is a powerful synchronization object.
Please read the readme files inside the zip file to know more about them..
Here is my new invention that is my new algorithm:
I have invented a new algorithm of my scalable Reader-Writer Mutex, and this one is costless on the reader side, this one doesn't use any atomic operations and/or StoreLoad style memory barriers on the reader side, my new algorithm has added a technic that looks like Seqlock, but this technic doesn't loop as Seqlock. Here is my algorithm:
On the reader side we have this:
--
procedure TRWLOCK.RLock(var myid:integer);
var myid1:integer;
id:long;
begin
myid1:=0;
id:=FCount5^.fcount5;
if (id mod 2)=0
then FCount1^[myid1].fcount1:=1
else FCount1^[myid1].fcount1:=2;
if ((FCount3^.fcount3=0) and (id=FCount5^.fcount5) and (FCount1^[myid1].fcount1=1))
then
else
begin
LockedExchangeAdd(nbr^.nbr,1);
if FCount1^[myid1].fcount1=2
then LockedExchangeAdd(FCount1^[myid1].fcount1,-2)
else if FCount1^[myid1].fcount1=1
then LockedExchangeAdd(FCount1^[myid1].fcount1,-1);
event2.wait;
LockedExchangeAdd(FCount1^[myid1].fcount1,1);
LockedExchangeAdd(nbr^.nbr,-1);
end;
end;
--
The writer side will increment FCount5^.fcount5 like does a Seqlock, and the reader side will grap a copy of FCount5^.fcount5 and copy it on the id variable, if (id modulo 2) is equal to zero that means the writer side has not modified yet Fcount3^.fcount3, and the reader side will test again if FCount3^.fcount3 equal 0, and if id=FCount5^.fcount5 didn't change and if FCount1^[myid1].fcount1 that we have assigned before didn't change and that means that we are sure that the writer side will block on FCount1^[myid1].fcount1 equal 1.
And notice with me that i am not looping like in Seqlock.
And the rest of my algorithm is easy to understand.
This technic that looks like Seqlock without looping like Seqlock will allow us to be sure that although the x86 architecture will reorder the loads of the inside reader critical section , the loads inside the reader critical section will not go beyond the load of FCount5^.fcount5 and this will allow my algorithm to work correctly.
My algorithm is FIFO fair on the writer side and FIFO fair on the
Reader side , and of course it is Starvation-free, and it is suitable for realtime critical systems.
My Fast_RWLockX and LW_Fast_RWLockX algorithms work the same.
and you can download the source code of my Fast_RWLockX and LW_Fast_RWLockX algorithms that work the same from here:
https://sites.google.com/site/aminer68/scalable-rwlock
Language: GNU C++ and Visual C++ and C++Builder
Operating Systems: Windows, Linux, Unix and Mac OS X on (x86)
Please click on the small arrow on the right of the zip file below to download...