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

問題文

2台のCPUから成るシステムがあり、使用中でないCPUは実行要求があったタスクに割り当てられるようになっている。このシステムで、二つのタスクA, Bを実行する際、それらのタスクは共通の資源Rを排他的に使用する。それぞれのタスクA, BのCPU使用時間、資源Rの使用時間と実行順序は図に示すとおりである。二つのタスクの実行を同時に開始した場合、二つのタスクの処理が完了するまでの時間は何ミリ秒か。ここで、タスクA, Bを開始した時点では、CPU、資源Rともに空いているものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：120

イ：140（正解）

ウ：150

エ：200

🔒 解説は解答すると表示されます

排他資源によるスケジューリング【午前解説】

正解の理由

タスクAは初段CPUが10msで資源Rに早く到達するため、資源Rを先に取得して使用（10〜60ms）します。その間にタスクBは初段CPUを使い40msでRへ到達し待機します。AはR使用後にCPUを60ms使って120msで完了します。一方BはRを60〜110msに使用し、続くCPU30msを110〜140msに実行して140msで完了します。したがって全体の終了時刻は最大の140msとなり、選択肢のうちイが正しいです。

（重要）この結果はAが先にRを使うスケジュールの場合の最短値です。仮に何らかの理由でBが先にRを使うスケジュールを強制すると、完了時刻は200msになります。よって「順序に依らず結果は同じ」とする記述は誤りです。

解法ステップ

各タスクの「Rに到達する時刻」を計算する。
- A: 初段CPU 10ms → R到着 $t = 10$
- B: 初段CPU 40ms → R到着 $t = 40$
到着順にRを割り当てる（Rは排他）：早く到着した方が先に使うのが通常の実行で最短になる。
- AがRを使用： $t = 10$ 〜 $60$ （50ms）
- BはR待ち：到着40ms→R取得は $60$ 〜 $110$ （50ms）
各タスクの残りCPUをRの後に実行できるか確認する（CPUは2台あるためほとんど待たない）。
- AのR終了は $60$ →そのままCPU60msを使い $60$ 〜 $120$ で完了
- BのR終了は $110$ →CPU30msを使い $110$ 〜 $140$ で完了
全体完了時刻は各タスクの完了時刻の最大値 ⇒ $max (120, 140) = 140$ ms

選択肢別の誤答解説

ア: 120
誤りの典型はBの最終CPU（30ms）をAの処理が終わる前に完了すると誤認することです。実際にはBはR待ちとその後のCPU実行で110〜140msかかるため120msでは終わりません。
イ: 140（正解）
上記の到達順・R使用順で算出される正しい完了時刻です。
ウ: 150
150msとする誤りは、BのR取得時刻やCPUの割り当てを誤って計算し、Bの最終CPUが120〜150msの間に実行されると見積もる場合に起こります。実際はBは110〜140msで完了します。
エ: 200
これは「Bが先にRを使う」順序（仮にBが40〜90msでRを使い、Aは10〜90ms待って90〜140でR使用、その後AがCPU60msで140〜200で完了する）を採ると得られる値です。このスケジュールは可能ではあるものの、問題の初期条件（Rが空いていてAが10msで到達する）では実際に起きないため、最短（妥当）な答えではありません。

よくある誤解

到着順は結果に影響しない：到着時刻が異なればR取得順が変わり、完了時刻が大きく変わるため注意。今回のようにAが早ければ短い完了時刻（140ms）になるが、逆順なら200msになる。
CPU台数を無視して直列処理と考える：CPUが2台あるため、ある時点で一方のCPUが空くと直ちに次のCPU処理に割り当てられる。これを無視すると過大評価・過小評価をする。
R使用中もCPUを占有すると誤認：問題の表記（CPU→R→CPU）はCPUを使い終えてからRへ移る形なので、R使用中はCPUは解放される点を忘れないこと。

補足コラム

この種の問題は「共有資源（ボトルネック）」を含むスケジューリング問題の基本パターンです。ポイントは

各段階の到達時刻（開始・終了）を時刻軸で追うこと、
資源が単一のときは到着順が待ち行列の順序を決めること、
複数CPUがある場合、CPUの空き状況を的確に把握すると待ち時間が短く見積もれることです。類題を解く際は必ず各段の「開始時刻」と「終了時刻」を整数で書き出して確認しましょう。

FAQ

Q. もしCPUが1台しかなければ完了時刻はどうなる？
A. CPUが1台だと初段CPUは直列実行になり、到達順が変わるので総時間は増加します。具体的には適切な順序を考慮すると、最短は別計算になります（この例では200ms以上になる可能性が高い）。

Q. 資源Rの使用時間が異なればどう考える？
A. 基本は同じ手順で到達時刻を求め、Rの開始・終了を順に決めて各タスクの残り処理を追えばよいです。Rが長い側がボトルネックになります。

Q. タスクの開始が同時でない場合は？
A. 各タスクのR到着時刻が変わるだけです。到着時刻の早い方が先にRを取るため、到着時刻を基準に同様に時系列で追います。

関連キーワード: スケジューリング、排他資源、待ち行列、CPU割当、フローショップ

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！