東北大学 工学研究科 電気・情報系 2018年8月実施 専門科目 問題5 計算機2

标签：

• Tohoku-University
• Semaphore
• Process-Synchronization

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

日本語原文

複数のプロセスを並行に動作させるシステムを考える。各プロセスはそのプロセス自身に局所的なひとつのレジスタ $R$ を持つ。システムは全てのプロセスで共有する3個の大域記憶領域 $S_0,S_1$、および $S_2$ を提供する。レジスタおよび大域記憶領域はそれぞれ整数値をひとつ保持し、$1$ に初期化される。システムにプログラム $M$ が与えられると、システムは起動し、$M$ を実行するプロセスがひとつ作られる。プログラムは命令の列である。命令 $I$ およびプログラム $M$ の文法は以下の通りである。

$$I::=S_i:=R\mid R:=S_i\mid R\texttt{++}\mid\langle M\rangle\mid P_i\mid V_i, \qquad M::=I;\cdots;I$$

ここで、$i\in\{0,1,2\}$ である。各命令の意味は以下の通りである。$S_i:=R$ はレジスタ $R$ の値を大域記憶領域 $S_i$ にコピーする。$R:=S_i$ は $S_i$ の値を $R$ にコピーする。$R\texttt{++}$ は $R$ に $1$ を加える。$\langle M\rangle$ は $M$ を実行する新しいプロセスをひとつ作成する。$P_i$ と $V_i$ は大域記憶領域をセマフォとして使用する命令である。$P_i$ は $S_i$ の値が $1$ 以上のとき $S_i$ から $1$ を減じる。そうでないならばこの命令は実行可能ではなく、従ってプロセスは $S_i$ の値が $1$ 以上になるまでブロックされる。$V_i$ は $S_i$ に $1$ を加える。プログラム中の各命令はプログラムの先頭から順に実行される。プロセスがプログラムの終端に達したとき、そのプロセスは終了する。全てのプロセスが終了したとき、システムは終了する。

動作できるプロセスは一度にひとつだけである。命令がひとつ実行された直後、システムは動作しているプロセスを切り替えることがある。次に動作するプロセスは次の命令が実行可能なプロセスの中から何らかの方法で選ばれる。次の命令は存在するがそのいずれも実行可能でないとき、システムはデッドロックに陥っており、従ってシステムは永久に終了しない。

このシステムにプログラム $M$ が与えられたとき、プロセスの切り替え方にかかわらずシステムが終了するならば、$M$ は常に終了すると言う。例えば、プログラム

〈R:=S0; S2:=R〉; 〈R:=S0; R++; S2:=R〉

は常に終了する。システムが終了した時の $S_2$ の値は $1$ または $2$ である。

以下の各プログラムについて、そのプログラムが常に終了するかどうか判定せよ。また、システムが終了したときに $S_2$ が取り得る値を全て求めよ。解答の根拠も示せ。

(1) 〈R:=S2; R++; S2:=R〉
(2) 〈R:=S2; R++; S2:=R〉; 〈R:=S2; R++; S2:=R〉
(3) 〈P0; R:=S2; R++; S2:=R; V0〉;
    〈P0; R:=S2; R++; S2:=R; V0〉
(4) 〈P0; P1; R:=S2; R++; S2:=R; V0; V1〉;
    〈P1; P0; R:=S2; R++; S2:=R; V0; V1〉
(5) P0; 〈P0; R:=S2; R++; S2:=R; V1〉;
    〈P1; R:=S2; R++; S2:=R; V0〉

题目描述

每个进程有局部整数寄存器 $R$，并共享整数 $S_0,S_1,S_2$，所有初值均为 $1$。指令 R:=Si、Si:=R、R++ 含义分别为读、写及加一；〈M〉 新建一个执行 $M$ 的进程。Pi 在 $S_i\ge1$ 时原子地减一，否则阻塞；Vi 原子地将 $S_i$ 加一。每条指令后均可能切换进程。所有进程结束时系统结束；有未结束进程但无可执行指令时发生死锁。

对以下各程序，判断是否无论如何调度均结束，并列出结束时 $S_2$ 的所有可能值，说明理由。

(1) 〈R:=S2; R++; S2:=R〉
(2) 〈R:=S2; R++; S2:=R〉; 〈R:=S2; R++; S2:=R〉
(3) 〈P0; R:=S2; R++; S2:=R; V0〉;
    〈P0; R:=S2; R++; S2:=R; V0〉
(4) 〈P0; P1; R:=S2; R++; S2:=R; V0; V1〉;
    〈P1; P0; R:=S2; R++; S2:=R; V0; V1〉
(5) P0; 〈P0; R:=S2; R++; S2:=R; V1〉;
    〈P1; R:=S2; R++; S2:=R; V0〉

Kai

程序	是否总结束	结束时 $S_2$
(1)	是	$2$
(2)	是	$2,3$
(3)	是	$3$
(4)	否	$3$
(5)	是	$3$

(1) 仅一个子进程执行一次加一。

(2) 两个进程均先读到 $1$ 时，两次写入均为 $2$；若第二次读取发生在第一次写入之后，最后得到 $3$。所有指令均不阻塞。

(3) $S_0$ 使两个读—改—写过程互斥，两次加一必顺序完成，且持锁进程总能执行到释放锁。

(4) 若第一个进程完成 P0，第二个完成 P1，二者随后互等而死锁。若最终结束，两个进程的加一仍在互斥区内，故 $S_2=3$。

(5) 主进程先将 $S_0$ 置为 $0$，第一个子进程在 P0 等待。第二个子进程取得初值为 $1$ 的 $S_1$，将 $S_2$ 从 $1$ 改为 $2$ 后执行 V0；第一个子进程才可继续，将 $S_2$ 改为 $3$。不存在循环等待。