[infinispan-dev] Semaphore vs Lock

[Dan Berindei]

On Tue, Mar 13, 2012 at 7:39 AM, Manik Surtani <manik at jboss.org> wrote:
>
> On 8 Mar 2012, at 05:42, Dan Berindei wrote:
>
>> On Wed, Mar 7, 2012 at 2:39 PM, Sanne Grinovero <sanne at infinispan.org> wrote:
>>> On 7 March 2012 12:05, Galder Zamarreño <galder.zamarreno at redhat.com> wrote:
>>>> Hi,
>>>>
>>>> I was reading up about Java's Semaphores (http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/Semaphore.html) and a couple of ideas came to my mind:
>>>>
>>>> 1. Wouldn't it make sense to use binary semaphores instead of locks in Infinispan? We're already having to override ReentrantLock in order to have locks owned by Transactions rather than threads. Initially I thought it might make easier for deadlock detection, but not so sure right now cos we're already changing things to avoid thread ownership of locks.
>>>>
>>
>> We don't support most of the Lock operations, so I think it would be
>> fair to remove 'implements Lock' from the OwnableReentrantLock
>> declaration. But we can't remove the reentrant part, as we acquire the
>> lock when we put a value in L1 in DistributionInterceptor - after we
>> have already acquired the lock once in LockInterceptor (that's before
>> we even consider a pessimistic transaction doing multiple puts on the
>> same key).
>>
>> I think a bigger problem is our reliance on AbstractQueuedSynchronizer
>> (used by Semaphore as well, btw), which forces us to use a
>> thread-local internally.
>
> Yes.  I did try and not implement Lock, and pass in the lock owner directly, but a lot of AQS is private or package-protected and as such can only access an "owner" via a thread local.  The other, other way is to completely re-implement AQS, but that (a) is non-trivial and error-prone and (b) would need to access JDK unsafe constructs which will hamper portability.
>

Indeed, reimplementing AQS could be more trouble than it's worth. But
outside of AQS there is very little code that's specific to
ReentrantLock or Semaphore.


>>
>>>> 2. Could lock striping become lock pooling with a simple object pool based on a Semaphore? In theory, we'd avoid the current issue with lock striping where two diff locks hash to the same segment and we have deadlocks. We could use, as the current lock striping logic does, the concurrency level to decide the number of semaphore permits.
>>>
>>
>> Pooling is definitely not free, you'll have extra contention on the
>> pool. But it would be interesting to see how it compares to normal
>> locking, especially with multi-socket machines.
>>
>> BTW, the current striping logic works fine with optimistic
>> transactions, because optimistic transactions always acquire the
>> striped locks in the same order.
>
> Well, lock striping is effectively an Object pool.  Except that the objects being pooled are Locks.  What am I missing here?
>

The way I see it, with a regular object pool, you would take the lock
out of the pool, lock it, put it in the key->lock map, do stuff, then
remove it from the key->lock map, unlock it, and put it back in the
pool.

With lock striping you have a direct mapping from keys to the locks in
the pool, so you can lock and unlock directly, meaning CPU usage will
definitely be lower than either a regular object pool or no pool.
However, since there are fewer locks than keys, it's easy for two
unrelated transactions to contend on the same lock and drive total
throughput down. With pessimistic locks it's even possible for the
transactions to acquire the same locks in a different order (leading
to deadlocks) even when they don't touch any common keys.

>>
>>> Concurrency level -> number of permits ?
>>> I don't get that, the way I'm reading it, it sounds like the more
>>> efficient version would be to remove the semaphore ;)
>>>
>>
>> Actually Galder does mention binary semaphores above, so the number of
>> permits must be fixed at 1. He probably meant concurrency level ==
>> number of semaphores in the pool.
>
> Which is the same as concurrency level setting the number of Locks in the pool, as per current design?  :)
>

The way I understood it, the only difference is that locks will be
(temporarily) assigned to individual keys instead of "stripes" of keys
- eliminating the spurious deadlocks in the current design.

Cheers
Dan