信号量与PV操作

处理进程同步和互斥的问题,用的最多的是信号量机制。它只能被两个标准的原语 wait(s) 和 signal(s) 访问,也可记为 P(s) 和 V(s)

  • P(s): 如果 s 是非零的,那么 P 将 s 减 1,并且立即返回。如果 s 为 0,那么就立即挂起这个线程,直到 s 变为非 0,而一个 V 操作会重启这个线程。在重启之后,P 操作将 s 减 1,并将控制返回给调用者。

  • V(s): V 操作将 s 加 1。如果有任何线程阻塞在 P 操作等待 s 变成非零,那么 V 操作会重启这些线程中的一个,然后该线程将 s 减 1,完成它的 P 操作。


用信号量来进行互斥

程序中经常会有一些 共享变量,而它往往会引入同步错误。如下所示 test.c,它创建了两个线程,每个线程都对共享计数变量 cnt 加 1。因为每个线程都对计数器增加了 n 次,所以 cnt 的预计值应该是 2n

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//test.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

void *thread(void *var);

/* 全局共享变量 */
volatile long cnt = 0;

int main(int argc, char **argv)
{
long n;

/* 创建两个线程 */
pthread_t tid1, tid2;

/* 获取数字参数 */
n = atoi(argv[1]);

/* 线程跑起来啦 */
pthread_create(&tid1, NULL, thread, &n);
pthread_create(&tid2, NULL, thread, &n);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);

/* 输出结果 */
if(cnt != (2 * n))
printf("Failed! cnt = %d\n", cnt);
else
printf("Success! cnt = %d\n", cnt);
exit(0);
}

/* 线程函数 */
void *thread(void *var)
{
long i, n = *((long *)var);
for(i = 0; i < n; ++i)
cnt += 1;
return NULL;
}

然而,当我们实际运行该程序时,不仅答案错误,而且每次得到的答案都不同!
如下图所示:
运行结果实际上,我们无法预测操作系统是否为这两个线程选择一个正确的顺序。在这个实例中,这两个线程就很可能是交叉运行的,所以最终输出的 cnt 值不是我们所期望的。

信号量提供了一种很方便的方法来确保对共享变量的互斥访问。基本思想是将每个共享变量与一个信号量 s(初值为 1)联系起来,然后用 P(s) 和 V(s) 操作将相应的临界区包围起来。
以这种方式来保护共享变量的信号量叫做 二元信号量,因为它的值总是 0 和 1。一个被用作一组可用资源的计数器的信号量被称为 计数信号量
如下所示:

1
2
3
4
5
6
7
8
9
/* 信号量 mutex = 1 */
sem_t mutex;
sem_init(&mutex, 0, 1);

for(i = 0; i < n; ++i){
sem_wait(&mutex); /* 相当于 P(mutex) */
cnt += 1;
sem_post(&mutex); /* 相当于 V(mutex) */
}

当我们再次运行这个程序时,它就可以每次都能产生正确的结果了。
成功


用信号量来调度共享资源

生产者-消费者问题

生产者和消费者线程共享一个大小为 n 的缓冲区。生产者线程反复地生产新的项目,并把它们放入缓冲区中。消费者线程不断地从缓冲区中取出这些项目,然后消费它们。

问题分析:因为放入和取出项目都涉及更新共享变量,所以我们必须保证对缓冲区的访问是互斥的。但是只保证互斥访问是不够的,我们还需要调度对缓冲区的访问。如果缓冲区是满的,那么生产者必须等待直到有一个空位可用;如果缓冲区是空的,那么消费者必须等待直到有一个项目可供消费。
伪代码描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* empty 为缓冲区的空位数, full 为可用项目数 */
semaphore mutex = 1, empty = n, full = 0;

producer(){
while(true){
P(empty); /* 看缓冲区中有空位没 */
P(mutex);
放入项目;
V(mutex);
V(full); /* 缓冲区中的项目数加 1 */
}
}

