跳到主要内容

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

标签：

Author​

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

Description​

クリティカルセクション（critical section、以下 CS）は、同時には一つのスレッドだけが実行を許されるプログラム領域である。CS を囲む前処理と後処理を設計してこれを達成する問題を、クリティカルセクション問題と呼ぶ。

スレッド 0 と 1 は変数 turn と flag を共有し、一方の更新は他方にも即座に反映される。初期値は turn = 0、両方の flag は false とする。スレッド 0 では i = 0, j = 1、スレッド 1 では i = 1, j = 0 とする。両スレッドは次のいずれかの同じプログラムを実行し、前処理以降を複数回実行する可能性がある。

プログラム 1：

while (turn != i) ;  // 待つ（前処理）
<クリティカルセクション>
turn = j;           // 後処理

プログラム 2：

flag[i] = true;  // このスレッドが CS に入ろうとしている（前処理）
turn = j;        // 別のスレッドを優先する（前処理）
while (flag[(a)] && turn == (b)) ;  // 待つ（前処理）
<クリティカルセクション>
flag[(c)] = false;  // 後処理

(1) 解決法には次の三性質が必要である。

  • A. 相互排除：CS に入っているスレッドがあれば、他のスレッドは CS に入れない。
  • B. 進行：CS に入っているスレッドがなく、1 個以上のスレッドが前処理を実行する場合、それらのうち 1 個は CS に入れる。
  • C. 有限の待ち回数：あるスレッドが前処理を始めてから CS に入るまでに、他のスレッドが先に CS に入る回数には上限がある。

プログラム 1 が満たさない一つを挙げ、その理由を述べよ。

(2) プログラム 2 は三性質をすべて満たす。(a)、(b)、(c) に入る i または j を答えよ。

(3) プログラム 1、2 は busy wait（ポーリング）を用いる。スレッドを待ち状態にする方法と比べて、消費電力についてどちらが優れるかを答え、理由を数行で述べよ。

题目描述​

临界区（critical section，简称 CS）是同一时刻最多只允许一个线程执行的程序区域。临界区问题是通过设计围绕临界区的前处理和后处理来满足这一要求。

线程 00 和线程 11 共享变量 turn 与数组 flag，任一线程的更新都会立即被另一线程看见。初始时 turn = 0，两个标志均为 false。在线程 00 中取 i = 0, j = 1，在线程 11 中取 i = 1, j = 0。两个线程执行同一个程序（程序 1 或程序 2），并且可能多次执行进入临界区的前处理及后续代码。

程序 1 为

while (turn != i) ;  // 等待（前处理）
<临界区>
turn = j;           // 后处理

程序 2 为

flag[i] = true;  // 本线程正尝试进入临界区（前处理）
turn = j;        // 让另一个线程优先（前处理）
while (flag[(a)] && turn == (b)) ;  // 等待（前处理）
<临界区>
flag[(c)] = false;  // 后处理

正确的并发控制方案应同时满足以下三项性质：

  • A. 互斥：当一个线程位于临界区时，其他线程不能进入临界区。
  • B. 进展：当没有线程位于临界区，且至少一个线程正在执行进入临界区的前处理时，其中一个线程能够进入临界区。
  • C. 有限等待：从一个线程开始前处理到它进入临界区之间，其他线程抢先进入临界区的次数存在上界。
  1. 程序 1 恰好不满足其中一项，指出是哪一项并说明原因。
  2. 程序 2 满足上述三项要求。分别用 i 或 j 填写空格 (a)、(b)、(c)。
  3. 程序 1、2 都采用忙等待（轮询）。比较它与“把等待线程转入等待状态”的实现方式，指出哪一种功耗更低，并用数行文字说明理由。

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 が低遅延になり得るが、電力消費という観点では待機状態方式が優れる。

本页目录