The locklib library

locklib is a library that handles high-level locks on objects. It differs from low-level locking in some important ways:

• Locks are not thread-related.
• It performs significantly slower than low-level locking libraries such as the ones in java.util.concurrent, although this is not a design issue emper se/em, it is a consequence.
• It allows pluggable types of locking system.
• It provides support for hierarchical locking.

Main concepts

locklib is built around three concepts: targets, holders and locks. A target is an object that can be locked. Targets may be arranged hierarchically. A holder is an object that has or is requesting some ownership on a target. A lock is a type of ownership that a holder has on target.

The main principles under which locklib operates are:

• Holders may hold one or more locks in a target.
• Holders may hold locks in multiple targets.
• Multiple holders may hold locks in the same target (although restrictions apply depending on the types of locks).
• Locks may be acquired or released at any time, in any order.
• Requesting a lock may require waiting. The requesting thread may be stopped while waiting for a lock. However, waiting is optional as requests may be asynchronous.
• Holders are not necessarily related to threads. Multiple threads may be requesting locks for the same holder.
• Targets may be organized hierarchically but they must not form cyclic graphs.
• Acquiring a lock in a target may force locks in parent targets to be acquired. This depends on the locking system (see below).
• As far as locklib is concerned, there are no restrictions on when can the target hierarchy be changed, changes do not require any locks to be held and changes do not affect any acquired locks. However, application semantics may require locks to be held but it is up to the user of locklib to decide.

Locking system

locklib was designed to be flexible about the types of locks and their operation. Defining types of locks requires defining a lock data type and a lock policy. locklib comes with two predefined locking systems: mutex locking and SX locking.

A lock data type is an enumeration that defines what types of locks exists. The example below shows the lock data type for the SX locking system:

public enum SxLockType {
        S_LOCK,
        X_LOCK
}

A lock policy is an instance of a class implementing the LockPolicy interface. A policy defines three rules:

• What locks are compatible, meaning, which locks types may be held simultaneously. If lock type A and lock type B are compatible, it means that a holder holding a lock of type A in a target does not block a holder holding a lock of type B on the same object. Note that lock compatibility is always symmetrical and does not apply if the holder is the same: if lock type A is not compatible with lock type C, if a holder has lock A on a target, it can request lock C on the same target and the request will be granted (provided no more incompatible locks exist).

  The following table shows the compatibility table for the mutex system:

  Compatiblity table for the mutex locking system.

  	LOCK
  LOCK	Not allowed

  The following table shows the compatiblity table for the SX system:

  Compatibility table for the SX locking system.

  	S_LOCK	X_LOCK
  S_LOCK	Allowed	Not allowed
  X_LOCK	Not allowed	Not allowed

• What lock is required to hold in the parent of a target to be able to acquire a lock in a target. For example, if target T has parent U and the policy establishes the the parent locking type for lock A is lock B, then requesting a lock of type A in T, a lock of type B in U is acquired first and then the lock A in T is acquired.

  The following table shows the parent locking requirements for the mutex system:

  Parent locking requirement for the mutex locking system.

  Lock requested:	Parent lock requested:
  LOCK	LOCK

  The following table shows the locking requirements for the SX locking system:

  Parent locking requirements for the SX locking system.

  Lock requested:	Parent lock requested:
  S_LOCK	S_LOCK
  X_LOCK	S_LOCK

• Whether starvation is allowed or not. Starvation control will slow down locking by delaying some locks to ensure all lock requests will eventually be handled. When starvation control is activated, new locks are only allowed if there are no locks waiting to be granted. For example, consider the following scenario for the SX locking system where a target has 2 S locks granted to holders H1 and H2 and a third lock, an X lock waiting for holder H3.

  Initial scenario to show starvation.

  Position #	Status	Type	Holder
  1	Granted	S_LOCK	H1
  2	Granted	S_LOCK	H2
  3	Waiting	X_LOCK	H3

  When a fourth request for a S lock for holder H4 arrives, different outcomes occur depending on whether starvation is allowed or not. The S lock is compatible with the current locks so, if starvation is allowed, the lock will be granted immediately as shown in the table below.

  Scenario after H4 requests an S_LOCK with starvation allowed.

  Position #	Status	Type	Holder
  1	Granted	S_LOCK	H1
  2	Granted	S_LOCK	H2
  3	Granted	S_LOCK	H4
  4	Waiting	X_LOCK	H3

  This allows faster response time as H4 does not need to wait but allows starvation because if requests for S locks keep arriving, H3 will never get its X lock. However, if starvation is not allowed, then the request by H4 will be queued and will only be processed after H3 has been granted its X lock, as shown in the table below.

  Scenario after H4 requests an S_LOCK with starvation allowed.

  Position #	Status	Type	Holder
  1	Granted	S_LOCK	H1
  2	Granted	S_LOCK	H2
  3	Waiting	X_LOCK	H3
  4	Waiting	S_LOCK	H4