Locking tutorial

The locking package merely consists of two interfaces for a lock manager and a multilevel lock and specific implementations. There is a generic implementation of a multi level lock with a subtle, yet simple compatibility mechanism. This mechanism allows for implementing quite a number of different lock types such as a read write lock which is provided for covenience. As explained earlier the locking agent can be any Java object. Have a look at the simple method for acquiring a lock for read access as a reference.

If you need a single or pre-determined number of classes the generic or read/write lock is all you need. However, sometimes you may not know how many locks and which locks you will need in advance. In this case you can use the lock manager with its default implementation. The most important method is for either creating a non existing lock in a specified resource or retrieving it if it was created before. It is important to make this atomic so there is no chance of accidently creating more than one lock for a single resource.

The whole trick is to have at most one lock for a resource and have different compatible lock levels for different agents acquiring the lock on that resource.

Example: Fine grained locks in Jakarta Slide

Lets get to the first example which is how Jakarta Slide handles fine grained locking in its WebDAV layer. Slide can store resources in all kinds of stores which most likely will implement their own locks for consistency. However, Slide has generic locking to be certain there are no deadlocks, and the behavior is similar for all stores to provide locking for stores that do not have locks of their own. All locks must be set at the very beginning of a request and released at the end of the request in an atomic block to ban the hazard of deadlocks. Slide does this with a simple synchronized block, but to have something to show here we will exercise it with a multi level lock. Such a lock is very simple and is merely exclusive. It will look like this:

GenericLock exclusive = new new GenericLock("Mutex", 1,
            new PrintWriterLogger(new PrintWriter(System.out), "Locking", false));

Now we have a lock called "Mutex" with a highest lock level of 1 and a logger that simply writes to stdout. Different lock levels and their compatibility is a special feature of GenericLock and is explained there in detail. As we have one locking level, this also is the only level we can possibly acquire causing an exclusive lock:

exclusive.acquire("Owner", 1, true, true, Long.MAX_VALUE);

This tries to acquire a lock of level one (=exclusive) for the agent "Owner". Parameters three and four tell the lock that it should block the current thread if this lock level can not be acquired and that this lock is reentrant. Reentrant means that the same agent can require lock levels that would be otherwise incompatible. Finally, there is a timeout which is the maximum time the agent will wait for a lock. If a lock still is unavailable after this time the method will return false. In our case the request will (practically) never time out; we just wait until we are served.

Now all requests with fine grained locks will be braced with the above statement and the release statement after all fine grained locks are acquired:

exclusive.release("Owner");

As a single agent ("Owner" in our case) can have at most one lock level on a lock - only the highest will be effective - no more than the agent is required as a parameter.

Coming to the fain grained locks: Slide puts read and write locks on resources accessed by WebDAV requests. As we really have no idea which resources will be accessed until we receive the request we use a lock manager which looks like this:

public final static READ_LOCK = 1;
public final static WRITE_LOCK = 2;

LockManager lockManager = new GenericLockManager(WRITE_LOCK,
            new PrintWriterLogger(new PrintWriter(System.out), "Locking", false));

Logs are the same as with the generic lock: they go to stdout. Before explaining more details, let's see how we get a lock from that manager:

GenericLock lock = (GenericLock) lockManager.atomicGetOrCreateLock("/");

This gives us the lock for the resource called "/" which is semantically associated with the root of Slide's resource tree. The highest lock level for the lock has been defined to two using the constant WRITE_LOCK. It is good practice to use constants for the lock levels in order to avoid unreadable code. This returns a lock that could have been created by this statement as well:

GenericLock readWrite = new new GenericLock("/", 2,
            new PrintWriterLogger(new PrintWriter(System.out), "Locking", false));

However, if we ask the lock manager for this lock the next time it will not create a new lock. Instead it will return the lock created first - preserving all lock levels already set. The assertion that all this will be done atomically is very important for correctness and because of this it is reflected in the name of the method.

