|
|
信号量和同步互斥 |
|
|
作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站 |
进程的互斥与P、V操作
一、临界资源
什么是临界资源: 任何时候只允许一个进程使用的资源为临界资源。
什么是临界区: 访问临界资源的代码段为临界区。
例如: 代码段1 a = count; a--; count = a; 代码段2 b = count; b++; count = b; 为临界区,count为临界资源。
对临界资源的访问必须满足以下条件: 一次只能有一个进程进入,其他进程等待。 进入者必须在有限时间内退出。 等待者应该有机会进入。
二、信号量
信号量的结构模型:(S,Q) 在2.4.x内核中,信号量数据结构定义为(include/asm/semaphore.h): struct semaphore { atomic_t count; int sleepers; wait_queue_head_t wait; #if WAITQUEUE_DEBUG long __magic; #endif };
信号量操作: 1) 初始化 2) P操作 a) S-- b) if(S < 0) 在Q队列中睡眠 else 进入 3) V操作 a) S++ b) if(S <= 0) 唤醒一睡眠进程(等待队列中有进程在睡眠) else 继续 P操作可以理解为申请资源,V操作可以理解为释放资源,在2.4.x内核semaphore结构中,count是资源计数,为正数或0时表示可用资源数,-1表示没有空闲资源且有等待进程,至于等待进程的数量并不关心,实现中依赖了sleepers,比较复杂,但好处是是up操作非常简单,只需汇编原子地将count加1,如果小于等于0表示有进程等待,调用__up_wakeup() --> __up(),否则返回。linux中的实现可以到arch/i386/kernel/semaphore.c中看到(2.4.x kernel),__down()和__up()。
信号量实现: 用ITRON的一个简单实现<An ITRON Implementation>做为例子。我粗略地看了一下代码,关于信号量(semaphore)的P/V操作,有计数器控制和等待队列。 SEMCB(semaphore control block)结构中有id,队列,计数器等成员。
OS_AcquireSemaphoreTimeOut() { ... lock() semcb->semcnt-- // counter -- if(semcb->semcnt < 0) { make_wait() // make current task in wait state queue_insert_tpri() // insert by priority to the semaphore's //wait queue,which is a circular queue } unlock() ... }
OS_FreeSemaphore() { ... lock() if(semcp->semcnt < 0) { wait_release_ok() | -> wait_release() // release a task from wait state } semcb->semcnt++ // counter ++ unlock() ... } 注:V操作中S先加1再判断是否小于等于0和先判断是否小于0再加1是等价的。 注:在这个实现中,semcnt值不仅正负分别表示资源空闲或有进程等待,其绝对值也是有意义的,为负时值代表等待的进程数,为正或零时值代表空闲的资源数。
三、同步互斥模型
S=1 A P(S) 临界区 V(S)
B P(S) 临界区 V(S)
生产者消费者问题 (生产者计算生成数,消费者打印之。)
1个生产者1个消费者,缓冲buf为1 2个信号量实现模型:put = 1 get = 0 A 计算x P(put) buf = x V(get) B P(get) y = buf V(put) 打印y
1个生产者2个消费者,缓冲buf为1(2个消费者一个打印奇数一个打印偶数) 3个信号量实现模型:put = 1 getj = 0 geto = 0 A 计算x P(put) buf = x if(x为奇) V(getj) else V(geto) B P(getj) y = buf V(put) 打印y C P(geto) y = buf V(put) 打印y 这个模型比较直观,但是用了3个信号量。在计算出x后判断其奇偶再"V"不同的信号量。 如果只使用2个信号量如何实现,生产者计算出x后直接"V"一个信号量,2个消费者取出后判断是否打印还是不于理会。 2个信号量实现模型:put = 1 get = 0 A 计算x P(put) buf = x V(get) B P(get) y = buf } if(y为奇) { V(put) 打印y } else V(get) C P(get) y = buf if(y为偶) { V(put) 打印y } else V(get)
1个生产者1个消费者,缓冲buf为m 2个信号量实现模型:put = m get = 0 A 计算x P(put) buf[t] = x t = (++t) % m V(get) B P(get) y = buf[k] k = (++k) % m V(put) 打印y
N个生产者M个消费者,缓冲buf为m 4个信号量实现模型:put = m get = 0 T = 1 K = 1 A 计算x P(put) P(T) buf[t] = x t = (++t) % m V(T) V(get) B P(get) P(K) y = buf[k] k = (++k) % m V(K) V(put) 打印y
四、删除一个信号量
删除一个信号量,系统应该释放一些资源。如果无进程在等待此信号量,处理比较简单。 如果有进程在等待此信号量,如何处理这些进程,有人说kill,但我看到的一个实现是唤醒。 除进程之外,这个等待队列也需要释放,否则会造成内存泄露。 不仅是删除一个信号量,在系统中当删除某个资源时,会释放等待队列的所有task。
OS_DelFlag --| OS_DelMessageBuffer --|--> call wait_delete(QUEUE *) --> OS_DelSemaphore --|
while() {wait_release();...} // release all tasks blocked on specified wait queue
五、由来
为什么敲打这么个东西。因为有个自主实现的基于ITRON的OS需要测试。在测试其信号量资源时我补充了一个测试用例,即当有进程在等待一个信号量时删除此信号量系统会有如何反应。基于此,先给测试人员做了presentation介绍信号量及同步互斥模型。然后粗略地看了看linux 2.4.x,ITRON和ucLinux三个系统的P/V操作和删除信号量的实现。因工作繁忙没有深入研究,简单整理一下用了两个小时边解bug边偷闲着输入完。然后steedhorse帮忙做了检查,经过了一个小时的讨论,改了一些错误,在此感谢。 有的问题我不是很清楚,希望看了后能提出来大家讨论。
|
|
相关文章:相关软件: |
|