Implements an MCS-locking Algorithm. More...

Detailed Description

template<typename ADAPTOR, typename RW_BLOCK>
class foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >

Implements an MCS-locking Algorithm.

Implementation Types: We implemented a few variants of MCS lock algorithm, so this switches the implementation defined below. Individual implementations are defined as individual functions so that we can also test each of them explicitly.

Implementation Type 1: "Simple" (RW_BLOCK = McsRwSimpleBlock): A combination of our MCSg lock and the original RW-MCS lock. This doesn't nicely support cancel, but functionality-wise it works. Cancellable-requests will cause frequent atomic operations in a shared place. Unconditional-requests and try-requests work just fine EXCEPT try-reader, which turns out to require doubly-linked list. For this, we have a meta-method to return whether the impl supports try-reader or not.

Implementation Type 2: "Extended" (RW_BLOCK = McsRwExtendedBlock): A combination of our MCSg lock, the original RW-MCS lock, and cancellable queue lock. This nicely supports cancel, allowing local spinning even for cancallable-requests. This also supports parallel async-lock nicely, but comes with complexity and more atomic instructions.

Lock Mode: foedus::xct::McsWwLock supports only exclusive lock (we call it ww below). foedus::xct::McsRwLock supports reader and writer (we call it rw below). All implementations can handle both types so far.

Lock Request Types

There are 3 lock request types:

Unconditional-lock. Simplest and fastest. When we have no risk of deadlock, this suffices. It always succeds although it might have to wait for long time.
Try-lock. Also simple, but maybe costly per-try. It issues one atomic op to a central place to acquire or fail.
Asynchronous-cancellable-lock. More complex. It allows come-back-later to check whether it acquired lock or not, and to cancel the lock. It must also allow doing this for multiple locks in parallel.

Writer-Upgrade: You might notice that we don't have a so-called upgrade method here to convert a read-lock to a write-lock. We don't need it in our architecture. We always release the read-lock first and take a write-lock using a new queue node. In traditional 2PL, this might violate serializability, but we are not using 2PL. Serializability on the record is always guaranteed by the read-verification. Also, writer-upgrade always has a risk of deadlock, even in a single-lock transaction. By getting rid of it, we make the RLL protocol simpler and more flexible.

References: TBD: original MCS paper and RW version. TBD: link to MCSg paper

Template Parameters

ADAPTOR	A template that implements the McsAdaptorConcept template concept. We explicitly instantiate for all possible ADAPTOR types in cpp.
RW_BLOCK	Queue node object for RW-lock. Either McsRwSimpleBlock or McsRwExtendedBlock. This also defines the implementation.

See also: foedus::xct::McsAdaptorConcept

Definition at line 87 of file xct_mcs_impl.hpp.

#include <xct_mcs_impl.hpp>

Public Member Functions
	McsImpl (ADAPTOR adaptor)

McsBlockIndex	acquire_unconditional_rw_reader (McsRwLock *lock)
	RW-lock methods: BEGIN. More...

McsBlockIndex	acquire_unconditional_rw_writer (McsRwLock *lock)
	[RW] Unconditionally takes a writer lock. More...

McsBlockIndex	acquire_try_rw_reader (McsRwLock *lock)
	Try-acquire. More...

McsBlockIndex	acquire_try_rw_writer (McsRwLock *lock)
	[RW] Try to take a writer lock. More...

AcquireAsyncRet	acquire_async_rw_reader (McsRwLock *lock)
	Async-acquire trios (acquire, cancel, retry) More...

AcquireAsyncRet	acquire_async_rw_writer (McsRwLock *lock)
	[RW] Asynchronously try to take a writer lock. More...

bool	retry_async_rw_reader (McsRwLock *lock, McsBlockIndex block_index)
	[RW] Returns whether the lock requeust is now granted. More...

bool	retry_async_rw_writer (McsRwLock *lock, McsBlockIndex block_index)

void	cancel_async_rw_reader (McsRwLock *lock, McsBlockIndex block_index)
	[RW] Cancels the lock request. More...

void	cancel_async_rw_writer (McsRwLock *lock, McsBlockIndex block_index)

void	release_rw_reader (McsRwLock *lock, McsBlockIndex block_index)
	Release and other stuffs. More...

void	release_rw_writer (McsRwLock *lock, McsBlockIndex block_index)
	[RW] Releases a writer lock. More...

Static Public Member Functions
static bool	does_support_try_rw_reader ()

