跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問9

标签：

Author​

GPT-5

Description​

Two threads, 0 and 1, share turn and flag; updates are immediately visible. Initially turn = 0 and both flags are false. In thread 0, i = 0, j = 1; in thread 1, i = 1, j = 0.

Program 1 uses

while (turn != i) ;
<critical section>
turn = j;

Program 2 uses

flag[i] = true;
turn = j;
while (flag[(a)] && turn == (b)) ;
<critical section>
flag[(c)] = false;

(1) A solution should satisfy mutual exclusion, progress, and bounded waiting. Program 1 fails exactly one of them. Identify it and explain why.

(2) Program 2 satisfies all three. Fill (a), (b), and (c) with i or j.

(3) Programs 1 and 2 use busy waiting (polling). Compare its power consumption with an approach that moves a waiting thread to a waiting state.

题目描述​

线程 00 和线程 11 共享变量 turn 与数组 flag，任一线程的更新都会立即被另一线程看见。初始时 turn = 0，两个标志均为 false。在线程 00 中取 i = 0, j = 1，在线程 11 中取 i = 1, j = 0。

程序 1 为

while (turn != i) ;
<临界区>
turn = j;

程序 2 为

flag[i] = true;
turn = j;
while (flag[(a)] && turn == (b)) ;
<临界区>
flag[(c)] = false;
  1. 正确的并发控制方案应同时满足互斥、进展和有限等待。程序 1 恰好不满足其中一项，指出是哪一项并说明原因。
  2. 程序 2 满足上述三项要求。分别用 i 或 j 填写空格 (a)、(b)、(c)。
  3. 程序 1、2 都采用忙等待（轮询）。将其功耗与“把等待线程转入等待状态”的实现方式进行比较。

考点​

  • 进程同步性质：依据可能的线程执行次序，分别检查轮流方案的互斥、进展和有限等待。
  • Peterson 算法：理解意愿标志与让权变量的作用，补全双线程进入区和退出区中的索引。
  • 忙等待开销：比较持续占用处理器轮询与阻塞等待在线程调度及功耗上的差异。

Kai​

(1)​

満たさないのは progress（進行性） である。例えば turn = 0 のときスレッド 0 がクリティカルセクション外で停止し、スレッド 1 だけが進入しようとすると、クリティカルセクションは空いているにもかかわらずスレッド 1 は永久に待つ。

排他性は turn が同時に 0 と 1 にならないことから保たれるが、厳密な交互実行を要求するため、進入を望まない相手にも順番を返してもらう必要がある。

(2)​

これは 2 スレッド用 Peterson アルゴリズムであり、待機条件と退出処理は

while (flag[j] && turn == j) ;
...
flag[i] = false;

である。したがって

(a)=j,(b)=j,(c)=i.\boxed{(a)=j,\qquad(b)=j,\qquad(c)=i}.

両者が同時に進入を試みた場合、最後に turn を書いた側が相手に譲るため一方だけが進入する。退出時に自分の flag を下げるので相手は進め、同じ相手に無制限に追い越されることもない。

(3)​

一般に、待機状態へ遷移させる方式の方が消費電力は小さい。busy wait は条件を繰り返し読み続けて CPU 命令を実行し、共有キャッシュラインへのアクセスも継続する。一方、ブロックされたスレッドは CPU を使用せず、CPU は他の処理を実行するか低消費電力状態に入れる。

非常に短い待ち時間ではスリープ・復帰のオーバーヘッドを避けるため spin が低遅延になり得るが、電力消費という観点では待機状態方式が優れる。

本页目录