基本情報技術者 2014年 秋期 午前（科目A） 問17
問題文
2台のCPUから成るシステムがあり、使用中でないCPUは実行要求があったタスクに割り当てられるようになっている。このシステムで、二つのタスクA, Bを実行する際、それらのタスクは共通の資源Rを排他的に使用する。それぞれのタスクA, BのCPU使用時間、資源Rの使用時間と実行順序は図に示すとおりである。二つのタスクの実行を同時に開始した場合、二つのタスクの処理が完了するまでの時間は何ミリ秒か。ここで、タスクA, Bを開始した時点では、CPU、資源Rともに空いているものとする。
選択肢
ア：120
イ：140（正解）
ウ：150
エ：200
タスクA（CPU10→R50→CPU60）とタスクB（CPU40→R50→CPU30）の並列実行【午前2 解説】
正解の理由
タスクA・Bを同時に開始するとCPUは2台あり、両方最初のCPU区間（A:10ms、B:40ms）は同時並行で実行可能です。資源Rは排他でしか1つのタスクしか使えないため、Rの50ms区間は順に実行されます。どちらが先にRを使うかによらず全体スケジュールを調べると、Aが先にRを使う場合もBが先に使う場合も最短完了時刻は同じで140msになります。したがって正解はイ（140）。
解法ステップ
- 各タスクの区間を時系列で書き出す（A: CPU10 → R50 → CPU60、B: CPU40 → R50 → CPU30）。
- 最初のCPU区間はCPU2台で同時実行可能なので、それぞれの終了時刻を計算（A終了10ms、B終了40ms）。
- 資源Rは1つしかないため、どちらか一方が先にRを占有。両方のR区間は直列化され合計100msに相当。
- しかしRの実行開始は各タスクの前段CPU終了後にしか始められない。よって先にRに入れるタスクはCPU終了が早いA（10ms）かB（40ms）かで場合分け。
- 各場合のタイムラインを描き、両タスクの最終終了時刻を求める。両場合とも最大完了時刻は140msとなる。
（以下はAが先にRを使う場合を示す具体的計算）
- 時刻0–10: AがCPU（終了10）／BがCPU（継続）
- 時刻10: AがRを獲得（10–60）、BはCPU継続（10–40）
- 時刻40: Bの最初のCPU終了。だがRはAが60まで占有しているためBは待ち（40–60）
- 時刻60: AがR終了してAは後段CPUを開始（60–120）、同時にBがRを開始（60–110）
- 時刻110: BがR終了して後段CPU（110–140）を実行
- 時刻120: Aが後段CPU終了（全体でAは120msで完了）
- 時刻140: Bが後段CPU終了（全体完了は140ms）
選択肢別の誤答解説
- ア: 120ms — 誤り。これはAが先に全部終わる120msを見て「早い方で決まる」と勘違いした計算。Bはまだ110–140の後段CPUが残る。
- イ: 140ms — 正解。上のタイムラインで両タスクが完了する最終時刻は140msである。
- ウ: 150ms — 誤り。R合計100ms＋最長CPU60ms等を単純に足して過大評価した結果。並列可能なCPU区間を考慮していない。
- エ: 200ms — 誤り。CPUや待ちの並列性を無視して最大値を足し合わせた完全過大評価。
よくある誤解
- 誤解1: 「CPUが2台あるからRの待ち時間はなくなる」と考えるミス。Rは1つしかないので待ちが必須です。
- 誤解2: 「Rの合計時間（50+50=100）だけ足せばよい」と単純合算するだけでCPU後の並行可能時間を無視する誤り。
- 誤解3: 「どちらか短い方を優先すれば常に最短になる」と思い込み、開始順によるCPU待ちや後続のCPU利用を見落とすこと。
補足コラム
- この種の問題は「リソース（資源）排他」と「複数CPUによる並列化」を組み合わせて考える必要があります。単純に各処理時間を合算するのではなく、各区間が同時に実行可能かどうか（依存・競合関係）を時系列に落とし込むことが重要です。
- 同様の考え方はプロセススケジューリングやデッドロック回避、スループット計算にも応用できます。
FAQ
Q1: どちらのタスクが先にRを使っても結果が同じになるのはなぜですか？
A1: Aが先にRを使う場合はBがR待ちをするがAの後段CPUとBの後段CPUが重なり、Bの後段が最後に終わる。Bが先にRを使う場合も対称的に最終完了時刻は同じになるため、最終的な最大完了時刻は140msに固定されるためです。
A1: Aが先にRを使う場合はBがR待ちをするがAの後段CPUとBの後段CPUが重なり、Bの後段が最後に終わる。Bが先にRを使う場合も対称的に最終完了時刻は同じになるため、最終的な最大完了時刻は140msに固定されるためです。
Q2: CPU台数が1台だったらどうなる？
A2: CPUが1台なら最初のCPU区間が直列化され、その待ち時間が増えるため全体時間は変化します。個別に時刻を再計算する必要があります。
A2: CPUが1台なら最初のCPU区間が直列化され、その待ち時間が増えるため全体時間は変化します。個別に時刻を再計算する必要があります。
Q3: 資源Rの利用順を強制できるなら短くなるか？
A3: 両パターン検討しても最終完了時刻は140msで変わらないため、順序変更しても改善しません（今回の値の組合せでは）。
A3: 両パターン検討しても最終完了時刻は140msで変わらないため、順序変更しても改善しません（今回の値の組合せでは）。
関連キーワード: スケジューリング、排他制御、並列処理、待ち時間最適化、プロセス同期
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！