動的再配置で動かすセグメントと読み書き回数を数える
基本情報技術者試験 平成29年度秋期 午前 問19 ／ ソフトウェア › オペレーティングシステム
過去問にチャレンジ
図のメモリマップで、セグメント2が解放されたとき、セグメントを移動(動的再配置)し、分散する空き領域を集めて一つの連続領域にしたい。1回のメモリアクセスは4バイト単位で行い、読取り、書込みがそれぞれ30ナノ秒とすると、動的再配置をするために必要なメモリアクセス時間は合計何ミリ秒か。ここで、1kバイトは1,000バイトとし、動的再配置に要する時間以外のオーバヘッドは考慮しないものとする。
- ア
1.5
- イ
6.0
- ウ
7.5
- エ
12.0
会話形式の解説
講師今回は動的再配置、つまりメモリ上のセグメントを動かして、ばらばらの空き領域を一つにまとめる処理の時間を求める問題です。注目するのは二つで、どのセグメントを動かすのかと、1回の移動で何回メモリにアクセスするのかです。
受験者図では左からセグメント1が500k、セグメント2が100k、セグメント3が800k、最後に空きが800kバイトです。セグメント2が解放されると、そこが空きになるのですね。
講師そうです。そのとき空きはどこにできていますか。
受験者セグメント3の左側に100k、右側に800kです。空きが二か所に分かれています。
講師では、空きを一つにつなげるには、どのセグメントを動かせば足りるでしょうか。
受験者セグメント3をセグメント1のすぐ後ろへ詰めれば、空きは右側にまとまります。セグメント1は先頭にあるので、動かさなくてよさそうです。
講師その通りです。動かすのはセグメント3の800kバイトだけです。1kバイトは1,000バイトと指定されているので800,000バイトです。4バイト単位で動かすと何回になりますか。
受験者800,000÷4で200,000回です。1回30ナノ秒なので、200,000×30ナノ秒で6ミリ秒でしょうか。
講師そこが一番の引っかけです。データを移動するとき、メモリへのアクセスは何をしていますか。
受験者元の場所から読み出して、新しい場所に書き込みます。読取りと書込みの両方が必要なので、1回の移動で30＋30の60ナノ秒ですね。
講師はい。200,000回×60ナノ秒で12,000,000ナノ秒です。1ミリ秒は1,000,000ナノ秒なので、ミリ秒に直すとどうなりますか。
受験者12ミリ秒です。読取りと書込みを別々に数えて400,000回×30ナノ秒としても、同じ12,000,000ナノ秒になります。6.0ミリ秒は片方のアクセスだけで計算した値なのですね。
講師よく確かめられました。ほかの選択肢も逆算すると、1.5ミリ秒は読み書き両方を含めて移動量が100kバイトの場合、7.5ミリ秒は500kバイトの場合にあたります。500kはセグメント1の大きさですが、先頭にあるので動かす必要はありません。図のどこを動かすのかを先に決めることが大切です。
受験者移動量を決めて、アクセス単位で割って回数を出し、読取りと書込みの両方の時間を掛ける、という順番で考えればよいのですね。
講師そうです。最後に単位も確認しましょう。本問は1kバイトを1,000バイトと指定しているので、1,024バイトで計算すると選択肢と合いません。ナノ秒からミリ秒へは10の6乗で割る、という換算も合わせて覚えておくと安心です。
まとめ
セグメント2を解放したあとの動的再配置では、セグメント3（800kバイト）をセグメント1の直後へ詰めるだけで空き領域が一つにまとまります。800,000バイトを4バイト単位で動かすので200,000回の移動になり、1回の移動には読取り30ナノ秒と書込み30ナノ秒の計60ナノ秒がかかります。合計は12,000,000ナノ秒、つまり12.0ミリ秒です。片方のアクセスだけで計算すると6.0ミリ秒になり、動かす必要のないセグメントを数えるとほかの選択肢の値になるので注意が必要です。
解答・解説
正解はエです
この問題のテーマ
セグメント2を解放したあと、空き領域を一つにまとめる動的再配置（コンパクション）で、メモリアクセスに合計何ミリ秒かかるかを計算する問題です。
解き方の考え方
図では左から順にセグメント1（500k）、セグメント2（100k）、セグメント3（800k）、空き（800k）と並んでいます。セグメント2が解放されると、空きはセグメント3の左側の100kと右側の800kに分かれます。セグメント3をセグメント1のすぐ後ろへ詰めれば空きは一つにつながるので、動かすデータは800kバイト＝800,000バイトです。4バイトずつ動かすので回数は800,000÷4＝200,000回です。1回の移動では読取り30nsと書込み30nsの両方が必要なので60nsかかり、合計は200,000×60ns＝12,000,000ns＝12ミリ秒です。検算として、読取りと書込みを別々に数えると400,000回×30ns＝12,000,000nsとなり、同じ12ミリ秒になります。
選択肢ごとの解説
- ×ア 1.51.5ミリ秒の場合、読み書きの両方を含めても移動量は100kバイトにしかなりません（25,000回×60ns）。実際に移動するのはセグメント3の800kバイトなので、この値とは合いません。
- ×イ 6.06.0ミリ秒は、200,000回の移動を読取りか書込みのどちらか一方の30nsだけで計算した値です。データを移動するには読み出してから書き込む必要があるので、1回あたり60nsで計算します。
- ×ウ 7.57.5ミリ秒の場合、読み書きの両方を含めると移動量は500kバイトになり、これはセグメント1の大きさと同じです。セグメント1はメモリの先頭にあるので動かす必要がなく、移動するのはセグメント3の800kバイトだけです。
- ○エ 12.0移動するのはセグメント3の800kバイトだけで、4バイト単位の読取りと書込みをそれぞれ数えると12.0ミリ秒になります。解き方で求めた値と一致します。
補足
本問では1kバイトを1,000バイトとするよう指定されています。1,024バイトで計算すると選択肢と合わなくなるので、問題文の単位の決まりに従ってください。
POINT
- 動的再配置では、空きを一か所に集めるために動かす必要があるセグメントだけを移動対象とします。
- メモリ上のデータを移動するには、1単位ごとに読取りと書込みの両方のアクセスが必要です。
- アクセス回数は、移動するバイト数を1回のアクセス単位（本問では4バイト）で割って求めます。
- ナノ秒からミリ秒に直すときはで割ります（1ms＝1,000,000ns）。