平成30年度 春期 午前 問8

✓ これが正解ウLIFO

解説

最後に呼んだ順に戻るので、後入れ先出しのスタックを使います。

設問は、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておくための記憶管理方式を尋ねています。四つの記述はどれも三文字か四文字の略語なので、何を決める規則なのかで仕分けると見通しが立ちます。再帰の呼び出しは、呼んだ順に深く入っていき、最後に呼んだものから先に戻ってきます。つまり最後に保存した内容が最初に必要になるので、後入れ先出しの規則、すなわち LIFO が当てはまります。この規則で内容を積んでおく場所がスタックで、呼び出すたびに戻り番地とレジスタの内容を積み、戻るときは一番上から降ろします。一回分の呼び出しがひとまとまりの段として積み重なるため、何段深く入っても順序が狂いません。出し入れの順序を決める規則なのか、それとも何を追い出すかを決める規則なのか。この仕分けが分かれ目になります。

ほかの選択肢はなぜ違うのか

• アFIFO：先に入れたものから先に出す順序を表す語で、待ち行列の側の規則です。再帰では最後に呼んだ相手の内容が真っ先に必要になるので、必要になる順序がちょうど逆を向いています。
• イLFU：使われた回数が最も少ないものを追い出す規則です。何を捨てるかを決める話であって、呼び出しの途中経過を積んでおき順に取り出す仕組みを指すものではありません。
• エLRU：最後に使われてから最も時間がたったものを追い出す規則です。主記憶やキャッシュの置換えで使う考え方で、保存した内容を取り出す順序を定めるものではありません。