IS, IX and SIX

Deadlock and IS, IX and SIX
---------------------------
Occasionally, I hit deadlock when developing a database application. Entering the Oracle error code, a page about Oracle lock mode come up: IS, IX and SIX, S, X. Most people recognized S as Share, X as eXclusive. It maps well to Read or Write lock.

LockSet
-------
On other occasions, I developed in memory lock set. Read/write, and even (update lock) are really easy, and I used it as a starting block. On the other hand, maintaining a set is more difficult to do efficiently. The main difficulties lie in obtaining the specified read/write lock struct from the lock set. If the specified lock doesn’t exist, a new struct representing an individual lock needs to add to the lock set. Two threads try to acquire the same lock must resolve to the same struct instance. So, the obtaining of a lock struct from the lock set must be guarded by a semaphore S(t). After a thread obtains the lock from the list, it then tries to acquire the lock. If the thread is acquiring the lock in a mode that conflicts with what has granted to another thread, it waits on the lock. The acquiring is protected by another semaphore S(r) to allow concurrency. In this way, acquiring different the lock will wait on different semaphore. Similarly, when the lock is finished, it go into S(t)again to see if the lock can be removed from the list. Based on this thinking, I developed this algorithm (of course, the actual code look different):

synchornized(lockSet) {
Lock lock = lockSet.get(id);
if (lock==null) {
lock = new Lock();
lockSet.add(lock);
lock.incrementVisitor();
}
}
synchronized(lock) {
lock.acquire(id, mode);
}
synchronized(lockSet) {
lock.decrementVisitor();
boolean free = false;
if (lock.hasNoVisitor())
synchronized(lock) {
free = lock.isFree();
}
}
lockSet.remove(lock);
}

I believe this is working code. However, it takes 4 synchronized blocks to achieve it. This is pretty inefficient: there must be a better way.

Tag: , , ,