応用情報技術者 2019年 秋期 午前2 問17

一時ファイル同時最大数【午前2解説】

正解の理由

解法ステップ

1. 規則の整理
   • 各ジョブ開始でそのジョブ専用の一時ファイル（50M）を作成する。
   • 辺 X→Y があるとき、X の一時ファイルは最初に生起される Y が参照し、Y の終了時に削除する。
   • 先行ジョブに複数の後続がある場合は「先に生起される一つだけ」が参照する。
   • ジョブの並列度（同時実行数）は 2。待ち行列順に実行される。
2. 実際の実行例（時刻を整数ステップで表現。各ジョブ処理時間は同じなので同一周期で完了/開始が揃う場合を想定）
   • 時刻0：A 開始 → ファイル A 作成（保持: A）
   • 時刻1：A 終了 → 後続 B, C を順に待ち行列へ追加。待ち行列から B, C が同時に開始（並列度2） → ファイル B, C 作成。A のファイルは B が終了するまで残る（B が A のファイルを参照するため）。
     • 保持: A, B, C
   • 時刻2：B, C 終了 → B の終了時点で A のファイルは削除される。B の後続は D, E（順に生起）、C の後続は E。E は両方の先行終了後に生起されるので、B と C の両方の終了で D と E が待ち行列に入る。待ち行列から D, E が同時に開始 → ファイル D, E 作成。
     • 参照関係：D は B のファイルを参照（B→D が B の最初の後続）、E は C のファイルを参照（C→E が唯一の後続）。
     • この時点で B と C のファイルは削除されていない（それぞれ D の終了、E の終了で削除される）。
     • 保持: B, C, D, E ＝ 4 個（ピーク）
3. ピーク時のファイル数は 4。したがって容量は $4\times 50=200$Mバイト。

選択肢別の誤答解説

• ア: 100
  • 100M（2個想定）は並列度から考えると過小評価。上の実行例で同時に4個存在する場面があるため不足します。
• イ: 150
  • 150M（3個想定）は一見妥当に見える場面（A,B,C が同時の箇所）がありますが、その後の D,E の開始で B,C のファイルが残ったまま D,E が作られる局面があり、同時に4つ存在します。
• ウ: 200
  • 正解。上記の手順でピーク4個を説明でき、$4\times 50=200$Mバイトになります。
• エ: 250
  • 250M（5個想定）は今回の依存関係と「最初に生起される一つだけが参照する」規則の下では発生しない同時数です。5個同時に存在させるためには別の並列化や異なる参照規則が必要になります。

よくある誤解

1. 「先行ジョブの一時ファイルは先行ジョブの終了時に削除される」と思い込む
   • 実際は「先行ジョブの一時ファイルは、その先行ジョブの最初の後続ジョブが参照し、その後続ジョブの終了時に削除される」。この差がピーク数の評価に直結します。
2. 「先行ジョブに複数の後続がある場合、全ての後続が同じファイルを参照して削除する」と誤認する
   • 問題文は「最初に生起されるジョブだけが先行ジョブの一時ファイルを参照する」と明記しています。複数後続のうち最初の1つだけが参照対象です。
3. 待ち行列順と実行多重度の関係を無視する
   • 待ち行列の順序（生起順）と並列度によってどのジョブが同時に開始するかが決まり、これが一時ファイルの同時数を左右します。生起順の理解が重要です。

補足コラム

• 一般的手法：この種の問題では「イベント（ジョブ開始／終了）ごとに一時ファイルの増減を追跡する」ことで確実にピークを求められます。処理時間が全て等しいときは同時終了・同時開始が発生しやすいので、図中の「矢印の順序（生起順）」を厳密に守ってシミュレーションすることが鍵です。
• 実務的には、こうした一時ファイルの寿命はプロセス間の責任範囲（どのプロセスが削除するか）を明確にしておかないとディスク占有が増大します。データフロー設計時に「誰が削除するか」を明示するのは重要です。

# 各ジョブの後続リストと優先順序を与え、同一処理時間で
# 待ち行列順・並列度2でイベントを進めるとピーク同時ファイル数を求められる

FAQ