On our search to improve "publishing of state", we have been drawn to distributed counters, and in particular for this post to the LongAdder. As Pedro as said LongAdder is not sequentially consistent, and the first approach was to apply the ingress/egress technique described in the Numa paper, the LongAdderRWLock. But during our research we discovered a way to use a single LongAdder to publish state, and still guarantee that the RW lock is linearizable.
Again, Pedro gave an example that shows how the sum() function can return an incorrect value, allowing a write to proceed without guaranteeing that all Readers had made the unlock.
After careful thinking, we realized that for this particular RW lock it is possible to give that guarantee, by only making sure that the "rollback" by the Reader is done on the same cell where it was incremented. I know that can be difficult to believe but its true!!! By rollback I mean the section of the code that the read operation runs after realizing that the lock is already acquired in write mode.
The code is very simple, but required a change to the LongAdder class to return the Cell where the increment occurred.
public void sharedLock() {
while (true) {
final LongAdderExt.Cell c = readers.increment();
if (!stampedLock.isWriteLocked()) {
// Acquired
lock in read-only mode
return;
} else {
// Rollback
logical counter to avoid blocking a Writer
if (c == null){
// in case the increment it is not done in a Cell
// but instead on base
readers.getandAddBase(-1);
} else {
c.getAndAdd(-1);
}
// If there
is a Writer, wait until it is gone
while (stampedLock.isWriteLocked())
{
Thread.yield();
}
}
}
}
/**
* Release the read lock.
*/
public void sharedUnlock() {
readers.decrement();
}
/**
* Acquires the write lock.
*/
public void exclusiveLock() {
// Try to acquire
the stampedLock in write-mode
stampedLock.writeLock();
while (true) {
final long egressSum = readers.sum();
if (egressSum == 0) return;
if (egressSum < 0) throw new
IllegalMonitorStateException();
Thread.yield();
}
}
/**
* Release the write lock.
*/
public void exclusiveUnlock()
{
if (!stampedLock.isWriteLocked()) {
// ERROR: tried
to unlock a non write-locked instance
throw new
IllegalMonitorStateException();
}
stampedLock.asWriteLock().unlock();
}
As usual we run our benchmark comparing both solutions, and the results follow.
The last plot shows results with number of threads ranging from 1 to 256, even though our machine has only 32 cores.
The results show that both solutions have similar performance but notice that LongAdderExtRWLock is expected to allocate half the memory of the LongAdderRWLock.
Hello,
ReplyDeleteFinally i have implemented my Distributed Lock, i think it's
good now cause it reduces the cache-coherence traffic and it is
much fair than the Windows critical section.
Description:
A scalable distributed Lock, it is as fast as the Windows critical section but it is much fair than the Windows critical section and the SpinLock with exponential backoff, and it reduces the cache-coherence traffic.
I have not used a Waitfree queue to implement my Scalable Distributed Lock, but you can use a Waitfree queue so that my Scalable Distributed Lock will be more efficient.
I said that my Distributed Lock is much fair than the Windows critical section and much fair than the SpinLock with expoenential backoff,
a proof of that ? just run the test.pas ,test1.pas and test2.pas
inside the zipfile and you will notice it.
You can download my Distributed Lock from:
http://pages.videotron.com/aminer/
Thank you,
Amine Moulay Ramdane.