com.bigdata.concurrent
Class NonBlockingLockManager<R extends Comparable<R>>

java.lang.Object
  com.bigdata.concurrent.NonBlockingLockManager<R>

public class NonBlockingLockManager<R extends Comparable<R>>
extends Object

This class coordinates a schedule among concurrent operations requiring exclusive access to shared resources. Whenever possible, the result is a concurrent schedule - that is, operations having non-overlapping lock requirements run concurrently while operations that have lock contentions are queued behind operations that currently have locks on the relevant resources. A ResourceQueue is created for each resource and used to block operations that are awaiting a lock. When locks are not being pre-declared, a WAITS_FOR graph is additionally used to detect deadlocks.

This implementation uses a single AcceptTask thread to accept tasks, update the requests in the ResourceQueues, and in general perform housekeeping for the internal state. Tasks submitted to this class ARE NOT bound to a worker thread until they are executed by the delegate Executor.

Version:

$Id: NonBlockingLockManager.java 4280 2011-03-08 15:06:58Z thompsonbry $

Author:

Bryan Thompson

TODO:

a fair option? What constraints or freedoms would it provide?, a SynchronousQueue for the acceptedTasks?, a SynchronousQueue for the writeService workQueue? FIXME In order to support 2PL we need to decouple the NonBlockingLockManager.LockFutureTask from the transaction with which it is associated. Otherwise each submit(Comparable[], Callable) will look like a new transaction (2PL is impossible unless you can execute multiple tasks for the same transaction).

Perhaps this would be easier if we did not delegate the task to an Executor since that does not really support the 2PL pattern., Support escalation of operation priority based on time and scheduling of higher priority operations. the latter is done by queueing lock requests in front of pending requests for each resource on which an operation attempt to gain a lock. The former is just a dynamic adjustment of the position of the operation in the resource queue where it is awaiting a lock (an operation never awaits more than one lock at a time). This facility could be used to give priority to distributed transactions over local unisolated operations and to priviledge certain operations that have low latency requirements. This is not quite a "real-time" guarentee since the VM is not (normally) providing real-time guarentees and since we are not otherwise attempting to ensure anything except lower latency when compared to other operations awaiting their own locks.

Nested Class Summary

protected static class	NonBlockingLockManager.Counters Counters for the NonBlockingLockManager.
protected class	NonBlockingLockManager.LockFutureTask<T> FutureTask which executes once it holds its locks.
protected class	NonBlockingLockManager.ResourceQueue<T extends NonBlockingLockManager.LockFutureTask<? extends Object>> Unbounded queue of operations waiting to gain an exclusive lock on a resource.
static class	NonBlockingLockManager.RunState Run states for the NonBlockingLockManager.

Field Summary

protected static boolean	DEBUG
protected Executor	delegate Tasks holding their locks are submitted to this service for execution.
protected static boolean	INFO
protected static org.apache.log4j.Logger	log
protected TxDag	waitsFor Used to track dependencies among transactions.

Constructor Summary

NonBlockingLockManager(int maxConcurrency, boolean predeclareLocks, Executor delegate)
Create a lock manager.

Method Summary

CounterSet	getCounters()
boolean	isOpen()
boolean	isShutdown()
boolean	isTerminated()
void	releaseLocksForTask(R[] resource) Release all locks held by the NonBlockingLockManager.LockFutureTask currently holding a lock on the specified resource.
void	shutdown()
void	shutdownNow()
<T> Future<T>	submit(R[] resource, Callable<T> task) Submit a task for execution.
<T> Future<T>	submit(R[] resource, Callable<T> task, TimeUnit unit, long lockTimeout, int maxLockTries)
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

log

protected static final org.apache.log4j.Logger log

INFO

protected static final boolean INFO

DEBUG

protected static final boolean DEBUG

waitsFor

protected final TxDag waitsFor

Used to track dependencies among transactions.

delegate

protected final Executor delegate

Tasks holding their locks are submitted to this service for execution.

Constructor Detail

NonBlockingLockManager

public NonBlockingLockManager(int maxConcurrency,
                              boolean predeclareLocks,
                              Executor delegate)

Create a lock manager. No concurrency limit imposed when predeclareLocks is true as deadlocks are impossible and we do not maintain a WAITS_FOR graph.

Parameters:

maxConcurrency - The maximum multi-programming level (ignored if predeclareLocks is true).

predeclareLocks - When true, operations MUST declare all locks before they begin to execute. This makes possible several efficiencies and by sorting the resources in each lock request into a common order we are able to avoid deadlocks entirely.

delegate - The service on which the tasks will be executed.

Note: The delegate MUST NOT use a bounded queue or cause tasks to be run in the caller's thread. The use of a SynchronousQueue or an unbounded LinkedBlockingQueue for the delegate's workQueue are both acceptable.

Note: If Executor.execute(Runnable) blocks for the delegate then the AcceptTask will also block and this class will be non-responsive until the delegate has accepted each [waitingTask] for execution. Some Executors can cause the task to be run in the caller's thread, which would be the AcceptTask itself and which also has the effect of causing this class to be non-responsive until the task is complete.

Method Detail

releaseLocksForTask

public final void releaseLocksForTask(R[] resource)

Release all locks held by the NonBlockingLockManager.LockFutureTask currently holding a lock on the specified resource.

Parameters:

resource[] - The declared locks for the task. FIXME This is an integration hack for AbstractTask. AbstractTask needs to be able to release the locks as soon as the work of an unisolated task is done (when it is waiting for a group commit) so that other tasks can gain access to the same indices and make it into the same group commit. It is using this method to obtain the NonBlockingLockManager.LockFutureTask and then release its locks.

AbstractTask really needs a refactor.

getCounters

public CounterSet getCounters()

submit

public <T> Future<T> submit(R[] resource,
                            Callable<T> task)

Submit a task for execution. The task will wait until it holds the declared locks. It will then execute. This method is non-blocking. The caller must use FutureTask.get() to await the outcome.

Parameters:

resource - An array of resources whose locks are required to execute the task.

task - The task to be executed.

Throws:

IllegalArgumentException - if resource is null or if any element of that array is null.

IllegalArgumentException - if the task is null.

RejectedExecutionException - if the task can not be queued for execution (including if the service is not running or if a blocking queue was used and the queue is at capacity).

TODO:

add variant for Runnable target., get rid [lockTimeout] since you can do get(timeout) on the Future and the task will be cancelled unless it is complete by the timeout., get rid of [maxLockTries] since you can specify a timeout and that will determine how much effort will be put into attempting to work around a deadlock?

submit

public <T> Future<T> submit(R[] resource,
                            Callable<T> task,
                            TimeUnit unit,
                            long lockTimeout,
                            int maxLockTries)

isOpen

public boolean isOpen()

isShutdown

public boolean isShutdown()

isTerminated

public boolean isTerminated()

shutdown

public void shutdown()

shutdownNow

public void shutdownNow()

toString

public String toString()

Overrides:

toString in class Object