18. Lock module

18.1. Introduction

.intro: This is the design of the lock module.

.readership: Any MPS developer; anyone porting the MPS to a new platform.

18.2. Background

.need: In an environment where multiple threads are accessing shared data, threads need to cooperate to maintain consistency. Locks provide a simple mechanism for doing this.

.ownership: A lock is an object which may be “owned” by a single thread at a time. By claiming ownership of a lock before executing some piece of code, a thread can guarantee that no other thread owns the lock during execution of that code. If some other thread holds a claim on a lock, the thread trying to claim the lock will suspend until the lock is released by the owning thread.

.data: A simple way of using this behaviour is to associate a lock with a shared data structure. By claiming that lock around accesses to the data, a consistent view of the structure can be seen by the accessing thread. More generally any set of operations which are required to be mutually exclusive may be performed so by using locks.

18.3. Requirements

.req.thread-safety: Support the locking needs of design.mps.thread-safety.

.req.binary: Provide binary locks: that is, locks that can be claimed, and until released, other attempts to claim them block. (This is needed to implement the arena lock.)

.req.recursive: Provide recursive locks: that is, locks that can be claimed again by the thread currently holding them, without blocking or deadlocking. (This is needed to implement the global recursive lock.)

.req.global: Provide global locks: that is locks that need not be allocated or initialized by the user.

.req.global.binary: Provide a global binary lock. (This is required to protect the data structure allowing multiple arenas to coordinate handling of protection faults: see design.mps.thread-safety.arch.global.binary.)

.req.global.recursive: Provide a global recursive lock. (This is required to protect pool class initialization: see design.mps.thread-safety.arch.global.recursive.)

.req.deadlock.not: There is no requirement to provide protection against deadlock. (Clients are able to avoid deadlock using traditional strategies such as ordering of locks; see design.mps.thread-safety.deadlock.)

18.4. Interface

LockStruct *Lock

An opaque type representing a lock. Clients that needs to allocate space for a lock should dynamically allocate space for the structure, calling LockSize() to determine the size.

size_t LockSize(void)

Return the size of a LockStruct for allocation purposes.

void LockInit(Lock lock)

Initialize the lock. This must be called before any use of the lock. After initialization, the lock is not owned by any thread.

void LockFinish(Lock lock)

Finish the lock. The lock must not be owned by any thread.

void LockClaim(Lock lock)

Wait, if necessary, until the lock is not owned by any thread. Then claim ownership of the lock by the current thread.

void LockRelease(Lock lock)

Releases ownership of a lock that is currently owned.

void LockClaimRecursive(Lock lock)

Remembers the previous state of the lock with respect to the current thread and claims the lock (if not already held).

void LockReleaseRecursive(Lock lock)

Restores the previous state of the lock remembered by the corresponding LockClaimRecursive() call.

void LockClaimGlobal(void)

Claims ownership of the binary global lock which was previously not held by current thread.

void LockReleaseGlobal(void)

Releases ownership of the binary global lock that is currently owned.

void LockClaimGlobalRecursive(void)

Remembers the previous state of the recursive global lock with respect to the current thread and claims the lock (if not already held).

void LockReleaseGlobalRecursive(void)

Restores the previous state of the recursive global lock remembered by the corresponding LockClaimGlobalRecursive() call.

18.5. Implementation

.impl.recursive: For recursive claims, the list of previous states can be implemented by keeping a count of the number of claims made by the current thread so far. In the multi-threaded implementations this is handled by the operating system interface, but a count is still kept and used to check correctness.

.impl.recursive.limit: The implementation imposes a limit on the number of recursive claims (see issue.lock-claim-limit). On Windows, the critical section object contains the field LONG RecursionCount. In typical POSIX Threads implementations, pthread_mutex_t uses an int for the count of recursive claims.

.impl.global: The binary and recursive global locks are typically implemented using the same mechanism as normal locks. (But an operating system-specific mechanism is used, if possible, to ensure that the global locks are initialized just once.)

.impl.an: Single-threaded generic implementation lockan.c:

  • single-threaded;

  • no need for locking;

  • locking structure contains count;

  • provides checking in debug version;

  • otherwise does nothing except keep count of claims.

.impl.w3: Windows implementation lockw3.c:

  • supports Windows threads;

  • uses critical section objects [cso];

  • locking structure contains a critical section object;

  • recursive and non-recursive calls use the same Windows function;

  • also performs checking.

.impl.ix: POSIX implementation lockix.c:

  • supports [POSIXThreads];

  • locking structure contains a mutex, initialized to check for recursive locking;

  • locking structure contains a count of the number of active claims;

  • non-recursive locking calls pthread_mutex_lock() and expects success;

  • recursive locking calls pthread_mutex_lock() and expects either success or EDEADLK (indicating a recursive claim);

  • also performs checking.

.impl.li: Linux implementation lockli.c:

  • supports [POSIXThreads];

  • also supports [LinuxThreads], a partial implementation of POSIX Threads that was used in Linux 2.4 and 2.5;

  • almost identical to .impl.posix, except that on LinuxThreads pthread_mutexattr_setkind_np is used where POSIX has pthread_mutexattr_settype.

18.6. Example

.example.init: An example of allocating and initializing a lock:

#include "lock.h"

static Lock lock;

void init()
{
    mps_addr_t p;
    if (mps_alloc(&p, pool, LockSize()) != MPS_RES_OK)
        exit(1);
    lock = p;
    LockInit(lock);
}

.example.binary: An example of using a binary lock:

void binaryUse()
{
    /* lock must not be owned by this thread, or else this deadlocks. */
    LockClaim(lock);
    /* lock is now owned by this thread. */
    /* cannot call binaryUse() at this point. */
    /* only one thread at a time may be at this point. */
    LockRelease(lock);
    /* lock not owned by this thread. */
}

.example.recursive: An example of using a recursive lock:

void recursiveUse()
{
    /* lock may or may not already be owned by this thread. */
    LockClaimRecursive(lock);
    /* lock is now owned by this thread. */
    /* cannot call binaryUse() at this point. */
    /* can call recursiveUse() at this point. */
    /* only one thread at a time may be at this point. */
    LockReleaseRecursive(lock);
    /* lock is still owned by this thread if it was before. */
}

18.7. References

cso

Microsoft Developer Network; “Critical Section Objects”; <http://msdn.microsoft.com/en-us/library/windows/desktop/ms682530.aspx>

LinuxThreads

Xavier Leroy; “The LinuxThreads library”; <http://pauillac.inria.fr/~xleroy/linuxthreads/>

POSIXThreads(1,2)

The Open Group; “The Single UNIX Specification, Version 2—Threads”; <http://pubs.opengroup.org/onlinepubs/7990989775/xsh/threads.html>