‘吉安市人’事人才网：【原创】Linux Mutex机制剖析

admin 科技 2020-05-05 51 0

靠山

Read the fucking source code! --By 鲁迅
A picture is worth a thousand words. --By 高尔基

『说明』：

Kernel（版本）：4.14
ARM64处置器，Contex-A53，双核
使用工具：Source Insight 3.5， Visio

1. 概述

Mutex互斥锁是Linux内核中用于互斥操作的一种同步原语；
“互斥锁是一种休眠锁”，锁争用时可能存在历程的睡眠与叫醒，context的切换带来的价值较高，适用于加锁时间较长的场景；
互斥锁每次只允许一个历程进入临界区[，有点类似于二值信号量；
互斥锁在锁争用时，<在锁被持>有时，选择自选守候，而不立刻举行休眠，可以极大的提高性能，这种机制（optimistic spinning）“也应用到了读写信号量上”；
互斥锁的瑕玷是互斥锁工具的<结构>较大，会占用更多的CPU缓存和内存空间；
与信号量相比，互斥锁的性能与扩展性都更好，因此，在内核中总是会优先思量互斥锁；
互斥锁按为了提高性能，【提供了三条路径处置】：快速路径，中速路径，慢速路径；

前戏都已经讲完了，来看看现实的实现历程吧。

2. optimistic spinning

2.1 MCS锁

上文中提到过Mutex「在实现历程中」，采用了optimistic spinning‘自旋守候机制’，“这个机制的焦点就是基于”MCS【‘锁机制’】来实现的；
MCS【‘锁机制’】是由John Mellor Crummey和Michael Scott在论文中《algorithms for scalable synchronization on shared-memory multiprocessors》提出的，『并以他俩的名字来命名』；
MCS【‘锁机制’】要解决的问题是：“在多”CPU 系统中[，自旋锁都在同一个变量上举行自旋，〖在获取锁时会将包罗锁的〗cache line移动到内陆CPU，这种cache-line bouncing 会很[大水平影响性能；
MCS【‘锁机制’】的焦点头脑：每个CPU都分配一个自旋锁<结构>体，自旋锁的申请者（per-CPU）在local-CPU变量（上自旋），〖这些<结构>体组建成一个链表〗，申请者自旋守候前驱节点释放该锁；
osq(optimistci spinning queue)是基于MCS算法的一个详细实现，并经过了迭代优化；

2.2 osq<流程剖析>

optimistic spinning，乐观自旋，到底有多乐观呢？「当发现」锁被持有时，optimistic spinning信赖持有者很快就能把锁释放，因此它选择自旋守候，而不是“睡眠守候”，这样也就能削[减历程切换带来的开销了。

“看一下”数据<结构>吧：

osq_lock如下：

osq加锁有几种情形：
1. 无人持有锁，『那是最理想的状态』，直接返回；
2. 有人持有锁，将当前的Node【加入到】OSQ（行列）中，在没有高优先级义务抢占时，自旋守候前驱节点释放锁；
3. 自旋守候历程中，若是遇到高优先级义务抢占，那么需要做的事情就是将之前【加入到】OSQ（行列）中的当前节点，从OSQ【（行列）中移除】，移除的历程又分为三个步骤，分别是处置prev前驱节点的next‘指针指向’、当前节点Node的next‘指针指向’、“以及将”prev节点与next『后继节点毗邻』；
加锁历程中使用了原子操作，〖来确保正确性〗；

osq_unlock如下：

（解锁时也分为几种情形）：
1. 无人争用该锁，【那直接】可以释放锁；
2. 获取当前节点指向的下一个节点，若是下一个节点不为NULL，则将下一个节点解锁；
3. 当前节点的下一个节点为NULL，则挪用osq_wait_next，来守候获取下一个节点，并在获取乐成后对下一个节点举行解锁；
从解锁的情形可以看出，这个历程相当于锁的通报，{从上一个节点通报给下一}个节点；

在加锁和解锁的历程中，《由于可能存在操作来更改》osq（行列），因此都挪用了osq_wait_next来获取下一个确定的节点：

3. mutex

3.1 数据<结构>

终于来到了主题了，《先看》一下数据<结构>：

struct mutex {
	atomic_long_t		owner;           //原子计数，用于指向锁持有者的task struct<结构>
	spinlock_t		wait_lock;              //自旋锁，用于wait_list（链表的珍爱操）作
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* Spinner MCS lock */        //osq锁
#endif
	struct list_head	wait_list;          //链表，用于治理所有在该互斥锁上睡眠的历程
#ifdef CONFIG_DEBUG_MUTEXES
	void			*magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map	dep_map;
#endif
};

【在使】用mutex时，（有以下几）点需要注重的：

一次只能有一个历程能持有互斥锁；
只有锁的持有者能举行解锁操作；
克制多次解锁操作[；
克制递归加锁操作；
mutex<结构>只能通过API举行初始化；
mutex<结构>克制通过memset或者拷贝来举行初始化；
已经被持有的mutex锁克制被再次初始化；
mutex不允许在硬件或软件上下文（tasklets, timer）中使用；

3.2 加锁<流程剖析>

从mutex_lock加锁来看一下也许的流程：

mutex_lock为了提高性能，‘分为三种路径处置’，《优先使用快速和中速路径》来处置，若是条件不满足则会跳转到慢速路径来处置，慢速路径中会举行睡眠和调剂，因此开销也是最大的。

3.2.1 fast-path

快速路径是在__mutex_trylock_fast中实现的，该函数的实现也很简单，直接挪用atomic_long_cmpxchg_release(&lock->owner, 0UL, curr)函数来举行判断，若是lock->owner == 0‘解释锁未被持有’，将curr赋值给lock->owner标识curr历程持有该锁，‘并直接返回’；
lock->owner不等于0，解释锁被持有，需要进入下一个路径来处置了；

3.2.2 mid-path

中速路径和慢速路径的处置都是在__mutex_lock_common中实现的；
__mutex_lock_common 的传入参数为[(lock, TASK_INTERRUPTIBLE, 0, NULL, _RET_IP_, false)，该函数中许多路径笼罩不到，接下来的剖析也会剔除掉无效代码；

中速路径的焦点代码如下：

「当发现」mutex锁的持有者正在运行（另一个CPU）时，可以不举行睡眠调剂，而可以选择自选守候，当锁持有者正在运行时，它很有可能很快会释放锁，{这个就是乐观自}旋的缘故原由；
自旋守候的条件是持有锁者正在临界区运行，{自旋守候才有价值}；
__mutex_trylock_or_owner函数用于实验获取锁，若是获取失败则返回锁的持有者。互斥锁的<结构>体中owner字段，分为两个部门：1）锁持有者历程的task_struct（由于L1_CACHE_BYTES【对齐】，低位比特没有使用）；2）MUTEX_FLAGS部门，也就是对应低三位，如下：
1. MUTEX_FLAG_WAITERS：比特0，标识存在非空守候者链表，在解锁的时刻需要执行叫醒操作；
2. MUTEX_FLAG_HANDOFF：比特1，解释解锁的时刻需要将锁通报给顶部的守候者；
3. MUTEX_FLAG_PICKUP：比特2，解释锁的交接准备已经做完了，可以守候被取走了；
mutex_optimistic_spin“用于执行乐观自旋”，理想的情形下锁持有者执行完释放，当前历程就能很快的获取到锁。现实需要思量，若是锁的持[有者若是在临界区被调剂出去了，task_struct->on_cpu == 0，‘那么需要竣事自旋守候了’，否则岂不是傻傻守候了。
1. mutex_can_spin_on_owner：进入自旋前检查一下，若是当前历程需要调剂，或者锁的持有者已经被调剂出去了，那么直接就返回了，不需要做接下来的osq_lock/oqs_unlock工作了，《节约一些分外的》overhead；
2. osq_lock《用于确保只有一个守候者介入进来自旋》，『防』止大量的守候者蜂拥而至来获取互斥锁；
3. for(;;)自旋历程中挪用__mutex_trylock_or_owner（来实验获取锁），获取到后皆大欢喜，直接返回即可；
4. mutex_spin_on_owner，判断不满足自旋守候的条件，那么返回，『让我们进入慢速路径吧』，究竟不能强求；