PV操作-同步与互斥

浅记学习PV操作的部分题目。

消费者与生产者

单生产者与单消费者

理解PV操作可以从消费者与生产者之间的关系入手。

一个生产者与消费者的情况

消费者想要获取一份商品，需要检查市场中该商品是否有余量：

• 如果剩余商品足够，则获取该商品。
• 如果剩余商品不足，则等待生产者生产该商品，生产后再获取。

消费者获取到商品之后应通知生产者：市场刚刚被消费了一份，出现了空位，你要继续生产。

生产者想要生产一份商品，需要检查市场中是否有空间允许加入新的商品：

• 如果市场没有饱和，存在相关需求，则生产一份商品加入市场。
• 如果市场已经饱和，没有位置插入商品，则等待市场出现空缺，有位置后再生产。

生产者生产出商品之后应通知消费者：刚刚制造了商品，市场出现了余量，你可以来买了。

尝试用代码表示

empty表示生产者当前有多少缓冲区可用。

• 1：有一个缓冲区可用。
• 0：没有缓冲区可用了。
• -1：没有缓冲区可用，同时有一个生产者在排队等待生产。

full表示消费者有多少商品可以使用。

• 1：有一个商品可用。
• 0：没有商品可用。
• -1：没有商品可用，同时有一个消费者在排队等待上架货物。

