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

标签：

• Osaka-University
• Computer-Architecture
• Operating-Systems

Author

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

Description

(1) 記憶システム

(1-1) 一度参照したアドレスを近いうちに再参照する性質と、その近傍のアドレスを参照する性質の名称を答えよ。(1-2) キャッシュと仮想記憶を導入する効果を一つずつ述べよ。

(1-3) バイトアドレス方式、直接マップキャッシュ（ブロック2 byte、タグを除くデータ容量8 byte）、ページング方式でページサイズ8 byte、主記憶32 byte、仮想記憶256 byteとする。主記憶の全領域をページングの対象とする。論理・物理アドレス変換をCPUとキャッシュの間で行い物理アドレスでキャッシュを参照する方式を物理アドレスキャッシュ、キャッシュと主記憶の間で変換し論理アドレスでキャッシュを参照する方式を論理アドレスキャッシュと呼ぶ。

• (1-3-1) 論理アドレス長、キャッシュブロック数、ページ表エントリ数、物理ページ番号長、物理／論理アドレスキャッシュのタグ長を求めよ。
• (1-3-2) 物理アドレスキャッシュにおいて、初期キャッシュは空で、物理ページ枠0,1,2,3に仮想ページ0,1,2,31がある。論理アドレスを順に $0,1,2,3,4,8,21,255$ と参照するとき、各回の主記憶ブロック番号、キャッシュブロック番号、タグと全体のヒット率を求めよ。ページ・ブロックはアドレス0から連続して配置される。

(2) ファイルシステム

(2-1) 次の空欄［ア］～［カ］に最も適切な語を選択肢から選び、その記号を答えよ。同じ選択肢を複数回用いてはならない。

ファイルは装置上の最小構成単位であるブロックに格納され、アクセスもブロック単位で行われる。ファイルの先頭ブロックから末尾へ順にアクセスする［ア］と、任意のブロックを任意順にアクセスする［イ］がある。［イ］において連続ファイル割付けを用いると、ファイル生成時に［ウ］を見積もる必要があり、未使用領域が［エ］した状態となる。これらを避ける方式として、各ブロックへのポインタ配列を索引ブロックに格納する［オ］や、各ブロックに次ブロックへのポインタを持たせる［カ］がある。

選択肢：(A) インデックスファイル割付け、(B) 直接アクセス、(C) 非断片化、(D) プロセス割付け、(E) 最大ファイルサイズ、(F) 順アクセス、(G) 断片化、(H) アクセス時間、(I) リンクファイル割付け。

(2-2) ブロックサイズ $b$ byte、アドレス長 $a$ byte、ファイルサイズ $s$ byteとする。(i)連続割当て、(ii)リンク割当て、(iii)インデックス割当てを比較せよ。(iii)では索引を1ブロックに収める。事前アクセスはなく、同じブロックを何度参照しても1個と数える。リンク割当てでは各ブロックに次ブロックのアドレスを格納する容量が必要である。床関数 $\lfloor x\rfloor$（$x$ 以下の最大整数）と天井関数 $\lceil x\rceil$（$x$ 以上の最小整数）を用いてよい。

• (2-2-1) $1\le n\le s$ とする。第 $n$ byteだけを読む場合／先頭から第 $n$ byteまで読む場合のアクセスブロック数、および最小割当て容量 $p$（$b$ の整数倍）を求めよ。
• (2-2-2) $r=s/b, e=s/p$ として、(i)と(iii)の $0<r\le3$ でのグラフを示せ。
• (2-2-3) $r$ が増えるときの利用効率の比 $e_{\mathrm{iii}}/e_{\mathrm{i}}$ の変化を述べよ。

Kai

(1)

(1-1) 順に 時間的局所性、空間的局所性。

(1-2) キャッシュは平均アクセス時間を短縮する。仮想記憶は主記憶容量を超えるアドレス空間をプログラムに提供する。

(1-3-1) 順に

$$8\text{ bit},\quad4,\quad32,\quad2\text{ bit},\quad2\text{ bit},\quad5\text{ bit}.$$

タグ長は「アドレス長−ブロック内1 bit−インデックス2 bit」である。

(1-3-2) 物理アドレスは順に $0,1,2,3,4,8,21,31$。

サイクル	0	1	2	3	4	5	6	7
主記憶ブロック	0	0	1	1	2	4	10	15
キャッシュブロック	0	0	1	1	2	0	2	3
タグ	0	0	0	0	0	1	2	3
ヒット／ミス	M	H	M	H	M	M	M	M

したがってヒット率は $2/8=\boxed{25\%}$。

(2)

(2-1) 順に 順アクセス(F)、直接アクセス(B)、最大ファイルサイズ(E)、断片化(G)、インデックスファイル割付け(A)、リンクファイル割付け(I)。

(2-2-1)

方式	第 $n$ byteだけ	先頭から第 $n$ byteまで	最小容量 $p$
(i)	$1$	$\lceil n/b\rceil$	$b\lceil s/b\rceil$
(ii)	$\lceil n/(b-a)\rceil$	$\lceil n/(b-a)\rceil$	$b\lceil s/(b-a)\rceil$
(iii)	$2$	$1+\lceil n/b\rceil$	$b(1+\lceil s/b\rceil)$

(ii)では各ブロックのデータ領域が $b-a$ byteとなる。(iii)では索引ブロックも数える。格納可能条件は $\lceil s/b\rceil\le\lfloor b/a\rfloor$。

(2-2-2) $k-1<r\le k$ に対し

$$\boxed{e_{\mathrm{i}}=r/k,\qquad e_{\mathrm{iii}}=r/(k+1)}\quad(k=1,2,3).$$

(2-2-3)

$$\boxed{\frac{e_{\mathrm{iii}}}{e_{\mathrm{i}}}=\frac{\lceil r\rceil}{\lceil r\rceil+1}}.$$

各区間では一定で、整数を越えるごとに増加し、大きなファイルほど1に近づく（単一索引ブロックの容量制限内）。