互斥锁

概述

互斥锁是用来保证不同线程正确访问共享数据的机制。访问共享数据的代码片段被称为临界区。 互斥锁 不可 用在 除线程以外 的其他上下文(Context)。

当线程等待互斥锁时，线程会被阻塞，并让出CPU的使用权。 互斥锁存在优先级反转问题：

优先级策略

XWOS内核采取优先级天花板和优先级继承的混会策略解决此问题：

• 线程和互斥锁都拥有优先级，它们在创建时需要指定一个 静态优先级 ， 当线程持有互斥锁时，线程可以获取互斥锁的优先级作为 动态优先级 ， 当互斥锁被线程等待时，互斥锁可以获取线程的优先级作为 动态优先级 ， 最终的优先级取 静态优先级 和 动态优先级 较大的一个；
• 假设线程A优先级低，线程B的优先级中，线程C的优先级高。 线程A已经获得锁的情况下，线程C等待锁。线程C的优先级会传递给锁， 锁的优先级再传递给线程A。线程A的优先级被临时提高至和线程C的优先级一样，线程A不会被线程B抢占。
• 优先级可以无限继承：假设线程A的优先级最低，线程 T1、T2、...、Tn 的优先级依次递增。 系统中有互斥锁 L、M1、M2、...、Mn 。 假设A持有L，T1持有M1去等待L，T2持有M2去等待M1，T3持有M3去等待M2，以此类推，Tn持有Mn去等待Mn-1。 由此形成优先级传递链： Tn->Mn-1->Tn-1->...->M3->T3->M2->T2->M1->T1->L->A ， Tn的优先级将会依次传递到 Mn-1、Tn-1、... 、M3、T3、M2、T2、M1、T1、L、A 。

互斥锁树与实时等待队列

如何寻找互斥锁与线程的 动态优先级 ，是寻找最大值的问题，因此可以采用与 时间树 类似的方法，使用红黑树解决此问题。 节点为互斥锁并查找最大优先级算法被称为 互斥锁树 ；节点为线程并查找最大优先级算法被称为 实时等待队列 。

• 使用一个 rightmost 指针指向最大值，可直接从 rightmost 快速获取最大值，时间复杂度为 O(1) ；
• rightmost 从红黑树中删除时，按照二叉树的性质，下一任 rightmost 是前任的左孩子（即前驱）。 如果前任的前驱为叶子，下一任 rightmost 一定是前任的父节点，算法时间复杂度为 O(1) ；
• 删除 rightmost 在系统中是一个高频次的操作，但由于 rightmost 缺少右子树，根据红黑树性质，左子树也不可能太复杂， 意味着删除 rightmost 后，调整红黑树的代价不会太大；
• 插入操作需要遍历树，时间复杂度为 O(logn) ；
• 红黑树中不允许存在关键字相等的节点，因此拥有相同优先级的节点相互连接成链表；
• 互斥锁解锁时，从等待队列中选择最高优先级的线程获取互斥锁，若最高优先级的线程不止一个，按照先进先出的方法选取线程。

互斥锁对象与对象描述符描述符

互斥锁对象是 XWOS对象 struct xwos_object 的派生类 。 类似的，互斥锁对象也用 互斥锁对象描述符 xwos_mtx_d 来解决有效性和身份合法性的问题。

互斥锁对象描述符由 互斥锁对象的指针 和 标签 组成：

typedef struct {
        struct xwos_mtx * mtx; /**< 互斥锁对象的指针 */
        xwsq_t tik; /**< 标签 */
} xwos_mtx_d;

通过对象描述符引用对象时，首先检测 obj->magic 的值，是否为 0x58574F53U ，由此可确定指针 obj 指向一个有效的 XWOS的对象 。 然后对比标签 obj->tik 和 tik 是否相等，由此可以确定对象的 身份 。 因为对象的 tik 是全局唯一的，当对象被释放后，它的 tik 会被析构函数析构为 0 。 当内存地址被重新构建为新的对象，那么它的 tik 一定与对象描述符的 tik 不一致。

使用互斥锁

静态初始化和销毁互斥锁

• 静态初始化： xwos_mtx_init()
  • 静态 是指用户预先定义线程结构体对象，这些对象在编译期由编译器分配内存。
• 销毁静态初始化的互斥锁： xwos_mtx_fini()

动态创建和删除互斥锁

• 动态创建： xwos_mtx_create()
  • 动态 是指程序在运行时，通过内存分配函数申请内存，并在申请的内存上构造对象。
• 删除动态创建的互斥锁： xwos_mtx_delete()

上锁

• xwos_mtx_lock() 等待并上锁互斥锁，只能在 线程 上下文使用
• xwos_mtx_trylock() 尝试上锁互斥锁，不会阻塞调用线程，只能在 线程 上下文使用
• xwos_mtx_lock_to() 限时等待上锁互斥锁，只能在 线程 上下文使用
• xwos_mtx_lock_unintr() 等待并上锁互斥锁，且等待不可被中断，只能在 线程 上下文使用

解锁

• xwos_mtx_unlock() 解锁互斥锁，只能在 线程 上下文使用

获取锁的状态

• xwos_mtx_get_status() 获取锁的状态

互斥锁对象的生命周期管理

互斥锁对象的基类是 XWOS对象 struct xwos_object 。 互斥锁对象也有两组生命周期管理的CAPI：

• 使用 对象指针 访问生命周期管理的CAPI：需要确保调用CAPI时，对象一定是有效的，且不存在 释放-又被申请 为另一个对象的情况。

  • xwos_mtx_grab() ：增加引用计数。
  • xwos_mtx_put() ：减少引用计数，当引用计数减少为 0 时，调用垃圾回收函数释放对象。

• 使用 对象描述符 访问生命周期管理的CAPI：用户无法确保对象一定有效或无法确保对象不会变成另一个对象时使用。

  • xwos_mtx_acquire() ：通过对象描述符确定对象有效且合法，再增加引用计数。
  • xwos_mtx_release() ：通过对象描述符确定对象有效且合法，再减少引用计数。 当引用计数减少为 0 时，调用垃圾回收函数释放对象。

CAPI参考

• 头文件 <xwos/osal/lock/mtx.h>