//生产者进程
while(1){
    //P(empty)
    empty--;//尝试生产一份商品
    if(empty<0)//没地方了，堵塞等待
        sleep(s1.queue);//有地方再生产
    full++;//生产完了，增加一份
    //V(full)
    if(full<=0){//有消费者还在等待
        wake_up(s2.queue);//唤醒消费者
    }
}
//消费者进程
while(1){
    //P(full)
    full--;//尝试消耗一份商品
    if(full<0)//商品不够了，堵塞等待
        sleep(s2.queue);//等着来货
    //V(empty)
    empty++;//有货，消耗一份
    if(empty<=0)//有生产者在堵塞
        wake_up(s1.queue);//唤醒生产者
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

PV操作底层

struct semaphore{
    //记录资源的个数
    int value;
    //记录等待在该信号上的进程
    PCB* queue;
}
P(semaphore S){
    s.value--;
    if(s.value<0)
        sleep(s.queue);
}
V(semaphore S){
    s.value++;
    if(s.value<=0)
        wake_up(s.queue);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

P操作就是信号量-1，如果有余量，允许操作，则继续操作，否则进入等待状态。
V操作就是信号量+1，如果有余量，允许操作，则唤醒一个等待中的进程。

代码表示

如果市场只允许在同一时间执行加入或取出一个操作，那么需要在向市场中添加、取出货物时进行PV操作。
并且初始值为1，表示只有这一个资源，当被一个进程占用时，其他进程将无法访问。

producter(){
    while(True){
        produce an item;
        P(empty);
        P(mutex);
        add item to buffer;
        V(mutex);
        V(full);
    }
}

consumer(){
    while(True){
        P(full);
        P(mutex);
        remove an item from buffer;
        V(mutex);
        V(empty);
        consume the item;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

多消费者与多生产者

dad(){
    while(True){
        prepare an apple;//准备一个苹果
        P(plate);//看看盘子有没有位置
        put an apple;//有的话把苹果放进去
        V(apple);//苹果就绪了
    }
}
daughter(){
    while(True){
        P(apple);//看看此时有没有苹果
        take an apple;//有的话取出苹果
        V(plate);//腾出盘子
        eat the apple;//吃掉苹果
    }
}
mom(){
    while(True){
        prepare an orange;//准备一个橙子
        P(plate);//看看盘子有没有位置
        put an orange;//把橙子放进去
        V(orange);//橙子就绪了
    }
}
son(){
    while(True){
        P(orange);//看看此时有没有橙子
        take an orange;//有的话取出橙子
        V(plate);//腾出盘子
        eat the orange;//吃掉橙子
    }
}
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

读者与写者

有以下需求：

• 允许多个读者同时对文件进行读操作。
• 只允许一个写者往文件写信息。
• 任一写者在完成写操作之前不允许其他读者或写者工作。
• 写者执行写操作之前，应让已有的读者和写者全部退出。

读优先

下面的伪代码存在问题：如果一直有读者请求访问，那么写者可能永远无法获取到资源。

//定义信号量
int count=0;
semaphore mutex=1;
semaphore rw=1;
//读者进程
reader(){
    while (True)
    {
        P(mutex);//请求操作临界资源
        if(count==0)//我是第一个来的
            P(rw);//占用资源
        count++;//访问人数++
        V(mutex);//释放临界资源
        reading...
        P(mutex);//请求操作临界资源
        count--;//我要走了，访问人数--
        if(count==0)//我是最后一个读者
            V(rw);//释放资源
        V(mutex);//释放临界资源
    }
}
writer(){
    while (True)
    {
        P(rw);//请求写操作
        writing...
        V(rw);//释放临界资源
    }
}
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

写优先

通过一个新的信号量w：

• 请求写的时候会申请这部分临界资源，堵塞之后的读写请求。
• 请求读操作时会申请这部分临界资源，并在成功申请后释放这部分资源。
  • 对于当前进程，成功申请则表明没有写进程在访问。读进程申请这部分资源只是为了检测有没有写进程，因此在申请后需要及时释放。
  • 对于后续的读进程，由于之前的读进程在申请到临界资源后会立即释放，因此信号量与申请前相同。不会堵塞后续的读进程。
  • 对于后续的写进程，由于之前的读进程在申请到临界资源后会立即释放，因此能够成功申请。由于写操作在写完之后才释放资源，所以写操作执行时会堵塞后续的读写请求，以避免出现“写者可能永远无法获取到资源”的情况。

// 定义信号量
int count = 0;
semaphore mutex = 1;
semaphore rw = 1;
semaphore w = 1;
// 读者进程
reader()
{
    while (True)
    {
        P(w);
        P(mutex);       // 请求操作临界资源
        if (count == 0) // 我是第一个来的
            P(rw);      // 占用资源
        count++;        // 访问人数++
        V(mutex);       // 释放临界资源
        V(w);
        reading... P(mutex); // 请求操作临界资源
        count--;             // 我要走了，访问人数--
        if (count == 0)      // 我是最后一个读者
            V(rw);           // 释放资源
        V(mutex);            // 释放临界资源
    }
}
writer()
{
    while (True)
    {
        P(w);
        P(rw);            // 请求写操作
        writing... V(rw); // 释放临界资源
        V(w);
    }
}

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

吸烟者问题

互斥隐藏在同步中

semaphore offer1=0,offer2=0,offer3=0,finish=0;
int num=0;
Smoker1(){
    while(True){
        P(offer1);
        抽烟...
        V(finish);
    }
}
Smoker2(){
    while(True){
        P(offer2);
        抽烟...
        V(finish);
    }
}
Smoker3(){
    while(True){
        P(offer3);
        抽烟...
        V(finish);
    }
}
Supplier(){
    while(True){
        //放材料
        P(finish);
        num++;
        num=num%3;
        if(num==0)
            V(offer1);
        else if(num==1)
            V(offer2);
        else
            V(offer3); 
    }
}
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

哲学家吃饭问题

需要信号量mutex，在申请chopstick之前申请信号量mutex，拿取左右筷子视为一次原子操作。
以避免“所有哲学家同时拿到了左筷子，等待右筷子，导致都没有两双筷子”的情况发生。

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;
Philosopher(){
    do{
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        V(mutex);
        eat...
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        think...
    }while(True);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

营业员与顾客

与前面几道不同，这里营业员和顾客方法内，各自P和V的数量是不相等的。
到底是P是V，用不用PV操作，要看实际的需求：

• P可以理解为：申请、占用，本质是-1。
• V可以理解为：释放、唤醒，本质是+1。

semaphore seats = 10;     // 有十个座位的资源信号量
semaphore mutex = 1;      // 取号机互斥的信号量
semaphore haveCustem = 0; // 顾客与营业员同步，无顾客时营业员休息

process 营业员
{
    while (True)
    {
        P(haveCustem); // 有没有顾客需要服务
        叫号...
        为顾客服务...
    }
}
process 顾客
{
    P(seats);                   // 是否有座位
    P(mutex);                   // 申请使用取号机
    从取号机上取号... 
    V(mutex);				 	// 取号完毕
    V(haveCustem);              // 通知营业员有新顾客到来
    等待营业员叫号... V(seats); // 离开座位
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22