目录
哲学家问题万能模板
Step 1. 定义互斥锁
信号量 Lock = 1;
Step 2. 定义资源数
比如,a 资源有 9 个,b 资源有 8 个,c 资源有 5 个,则:
int a = 9;
int b = 8;
int c = 5;
Step 3. 写代码模板
代码思路:
- 申请资源:
- 进程先检测目前资源总数满不满足自身的需求。
- 若满足,则一气呵成地把所需要的资源全部占用。然后开始完成操作
- 若不满足,则忙别的事,然后进行下一轮检测。
- 归还资源:
- 使用完资源后,进程也需要一气呵成地把所需要的资源全部归还。
Process(){
while(1){
P(Lock);
if(所有资源都够){ // 资源足够
所有资源数减少;
取xxx资源;
V(Lock);
break; // 已获得所需资源,跳出循环,开始完成操作
}
else{ // 资源不够,忙别的事,然后进行下一轮检测
V(Lock);
做别的事;
}
}
完成操作;
P(Lock);
归还所有资源,所有资源数增加;
V(Lock);
}
另外一种思路
还有一种解题思路是:破坏“请求和保持”条件,采⽤“静态分配”的思想,让进程⼀⼝⽓获得所有资源,再开始运⾏(可参见生产者消费者模型的“老和尚喝水、小和尚取水”的问题,那道题在进程开始操作前先连续 P 操作申请资源,全部申请完资源后再执行操作),但是这种代码的并发度没有上述模板代码的高,要想拿满分比较难。参考代码如下:
Process(){
while(1){
P(Lock); // 申请资源
P(资源1);
P(资源2);
P(资源3);
...
V(Lock);
完成操作;
P(Lock); // 归还资源
V(资源1);
V(资源2);
V(资源3);
...
V(Lock);
}
}
题目 1:经典版哲学家问题
【题目 1】一张圆桌上坐着五名哲学家,在每两名哲学家中间放着一根筷子,哲学家们的生活方式只做两件事:思考和进餐。饥饿时哲学家必须同时拿起两只筷子时才能进餐,进餐完毕后,放下筷子,进行思考。如果筷子被紧挨着的一名哲学家使用着,则不能争抢,必须等待,当这名哲学家就餐完毕后,放下筷子,才能使用。
Step 1. 定义互斥锁
信号量 Lock = 1;
Step 2. 定义资源数
有 5 根筷子,1 表示资源数量,定义如下:
int chopsitck[5] = {1, 1, 1, 1, 1};
Step 3. 写代码模板
第 i 个哲学家进程如下:
Process(i){
while(1){
P(Lock);
if ((chopsitcks[i] == 1) && (chopsitcks[(i+1)%5] == 1)) { // 检查左边和右边有没有筷子
chopsitcks[i]--; // 取走左边筷子
chopsitcks[(i+1)%5]--; // 取走右边筷子
V(Lock);
break;
}
else{ // 资源不够,忙别的事,然后进行下一轮检测
V(Lock);
思考;
}
}
吃饭;
P(Lock);
chopsitcks[i]++; // 归还左边筷子
chopsitcks[(i+1)%5]++; // 归还右边筷子
V(Lock);
}
将三个代码段拼在一起,即为本题最终答案。
题目 2:加强版哲学家问题(1)
【题目 2】有 n(n ≥ 3)位哲学家围坐在一张圆桌边,每位哲学家交替地就餐和思考。在圆桌中心有 m(m ≥ 1)个碗,每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后,才能就餐,进餐完毕,将碗和筷子放回原位,并继续思考。 为使尽可能多的哲学家同时就餐,防止出现死锁现象。请使用信号量的 P、V 操作 [wait()、signal() 操作] 描述上述过程中的互斥与同步,并说明所用信号量及初值的含义。
Step 1. 定义互斥锁
信号量 Lock = 1;
Step 2. 定义资源数
- 有 n 根筷子,1 表示资源数量。
- 有 m 个碗。
定义如下:
int chopsitck[n] = {1}; // 全部为 1
int bowl = m; //碗的资源数为 m
Step 3. 写代码模板
第 i 个哲学家进程如下:
Process(i){
while(1){
P(Lock);
if ((chopsitcks[i] == 1) && (chopsitcks[(i+1)%5] == 1) && (bowl > 0)) { // 检查左边和右边有没有筷子,且还有没有碗
chopsitcks[i]--; // 取走左边筷子
chopsitcks[(i+1)%5]--; // 取走右边筷子
bowl--; // 取走一个碗
V(Lock);
break;
}
else{ // 资源不够,忙别的事,然后进行下一轮检测
V(Lock);
思考;
}
}
吃饭;
P(Lock);
chopsitcks[i]++; // 归还左边筷子
chopsitcks[(i+1)%5]++; // 归还右边筷子
bowl++; //归还一个碗
V(Lock);
}
将三个代码段拼在一起,即为本题最终答案。
题目 3:加强版哲学家问题(2)
【题目 3】俗话说,“⼲饭⼈,⼲饭魂,⼲饭⼈吃饭得⽤盆”。⼀荤、⼀素、⼀汤、⼀⽶饭,是每个⼲饭⼈的标配。饭点到了,很多⼲饭⼈奔向⻝堂。每个⼲饭⼈进⼊⻝堂后,需要做这些事:拿⼀个盆打荤菜,再拿⼀个盆打素菜,再拿⼀个盆打汤,再拿⼀个盆打饭,然后找⼀个座位坐下⼲饭,⼲完饭把盆还给⻝堂,然后跑路。现在,食堂⾥共有 N 个盆,M 个座位。请使⽤ P、V 操作描述上述过程的互斥与同步,并说明所⽤信号量及初值的含义。
Step 1. 定义互斥锁
信号量 Lock = 1;
Step 2. 定义资源数
- 有 N 个盆
- 有 M 个座位
定义如下:
int pot = N; // 盆的资源数为 N
int seat = M; //座位的资源数为 M
Step 3. 写代码模板
由题意知,每个人需要四个盆、一个座位。进程如下:
Process(){
while(1){
P(Lock);
if ((pot >= 4) && (seat > 0)){ // 如果盆的数量还有四个及以上,且还有座位,则资源足够
pot -= 4; // 取走四个盆
seat--; // 占用一个座位
V(Lock);
break; // 已获得所需资源,跳出循环,开始完成操作
}
else{ // 资源不够,进行下一轮检测
V(Lock);
}
}
打饭;
吃饭;
P(Lock);
pot += 4; // 归还四个盆
seat++; // 归还一个座位
V(Lock);
}
将三个代码段拼在一起,即为本题最终答案。
题目 4:老和尚喝水、小和尚取水
【题目 4】某寺庙有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用。水缸可以容纳 10 桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶,且不可同时进行。试给出有关取水、入水的算法描述。
Step 1. 定义互斥锁
这题我刚刚在开头已经提到过,在生产者消费者问题那里也已经做过了一遍,那么我首先说明一下为什么又把这道题目放上来。因为大部分生产者消费者的题目的进程都只需要一个资源,但有些生产者消费者的题目需要多类或多个资源,这个时候我们就可以按哲学家问题的角度去看问题,按照这里所给出的模板,代码并发度比之前的要高。所以,这类多资源题目很有必要再放上来分析,这也有助于我们打开思路。
信号量 Lock = 1;
Step 2. 定义资源数
- 有 3 个水桶
- 有 1 个井
- 有 10 个水缸空位
- 有 0 个水缸的水
定义如下:
int tong = 3; // 桶的资源数为 3
int jing = 1; // 井的资源数为 1
int gang = 10; // 水缸空位资源数为 10
int shui = 0; // 水缸里的水资源数为 0
Step 3. 写代码模板
由题意知,小和尚需要一个桶、一个井、一个水缸空位。进程如下:
小和尚(){
while(1){
P(Lock);
if ((tong > 0) && (jing > 0) && (gang > 0)){ // 检查资源是否足够
tong--; // 占用一个桶
jing--; // 占用一个井
gang--; // 占用一个水缸空位
取桶;
到水井打水;
V(Lock);
break; // 已获得所需资源,跳出循环,开始完成操作
}
else{ // 资源不够,进行下一轮检测
V(Lock);
}
}
P(Lock);
往水缸入水;
shui++; // 水缸的水增加
tong++; // 归还一个桶
jing++; // 归还一个井
V(Lock);
}
老和尚需要一个桶和一个水缸的水,进程如下:
老和尚(){
while(1){
P(Lock);
if ((tong > 0) && (shui > 0)){ // 检查资源是否足够
tong--; // 占用一个桶
shui--; // 占用一个水缸的水
取桶;
V(Lock);
break; // 已获得所需资源,跳出循环,开始完成操作
}
else{ // 资源不够,进行下一轮检测
V(Lock);
}
}
喝水;
P(Lock);
tong++; // 归还一个桶
gang++; // 归还一个水缸空位
V(Lock);
}
是不是比用生产者消费者问题的方法要方便?思路也变得清晰简单多了。
标签:PV,操作系统,Lock,定义,Step,筷子,资源,哲学家 From: https://www.cnblogs.com/Mount256/p/16785381.html