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
}
更多推荐
所有评论(0)