哲学家进餐问题有多种...
解答:
哲学家进餐问题有多种解决方案,主要有
方法一:至多只允许有n-1位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕时能释放出他用过的两只筷子,从而使更多的哲学家能够进餐。
semaphore count = n-1; // 可进餐名额数量
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
P(count);
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
V(count);
}
}
CoEnd
方法二:仅当哲学家的左、右两只筷子均可用时,才允许他拿起筷子进餐。
semaphore mutex = 1; // 保证每个时刻只有一个哲学家取筷子的互斥信号量
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
P(mutex);
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
V(mutex);
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
}
}
CoEnd
方法三:规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子,而偶数号哲学家则相反。
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
if (i%2==1) {
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
} else {
P(chopsticks[(i+1)%n]); // 取右边筷子
P(chopsticks[i]); // 取左边筷子
}
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
}
}
CoEnd
由于本题引入了新资源碗,每位哲学家必须取到一个碗和两侧的筷子后,才能就餐。
方法一
使用哲学家进餐问题的模板一:综合考虑碗的数量m和最大可进餐名额数量n-1,限制碗的数量为 min{m, n-1},得到新的最大可进餐名额数量。本题适合采用方法一,伪代码如下:
semaphore bowls = min(n-1, m); // 可用碗数量即可进餐名额数量
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
P(bowls);
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
V(bowls);
}
}
CoEnd
方法二
使用哲学家进餐问题的模板二:仅当哲学家的左、右两只筷子和碗均可用时,才允许他拿起筷子进餐。这里需要引入互斥信号量,保证进餐请求能够按照顺序执行,根据银行家算法,对于任意一个请求序列,均存在安全序列,不会产生死锁。这里拿左、右两只筷子和碗的顺序不会影响结果的正确性。
semaphore bowls = m; // 所有碗资源的信号量
semaphore mutex = 1; // 保证每个时刻只有一个哲学家取筷子的互斥信号量
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
P(mutex);
P(bowls); // 取碗
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
V(mutex);
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
V(bowls); // 放回碗
}
}
CoEnd
由于方法二会限制进餐请求的顺序,相比方法一降低了并行度。
方法三
使用哲学家进餐问题的模板三:规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子,而偶数号哲学家则相反。若 m≥n ,每个哲学家一定都能拿到碗,若 m<n ,则会对同时进餐的名额产生限制,要求拿到碗的哲学家才能去拿筷子。
semaphore bowls = m; // 所有碗资源的信号量
semaphore chopsticks[n]; // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
while (true) {
思考;
P(bowls); // 取碗
if (i%2==1) {
P(chopsticks[i]); // 取左边筷子
P(chopsticks[(i+1)%n]); // 取右边筷子
} else {
P(chopsticks[(i+1)%n]); // 取右边筷子
P(chopsticks[i]); // 取左边筷子
}
进餐;
V(chopsticks[i]); // 放回左边筷子
V(chopsticks[(i+1)%n]); // 放回右边筷子
V(bowls); // 放回碗
}
}
CoEnd
如果不使用上述方法,可能会产生死锁,在碗资源数不足的情况下,可能会出现一部分哲学家拿到筷子但拿不到碗,一部分哲学家拿到碗但拿不到筷子,举个例子,有A、B、C、D共4个哲学家,依次围坐在一张圆桌边,有4根筷子,2个碗,A、C各拿到2根筷子,B、D各拿到1个碗,4人均无法进餐,处于死锁状态。
登录后提交答案
暂无评论,来抢沙发