As a first approach you could consider doing it on the fly and calling toArray() every time exclusiveLock() is called, but this means that you are allocating memory in a code path that is meant to be ran many times and fast. This is a big no-no because it causes the Garbage Collector to trash too much and makes the lock slower. How slow, depends on how good is the GC of the VM you're using, but don't expect that approach to improve performance.
A second approach is to have a reference to an array (lets call it readersStateArrayRef) that is updated whenever a new thread does a read-lock or is terminated, i.e. whenever addState() or removeState() are called. This is also not a good approach because you need to maintain consistency between the CLQ and the array, and for that you need a lock. Apart from the problem of wanting to implement a lock with another lock (which sounds like an infinite recursive loop), there is the issue that removeState() is called from finalize() and having a lock in it may cause other threads to block... or the GC to block? I would say it's not a good idea at all.
There is a third approach which actually works, that Andreia thought of yesterday. The reasons why it works are complex and subtle, and I'll try to enumerate them here, but first lets describe the how .
We start by creating an atomic reference to an array of AtomicInteger (the states of each reader) and a static dummy array just so we have a reference we can differentiate from null and from other valid array references:
private final static AtomicInteger[] dummyArray = new AtomicInteger[0];
private final AtomicReference<AtomicInteger[]> readersStateArrayRef;
Now, we make it so that every change to the CLQ readersStateList is followed by a readersStateArrayRef.set() to null, and in this way mark the array as being out-of-sync with the CLQ. This means that that in addState() and removeState() we need to call readersStateArrayRef.set() after adding or removing from the CLQ.
On the exclusiveLock() function, we check if the readersStateArrayRef is null or not. If it is null, then we need to re-make the array using ConcurrentLinkedQueue.toArray(), and if it is not null then it means it is in-sync with the CLQ and we can use the array to scan the states of the Readers.
We have to check for null only after the writerOwner has been acquired by the current lock, because after that, even if the another thread adds to the CLQ, the state that it adds will always be SRWL_STATE_NOT_READING because it will see that there is a Writer ongoing and not be able to transition to SRWL_STATE_READING (or only temporarily). If the thread is terminating, then there can be a leftover reference to its state (AtomicInteger) on the array, but that's fine because the state will be SRWL_STATE_NOT_READING (worst-case scenario it was set by removeState() ).
This means that it is safe to have temporary inconsistency between the array and the CLQ as long as it happens after the writerOwner have been set... an important an non trivial detail.
We could imagine that something like this would be enough:
// Try to acquire the lock in write-mode
while (!writerOwner.compareAndSet( SRWL_INVALID_TID, tid_self))
Thread.yield();
AtomicInteger[] localReadersStateArray = readersStateArrayRef.get();
if (localReadersStateArray == null) {
// Convert the CLQ to an array
localReadersStateArray =
readersStateList.toArray(new AtomicInteger[readersStateList .size()]);
readersStateList.toArray(new AtomicInteger[readersStateList .size()]);
readersStateArrayRef.set(localReadersStateArray);
}
// Scan the array of Reader states
for (AtomicInteger readerState : localReadersStateArray) {
while (readerState.get() == SRWL_STATE_READING) Thread.yield();
}
but it is not, and in fact, it's wrong!
The reason it doesn't work is because we can have a race condition with a new thread calling addState() after the call to toArray() but before the call of readersStateArrayRef.set(localReadersStateArray), which would not impact the current running exclusiveLock() but it would cause the next call to exclusiveLock() to believe that that readersStateArray was in sync with the CLQ (because it was non-null), when in fact it was out of sync.
This could cause some reader states to be permanently left out of the scan by the writers, which would mean the lock would not be working properly.
The way to overcome this is to use the dummyArray we defined previously, by setting the readersStateArrayRef to the dummyArray before calling CLQ.toArray(), and afterwards doing a compareAndSet() from dummyArray to the newly created array.
If the CAS is successful then the array is in-sync with the CLQ and the next exclusiveLock() will be able to scan only the array.
If the CAS fails, there was another thread calling addState() or removeState() and the CLQ is most likely out-of-sync with the array. This is not an issue for the currently running exclusiveLock() but the next call will see the null and re-make the array by calling again toArray().
In fact, we don't even need to check the outcome of the CAS, but it needs to be a CAS because if the old reference was not dummyArray we can not overwrite it with the reference to the new array, only the next call of exclusiveLock() will be able to do that.
The working code looks like this:
// Try to acquire the lock in write-mode
while (!writerOwner.compareAndSet( SRWL_INVALID_TID, tid_self))
Thread. yield();
AtomicInteger[] localReadersStateArray = readersStateArrayRef.get();
if (localReadersStateArray == null) {
// Set to dummyArray before scanning the readersStateList
readersStateArrayRef.set(dummyArray );
// Copy the CLQ to an array
localReadersStateArray =
readersStateList.toArray(new AtomicInteger[readersStateList.size()]);
readersStateArrayRef.compareAndSet(dummyArray, localReadersStateArray);
}
// Scan the array of Reader states
for (AtomicInteger readerState : localReadersStateArray) {
while (readerState.get() == SRWL_STATE_READING) Thread.yield();
}
This approach can give a 10% to 20% improvement for a large number of Writes (50% and 20% Writes), and has no impact when the number of Writes is low, as is to be expected.
We're going to run a few more tests before adding it to the next release of the Concurrency Freaks Library :)
No comments:
Post a Comment