基本情報技術者 2014年 秋期 午前（科目A） 問17

二 CPU システムで共有資源を排他的に使うタスクの完了時間算出【午前2 解説】

要点まとめ

• 結論：二つのタスクを同時開始すると、両方の完了は最大で 140 ミリ秒後に終了します。
• 根拠：A が $t=10$ から資源Rを 50ms 使用し $t=60$ でR開放、B はその後 $t=60$ からRを使用して $t=110$ に開放、B の後半 CPU が $t=110$–$140$。
• 差がつくポイント：二つのCPUがあるためCPU待ちが発生せず、R の占有順（先にRを要求したAが先）で全体の所要時間が決まります。

正解の理由

• A: CPU10（$0$–$10$）→ R50（$10$–$60$）→ CPU60（$60$–$120$）
• B: CPU40（$0$–$40$）→ R50（待ち、$60$–$110$）→ CPU30（$110$–$140$）

よくある誤解

• 「Rは並列に使える」と考える誤り：R は排他的なので同時使用は不可で、要求順で待ちが発生します。
• 「CPU が余っているから待ちがなくなる」と短絡的に考える：CPU が空いていても、R を待っているタスクはCPUを使えないので総合時間は変わります。
• 「B の R 使用が $t=40$ から始まる」と誤認する：A が先に R を取得するため B は R を $t=60$ から使用します。

解法ステップ

1. 各タスクの時系列を分割（CPU / R / CPU）で整理する。
2. 同時開始なので初期のCPU区間は並列に実行できることを確認する。
3. 各タスクが最初にRを要求する時刻を求める（A: $t=10$, B: $t=40$）。
4. R は排他なので早く来た方（A）が先に使用し、後発（B）は終了まで待つ。
5. 待ち時間を考慮して各区間の開始・終了時刻を順に算出する。
6. 全タスクの終了時刻の最大値を求め、所要時間とする（今回 $140$ms）。

選択肢別の誤答解説

• ア: 120
  誤りの典型例は「R の待ちが発生せず、両者とも $t=120$ に終わる」と考えることです。実際にはBはRを待ち、最終 CPU を $t=110$–$140$ に実行するため 120ms には終わりません。
• イ: 140
  正解。上記の時系列計算により全体完了は $t=140$ です。
• ウ: 150
  150ms を選ぶ誤りは、R の排他時間やCPUの並列利用を二重に考慮（過剰に待たせる）した結果です。今回の条件下では余計な待ち時間は発生しません。
• エ: 200
  過度に保守的な見積もりで、R を両者が直列で全部待つ（あるいは何らかの追加待ちが入る）ように誤解したケースです。実際はA が先にRを取りBは一回だけ待つため 200ms にはなりません。

補足コラム

• クリティカルパスの考え方：今回の全体所要時間は「A の後半 CPU」と「B の後半 CPU」の終了時刻の最大値で決まります。R によりタスク間が直列化される区間が全体時間に影響します。
• スケジューリング視点：CPU が複数あっても共有資源の排他がボトルネックになれば CPU 並列性の効果は限定的になります。資源保護（mutex）や優先度制御の設計が重要です。

FAQ