Constructor & Destructor Documentation

template<typename ADAPTOR, typename RW_BLOCK>

foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::McsImpl ( ADAPTOR adaptor )

inlineexplicit

Definition at line 89 of file xct_mcs_impl.hpp.

89 : adaptor_(adaptor) {}

Member Function Documentation

template<typename ADAPTOR, typename RW_BLOCK>

AcquireAsyncRet foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_async_rw_reader ( McsRwLock * lock )

Async-acquire trios (acquire, cancel, retry)

[RW] Asynchronously try to take a reader lock.

Precondition: the lock must NOT be taken by this thread yet.

template<typename ADAPTOR, typename RW_BLOCK>

AcquireAsyncRet foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_async_rw_writer ( McsRwLock * lock )

[RW] Asynchronously try to take a writer lock.

Precondition: the lock must NOT be taken by this thread yet (even in reader mode).

template<typename ADAPTOR, typename RW_BLOCK>

McsBlockIndex foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_try_rw_reader ( McsRwLock * lock )

Try-acquire.

[RW] Try to take a reader lock.

Precondition: the lock must NOT be taken by this thread yet.

Returns: 0 if failed, the block index if acquired.

See also: does_support_try_rw_reader()

template<typename ADAPTOR, typename RW_BLOCK>

McsBlockIndex foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_try_rw_writer ( McsRwLock * lock )

[RW] Try to take a writer lock.

Precondition: the lock must NOT be taken by this thread yet (even in reader mode).

Returns: 0 if failed, the block index if acquired.

template<typename ADAPTOR, typename RW_BLOCK>

McsBlockIndex foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_unconditional_rw_reader ( McsRwLock * lock )

RW-lock methods: BEGIN.

Unconditional-acquire [RW] Unconditionally takes a reader lock.

template<typename ADAPTOR, typename RW_BLOCK>

McsBlockIndex foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::acquire_unconditional_rw_writer ( McsRwLock * lock )

[RW] Unconditionally takes a writer lock.

template<typename ADAPTOR, typename RW_BLOCK>

void foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::cancel_async_rw_reader	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

[RW] Cancels the lock request.

Precondition: block_index != 0

Note: this works no matter whether the request is no granted or not.

template<typename ADAPTOR, typename RW_BLOCK>

void foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::cancel_async_rw_writer	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

template<typename ADAPTOR, typename RW_BLOCK>

static bool foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::does_support_try_rw_reader ( )

static

Returns: whether this impl supports acquire_try_rw_reader()/retry_async_rw_reader().

See also: acquire_try_rw_reader()

template<typename ADAPTOR, typename RW_BLOCK>

void foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::release_rw_reader	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

Release and other stuffs.

[RW] Releases a reader lock.

Precondition: the lock must be now in reader mode.

template<typename ADAPTOR, typename RW_BLOCK>

void foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::release_rw_writer	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

[RW] Releases a writer lock.

Precondition: the lock must be now in writer mode.

Referenced by foedus::xct::SysxctLockList::release_all_locks().

Here is the caller graph for this function:

template<typename ADAPTOR, typename RW_BLOCK>

bool foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::retry_async_rw_reader	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

[RW] Returns whether the lock requeust is now granted.

Precondition: block_index != 0

Note: this is an instantenous check. Timeout is handled by the caller.

See also: does_support_try_rw_reader()

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_async_rw_reader(), foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_try_rw_reader(), and foedus::xct::McsImpl< ADAPTOR, McsRwExtendedBlock >::cancel_async_rw_reader().

Here is the caller graph for this function:

template<typename ADAPTOR, typename RW_BLOCK>

bool foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >::retry_async_rw_writer	(	McsRwLock *	lock,
		McsBlockIndex	block_index
	)

Referenced by foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_async_rw_writer(), and foedus::xct::McsImpl< ADAPTOR, McsRwSimpleBlock >::acquire_try_rw_writer().

Here is the caller graph for this function:

The documentation for this class was generated from the following file:

/home/shino/foedus_code/foedus-core/include/foedus/xct/xct_mcs_impl.hpp

Detailed Description

template<typename ADAPTOR, typename RW_BLOCK> class foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >

Public Member Functions

Static Public Member Functions

Constructor & Destructor Documentation

Member Function Documentation

template<typename ADAPTOR, typename RW_BLOCK>
class foedus::xct::McsImpl< ADAPTOR, RW_BLOCK >