1

I have a method which is invoked on object instance by 3 concurrent threads. The lock i am interested is based on value not as object. For example, If two threads (T1,T2) are processing RecordID=123 and T3 is processing RecordID=456. The method should lock only T2 and T3 should proceed with execution.

Currently, i am using Lock but it will lock T2 and T3 both if T1 gets lock.

public void doSomething(String id){
      try {
       lock.lock();
       MyRecord r = find(id);
       ...
       ....
       } finally{
         lock.unlock();
       }
}
gpa
  • 2,411
  • 6
  • 38
  • 68

1 Answers1

9

Solution could be to implement segmented locking based on hash code, similarily to how it is made in ConcurrentHashMap:

int concurrencyLevel = 1 << 8;   // 256 locks
final Lock[] locks = new Lock[concurrencyLevel];
// initialize locks

void doSomething(String id) {
    Lock lock = locks[id.hashCode() & (concurrencyLevel - 1)];  // select one of 256 locks 
    lock.lock();
    try {
        // do some work
    } finally {
        lock.release();
    }
}

Same id values always have the same hash code, so they will use the same lock from the pool.

Alex Salauyou
  • 14,185
  • 5
  • 45
  • 67
  • So `1<<0` is also ok? :) – ZhongYu Oct 21 '15 at 16:16
  • @bayou.io certainly, with `1 << 0` only one lock will be used – Alex Salauyou Oct 21 '15 at 16:19
  • be careful though. a general purpose lock might be occupied for an extended period, therefore it is best to as fine-level as possible. – ZhongYu Oct 21 '15 at 16:25
  • 1
    @bayou.io idea is to initialize all locks before execution, so race condition cannot occur on taking lock from the array--it is always there and is always one for every hashcode remainder. – Alex Salauyou Oct 21 '15 at 16:36
  • I mean you can use coarse-locking in some situations; but not as a general purpose solution. OP probably needs a lock for longer period of time (while processing a record); coarse-locking might be too bad for the throughput. – ZhongYu Oct 21 '15 at 16:41
  • @bayou.io yes, this is definitely the issue: performance will decrease if many collisions occur. But often in such tasks you deal with limited resources (i. e. DB connection pool or thread pool executor), so concurrency level can be adjusted to utilize those resources as effective as possible. – Alex Salauyou Oct 21 '15 at 18:50
  • 2
    Don't forget that hashCode can return negative values. Also, the code above doesn't provide a good distribution. As safer way to do it is: locks[Math.abs(id.hashCode()) % concurrencyLevel] – Slava Imeshev Oct 22 '15 at 07:01
  • @SlavaImeshev when y is power of 2 and x >= 0, `x & (y - 1) = x % y`, when x < 0, it returns `y + (x % y))`. It is common notation to find positive remainder of x divided by y when y is power of 2, based on bit masking. – Alex Salauyou Oct 22 '15 at 07:28