内容简介:说明:本文将分析信号量与读写信号量的机制,开始吧。信号量的实现很简单,先看一下数据结构:
背景
Read the fucking source code! A picture is worth a thousand words.
说明:
- Kernel版本:4.14
- ARM64处理器,Contex-A53,双核
- 使用工具:Source Insight 3.5, Visio
1. 概述
semaphore
本文将分析信号量与读写信号量的机制,开始吧。
2. 信号量
2.1 流程分析
- 可以将信号量比喻成一个盒子,初始化时在盒子里放入N把钥匙,钥匙先到先得,当N把钥匙都被拿走完后,再来拿钥匙的人就需要等待了,只有等到有人将钥匙归还了,等待的人才能拿到钥匙;
信号量的实现很简单,先看一下数据结构:
struct semaphore { raw_spinlock_t lock; //自旋锁,用于count值的互斥访问 unsigned int count; //计数值,能同时允许访问的数量,也就是上文中的N把锁 struct list_head wait_list; //不能立即获取到信号量的访问者,都会加入到等待列表中 }; struct semaphore_waiter { struct list_head list; //用于添加到信号量的等待列表中 struct task_struct *task; //用于指向等待的进程,在实际实现中,指向current bool up; //用于标识是否已经释放 };
流程如下:
-
down
接口用于获取信号量,up
用于释放信号量; - 调用
down
时,如果sem->count > 0
时,也就是盒子里边还有多余的锁,直接自减并返回了,当sem->count == 0
时,表明盒子里边的锁被用完了,当前任务会加入信号量的等待列表中,设置进程的状态,并调用schedule_timeout
来睡眠指定时间,实际上这个时间设置的无限等待,也就是只能等着被唤醒,当前任务才能继续运行; - 调用
up
时,如果等待列表为空,表明没有多余的任务在等待信号量,直接将sem->count
自加即可。如果等待列表非空,表明有任务正在等待信号量,那就需要对等待列表中的第一个任务(等待时间最长)进行唤醒操作,并从等待列表中将需要被唤醒的任务进行删除操作;
2.2 信号量缺点
- 对比下
《Linux Mutex机制分析》
说过的Mutex
,Semaphore
与Mutex
在实现上有一个重大的区别:ownership
。Mutex
被持有后有一个明确的owner
,而Semaphore
并没有owner
,当一个进程阻塞在某个信号量上时,它没法知道自己阻塞在哪个进程(线程)之上; - 没有
ownership
会带来以下几个问题:- 在保护临界区的时候,无法进行优先级反转的处理;
- 系统无法对其进行跟踪断言处理,比如死锁检测等;
- 信号量的调试变得更加麻烦;
因此,在 Mutex
能满足要求的情况下,优先使用 Mutex
。
2.3 其他接口
信号量提供了多种不同的信号量获取的接口,介绍如下:
/* 未获取信号量时,进程轻度睡眠: TASK_INTERRUPTIBLE */ int down_interruptible(struct semaphore *sem) /* 未获取到信号量时,进程中度睡眠: TASK_KILLABLE */ int down_killable(struct semaphore *sem) /* 非等待的方式去获取信号量 */ int down_trylock(struct semaphore *sem) /* 获取信号量,并指定等待时间 */ int down_timeout(struct semaphore *sem, long timeout)
3. 读写信号量
【原创】linux spinlock/rwlock/seqlock原理剖析(基于ARM64) 文章中,我们分析过读写自旋锁,读写信号量的功能类似,它能有效提高并发性,我们先明确下它的特点:
- 允许多个读者同时进入临界区;
- 读者与写者不能同时进入临界区(读者与写者互斥);
- 写者与写者不能同时进入临界区(写者与写者互斥);
3.1 数据结构
读写信号量的数据结构与信号量的结构比较相似:
struct rw_semaphore { atomic_long_t count; //用于表示读写信号量的计数 struct list_head wait_list; //等待列表,用于管理在该信号量上睡眠的任务 raw_spinlock_t wait_lock; //锁,用于保护count值的操作 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* spinner MCS lock */ //MCS锁,参考上一篇文章Mutex中的介绍 /* * Write owner. Used as a speculative check to see * if the owner is running on the cpu. */ struct task_struct *owner; //当写者成功获取锁时,owner会指向锁的持有者 #endif #ifdef CONFIG_DEBUG_LOCK_ALLOC struct lockdep_map dep_map; #endif };
- 最关键的需要看一下
count
字段,掌握了这个字段的处理,才能比较好理解读写信号量的机制; - 【原创】linux spinlock/rwlock/seqlock原理剖析(基于ARM64) 文章中提到过读写自旋锁,读写自旋锁中的
lock
字段,bit[31]用于写锁的标记,bit[30:0]用于读锁的统计,而读写信号量的count
字段也大体类似;
- 以32位的count值为例,高16bit代表的是
waiting part
,低16bit代表的是active part
; -
RWSEM_UNLOCKED_VALUE
:值为0,表示锁未被持有,没有读者也没有写者; -
RWSEM_ACTIVE_BIAS
:值为1,,该值用于定义RWSEM_ACTIVE_READ_BIAS
和RWSEM_ACTIVE_WRITE_BIAS
; -
RWSEM_WAITING_BIAS
:值为-65536,当有任务需要加入到等待列表中时,count值需要加RWSEM_WAITING_BIAS
,有任务需要从等待列表中移除时,count值需要减去RWSEM_WAITING_BIAS
; -
RWSEM_ACTIVE_READ_BIAS
:值为1,当有读者去获取锁的时候,count值将加RWSEM_ACTIVE_READ_BIAS
,释放锁的时候,count值将减去RWSEM_ACTIVE_READ_BIAS
; -
RWSEM_ACTIVE_WRITE_BIAS
,值为-65535,当有写者去获取锁的时候,count值将加RWSEM_ACTIVE_WRITE_BIAS
,释放锁的时候,count值需要减去RWSEM_ACTIVE_WRITE_BIAS
;
在获取释放读锁和写锁的全过程中, count
值伴随着上述这几个宏定义的加减操作,用于标识不同的状态,可以罗列如下:
-
0x0000000X
:活跃的读者和正在申请读锁的读者总共为X
个,没有写者来干扰; -
0x00000000
:没有读者和写者来操作,初始化状态; -
0xFFFF000X
:分为以下几种情况:-
0xFFFF000X = RWSEM_WAITING_BIAS + X * RWSEM_ACTIVE_READ_BIAS
,表示活跃的读者和正在申请读锁的读者总共有X
个,并且还有一个写者在睡眠等待; -
0xFFFF000X = RWSEM_ACTIVE_WRITE_BIAS + (X - 1)* RWSEM_ACTIVE_READ_BIAS
,表示有一个写者在尝试获取锁,活跃的读者和正在申请读锁的读者总共有X-1
个;
-
-
0xFFFF0001
:分为以下几种情况:0xFFFF0001 = RWSEM_ACTIVE_WRITE_BIAS 0xFFFF0001 = RWSEM_ACTIVE_READ_BIAS + RWSEM_WAITING_BIAS
3.1 读信号量
3.1.1 读者获取锁
- 特点:读者与读者可以并发执行,读者与写者互斥执行,因此当有写者持有锁的时候,读者将进入睡眠状态;
- 当
sem->count
加1后还是小于0,代表锁已经被写者持有了,读者获取锁失败,进入rwsem_down_read_failed
函数; - 如果
sem->wait_list
是空时,代表没有任务在等待列表中,首次加入时,sem->count
值需要加上RWSEM_WAITING_BIAS
,表示有任务在等待列表中; - 如果此时
sem->count == RWSEM_WAITING_BIAS
或者count > RWSEM_WAITING_BIAS && adjustment != RWSEM_ACTIVE_READ_BIAS
,表示此时写者将锁释放了,因此需要去唤醒在等待列表中的任务; - 如果写者没有释放锁,那就进入循环,并调用
schedule
让出CPU,直到锁被释放了,那么从代码流程中看,只有!waiter.task
时才会跳出循环,也就是waiter.task == NULL
时,才是获取成功,这个操作是在__rwsem_mark_wake
中通过smp_store_release(&waiter->task, NULL)
实现的; - 在等待获取锁的循环中,需要对信号进行处理,如果对应的等待任务没被唤醒,那么直接跳转到
out_nolock
处,接下来的处理就是一些逆操作了,包括从等待列表中删除,如果是等待列表中的首个任务,还需要减去RWSEM_WAITING_BIAS
等;
总结一下:
读者获取锁的时候,如果没有写者持有,那就可以支持多个读者直接获取;而如果此时写者持有了锁,读者获取失败,它将把自己添加到等待列表中,(这个等待列表中可能已经存放了其他来获取锁的读者或者写者),在将读者真正睡眠等待前,还会再一次判断此时是否有写者释放了该锁,释放了的话,那就需要对睡眠等待在该锁的任务进行唤醒操作了
3.1.2 读者释放锁
- 释放锁的时候
sem->count
值进行减1操作; - 减1操作之后得到的
count
值小于-1,并且active part
是全零,代表等待列表中有写任务在睡眠等待,因此需要进行唤醒操作; - 唤醒操作中,如果有自旋等待的任务,那就可以直接返回了,毕竟人家在自旋呢,又没有睡眠;
- 没有自旋等待任务,那就去唤醒等待列表中的任务了;
3.2 写信号量
3.2.1 写者获取锁
- 写者的特点:看谁都不顺眼,跟谁都互斥,有我没你。只要有一个写者在持有锁,其他的读者与写者都无法获取;
- 在写者获取锁的时候,将
sem->count
值加上RWSEM_ACTIVE_WRITE_BIAS
,如果这个值不等于RWSEM_ACTIVE_WRITE_BIAS
,表示有其他的读者或写者持有锁,因此获取锁失败,调用rwsem_down_write_failed
来处理; - 调用
rwsem_optimistic_spin
进行乐观自旋去尝试获取锁,获取了的话,则直接返回,optimistic spin
可以参考《Linux Mutex机制分析》
文章中的分析,它的作用也是性能的优化,认为锁的持有者会很快释放,因此当前进程选择自旋而不是让出CPU,减少上下文切换带来的开销; - 如果等待列表中有读者任务在睡眠等待,此时假如写者释放了锁,那么需要先将读者任务都给唤醒了;如果等待列表中没有任务,也就意味着当前的写者是第一个任务,因此将
sem->count
值加上RWSEM_WAITING_BIAS
; - 循环等待获取锁,这个过程与
down_read
是类似的;
总结
写者获取锁时,只要锁被其他读者或者写者持有了,则获取锁失败,然后进行失败情况处理。在失败情况下,它本身会尝试进行optimistic spin去尝试获取锁,如果获取成功了,那就是皆大欢喜了,否则还是需要进入慢速路径。慢速路径中去判断等待列表中是否有任务在睡眠等待,并且会再次尝试去查看是否已经有写者释放了锁,写者释放了锁,并且只有读者在睡眠等待,那么此时应该优先让这些先等待的任务唤醒
3.2.2 写者释放锁
sem->owner RWSEM_ACTIVE_WRITE_BIAS
3.3 总结
理解读写信号量有几个关键点:
MCS锁 count
参考
欢迎关注公众号,不定期分享内核机制文章
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Linux信号处理机制
- xenomai内核解析之信号signal(二)---xenomai信号处理机制
- Python内核阅读(二十五):信号处理机制
- OS-操作系统学习笔记-5:进程同步与进程互斥(二):信号量机制
- 树莓派基础-模拟信号和数字信号的区别
- 没信号也可救你命:苹果新专利让iPhone无信号也可充当紧急信标
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
《数据结构》算法实现及解析
高一凡 / 西安电子科技大学出版社 / 2002-10-1 / 35.0
《数据结构算法实现及解析》配有光盘,光盘中包括书中所有程序及用标准C语言改写的程序。所有程序均在计算机上运行通过。《数据结构算法实现及解析》适用于使用教科书的大中专学生和自学者。书中的基本操作函数也可供从事计算机工程与应用工作的科技人员参考和采用。一起来看看 《《数据结构》算法实现及解析》 这本书的介绍吧!