没有合适的资源?快使用搜索试试~ 我知道了~
首页LINUX内核信号量设计与实现
LINUX内核信号量设计与实现
5星 · 超过95%的资源 需积分: 10 13 下载量 4 浏览量
更新于2023-06-25
评论
收藏 68KB PDF 举报
为了同步对内核共享资源的访问,内核提供了down 函数和up 函数用于获取和释放 资源。down 和up 所保护的访问资源的内核代码区域,就构成一个临界区。在等待 获取资源进入临界区的过程中,代表进程运行的内核控制路径可以睡眠。
资源详情
资源评论
资源推荐
LINUX 内核信号量设计与实现
taoistf just for fun
taoistf@gmail.com
2008/08/18
一 LINUX 内核信号量简介
为了同步对内核共享资源的访问,内核提供了 down 函数和 up 函数用于获取和释放
资源。down 和 up 所保护的访问资源的内核代码区域,就构成一个临界区。在等待
获取资源进入临界区的过程中,代表进程运行的内核控制路径可以睡眠。
我们从 LINUX 内核信号量最直观的设计/实现出发,通过一步步改进,揭示在 x86
平台上完整的信号量设计/实现,然后探讨在不同平台上通用的信号量设计/实现。
二 LINUX 内核信号量的初步设计与实现
1 数据结构
我们首先分析信号量 semphore 应具备的数据结构。它需要一个计数 count,表示能
进入临界区的进程个数。conut 一般初始化为 1,表示信号量是互斥信号量,一次只
允许一个进程进入临界区。它也能被初始化为其他正值,表示可有多个进程同时进
入临界区。
当进程不能进入临界区时,它必须在信号量上睡眠,因此需要一个表示“等待队列头”
的字段 wait。在 SMP 中,等待队列需要自旋锁来保护,因此 wait 结构中应含有自
旋锁 lock,和指向等待队列链表的指针 task_list。而插入等待队列的“等待元素”,其
字段中应含有指向进程结构的指针 task,及能够链入等待队列的指针 task_list。
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
具体表示如下:
struct wait_queue_t{
struct task_struct * task;
struct list_head task_list;
};
/* 等待元素结构 */
struct wait_queue_head_t{
spinlock_t lock;
struct list_head task_list;
};
/* 等待队列头结构 */
struct semphore{
int count;
wait_queue_head_t wait;
}
/* 信号量结构 */
2 算法
当进程需要获取信号量时,它调用down函数进入临界区。down将semphore的count
字段减1,若count非负,则可进入临界区;否则,加入睡眠队列。当进程离开临界
区时,它调用up函数。up将semphore的count字段加1,若count非正,表示有进程睡
眠,则将进程从wait等待队列中移走并唤醒它。
这里有一个问题:当up唤醒等待队列中睡眠进程时,是唤醒所有等待进程,还是只
唤醒一个?如果唤醒所有进程,它们醒来后,就会去竞争一个获得信号量的机会,
竞争失败的进程只能再度睡眠,这就使得系统有许多无谓的schedule切换,降低了系
统性能。所以,up只唤醒一个进程。为了保持FIFO的唤醒顺序,down会将新进程以
独占方式(表示唤醒时只唤醒一个)加在等待队列尾部,up则去唤醒等待队列头部
的第一个独占进程。
3 实现
由于信号量的实现效率与系统性能息息相关,为了达到高效的信号量实现,不同的
cpu系统根据各自特点,提供了不同版本。我们以x86平台为例,介绍信号量的实现
与优化。
我们要注意一点:由于 x86 平台对原子指令有很好的支持,而并发的多个进程可能
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
会同时修改或读取 count 值,所以对 count 的修改与读取都要使用原子指令。为了达
到高效,down 函数与 up 函数都使用汇编语言实现。down 函数特别要保证:进程能
以最快的速度,判断出能否进入临界区。这样才能保证高效的系统性能。
按上述算法,其实现过程是很直接的。
设sem是类型为struct semphore的信号量地址。
down:
movl $sem, %ecx
lock;decl (%ecx);
jns 1f
/* 如非负,则往前跳到标号1处进入临界区 */
/* 调用者堆栈保存约定 */
pushl %eax
pushl %edx
pushl %ecx
call __down
/* 如为负,调用__down加入睡眠队列 */
popl %ecx
popl %edx
popl %eax
1:
void __down(struct semaphore * sem)
{
struct task_struct *tsk = current;
/* 申明“等待元素结构”,并将结构中的进程指针初始化为tsk */
DECLARE_WAITQUEUE(wait, tsk);
tsk->state = TASK_UNINTERRUPTIBLE;
/* 将wait表示的“等待元素”以独占方式加在sem->wait表示的等待队列尾部 */
add_wait_queue_exclusive(&sem->wait, &wait);
schedule();
}
up:
movl $sem, %ecx
lock;incl (%ecx);
jg 1f
/* 如为正,则往前跳到标号1处执行up后第一条指令 */
/* 调用者堆栈保存约定 */
pushl %eax
pushl %edx
pushl %ecx
call __up
/* 如为非正,调用__up唤醒睡眠进程 */
popl %ecx
popl %edx
popl %eax
1:
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
void __up(struct semaphore * sem)
{
/* 在sem->wait表示的等待队列中,获取其第一个“等待元素”wait */
struct wait_queue_t *wait = list_entry(&sem->wait.task_list,struct wait_queue_t ,
task_list);
remove_wait_queue(&sem->wait, &wait);
/* 在等待队列中删除“等待元素” */
wake_up(sem->wait);
/* 唤醒等待队列中的第一个“等待元素”所表示的独占进程 */
}
三 一步步改进信号量的设计与实现
前面提到过,信号量的实现效率与系统性能息息相关。下面,我们围绕如何提高性
能,对上述信号量的设计/实现进行改进。
1 分析上述实现中的性能问题
我们设想这样的情景:当wait等待队列不空时,up出现,它唤醒wait队列的第一个进
程prev。与此同时,有一个进程next(通过内核控制路径)调用down试图进入临界
区。但prev原来调用down试图进入临界区时对count减1,在未能进入临界区而睡眠
时并未恢复,直到prev被唤醒并调度执行进入临界区,而且执行完临界区代码,再
调用up时才会对count增1。所以,进程next只可能在prev之后,进入临界区。也就是
说:进程完全是按照发出down调用的次序,以FIFO方式进入临界区,这非常公平。
但我们要注意一点:当up出现时,说明可有一个进程进入临界区。如果prev的优先
级较低,它被唤醒后,很可能长时间都不能获得调度,在这段时间内,尽管允许进
程进入临界区,而且进程next又试图进入临界区,但任何试图进入临界区的进程发
只能睡眠!
我们从系统性能的角度来考察是否允许next在prev之前进入临界区。对内核信号量的
争用,影响系统性能的关键就是进程上下文切换schedule的代价。如果不允许next
在prev之前进入临界区,则next必须被shedule切换掉。而允许next在prev之前进入临
界区,则prev“至多”再次被shedule。
而在以下两种情形下,prev无须被再次shedule切换掉。
a 在单cpu上,up唤醒prev后,由于进程next在prev之前获得调度运行,prev无须再次
进行shedule切换。
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
剩余18页未读,继续阅读
xushiyan
- 粉丝: 37
- 资源: 16
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2