The locks created by the above lock manager have two levels where the write level is exclusive and the read level is shared. This means if there is a write lock there can be no read locks and the other way round. However, in the absense of a write lock read locks can happily coexist with other read locks - they are shared - while write locks can not coexist with other write locks - they are exclusive. This is very useful for webdav server locks as a there is no reason not to allow two GET requests to the same resource at the same time. However, you should not allow a PUT and a GET request to the same resource at the same time or two PUT requests. This means that none of the below statements will block

readWrite.acquire("request1", READ_LOCK, true, true, Long.MAX_VALUE);
readWrite.acquire("request2", READ_LOCK, true, true, Long.MAX_VALUE);

which would mean two requests called "request1" and "request2" can read the root resource at the same time. Without releasing both of the above locks the following write request will be blocked:

readWrite.acquire("request3", WRITE_LOCK, true, true, Long.MAX_VALUE);

Advanced Example: Mixing fine grained with global locks

In Slide there is a search method that allows you to query for a set of documents that satisfy certain search conditions. When you execute such a query the result documents and indices will be touched with read access. As we learned before we need to acquire all locks on the documents accessed before starting the actual request to guarantee correctness and eliminate the hazard of deadlocks. Of course there is no way to determine which documents this will be beforehand as that would require anticipating the search results. Effectively, we need a global read lock. Now, while there is a global read lock no other request may be allowed to write concurrently. More than one concurrent search request having a global read lock would be no problem, but all requests that write in any way must acquire an exclusive write lock. Easy, one could say, so we have a lock with levels READ and WRITE which is a simple read/write-lock as we have seen above. However, this is not quite adequate as it will demolish our fine grained locking mentioned before: writes would now be globally exclusive again. So, what we want from our lock is that an unrestricted number of search requests - in absence of any write requests - may happen concurrently. Additionally, an unrestricted number of concurrent write requests - in absence of any search requests - should be allowed as well. Sometimes the solution to a problem becomes obvious as soon as you have written it down - like in or case: we need two read/write locks!

Now a search request would try to acquire those locks before it executes:

public final static SHARED_LOCK = 1;
public final static EXCLUSIVE_LOCK = 2;

searchLock.acquire("search request", SHARED_LOCK, true, true, Long.MAX_VALUE);
writeLock.acquire("search request", EXCLUSIVE_LOCK, true, true, Long.MAX_VALUE);

Note that we now call lock level one SHARED and lock level two EXCLUSIVE instead of READ and WRITE as it fits the semantics of these operations better. Any write request will call these statements

writeLock.acquire("write request", SHARED_LOCK, true, true, Long.MAX_VALUE);
searchLock.acquire("write request", EXCLUSIVE_LOCK, true, true, Long.MAX_VALUE);

as the counter part of the above.

That's it, isn't it? No, it is not. You might have already noticed that nothing has been gained. Now all write methods block each other in the searchLock and all search methods block each other in the writeLock! Sigh! This is not what we wanted, we just wanted to disallow any search when writing and any write when searching. The exclusive locks for write and search should have been compatible. This is tough as the compatibility mechanism of the generic lock is based on the order of the levels and the highest simply is exclusive. Adding another lock level to make the formerly highest non-exclusive would only cause a mess as no one would understand anything any more and most important it would still not be compatible to itself. Luckily, next to the additional reentrant compatibility we have already used above there is the so called support compatibility of locks. When acquiring a lock level you can ask the generic lock not to consider lock levels acquired by other locking agents - such as the search method - for compatibility calculation if they have the same lock level you desire. This results in the following code which is the final version:

searchLock.acquire("search request", SHARED_LOCK, true, true, Long.MAX_VALUE);
writeLock.acquire("search request", EXCLUSIVE_LOCK, true, 
            GenericLock.COMPATIBILITY_REENTRANT_AND_SUPPORT, Long.MAX_VALUE);

and

writeLock.acquire("write request", SHARED_LOCK, true, true, Long.MAX_VALUE);
searchLock.acquire("write request", EXCLUSIVE_LOCK, true, 
            GenericLock.COMPATIBILITY_REENTRANT_AND_SUPPORT, Long.MAX_VALUE);

As much for our short round trip. More information about this additional compatibility can be found here. If you still need more turn to the mailing list, go through the Javadocs and as the last resort through the sources ;)