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

二つのタスクと共有資源Rの実行時間計算【午前2 解説】

要点まとめ

• 結論：両タスクを同時開始した場合の完了時間は140msで、タスクBが資源Rの待ちで遅延するため合計は140msになります。
• 根拠：Aが10msでRを先取りして10–60msまで占有、Bは40msでR到達後60msまで待ち、Bの最終CPUは110–140msで完了します。
• 差がつくポイント：R使用中はCPUを占有しない（ブロック状態でCPUが空く）という理解と、2台CPUが並行に最終CPUを割当てられる点を見落とさないこと。

正解の理由

よくある誤解

• 「Rを使う間もCPUを使っている」と考え、R使用時間とCPU時間を同時に消費すると誤算する。今回の図ではRはCPUとは別の資源で、R使用中はCPUを放す前提です。
• 「一つのCPUしかない想定で計算する」ことで、最終CPU時間が直列化され150msや200msを導きがちだが、問題は2台CPUがある点を活かす必要があります。
• BがR待ちの間もCPUが使えると仮定して重複を過大評価する（逆に短く見積もる）ミス。

解法ステップ

1. 各タスクの各段階（CPU1 → R → CPU2）の開始終了時刻を時系列で追う。
2. 両タスク同時開始（t=0）から初期CPU終了時刻を計算：Aは10ms、Bは40ms。
3. 先にRに到達したタスクがRを占有し、その間もう一方は待ち状態になる。R使用はCPUを占有しないので待ち時はCPUを放す。
4. Rの占有終了時に解放→次のCPU段階へ遷移し、空いているCPUに割り当てる（2台あるため同時実行可能）。
5. 各タスクの最終終了時刻の大きい方を答えとする。

• A: CPU1 0–10 → R 10–60 → CPU2 60–120
• B: CPU1 0–40 → 待ち 40–60 → R 60–110 → CPU2 110–140

選択肢別の誤答解説

• ア: 120
  誤り。120msはAの完了時刻であり、Bが110–140msで完了するため両者完了は140msになります。Bの最終CPU（30ms）をAの終了までに終わると誤認した場合に出る値です。
• イ: イ（140）
  正解。上のタイムライン通り、BがR待ちのため最終完了が140msになります。
• ウ: 150
  誤り。150msはたとえばR使用中にもCPUを占有するとか、最終CPUが直列に続くと誤って想定した場合に出やすい値です。本問では2台CPUで並行実行可能なため150msにはなりません。
• エ: 200
  誤り。Rを含め全工程を完全に直列（A全完了→B全完了）した場合の近似値（10+50+60 + 40+50+30 = 240 など）とも異なります。200は誤った重複計算や資源割当の誤解による大きな過大評価です。

補足コラム

• この種の問題は「クリティカルセクション（資源R）」と「CPU利用」の独立性を正確に理解することが鍵です。RがI/OやロックのようにCPUを使わない資源の場合、待ち行列が発生してもCPUは解放され、他のタスクに割り当てられます。
• もしR使用中もCPUを消費する（RがCPU-boundな処理である）設計なら時刻は大きく変わります。問題文や図で資源の独立性を読み取ることが重要です。
• 試験では図で並列機器台数（ここではCPU:2台）や「排他」表現を見落とさないようにしましょう。短い図の読み違いが致命的です。

FAQ