consumer(){
while(true){
P(full); /* 看缓冲区中有项目没 */
P(mutex);
取出项目;
V(mutex);
V(empty); /* 缓冲区的空位数加 1 */
}
}

注意:这里每次对 empty 和 full 变量的 P 操作一定要放在对 mutex 的 P 操作之前,而这里的 V 操作没有先后顺序的问题。原因很显然,如果先 P(mutex) 的话,只要 empty 或 full 为 0,那么程序就极有可能发生死锁。

读者-写者问题

1. 读者优先

一个数据对象(例如一个文件或记录)若被多个并发进程共享,其中读者进程只需要读该数据对象的内容,写者进程则需要修改其内容。
多个读者可以同时访问这个共享数据对象,但是,如果一个写者和任何一个其他的读者或写者同时访问这个数据对象,就有可能导致不确定的访问结果。
要求:

  • 允许多个读者进程同时读文件
  • 只允许一个写者进程写文件
  • 任何一个写者进程在完成写操作之前不允许其他读者或写者工作
  • 写者执行写操作前,应等待已有的写者或读者全部退出
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
31
32
33
/*  
* count 为读者数量,
* rw 为访问文件的互斥信号量
* mutex 为更新 count 的互斥信号量
*/

semaphore mutex = 1, rw = 1;
int count = 0;

writer(){
while(true){
P(rw);
写作;
V(rw);
}
}

reader(){
while(true){
P(mutex);
if(count == 0)
P(rw); /* 一旦有读者,就阻止写者进入 */
count++;
V(mutex);
阅读;
P(mutex);
count--; /* 阅读结束,读者离开 */
if(count == 0) /* count = 0 说明读者全部退出了 */
V(rw); /* 现在可以让给写者写了 */
V(mutex);

}
}

其实从上面的代码中,我们也能看出 读者是优先 的。由于允许多个读者同时进行读操作,在有读者的情况下,假设一个写者到来,因为读者进程还未释放信号量 rw, 所以写者不能访问文件。这样,只要有一个读者还在读文件,随后而来的读者都被允许访问文件,而写者将一直被挂起直到所有读者退出为止。这会使写者发生饥饿现象。

2. 写者优先

当有读进程正在读文件时,若有写进程请求访问,这时应禁止后续读者进程的请求,等到已在共享文件中的读进程执行完毕,立即让给写进程执行,只有在无写进程的情况下才允许读进程再次执行。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
* reader_count 为读者数量
* writer_count 为写者数量
* mutex_rc 为更新 reader_count 的互斥信号量
* mutex_wc 为更新 writer_count 的互斥信号量
* wr 读者进程在此排队
* wsem 为写者互斥信号量
* rsem 为读者 "互斥" 信号量
*/

semaphore mutex_rc = 1, mutex_wc = 1, wr = 1, wsem = 1, rsem = 1;
int reader_count = 0, writer_count = 0;

writer(){
while(true){
P(mutex_wc);
writer_count++;
if(writer == 1) /* 实现写者优先 */
P(rsem); /* 直接抢占 rsem, 此时还有读者在 wr 上排队呢 */
V(mutex_wc);
P(wsem);
写文件;
V(wsem);
P(mutex_wc);
writer_count--;
if(writer_count == 0)
V(rsem); /* 写者退出,读者才可进入 */
V(mutex_wc);
}
}

reader(){
while(true){
P(wr);
P(rsem); /* 让其他读者先在 wr 上排队 */
P(mutex_rc);
reader_count++;
if(reader_count == 1)
P(wsem); /* 只要有读者,就阻塞写者进程 */
V(mutex_rc);
V(rsem); /* 先释放的是 rsem */
V(wr); /* 允许其他读者进程进入 */
读文件;
P(mutex_rc);
reader_count--;
if(reader_count == 0)
V(wsem); /* 读者退出,写者才可进入 */
V(mutex_rc);
}
}

3. 读写公平

