跳到主要内容

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

标签：
留学警示（商务部公告2026年第12号）

根据中华人民共和国商务部公告2026年第12号，东京科学大学（東京科学大学/Institute of Science Tokyo）已被列入关注名单。请中国留学申请者慎重考虑相关风险，在做出留学决定前充分了解相关政策及其可能带来的影响。

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.

Kai​

(1)​

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

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

(2)​

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

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

である。したがって

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

(3)​

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

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

目录