408王道操作系统强化——PV大题解构

目录

1.解题思路

2.生产者 - 消费者

3.理发师

4.读者 - 写者问题

5.哲学家进餐

6.读者 - 写者（写优先）

7.读者 - 写者（读写公平）

---

1.解题思路

1.确定函数的个数：梳理题目中有几个进程，一个进程对应一个函数（根据动作是否一致区分是否为统一进程）

2.确定函数的动作：

①动作是什么：在函数内部，用中文描述动作（允许用中文的伪代码形式答题）

②动作的次数：只做一次（不加while）还是重复进行（while循环）

3.确定函数是否在每个动作之前需要进行P操作：如果需要进行P操作，则一定有与之对应的V操作；需要思考这个V操作应该被放在哪进行

①消耗资源型的P操作：题目一般会显性给出，例如每次动作需要消耗一个缓冲区空间（P操作减少缓冲区空间，V操作增加缓冲区空间，缓冲区无空间时无法进行动作）

②互斥型的P操作：需要注意隐含的互斥关系，例如缓冲区的互斥访问

4.确定信号量的个数：所有PV操作定义完成后，再确定信号量的个数

5.检查是否发生死锁：连续进行多个P操作的地方是否会发生死锁（只有一个P操作不会发生死锁）

①某信号量的PV连续出现（中间没有夹杂别的P操作），则不会发生死锁：不发生请求和保持

//不夹杂其余P操作
P(mutex);
动作;
V(mutex);
 
