Mutex

Overview

A mutex is a mechanism used to ensure that different threads correctly access shared data. The code fragment that accesses shared data is called a critical section. A mutex must not be used in any context other than thread context.

When a thread waits for a mutex, the thread is blocked and yields CPU usage. Mutexes have the problem of priority inversion:

Priority Strategy

The XWOS kernel adopts a hybrid strategy of priority ceiling and priority inheritance to solve this problem:

• Threads and mutexes both have priority. They need to specify a static priority at creation time. When a thread holds a mutex, the thread can acquire the mutex’s priority as a dynamic priority. When a mutex is waited on by a thread, the mutex can acquire the thread’s priority as a dynamic priority. The final priority is the larger of the static priority and dynamic priority;
• Suppose thread A has low priority, thread B has medium priority, and thread C has high priority. When thread A already holds the lock, thread C waits for the lock. Thread C’s priority is passed to the lock, and the lock’s priority is then passed to thread A. Thread A’s priority is temporarily raised to match thread C’s priority, so thread A is not preempted by thread B.
• Priority can be inherited infinitely: Suppose thread A has the lowest priority, and the priorities of threads T1, T2, …, Tn increase sequentially. There are mutexes L, M1, M2, …, Mn in the system. Suppose A holds L, T1 holds M1 waiting for L, T2 holds M2 waiting for M1, T3 holds M3 waiting for M2, and so on, with Tn holding Mn waiting for Mn-1. This forms a priority inheritance chain: Tn -> Mn-1 -> Tn-1 -> … -> M3 -> T3 -> M2 -> T2 -> M1 -> T1 -> L -> A. Tn’s priority is propagated sequentially to Mn-1, Tn-1, …, M3, T3, M2, T2, M1, T1, L, A.

Mutex Tree and Real-time Wait Queue

Finding the dynamic priority of mutexes and threads is a problem of finding the maximum value, so a method similar to the Time Tree can be used, solving this problem with a red-black tree. The algorithm with mutexes as nodes and finding the maximum priority is called the mutex tree; the algorithm with threads as nodes and finding the maximum priority is called the real-time wait queue.

• A rightmost pointer pointing to the maximum value allows direct and fast retrieval of the maximum value from rightmost, with a time complexity of O(1);
• When rightmost is removed from the red-black tree, according to the properties of a binary tree, the next rightmost is the left child (i.e., predecessor) of the former. If the predecessor of the former is a leaf, the next rightmost must be the parent node of the former, with an algorithmic time complexity of O(1);
• Removing rightmost is a high-frequency operation in the system, but since rightmost lacks a right subtree, and according to the properties of the red-black tree, the left subtree cannot be too complex either, meaning that the cost of rebalancing the red-black tree after removing rightmost is not too high;
• The insert operation requires traversing the tree, with a time complexity of O(logn);
• Red-black trees do not allow nodes with equal keys, so nodes with the same priority are linked together into a linked list;
• When a mutex is unlocked, the highest priority thread is selected from the wait queue to acquire the mutex. If there is more than one highest priority thread, threads are selected in FIFO order.

Mutex Object and Object Descriptor

The mutex object is a derived class of the XWOS Object struct xwos_object. Similarly, the mutex object also uses the mutex object descriptor xwos_mtx_d to solve the problems of validity and identity verification.

The mutex object descriptor consists of a pointer to the mutex object and a tag:

typedef struct {
        struct xwos_mtx * mtx; /**< Pointer to the mutex object */
        xwsq_t tik; /**< Tag */
} xwos_mtx_d;

When referencing an object through the object descriptor, first check whether the value of obj->magic is 0x58574F53U, which confirms that the pointer obj points to a valid XWOS object. Then compare the tags obj->tik and tik to see if they are equal, which confirms the identity of the object. Because the object’s tik is globally unique, when the object is released, its tik is destructed to 0 by the destructor. When a memory address is reconstructed as a new object, its tik will definitely be inconsistent with the tik in the object descriptor.

Using Mutex

Static Initialization and Destruction of Mutex

• Static initialization: xwos_mtx_init()
  • Static means that the user pre-defines thread structure objects, which are allocated memory by the compiler at compile time.
• Destroy statically initialized mutex: xwos_mtx_fini()

Dynamic Creation and Deletion of Mutex

• Dynamic creation: xwos_mtx_create()
  • Dynamic means that at runtime, the program allocates memory via a memory allocation function and constructs the object on the allocated memory.
• Delete dynamically created mutex: xwos_mtx_delete()

Locking

• xwos_mtx_lock() Wait for and lock the mutex. Can only be used in thread context.
• xwos_mtx_trylock() Try to lock the mutex, will not block the calling thread. Can only be used in thread context.
• xwos_mtx_lock_to() Wait for the mutex with a timeout. Can only be used in thread context.
• xwos_mtx_lock_unintr() Wait for and lock the mutex, and the wait is uninterruptible. Can only be used in thread context.

Unlocking

• xwos_mtx_unlock() Unlock the mutex. Can only be used in thread context.

Getting Lock State

• xwos_mtx_get_status() Get the state of the lock.

Lifecycle Management of Mutex Objects

The base class of the mutex object is the XWOS Object struct xwos_object. The mutex object also has two sets of CAPI for lifecycle management:

• Using object pointer to access lifecycle management CAPI: requires ensuring that the object is definitely valid when calling the CAPI, and that there is no scenario of release-then-allocate as another object.

  • xwos_mtx_grab() : Increase reference count.
  • xwos_mtx_put() : Decrease reference count. When the reference count reaches 0, invoke the garbage collection function to release the object.

• Using object descriptor to access lifecycle management CAPI: used when the user cannot guarantee that the object is definitely valid or cannot guarantee that the object has not become another object.

  • xwos_mtx_acquire() : Confirm the object is valid and legitimate via the object descriptor, then increase reference count.
  • xwos_mtx_release() : Confirm the object is valid and legitimate via the object descriptor, then decrease reference count. When the reference count reaches 0, invoke the garbage collection function to release the object.

CAPI Reference

• Header <xwos/osal/lock/mtx.h>