Skip to main content

Mutual Exclusion In JavaSpaces

Posted by unoinpiu on May 12, 2007 at 12:35 AM PDT


A few months ago I wrote a blog about javaspaces and its (lack of ?) popularity. The blog fuelled an interesting debate.
Yet, some of my concerns remained unanswered. Surely if Javaspaces technology had acquired more popularity by now,
many space based patterns and techniques would have been described over the internet.

Today, I will embark myself in such a task and attempt to describe a fundamental pattern in any space based architecture.
Without it, complex architectures relying on features like clustering, resilience and load-balancing would be even harder to achieve,
unless ofcourse we rely on vendor specific extensions.

Mutual Exclusion in JavaSpaces

The primary means of ensuring mutual exclusion in Java is through a synchronized block.
A synchronized block specifies explicitly an object it locks. Since there is only one lock per object, this prevents any other thread from running until this block completes.

public void test()
{
    ...
    synchronized (myLock)
    {
... // synchronized block
    }
    ...
}

In a space architecture processes coordinate their activities around one or more spaces. In some circumstances there might be some work which should not be executed simultaneously by more than one process. A synchronized block of code obviously would not have any effect on another process running the same code.

One solution is to have one entry in a space which is accessible by each process. When a process needs to perform a "synchronized" task it takes the entry from the space and holds it until its task is completed.

Should another process want to perform the same task (race condition) it would have to wait until the entry is released back into the space.

public void test()
{
    Entry e = space.take(lock, null, Long.MAX_VALUE)
    try
    {
         // synchronized block.
         ...
    }
    finally
    {
        space.write(e, null, Lease.ForEver)
    }
}

Unfortunately this solution does not take into account the possibility that the process which holds the entry might terminate abruptly.
In such a case the other processes would be stuck for ever waiting for an entry. To resolve this problem we need to introduce Transactions.

A process now attempts to take the entry in a transaction. Transactions are leased resources so if the process that aquires the entry suddendly terminates the lease expires and the transaction is automatically aborted. On the other hand once a process performs the critical code it can either explicitly abort the transaction or write back the entry and commit the transaction. Either way the result is the same.

The algorithm just described can be easily captured by a class like the one below (note: you can easily adapt this class, make it implement an interface, modify the signature of its methods and add some more. Remember I am describing a pattern not an API)

public class Gate
{
    /** sets the javaspace where the gate-entries will be read **/
    void setSpace(JavaSpace space) { ... }

    /** sets the transactionManager from where transactions can be created**/
    void setTransactionManager(TransactionManager tm) { ... }

    /** sets a unique identifier for the gate. Implementations will ensure that the given key is used in the template entry **/
    setGateKey(String key) { ... }

    setLeaseDuration(long leaseDuration) { ... }
    setRenewalGap(long renewalGap) { ... }
    ...

    /** enters or blocks this thread until it is possible for this thread to access the gate. (possibly for-ever).
       The implementation will ensure that if the calling thread manages to take the gate-entry it will kick off a thread responsible to renew repeatedly the lease before it expires, until the exit method is invoked **/
         
     void enter();

    /** exits this gate. The implementation will abort/commit the aquired transaction. **/
     void exit();
}

... and so the hypotetical client code then becomes

public void test()
{
    gate.enter();    
     
    // synchronized block.
    ...

    gate.exit();
}

The implementation above has still one potential problem: starvation.

If many processes compete for the same gate-entry it is possible that one process (peraphs running on a slower cpu and/or a slower network connection)
will always be beaten.
You could improve the solution in different ways to enforce fair access to shared resources but you probably don't want to do that. Infact if that is the case it is likely that your distributed architecture has some clear performance bottlenecks, specifically around your multi-process synchronized blocks.

So let's conclude this blog with a simple example of where to use this pattern.

Suppose you have an application A which performs some simple yet critical work against space S. Application A has been identified as SPOF but we can not run two A processes because they would interfere with each other.
The possibility of hardware failure makes any solution based on a script which would restart the application useless.
The solution is to deploy the application A on two (or more ?) machines. However before doing so we modify application A so to implement
the mutual exclusion pattern for the entirety of its process. In this way only one process A will be active and, should the process fail, another one will soon replace it.

Related Topics >>