東大 情報理工学系研究科 コンピュータ科学専攻 専門科目（コンピュータ科学） 2022年度 院試 解答例・解説

応答時間とターンアラウンド時間を分ける

応答時間は「到着から初めてCPUを得るまで」，ターンアラウンド時間は 「到着から完了まで」である。Round Robin では初回実行は早くなりやすいが， 完了までには何度もキューに戻るため，ターンアラウンド時間が小さくなるとは限らない。

プリエンプションの効果

Preemptive SJF では，時刻 $25$ に短いジョブが到着した時点で $P_4$ を中断する。 この1点が Non-Preemptive SJF との主要な差である。 到着時刻がある問題では，単に処理時間の短い順に並べるのではなく， 各イベント時刻で実行可能集合を更新する必要がある。

Stooge sort型の再帰

このプログラムは，接頭部，接尾部，接頭部を順に整列する Stooge sort 型の構造を持つ。 中央で十分に重なるからこそ，左にある大きい要素と右にある小さい要素が再帰呼び出しを通じて 入れ替わる。各呼び出しが半分程度しか覆わない場合，端は整列しても中央の順序が残る。

オーダー計算

3個の部分問題のサイズが $3n/4$ なので，分割統治の指数は $\log_{4/3}3$ になる。通常のマージソートのような線形の併合処理はなく， 基底部の実行回数だけを数えるため，この再帰木の葉数がそのまま答えになる。

出現位置の制約

$aba$ は自分自身と2文字ずれて重なることができるが，1文字ずれて重なることはできない。 そのため，出力では $\mathrm{t}$ が連続しない。 さらに，出現開始位置として使えるのは末尾2文字より前までであるため， 長い語では末尾が必ず $\mathrm{ff}$ になる。

有限状態変換として見る

この写像は一見すると入力全体を見ているように見えるが，固定語 $w$ の出現判定に必要なのは 長さ $|w|$ の窓だけである。したがって有限個のバッファ状態で処理できる。 この観点を使うと，正規言語・文脈自由言語に対する閉包性の議論が自然に書ける。

ループ回数を先に確定する

パイプライン問題では，まず動的命令数を決める必要がある。 このプログラムでは $x4$ が4ずつ増え，$64$ 未満の間だけループするので， ロード・加算・更新・分岐の4命令が16回実行される。

ロード直後だけが特別

ALU命令同士の依存はフォワーディングで吸収できるが，ロード直後の使用は別である。 ロード値はメモリアクセスステージまで得られないため，直後の実行ステージに間に合わない。 この1サイクルの差が，被ロード・データハザードとして現れる。