跳到主要内容

大阪大学 情報科学研究科 情報工学 2020年度 計算機システムとシステムプログラム

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

(1) 数値表現​

(1-1) 次の空欄(a)～(e)を選択肢から選び、記号で答えよ。固定小数点と浮動小数点のうち、科学技術計算では(a)等の理由から(b)表現が、小型機器の制御等では(c)等の理由から(d)表現が多く用いられる。いずれの方式も、指数の底が2なら十進数の(e)を誤差なく表せない。

選択肢：(ア) 固定小数点、(イ) 浮動小数点、(ウ) 演算回路が簡潔になる、(エ) 表現できる数の範囲が広い、(オ) 小数を誤差なく表現できる、(カ) 0.5、(キ) 0.25、(ク) 0.1。

(1-2) 浮動小数点数を A=(−1)s2e−7(1+m)A=(-1)^s2^{e-7}(1+m) とする。上位から符号1 bit、指数4 bit（7余り表現）、仮数小数部9 bitを格納する。指数 e=0,15e=0,15 は特殊値用とし、非正規化数は使わない。仮数の整数部1は隠れビットで、丸めは小数部の切り捨てである。(1-2-1)～(1-2-3)では導出過程も示せ。

  • (1-2-1),(1-2-2) 正の有限最大値と正の最小値を十進で求めよ。
  • (1-2-3) −36.66-36.66 を表すビット列を求めよ。
  • (1-2-4) 繰り返し計算で切り捨てを用いるときの問題を説明せよ。

(2) 仮想記憶​

(2-1) 次の空欄を埋めよ。仮想記憶は主記憶より大きい(a)を提供する。プロセスが指定する(b)を、(d)上の表を用いて(c)へ変換する。固定長単位の方式は(e)、可変長単位の方式は(f)である。(e)では領域の確保と解放を繰り返しても(g)がほぼ生じない一方、固定長ページにより(h)が発生する。これは使用領域が(i)に比べ小さい場合に顕著である。

選択肢は次の通りであり、同じ選択肢を複数回用いてはならない：(ア) 主記憶、(イ) ページ、(ウ) 内部断片化、(エ) スラッシング、(オ) 実アドレス、(カ) 仮想アドレス、(キ) アドレス空間、(ク) 補助記憶、(ケ) メモリ階層、(コ) ページング、(サ) セグメント、(シ) 外部断片化、(ス) ページフォールト、(セ) レジスタ、(ソ) セグメンテーション。空欄には選択肢の記号で答えよ。

(2-2) ページ枠3個、初期状態は空とする。参照列 S=(0,1,2,0,3,1,4,3,2,3,1,2,4)S=(0,1,2,0,3,1,4,3,2,3,1,2,4) に対し、LRUとFIFOでページフォールトが起きる参照を示せ。

(2-3) 主記憶アクセス2 μ\mus、フォールト1回の追加時間8 ms、1命令当たり平均2回のメモリアクセスとする。フォールトなしに比べた平均実行時間の増加を10%以下にするためのフォールト確率 PP の上限を導出過程とともに求めよ。フォールトがない場合のメモリアクセス時間は主記憶アクセス時間に等しく、演算時間その他のオーバーヘッドは無視する。

(2-4) 参照列を変えず、LRUのフォールトを削減する方法を述べよ。

Kai​

(1)​

(1-1) 科学技術計算では表現範囲が広い浮動小数点を、機器制御では演算回路が簡素になる固定小数点を用いる。有限の2進小数で正確に表せないのは 0.1\boxed{0.1}。

(1-2-1)

Amax⁡=214−7(2−2−9)=255.75.\boxed{A_{\max}=2^{14-7}(2-2^{-9})=255.75}.

(1-2-2)

Amin⁡=21−7=0.015625.\boxed{A_{\min}=2^{1-7}=0.015625}.

(1-2-3) 36.66=25(1+0.145625)36.66=2^5(1+0.145625) なので e=12=(1100)2e=12=(1100)_2、⌊0.145625⋅512⌋=74=(001001010)2\lfloor0.145625\cdot512\rfloor=74=(001001010)_2。よって

1  1100  001001010\boxed{1\;1100\;001001010}

となり、表す値は −36.625-36.625。

(1-2-4) 切り捨てによる誤差が一方向へ偏り、反復で累積する。特に小さい増分が仮数の最下位桁より小さいと、加算結果が元の値と同じになり計算が進まないことがある。

(2)​

(2-1) 順に アドレス空間、仮想アドレス、実アドレス、主記憶、ページング、セグメンテーション、外部断片化、内部断片化、ページ。

(2-2) 参照を先頭から1番として

方式フォールトが起こる参照位置回数
LRU1,2,3,5,6,7,9,11,139
FIFO1,2,3,5,7,11,127

(2-3) 1アクセスの平均時間は 2+8000P2+8000P μ\mus。したがって

2(2+8000P)≤1.1⋅2⋅2⇒P≤2.5×10−5.2(2+8000P)\le1.1\cdot2\cdot2\quad\Rightarrow\quad\boxed{P\le2.5\times10^{-5}}.

(2-4) プロセスに割り当てるページ枠数を増やす。LRUでは枠数を増やすと保持ページ集合が包含関係で拡大するため、フォールト数は増えず、作業集合が収まれば初回読込み以外のフォールトを抑えられる。

本页目录