//夹杂其余P操作
P(mutex);
P(full);
动作;
V(empty);
V(mutex;

②连续多个P导致的死锁可尝试调整P顺序解决

2.生产者 - 消费者

 1.确定函数的个数（3）：生产车间A和生产车间B虽然都是生产车间，但是它们俩执行的动作不一致，故不是同一个进程，即生产车间A和生产车间B需要对应不同的函数；进程 = 生产车间A（P1） + 生产车间B（P2） + 装配车间（C）

2.确定函数的动作：

①动作是什么：

P1和P2分别生产A、B两种零件，并将分别把它们送到货架F1、F2上

C从货架上分别取出A、B后，组装成A + B

②动作的次数：P1、P2和C都是不断重复 → while

3.确定函数是否在每个动作之前需要进行P操作：

①P1生产A零件之前不需要消耗资源

P1将A放到F1前需要消耗1个F1货架（A缓冲区）的剩余容量 → C从F1上取A后会释放1个F1货架的剩余容量

②P2生产B零件之前不需要消耗资源

P2将B放到F2前需要消耗1个F2货架（B缓冲区）的剩余容量 → C从F2上取B后会释放1个F2货架的剩余容量

③C从F1取A前需要消耗1个F1货架上的A产品 → P1把A放到F1后释放1个F1货架上的A产品

C从F2取B前需要消耗1个F2货架上的B产品 → P2把B放到F2后释放1个F2货架上的B产品

C组装成A+B前不需要消耗资源

④P1和C对F1的访问是互斥的（mutex1）；P2和C对F2的访问是互斥的（mutex2）

4.确定信号量的个数：F1 = F2 = 10，full1 = full2 = 0，mutex1 = mutex2 = 1

5.检查是否发生死锁：先P同步信号量（F1、F2、full1、full2），再P互斥信号量(mutex1、mutex2）

---

1.确定函数的个数（2）：老和尚喝水，小和尚取水

2.确定函数的动作：

①动作是什么：

老和尚从缸中打水、喝水

小和尚从井中打水、放水

 ②动作的次数：不断进行 → while

3.确定函数是否在每个动作之前需要进行P操作：

①老和尚打水前消耗1个桶 → 老和尚喝水后增加1个桶

老和尚喝水前消耗1个水缸里的水 → 小和尚打水后增加1个水缸里的水

②小和尚打水前消耗1个桶 → 小和尚放水后增加1个桶

小和尚打水前消耗1个水缸的剩余容量 → 老和尚喝水后增加1个水缸的剩余容量

③小和尚之间对井的访问是互斥的（mutex1）；老和尚间和小和尚间、老和尚和小和尚对水缸的访问是互斥的（mutex2）

4.确定信号量的个数：互斥访问信号量为1，其余为资源数量

5.检查是否发生死锁：

①如果老和尚和小和尚都是先对tong进行P操作（先进行取水桶操作），则可能发生：三个老和尚同时取水，并取得水桶（此时完成了三个P(tong)，则tong = 0），但是水缸中没有水（full = 0），即老和尚进程被阻塞在P（full）；而若干个小和尚想去打水，水桶却被取光（tong = 0），即小和尚进城被阻塞在P(tong)，这样就形成了死锁

②同理，也可能发生三个小和尚分别拿着桶，而水缸中水满（empty = 0），被阻塞在P（empty）；而老和尚苦于没有水桶，被阻塞在P（tong）

解决方法：调整老和尚进程和小和尚进程的取桶顺序

老和尚先判断水缸中有没有水，水缸有水的情况下才去取桶喝水，即先P（full）再P（tong）

小和尚先判断水缸中有没有剩余容量，水缸中有剩余容量的情况下才去取桶打水，即先（empty）再P（tong）

---

 

1.确定函数的个数（2）：所有生产者动作一致，故所有生产者视为一类进程；所有消费者动作一致，故所有消费者视为一类进程

2.确定函数的动作：

①动作是什么：

P生产产品，并将产品放入缓冲区

C从缓冲区取10个产品

②动作的次数：P和C都是不断重复 → while

3.确定函数是否在每个动作之前需要进行P操作：

①P生产产品前不需要消耗资源

P将产品放入缓冲区前需要消耗1个缓冲区剩余容量 → C从缓冲区取10个产品后增加10个缓冲区剩余容量（每取出1个产品，增加1个缓冲区容量，通过for循环实现）

②C从缓冲区取10个产品前需要消耗10个缓冲区产品数量（for循环实现） → P将产品放入缓冲区后增加1个缓冲区产品数量

③P和C对缓冲区的访问是互斥的（mutex）

④多个C之间P操作是互斥的：如果只是简单的使用for循环设置在取10个产品前，则可能发生多个C轮流的取产品

4.确定信号量的个数

5.检查是否发生死锁：否

3.理发师

1.服务与被服务的关系

2.区别：需要额外设置变量记录当前等待的顾客有多少个，且该变量的访问是要互斥进行的，即需要夹在PV操作中

3.理发师问题实际上是生产者 - 消费者问题的变式：

①生产者 - 消费者问题：生产者生产资源，消费者消费资源；缓冲区限制资源上限

②理发师问题：将顾客和服务员分别视为一种资源

顾客：每个顾客到店时，生产一个顾客资源；在被服务前，消耗一个服务员资源

服务员：提供服务前，消耗一个顾客资源；确定有顾客时，生产一个服务员资源；再提供服务

特点：1.顾客无上限        2.服务员在没有顾客的时候可以休息，通过P(customer)实现

int waiting = 0;    //表示当前有多少顾客正在等待
semaphore mutex = 1;    //实现对waiting变量的互斥访问
//顾客资源，初始无顾客到店
//顾客资源不够时，服务员资源需要阻塞等待
semaphore customer = 0;
//服务眼资源，初始无服务员上岗
//服务员资源不够时，顾客需要阻塞等待
semaphore server = 0;
 
server_i(){    //消耗顾客资源，生产服务员资源
    while(1) {    //
        P(customer);    //在提供服务前，需要消耗顾客资源
        //如果当前没有顾客，则会被阻塞在P(customer)
        //当有一个顾客到店时，顾客就会生产一个顾客资源
        //此时被阻塞在P(customer)的服务员就会被唤醒，并提供服务
        //此时再对waiting变量进行--操作
        P(mutex);    //访问waiting变量时需上锁
        waiting--;    //顾客数 - 1，相当于“叫号”操作
        V(server);    //服务员生产服务员资源
        V(mutex);    //解锁
        提供服务;
    }
}
 
//顾客只需要被服务一次，故无需while循环
costumer(){    //生产顾客资源，消耗服务员资源
    P(mutex);    //访问waiting变量时需上锁
    waiting++;    //顾客数 + 1，相当于"取号"操作
    V(customer);    //生产顾客资源
    V(mutex);    //解锁
    //当前没有空闲服务员时，则会被阻塞在P(server)
    //当某个服务员完成服务时，该服务员进程执行下一轮循环
    //即服务员进程执行V(server)后，顾客进程被唤醒
    P(server);    //消耗服务员资源
    被服务;
}

特点：顾客到店时，会检查waiting变量是否小于m，即等待数量有上限

int waiting = 0;
semaphore mutex = 1;
semaphore server = 0;
semaphore customer = 0;
 
//服务员进程和第一种情况一致
Server_i(){
    while(1) {
        P(customer);
        P(mutex);
        waiting--;
        V(server);
        V(mutex);
        提供服务;
    }
}
 
//需要对waiting变量进行判断是否小于m
//小于m则进行和第一种情况一样的后续操作
//大于等于m则解锁后直接离开
Customer(){
    P(mutex);    //互斥访问变量waiting，上锁
    if (waiting < m) {    //当前等待顾客的个数 < m
        waiting++;    //顾客等待数 + 1
        V(customer);    //生产顾客资源
        V(mutex);    //解锁
        P(server);    //消耗服务员资源
        被服务;
    } else {    //当前等待顾客的个数 >= m
        V(mutex);    //解锁
        离开;
    }
}

特点：①在没有顾客时，服务员不能休息，必须忙等，即不断的轮询（while）检查waiting变量，判断当前是否有正在等待的顾客

②此情况下无需申明customer变量，即服务员无需阻塞

③用waiting变量判断服务员当前是否需要为顾客提供服务

int waiting = 0;    //表示当前正在等待的顾客数
semaphore mutex = 1;
semaphore server = 0;
 
Server_i() {
    while (1) {
        P(mutex);    //上锁
        if (waiting > 0) {    //当前有顾客
            waiting--;    //"叫号"
            V(server);    //生产服务员资源
            V(mutex);    //解锁
        } else {
            V(mutex);    //解锁
            continue;    //进行下一轮循环，实现忙等
        }
        提供服务;
    }
}
 
Customer(){
    P(mutex);    //上锁
    waiting++;    //"取号"
    V(mutex);    //解锁
    P(server);    //消耗服务员资源
    被服务;
}

4.读者 - 写者问题

1.第一个进程上锁，最后一个进程解锁：通过count变量记录该进程当前的数量

2.同类进程不互斥，不同类进程互斥（读者 - 写者问题的最主要特点）

3.写者进程不用判断是否自己是第一个/最后一个进程

---

---

1.从南往北的车只要有一辆占据，其余从南到北的车就可以一直使用该路；同理从北往南的车（同类的进程可以共享资源，不同类的进程互斥资源）

2.申明count1变量和count2变量分别用于记录当前P1/P2有几个进程正在使用该临界资源，初始为0

3.在每个进程开始时，通过count是否为0判断自己是不是第一个进程，如果是，则对临界资源进行上锁

4.进行count++，表示自己正在使用临界资源，并在使用完临界资源后进行count--

5.在每个进程结束时，通过count是否为0判断自己是不是最后一个进程，如果是，则对临界资源进行解锁

从左往右的猴子是一类进程，共享绳索这个资源；从右往左的猴子是一类进程，共享绳索；而不同进程间对绳索这一资源是互斥的

---

1、2、3种不同的录像片对应不同的进程，不同进程互斥访问录像厅（临界资源），统一进程共享录像厅 

5.哲学家进餐

特征：只有一类进程，且该类进程只有同时拥有多种资源才能进行

第三个思路最通用：

①将每种资源通过int类型的变量定义（使用变量将资源数量具象化）

②在进程开始运行时，先使用P（MUTEX）操作实现对各种资源进行互斥的访问，目的是逐一判断当前进程所需的各种资源是否满足运行的需要

③如果资源都满足，则拿走这些资源（一口气拿走），然后V（MUTEX），再执行动作

循环条件下：如果只要有一个资源不满足，则V（MUTEX），然后结束此次循环，进行下一次循环（continue）；

只进行一次：如果只要有一个资源不满足，则使用goto语句返回函数的第一句重新进行判断（手动实现循环）

其中②实现同一时间只可能有一个进程在进行判断/拿走临界资源

最后完成动作归还资源时也要进行上锁，保证归还动作一气呵成的完成

int a = n;    //用int类型表示各种资源
int b = m;
semaphore mutex = 1;    //互斥信号量，同时仅允许一个进程判断并拿走临界资源
 
Philosopher () {    //进行多次，while
    while (1) {
        P(mutex);
        if (条件满足) {    //资源够用，将所需资源分配给该进程，并解锁
            a--;
            b--;
            将a和b分配给该进程;
            V(mutex);
        } else {    //资源不够，则解锁，并进行下一轮循环判断
            V(mutex);
            continue;
        }
        进行主体动作;
        P(mutex);    //完成动作后，归还资源
        a++;
        b++;
        V(mutex);
    }
}
 
Philosopher () {    //进行一次，使用goto
start: 
    P(mutex);    //上锁
    if (条件满足) {
        a--;
        b--;
        将a和b分配给该进程;
        V(mutex);
    }
    else {
        V(mutex);
        goto start;
    }
    进行主体动作;
    P(mutex);    //上锁
    a++;    //归还a资源
    b++;    //归还b资源
    V(mutex);    //解锁
}

①变量wan表示剩余碗的数量

数组a中a[i] = 1表示第i个哲学家的左手有筷子，a[(i + 1) % n] = 1表示第i个哲学家的右有筷子（需要对右手边的筷子进行取模操作，第n个哲学家的右手边筷子就是第1个哲学家左手的筷子）

②P（mutex）实现对临界资源的上锁

③判断wan变量和左右筷子是否都在，任意条件不满足则V（mutex）（解锁）并结束循环；条件都满足时，则对这两个变量进行 - 1操作，表示取出该临界资源

④V（mutex）实现对临界资源的解锁

⑥进餐（即自己的主体动作）

⑦归还拥有的临界资源

另一个哲学家进行上锁并判断

---

检查当前是否有4个盆和1个座位，再去完成打饭和坐落（主体动作）

①解法一：信号量

 

②解法二：int类型变量（此时每个干饭人只进行一次，不能使用continue）

int seat = m;    //剩余m个座位
int plate = n;    //剩余n个盘子
semaphore mutex = 1;    //互斥信号量
 
Eatman () {
start: 
    进入餐厅;
    P(mutex);
    if (seat >= 4 && plate >= 1) {    //满足进餐条件，取走资源，并解锁
        seat -=4;
        plate--;
        V(mutex);
    }
    else {    //不满足进餐资源，解锁，并重新判断
        V(mutex);
        goto start;
    }
    干饭;
    P(mutex);
    plate += 4;    //干饭结束归还资源
    seat++;
    V(mutex);
}

6.读者 - 写者（写优先）

semaphore read = 1;    //读上锁
semaphore write = 1;    //写上锁
semaphore rmutex = 1;    //互斥访问readCount
semaphore wmutex = 1;    //互斥访问writeCount
int readCount = 0, writeCount = 0;    //分别记录当前的读者/写者数量
 
//每个读者进程需要通过read信号量判断当前读者是否可进入临界区
//可以进入临界区，则检查自己是否是第一个进入临界区的读者进程
//如果是第一个读者进程，则通过P(write)，写上锁，阻塞写者进程
//如果是最后一个读者，则通过V(wrtie)，写解锁，唤醒写者进程
Reader(){
    while (1) {
        P(read);    //读上锁，即判断读者当前是否可以进入临界区
        P(rmutex);    //互斥访问readCount变量，上锁
        readCount++;    //读者数量 + 1
        //判断是否为第一个读者进程，若是则写上锁
        if (readCount == 1) P(write);
        V(rmutex);    //解锁
        V(read);    //读解锁
        读者读;
        P(rmutex);    //互斥访问readCount变量，上锁
        readCount--;    //读者数量 - 1
        //判断是否为最后一个读者进程，若是则写解锁
        if (readCount == 0) V(write);
        V(rmutex);    //解锁
    }//while
}
 
//每个写者进程需要判断自己是否为第一个写者进程
//如果是，则P(read)，读上锁，阻塞后续出现的读者进程，即实现写优先
//最后一个写者进程负责V(read)，读解锁，唤醒读者进程
//写者 - 写者，读者 - 写者通过写上锁实现互斥的访问临界区
Writer(){
    while(1) {
        P(wmutex);    //互斥访问writeCount变量，上锁
        writeCount++;    //写者数量 + 1
        //判断是否为第一个写者进程，如果是则读上锁，实现写优先
        if (writeCount == 1) P(read);    
        V(wmutex);    //解锁
        P(write);    //实现读者-写者互斥，写者-写者互斥
        写者写
        V(write);
        P(wmutex);    //互斥访问writeCount变量，上锁
        writeCount--;
        //判断是否为最后一个写者进程，如果是则读解锁
        if (writeCount == 0) V(read);
        V(wmutex);
    }//while
}

7.读者 - 写者（读写公平）

semaphore lock = 1;    //实现读着 - 写者、写者 - 写者对临界区的互斥访问
int readCount = 0;    //记录当前读者数量
semaphore rmutex = 1;    //实现对readCount变量的互斥访问
semaphore queue = 1;    //读写队列，实现读写公平
 
//所有读者/写者都同一到队列中排队
//当临界区中有多个读者或者一个写者时，Queue = 0，写者到达，则阻塞在队首
//当临界区中没有进程时，Queue = 1，写者到达则直接访问
writer(){
    while(1) {
        P(queue);    //排队
        P(lock);    //检查是否可以进入临界区，可以则进入并上锁，不能则阻塞
        //如果可以执行V(Queue)，则说明已经执行P(lock)，即已经进入临界区
        //而有P(lock)存在，唤醒队首元素并不影响互斥访问临界区
        V(Queue);    //唤醒下一个队首进程
        写者写;
        V(lock);    //退出临界区，解锁
    }//while
}
 
//只有第一个读者进程执行P(lock)，即判断临界区是否上锁/对临界区上锁
//其余的读者进程在readCount不为1时，从队列中被唤醒后，直接进入临界区
//因此，连续的读者进程访问临界区将不会阻塞
//而写者进程将会因第一个读者进程的P(lock)而被阻塞，从而实现读者 - 写者互斥
//最后一个读者进程实现对临界区的解锁
reader(){
    while(1) {
        P(queue);    //排队
        P(rmutex);    //互斥访问readCount
        readCount++;    //读者数量 + 1
        if(readCount == 1) P(lock);    //自己是第一个读者进程，临界区上锁
        V(rmutex);
        V(queue);    //唤醒队首进程
        读者读;
        P(rmutex);    //互斥访问readCount
        readCount--;    //读者数量 - 1
        if (readCount == 0) V(lock);    //自己是最后一个读者进程，临界区解锁
        V(rmutex);    
    }//while
}