| 十一月 | ||||||
|---|---|---|---|---|---|---|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
| 27 | 28 | 29 | 30 | 31 | 1 | 2 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
信号量和同步互斥
进程的互斥与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帮忙做了检查，经过了一个小时的讨论，改了一些错误，在此感谢。
有的问题我不是很清楚，希望看了后能提出来大家讨论。