信号量与PV操作

on 2019-08-01 | by Jiaqiang's Bolg 关注作者

处理进程同步和互斥的问题，用的最多的是信号量机制。它只能被两个标准的原语 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。

//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。一个被用作一组可用资源的计数器的信号量被称为计数信号量。
如下所示:

/* 信号量 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 的缓冲区。生产者线程反复地生产新的项目，并把它们放入缓冲区中。消费者线程不断地从缓冲区中取出这些项目，然后消费它们。

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

/* 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. 读者优先

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

允许多个读者进程同时读文件只允许一个写者进程写文件任何一个写者进程在完成写操作之前不允许其他读者或写者工作写者执行写操作前，应等待已有的写者或读者全部退出

/*  
* 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. 写者优先

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

/*
* 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. 读写公平

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

/*
* 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。当一名哲学家左右两边的筷子都可用时，才允许他拿起筷子。
代码如下：

/*
* 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 个供等候顾客休息的椅子。若无顾客，理发师则睡眠。顾客到来时唤醒理发师，若理发师正在理发，新来的顾客坐在空闲的休息椅上等候；若没有可供休息的椅子，顾客离开。

/*
* 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操作

用信号量来进行互斥

用信号量来调度共享资源

生产者-消费者问题

读者-写者问题

1. 读者优先

2. 写者优先

3. 读写公平

哲学家就餐问题

睡眠理发师问题

添加我喜欢的博客

编辑我的关注

更多推荐博客

信号量与PV操作

用信号量来进行互斥

用信号量来调度共享资源

生产者-消费者问题

读者-写者问题

1. 读者优先

2. 写者优先

3. 读写公平

哲学家就餐问题

睡眠理发师问题

添加我喜欢的博客

编辑 我的关注

更多 推荐博客

编辑我的关注

更多推荐博客