经 典 进 程 通信 问 题

2.4.1 哲 学 家 用餐 问 题
哲 学 家 就 餐 问 题 是 一 个 典 型 的 进 程 同 步 问 题 它 是 由 Dijkstra 提 出 并 解 决 的， 该 问 题 的 描 述 如 下：
有 五 个 哲 学 家， 他 们 的 生 活 是 交 替 地 进 行 思 考 和 就 餐。 哲 学 家 们 共 一 张 圆 桌， 周 围 放 有 五 张 椅 子， 每 人 坐 一 张。 在 圆 桌 上 有 五 个 碗 和 五 只 筷 子， 当 一 个 哲 学 家 思 考 时， 他 不 与 同 事 交 谈， 饥 饿 时 便 试 图 取 左、 右 最 靠 近 他 的 筷 子， 但 他 可 能 一 支 都 拿 不 到。 只 有 在 他 拿 到 两 支 筷 子 时 方 能 就 餐。 餐 毕， 放 下 筷 子 继 续 思 考。

一 个 简 单 的 解 法 是， 用 一 个 信 号 量 表 示 一 支 筷 子， 这 五 个 信 号 量 构 成 信 号 量 数 组， 其 描 述 为：
var chopstick: array[0...4] of semaphore;
所 有 信 号 量 被 初 始 化 为1 ， 第i 个 哲 学 家 的 活 动 可 描 述 为：
repeat
P (chopstick[i]);
P (chopstick[ (i+1) mod 5 ] );
..........
eat;
..........
V (chopstick[i]);
V (chopstick[(i+1) mod 5]);
..........
think;
..........
until false;
虽 然 上 述 解 法 可 保 证 不 会 有 两 个 相 邻 的 哲 学 家 同 时 就 餐， 但 可 能 引 起 死 锁。 假 如 五 个 哲 学 家 同 时 饥 饿 而 拿 起 各 自 左 边 的 筷 子， 使 五 个 信 号 量 chopstick 均 为 0； 当 他 们 再 试 图 去 拿 右 边 的 筷 子 时， 他 们 都 无 限 期 地 等 待。 对 于 死 锁 问 题 可 采 取 这 样 几 种 解 决 方 法：
(1) 至 多 只 允 许 四 个 哲 学 家 同 时 就 餐， 以 保 证 至 少 有 一 个 哲 学 家 可 以 就 餐， 最 终 总 会 释 放 出 他 所 用 过 的 筷 子， 从 而 可 使 更 多 的 哲 学 家 就 餐；
(2) 仅 当 哲 学 家 的 左、 右 两 支 筷 子 均 可 用 时， 才 允 许 他 拿 起 筷 子 就 餐；
(3) 规 定 奇 数 号 哲 学 家 先 拿 起 其 左 边 筷 子， 然 后 再 去 拿 右 边 筷 子； 而 偶 数 号 哲 学 家 则 相 反。 按 此 规 定，1、2 号 哲 学 家 竞 争 1 号 筷 子，3、4 号 哲 学 家 竞 争 3 号 筷 子， 即 五 个 哲 学 家 都 先 竞 争 奇 数 号 筷 子， 获 得 后， 再 去 竞 争 偶 号 筷 子， 最 后 总 会 有 某 一 个 哲 学 家 能 获 得 两 支 筷 子 而 就 餐。
|Back to Top|
2.4.2 读者－ 写 者 问 题 (Reader-Writers Problem)
一 个 数 据 文 件 或 记 录 ( 统 称 数 据 对 象 )， 可 被 多 个 进 程 共 享， 其 中 有 些 进 程 要 求 读， 而 另 一 些 进 程 要 求 写 或 修 改。 我 们 把 只 要 求 读 的 进 程 称 为“ 读 者”， 其 它 进 程 称 为 “ 写 者”。 允 许 多 个 读 者 同 时 读 一 个 共 享 对 象， 但 绝 不 允 许 一 个 写 者 和 其 它 进 程 ( 读 者 或 写 者 ) 同 时 访 问 共 享 对 象。 所 谓“ 读 者－ 写 者 问 题”， 是 指 保 证 一 个 写 者 必 须 与 其 它 进 程 互 斥 地 访 问 共 享 对 象 的 同 步 问 题。 该 问 题 首 先 在 1971 年 由 Courtois 等 人 解 决， 此 后 读 者－ 写 者 问 题 常 被 用 来 测 试 新 同 步 原 语。
利 用 信 号 量 机 制 解 决 读 者－ 写 者 问 题
为 了 解 决 读 者－ 写 者 问 题， 可 设 置 两 个 信 号 量：
(1) 读 互 斥 信 号 量 rmutex ， 用 于 使 读 者 互 斥 地 访 问 共 享 变 量 readcount;
(2) 写 互 斥 信 号 量 wmutex， 用 于 实 现 一 个 写 者 与 其 它 读 者 和 写 者 互 斥 地 访 问 共 享 对 象。
读 者－ 写 者 问 题 可 描 述 如 下：
var rmutex,wmutex: semaphore :=1,1;
readcount: integer: =0;
begin
parbegin
reader: begin
repeat
P(rmutex);
if readcount = 0 then (wmutex);
readcount := readcount+1;
V(rmutex);
...
Perform read operation
...
P(rmutex);
readcount := readcount -1;
if readcount = 0 then V(wmute);
V(rmutex);
until false;
end
Writer:begin
repeat
P(wmutex);
Perform Write operation;
V(wmutex);
until false;
end
parend
end
|Back to Top|
2.4.3 睡 着 的 理发 师 问 题 (The Sleeping Barber Problem)
睡 着 的 理 发 师 问 题 又 是 一 个 有 趣 的 进 程 同 步 问 题。
在 理 发 馆 中， 有 一 个 理 发 师， 一 张 理 发 椅 和 n 个 为 等 待 顾 客 所 设 的 椅 子。 如 果 没 有 顾 客 来， 理 发 师 就 会 坐 在 理 发 椅 上 睡 觉， 当 一 个 顾 客 来 到 时， 他 必 须 唤 醒 睡 着 了 的 理 发 师。 如 果 在 理 发 师 理 发 时， 又 有 别 的 顾 客 到 达， 他 们 要 么 坐 下 ( 如 果 有 空 的 椅 子 )， 要 么 离 开 ( 如 果 所 有 的 椅 子 都 被 坐 满)。
解 决 方 法 是 使 用 三 个 信 号 量：
1. customers , 用 于 记 录 等 候 的 顾 客 的 数 量。
2. barbers， 用 于 记 录 空 闲 理 发 师 的 数 量。
3. mutex, 用 于 进 程 之 间 的 互 斥。
另 外 还 需 使 用 一 个 变 量 waiting， 也 是 用 于记 录 等 候 的 顾 客 的 数 量。
例 程 如 下：
#include "prototypes.h"
#define CHAIRS 5 /*chairs for waiting customers */
typedef int semaphore; /* use your imagination */
semaphore customers = 0 ; /* # of customers waiting for service */
semaphore barbers=0; /* # of barbers waiting for customers */
semaphore mutex=1; /* for mutual exclusion */
int waiting = 0; /* customers are waiting (not being cut) */
　 　
void Barber(void) 　
{while (TRUE){ 　

p(customers);

p(mutex);

waiting=waiting-1;

v(barbers);

v(mutex);

cut_hair();

/* go to sleep if # of customers is 0*/
/* acquire access to 'waiting' */
/* decrement count of waiting customers*/
/* one barber is now ready to cut hair */
/* release 'waiting' */
/* cut hair (outside critical region) */
}} 　
　 　
Void Customer(void) 　
{ 　
p(mutex); /* enter critical region */
if (waiting < CHAIRS) { /* if there are no freee chairs, leave */

waiting = waiting + 1;

v(customers);

v(mutex);

p(barbers);

get_haircut();

/* increment count of waiting customers */

/* wake up barber if necessary*/
/* release access to 'waiting'*/
/* go to sleep if # of free barbers 0 */
/* be seated and be served */
} else { v(mutex); /* shop is full, do not wait */
}}