一口Linux

电子技术应用专栏作家——一口Linux。一起学习嵌入式、Linux、网络、驱动、arm知识

带你走进Linux内核源码中最常见的数据结构之「mutex」

0
阅读(434)

1 定义

互斥锁(英语:Mutual exclusion,缩写 Mutex)是一种用于多线程编程中,防止两条线程同时对同一公共资源(比如全域变量)进行读写的机制。

该目的通过将代码切片成一个一个的**临界区域(critical section)**达成。临界区域指的是一块对公共资源进行存取的代码,并非一种机制或是算法。一个程序、进程、线程可以拥有多个临界区域,但是并不一定会应用互斥锁。

例如:一段代码(甲)正在分步修改一块数据。这时,另一条线程(乙)由于一些原因被唤醒。如果乙此时去读取甲正在修改的数据,而甲碰巧还没有完成整个修改过程,这个时候这块数据的状态就处在极大的不确定状态中,读取到的数据当然也是有问题的。更严重的情况是乙也往这块地方写数据,这样的一来,后果将变得不可收拾。因此,多个线程间共享的数据必须被保护。达到这个目的的方法,就是确保同一时间只有一个临界区域处于运行状态,而其他的临界区域,无论是读是写,都必须被挂起并且不能获得运行机会。

互斥锁实现多线程同步的核心思想是:有线程访问进程空间中的公共资源时,该线程执行“加锁”操作(将资源“锁”起来),阻止其它线程访问。访问完成后,该线程负责完成“解锁”操作,将资源让给其它线程。当有多个线程想访问资源时,谁最先完成“加锁”操作,谁就最先访问资源。

当有多个线程想访问“加锁”状态下的公共资源时,它们只能等待资源“解锁”,所有线程会排成一个等待(阻塞)队列。资源解锁后,操作系统会唤醒等待队列中的所有线程,第一个访问资源的线程会率先将资源“锁”起来,其它线程则继续等待。当有多个线程想访问“加锁”状态下的公共资源时,它们只能等待资源“解锁”,所有线程会排成一个等待(阻塞)队列。资源解锁后,操作系统会唤醒等待队列中的所有线程,第一个访问资源的线程会率先将资源“锁”起来,其它线程则继续等待。

image.png

mutex有什么缺点?

不同于mutex最初的设计与目的,现在的struct mutex是内核中最大的锁之一,比如在x86-64上,它差不多有32bytes的大小,而struct samaphore是24bytes,rw_semaphore为40bytes,更大的数据结构意味着占用更多的CPU缓存和更多的内存占用。

什么时候应该使用mutex?

除非mutex的严格语义要求不合适或者临界区域阻止锁的共享,否则相较于其他锁原语来说更倾向于使用mutex

mutex与spinlock的区别?

image.png


spinlock是让一个尝试获取它的线程在一个循环中等待的锁,线程在等待时会一直查看锁的状态。而mutex是一个可以让多个进程轮流分享相同资源的机制
spinlock通常短时间持有,mutex可以长时间持有
spinlock任务在等待锁释放时不可以睡眠,mutex可以
看到一个非常有意思的解释:

spinlock就像是坐在车后座的熊孩子,一直问”到了吗?到了吗?到了吗?…“

mutex就像一个司机返回的信号,说”我们到了!“

2 实现

看一下Linux kernel-5.8是如何实现mutex的2 实现

image.png

可以看到,mutex使用了原子变量owner来追踪锁的状态,owner实际上是指向当前mutex锁拥有者的struct task_struct *指针,所以当锁没有被持有时,owner为NULL。

image.png

上锁

当要获取mutex时,通常有三种路径方式

fastpath:通过 cmpxchg() 当前任务与所有者来尝试原子性的获取锁。这仅适用于无竞争的情况(cmpxchg() 检查 0UL,因此上面的所有 3 个状态位都必须为 0)。如果锁被争用,它会转到下一个可能的路径。
midpath:又名乐观旋转(optimistic spinning)—在锁的持有者正在运行并且没有其他具有更高优先级(need_resched)的任务准备运行时,通过旋转来获取锁。理由是如果锁的所有者正在运行,它很可能很快就会释放锁。mutex spinner使用 MCS 锁排队,因此只有一个spinner可以竞争mutex。
MCS 锁(由 Mellor-Crummey 和 Scott 提出)是一个简单的自旋锁,具有公平的理想属性,每个 cpu 都试图获取在本地变量上旋转的锁,排队采用的是链表实现的FIFO。它避免了常见的test-and-set自旋锁实现引起的昂贵的cacheline bouncing。类似MCS的锁是专门为睡眠锁的乐观旋转而量身定制的(毕竟如果只是短暂的自旋比休眠效率要高)。自定义 MCS 锁的一个重要特性是它具有额外的属性,即当spinner需要重新调度时,它们能够直接退出 MCS 自旋锁队列。这有助于避免需要重新调度的 MCS spinner持续在mutex持有者上自旋,而仅需直接进入慢速路径获取MCS锁。
slowpath:最后的手段,如果仍然无法获得锁,则将任务添加到等待队列并休眠,直到被解锁路径唤醒。在正常情况下它阻塞为 TASK_UNINTERRUPTIBLE。
虽然正式的内核互斥锁是可休眠的锁,但midpath路径 (ii) 使它们更实际地成为混合类型。通过简单地不中断任务并忙于等待几个周期而不是立即休眠,此锁的性能已被视为显着改善了许多工作负载。请注意,此技术也用于 rw 信号量。

具体代码调用链很长…

image.png

尝试上锁

image.png

释放锁

image.png

很显而易见,mutex持有者不为NULL即表示锁定状态。

3 实际案例

实验:

image.png

image.png

我们可以看到一个简单的cnt++,对应

image.png

CPU先将cnt的值读到寄存器eax中,然后将[eax] + 1,最后将eax的值返回到cnt中,这些操作不是**原子性质(atomic)**的,这就导致cnt被多个线程操作时,+1过程会被打断。

加入mutex保护临界资源

image.png

image.png


原文链接:https://mp.weixin.qq.com/s/T_dVFYAYeZ_yE4GAY0K_SA

微信图片_20220701092006.jpg

电子技术应用专栏作家一口Linux


Baidu
map