Linux内核源码中最常见的数据结构之【mutex】

↓推荐关注↓

作者：Math X CS

1 定义

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

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

例如：一段代码（甲）正在分步修改一块数据。这时，另一条线程（乙）由于一些原因被唤醒。如果乙此时去读取甲正在修改的数据，而甲碰巧还没有完成整个修改过程，这个时候这块数据的状态就处在极大的不确定状态中，读取到的数据当然也是有问题的。更严重的情况是乙也往这块地方写数据，这样的一来，后果将变得不可收拾。

因此，多个线程间共享的数据必须被保护。达到这个目的的方法，就是确保同一时间只有一个临界区域处于运行状态，而其他的临界区域，无论是读是写，都必须被挂起并且不能获得运行机会。

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

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

mutex有什么缺点？

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

什么时候应该使用mutex？

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

mutex与spinlock的区别？

• spinlock是让一个尝试获取它的线程在一个循环中等待的锁，线程在等待时会一直查看锁的状态。而mutex是一个可以让多个进程轮流分享相同资源的机制

• spinlock通常短时间持有，mutex可以长时间持有

• spinlock任务在等待锁释放时不可以睡眠，mutex可以

看到一个非常有意思的解释：

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

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

2 实现

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

structmutex{

atomic_long_towner;

spinlock_twait_lock;

# ifdefCONFIG_MUTEX_SPIN_ON_OWNER

structoptimistic_spin_queueosq; /* Spinner MCS lock */

# endif

structlist_headwait_list;

# ifdefCONFIG_DEBUG_MUTEXES

void*magic;

# endif

# ifdefCONFIG_DEBUG_LOCK_ALLOC

structlockdep_mapdep_map;

# endif

};

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

/*

* This is the control structure for tasks blocked on mutex,

* which resides on the blocked task's kernel stack:

* 表示等待队列wait_list中进程的结构体

*/

structmutex_waiter{

structlist_headlist;

structtask_struct* task;

structww_acquire_ctx* ww_ctx;

# ifdefCONFIG_DEBUG_MUTEXES

void*magic;

# endif

};

上锁

当要获取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 信号量。

具体代码调用链很长…

/*不可中断的获取锁*/

void__sched mutex_lock(struct mutex *lock)

{

might_sleep;

/*fastpath*/

if(!__mutex_trylock_fast(lock))

/*midpath and slowpath*/

__mutex_lock_slowpath(lock);

}

__mutex_trylock_fast(lock) -> atomic_long_try_cmpxchg_acquire(&lock->owner, &zero, curr) -> atomic64_try_cmpxchg_acquire(v, (s64 *)old, new);

__mutex_lock_slowpath(lock)->__mutex_lock(lock, TASK_UNINTERRUPTIBLE, 0, NULL, _RET_IP_) -> __mutex_lock_common(lock, state, subclass, nest_lock, ip, NULL, false)

/*可中断的获取锁*/

intmutex_lock_interruptible(struct mutex *lock);

尝试上锁

int__sched mutex_trylock(struct mutex *lock)

{

boollocked;

# ifdefCONFIG_DEBUG_MUTEXES

DEBUG_LOCKS_WARN_ON(lock->magic != lock);

# endif

locked = __mutex_trylock(lock);

if(locked)

mutex_acquire(&lock->dep_map, 0, 1, _RET_IP_);

returnlocked;

}

staticinlinebool__mutex_trylock(struct mutex *lock)

{

return!__mutex_trylock_or_owner(lock);

}

释放锁

void__sched mutex_unlock(struct mutex *lock)

{

# ifndefCONFIG_DEBUG_LOCK_ALLOC

if(__mutex_unlock_fast(lock))

return;

# endif

__mutex_unlock_slowpath(lock, _RET_IP_);

}

跟加锁对称，也有fastpath, midpath, slowpath三条路径。

判断锁状态

boolmutex_is_locked(struct mutex *lock)

{

return__mutex_owner(lock) != NULL;

}

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

3 实际案例

实验：

# include<pthread.h>

# include<stdio.h>

# defineLOOP 1000000

intcnt = 0;

intcs1 = 0, cs2 = 0;

void* task( void* args) {

while( 1)

{

if(cnt >= LOOP)

{

break;

}

cnt++;

if(( int)args == 1) cs1 ++; elsecs2++;

}

returnNULL;

}

intmain{

pthread_ttid1;

pthread_ttid2;

/* create the thread */

pthread_create(&tid1, NULL, task, ( void*) 1);

pthread_create(&tid2, NULL, task, ( void*) 2);

/* wait for thread to exit */

pthread_join(tid1, NULL);

pthread_join(tid2, NULL);

printf( "cnt = %d cs1=%d cs2=%d total=%d\n", cnt,cs1,cs2,cs1+cs2);

return0;

}

输出：

cnt = 1000000cs1= 958560cs2= 1520226total= 2478786

$> g++ -E test.c -o test.i

$> g++ -S test.i -o test.s

$> vim test.s

.file "test.c"

.globl _cnt

.bss

.align 4

_cnt:

.space 4

.text

.globl __Z5task1Pv

.def __Z5task1Pv; .scl 2; .type 32; .endef

__Z5task1Pv:

...

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

movl _cnt, %eax

addl $1, %eax

movl %eax, _cnt

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

加入mutex保护临界资源

# include<pthread.h>

# include<stdio.h>

# defineLOOP 1000000

pthread_mutex_tmutex;

intcnt = 0;

intcs1 = 0, cs2 = 0;

void* task( void* args) {

while( 1)

{

pthread_mutex_lock(&mutex);

if(cnt >= LOOP)

{

pthread_mutex_unlock(&mutex);

break;

}

cnt++;

pthread_mutex_unlock(&mutex);

if(( int)args == 1) cs1 ++; elsecs2++;

}

returnNULL;

}

intmain{

pthread_mutex_init(&mutex , NULL);

pthread_ttid1;

pthread_ttid2;

/* create the thread */

pthread_create(&tid1, NULL, task, ( void*) 1);

pthread_create(&tid2, NULL, task, ( void*) 2);

/* wait for thread to exit */

pthread_join(tid1, NULL);

pthread_join(tid2, NULL);

printf( "cnt = %d cs1=%d cs2=%d total=%d\n", cnt,cs1,cs2,cs1+cs2);

return0;

}

输出：

cnt = 1000000cs1= 517007cs2= 482993total= 1000000

结果正确

- EOF -

加主页君微信，不仅Linux技能+1

主页君日常还会在个人微信分享 Linux相关工具、资源和 精选技术文章，不定期分享一些 有意思的活动、 岗位内推以及 如何用技术做业余项目

加个微信，打开一扇窗

点击标题可跳转

1、 Linux 6.0 正式发布

2、 Linux 管道到底能有多快？

3、 Linus Torvalds：Rust 将被合并到 Linux 6.1 主线

看完本文有收获？请分享给更多人

推荐关注「Linux 爱好者」，提升Linux技能

点赞和在看就是最大的支持❤️