读写进程有着相同的优先级。当一个写进程写文件时,若先有一些读进程要求访问文件,后有另一个写进程要求写文件,则当前写进程结束时,会是一个读进程而不是写进程占用文件。(这也是王道书本上所给出的方法)
代码简单易懂,我就不多写注释了。

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
31
32
33
34
35
36
/*
* count 为读者数量
* rw 为访问文件的互斥信号量
* mutex 为更新 count 的互斥信号量
* w 让读进程和写进程在此排队
*/

semaphore rw = 1, mutex = 1, w = 1;
int count = 1;

writer(){
while(true){
P(w); /* 在无读写进程请求时进入 */
P(rw);
写文件;
V(rw);
V(w);
}
}

reader(){
while(true){
P(w); /* 在无读写进程请求时进入 */
P(mutex);
if(count == 0)
P(rw);
count++;
V(mutex);
读文件;
P(mutex);
count--;
if(count == 0)
V(rw);
V(mutex);
}
}

如书本上所说,大部分练习题和真题用消费者-生产者模型或读者-写者问题就能解决,但对于下述的这些问题也要熟悉。毕竟,考研复习的关键在于反复多次和全面

哲学家就餐问题

有 5 个哲学家围坐在一圆桌旁,桌中央有一盘通心,每人面前有一只空盘子,每两个人之间放一只筷子。为了吃面,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左手边和右手边取筷子。
如下图所示:

哲学家就餐问题

分析:哲学家只有拿到两根筷子才可以进餐,进餐完毕后,放下筷子。定义互斥信号量数组 chopstick[5] = {1, 1, 1, 1, 1} 用于对 5 个筷子的互斥访问。哲学家按顺序编号为 0~4,哲学家 i 左边筷子的编号为 i, 右边筷子的编号为 (i+1)%5。当一名哲学家左右两边的筷子都可用时,才允许他拿起筷子。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* mutex 为取筷子的互斥信号量
* chopstick[i] 为对筷子的互斥访问信号量
*/

semaphore mutex = 1;
semaphore chopstick[5] = {1, 1, 1, 1, 1};

Pi(){
do{
P(mutex);
P(chopstick[i]);
P(chopstick[(i+1)%5]);
V(mutex);
吃面;
V(chopstick[i]);
V(chopstick[(i+1)%5]);
}while(true)
}

疑问: 这里,我有一个小小的疑问——为什么要用 do-while 呢?我参考了课本教材以及《现代操作系统》这两本书,书上的确都是这么用的,但是却没给出使用它的理由。按理说,在上面的伪代码中直接使用 while 也没问题啊!很奇怪!

睡眠理发师问题

理发店里有一个理发师,一把理发专用椅子, N 个供等候顾客休息的椅子。若无顾客,理发师则睡眠。顾客到来时唤醒理发师,若理发师正在理发,新来的顾客坐在空闲的休息椅上等候;若没有可供休息的椅子,顾客离开。

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
31
32
33
/*
* wait_count 为等待理发的顾客数
* customer 表示等待理发的顾客, 可以用来阻塞理发师进程
* baber 表示等待顾客的理发师, 可以用来阻塞顾客进程
* mutex 为更新 wait_count 的互斥信号量
*/

semaphore custmoer = 0, baber = 0, mutex = 1;
int wait_count = 0;

baber(){
while(true){
P(custmoer); /* 看有没有顾客 */
P(mutex);
wait_count--;
V(mutex);
给顾客理发;
V(baber); /* 理发结束, 释放理发师 */
}
}

custmoer(){
P(mutex);
if(wait_count < N){ /* 看还有没有空椅子 */
wait_count++;
V(mutex);
V(custmoer); /* 顾客在 custmoer 上等待理发 */
P(baber);
接受理发;
}
else
V(mutex); /* 没空椅子了, 顾客离开 */
}

还有最后一个吸烟者问题,不过我觉得它和书本上那个 “往一个盘子里放苹果和橘子” 的问题很像,都挺简单的,这里就不多赘述了。

推荐阅读: PV操作真题演练

------本文结束感谢您的阅读 ------
0%