Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説! 数式が読み込まれない場合は1回再読み込みしてみてください。

本番レベル模試 計算機システム2編(総復習)

こんにちは、ももやまです。

今回は「うさぎでもわかる計算機システム2」の総復習として、復習問題を作成してみました!

試験時間は90分で100点満点で、60点以上が合格です。

試験前や腕試しに是非チャレンジしてみてください!

なお、問題はこちらからダウンロードできます!


問題にチャレンジするまえに、こちらのマラソンモードをクリア(90点)してから挑むことをおすすめします。

1.CPUについて


CPUについて述べられた次の文章の空欄〔 ア 〕~〔 カ 〕に当てはまる適切な語句を答えなさい。(配点  6)


CPUとは〔 ア 〕の略称であり,CPUはコンピュータの性能を決めるうえで最も重要なハードウェアである。CPUはメモリ からプログラムを〔 イ 〕し,それを命令として〔 ウ 〕し,〔 エ 〕することで処理する.CPUは 命令を実行するために,レジスタを用いる.CPUは特定用途の専用レジスタと用途が固定されない〔 オ 〕をもち,それらを合わせてレジスタセットと呼ぶ。また,CPU の性能向上の工夫として,命令実行の各ステージを並列化する〔 カ 〕という手法がある。


★解答★

[1点 × 5 = 5点]

ア:Central Processing Unit
イ:フェッチ
ウ:デコード(解読)
エ:実行
オ:汎用(はんよう)レジスタ カ:パイプライン処理

★解説・コメント★

命令実行のCPUの動きに関する問題でした。

命令実行時の、

  1. 命令フェッチ(メモリ→CPUへ命令読み込み)
  2. 命令デコード(解読)(読み込んだ命令をデコーダで解読)
  3. 命令実行(解読された命令の実行、ALUで演算)
  4. 結果の格納(演算結果をメモリ・レジスタに格納)

の4ステップの流れは確実に理解しておきましょう。

2.1問1答


次の説明が指す語句をそれぞれ答えなさい。(配点  5)

(1) 機械語を人間にとってわかりやすくし、さらに1対1対応した言語

(2) 分割コンパイルによって生成され、リンカによって結合されるプログラム単位

(3) ニーモニックの中の,命令の種類を表す部分

(4) トランスレータの機械語の出力プログラム

(5) 人間が理解できる言語で書かれたプログラムを計算機上で実行させるための処理を行うソフトウェア


[1点 × 5 = 5点]

★解答★

(1) アセンブリ(言語)
(2) オブジェクトモジュール
(3) オペコード(部)
(4) オブジェクトコード
(5) コンパイラ


★コメント★

こちらもコンパイラ関連の問題でした。

(1), (3), (5)は基本問題なので正解しましょう。(2), (4)は少し難しいかも?

3.高級言語・アセンブリ言語・機械語の違い


次の1~6は機械語,アセンブリ言語,プログラミング言語のいずれかの言語について書かれたものである。それぞれの言語に該当するものをすべて選びなさい。ただし,異なる言語間で同じ選択肢を何度選んでもよい。(配点  3)

  1. CPUにより異なる
  2. 同一CPUでも複数の形式が存在する場合がある
  3. テキストとして表現される
  4. コンパイラを用いて実行可能な形に変換する
  5. CPUが直接実行できる形式の言語である
  6. 高級言語と呼ばれる

★解答★

[1点×3=3点]

機械語:1, 5
アセンブリ:1, 2, 3
プログラミング言語:3, 4, 6

★解説・コメント★

  1. CPUにより異なる→
    CPUにより異なるのは機械語、当然機械語と1対1対応したアセンブリ言語も該当する。

  2. 同一CPUでも複数の形式が存在する場合がある→
    機械語への対応の仕方が複数あるアセンブリ言語のみ該当。
    (機械語はCPUごとに必ず1通りなので機械語を選ばないように注意!)

  3. テキストとして表現される
    →プログラミング言語はもちろん該当。アセンブリ言語もテキストに該当する点に注意。

  4. コンパイラを用いて実行可能な形に変換する
    →コンパイラを使うのはプログラミング言語(CとかJavaとか)だけ

  5. CPUが直接実行できる形式の言語である
    →機械語のみ該当。アセンブリも「アセンブル(コンパイルのアセンブリVer)」という処理を行わないとダメな点に注意。

  6. 高級言語と呼ばれる。
    → プログラミング言語(CとかJavaとか)は高級言語と呼ばれます。

4.構文木・解析木


次のように文法・入力文字列が与えられているとする。このとき、次の問いに答えなさい。
(配点  8)


生成規則

<式> → <項> | <式> op2 <項>
<項> → <因子> | <項> op1 <因子>
<因子> → <名前>
<名前> → a | b | c | d | e

非終端記号 <式>, <項>, <因子>, <名前>

終端記号 op1, op2, a, b, c, d, e

出発記号 <式>

入力文字列 a op2 b op1 c


問1 コンパイラ内で字句解析/構文解析を行う部分をそれぞれカタカナで何というか。

問2 生成規則に登場する , | といった構文を定義する記号のことをなんというか。

問3 入力文字列 a op2 b op1 c に対して字句解析を行い、その結果および解析木を示しなさい。

問4 入力文字列に対する構文木を記しなさい。

問5 op1, op2を演算子としてみたとき、どちらの優先度が高いか、あるいは同じか答えなさい。



★解答・解説★

問1 [1点×2=2点]

解答:字句解析を行う部分→スキャナ 構文解析を行う部分→パーサ


問2

解答:メタ記号 [1点]


問3 [2点]

解析木

f:id:momoyama1192:20200214084948g:plain


問4 [2点]

構文木

f:id:momoyama1192:20200214232608g:plain


問5 [1点]

解答:op1

理由:a op2 b op1 c という順番にも関わらず、op1 を優先的に処理するから。

5.OSの基礎・正誤問題


つぎの(1)~(10)の文章が正しければ〇、誤りであれば×を解答欄に示しなさい。

(1) iPhoneは常に1つのプログラムのみを実行するので、OS (iOS) にプロセスの概念はない。
(2) 入出力要求を出したプロセスは、入出力が完了するまでCPUを必要としない。
(3) システムコールはサブルーチンコールの一種である。
(4) IPLは、Interactive Programming Languageの略であり、インタプリタを用いて実行されるプログラミング言語を表す。
(5) ファイルとは、OSにより仮想化、および抽象化された補助記憶装置である。
(6) 新たに生成されたプロセスは最初に待ち状態となる。
(7) DMAは、Direct Memory Accessの略であり、CPUがバスを介さず、直接メモリへアクセスすることである。
(8) 磁気ディスクのシーク時間はデータサイズ(ブロックサイズ)の大きさには依存しない。
(9) UNIXにおいては、そのままメインメモリにロードして実行できるように、ロードモジュールには物理アドレスが振られている。
(10) UNIXのiノードにはファイルの型、および大きさは記録される一方、ファイル名は記録されない。


★解答・解説★

[10点満点:1ミス -2点]

(1) 解答:×
iPhoneだろうが、Androidだろうが、スマホやPCじゃなかろうが、OSが入っているものはプロセスの概念が存在します。

(2) 解答:〇
問題の通りです。入出力を待っている状態のことを待ち状態というのも頭にいれておきましょう。

(3) 解答:×
サブルーチンコールではなく、割込みの一種です。

(4) 解答:×
IPLは、Initial Program Loaderの略で、要求されたプログラムをメインメモリにロードするOSの機能の一部のことです。

(5) 解答:〇
設問の通りです。

(6) 解答:×
新たに生成されたプロセスは実行可能状態となります。なお、待ち状態は入出力を待つ必要が出てきたときになる状態のことです。

(7) 解答:×
ちょっと難しい問題でした。 DMAは、確かにDirect Memory Accessの略ですが、CPUがバスを介さず、直接メモリへアクセスのではなく、入出力装置とメインメモリ間のデータ転送をCPUを介さずに直接できるようにすることを表します。

(8) 解答:〇
シーク時間は、ディスク上にある目的のトラックにヘッドを移動させるのにかかる時間のことなので、データの大きさには一切影響しません。なお、データの大きさが影響するのは実際にデータを転送する「データ転送時間」だけです。

(9) 解答:×
ロードモジュールには仮想アドレスが振られています。

(10) 解答:〇
設問の通りです。UNIXでは、ファイル名とiノードの対でファイルを記録しています。
iノードには、ファイルの型、、保護情報、所有者IDなど様々な情報が記録されています。

6.OSの基礎2


OSに関する以下の問いに答えなさい。(配点  9)

問1 OSとは何の略称か。

問2 OSを立ち上げることをなんというか。

問3 次のア~エはそれぞれどのメモリ領域に割り当てられるか。1~4の番号で答えよ。    ア:関数への引数
イ:malloc()により動的に確保された変数
ウ:静的変数
エ:CPUの命令コード

★選択肢★

  1. data領域
  2. heap領域
  3. stack領域
  4. text領域

問4 次のア~ウの作業はそれぞれ 1. 対話処理、2. バッチ処理、3. リアルタイム処理のうちのどの処理で行うのが最も適切か。1~3の番号で答えよ。

ア:銀行ATMからの預金・引き出し・送金の操作
イ:自動車の自動運転技術
ウ:毎日の天気予報


★解答★

問1 Operating System [1点×4]
問2 ブートストラップ(Bootstrap) [1点×4]
問3 ア: 3 イ: 2 ウ: 1 エ: 4 [1点×4]
問4 ア: 1 イ: 3 ウ: 2 [1点×4]

★解説・コメント★

問1, 問2:覚えましょう()

問3:4つの領域について軽く復習しておきましょう。詳しく復習したい人はこちらから。

  1. data領域 → 静的(static)変数や広域(global)変数用
  2. heap領域 → 動的に確保される領域
  3. stack領域 → 局所変数・関数の引数など
  4. text領域 → CPUの命令コード用

問4:バッチ処理・対話処理・リアルタイム処理の違いを軽く復習しておきましょう。詳しく復習したい人はこちらから。

バッチ処理:引き込もってひたすら処理していく。とにかくスループット(処理効率)が重要。
対話処理:ユーザーなどとやり取りしながら処理していく。応答性がある程度重要視される。
リアルタイム処理:組み込み機器などに用いられる。0.01秒の遅れが致命傷となるので応答性が非常に重要。

7.磁気ディスク


磁気ディスク(以下HDD)について述べられた次の文章を読んで以下の問いに答えなさい。
(配点 11)


 HDDの記録面を同心円状に分割した一周分の記憶領域は〔 ア 〕と呼ばれる。複数の記録面は共通の回転軸をもち,ある半径上に位置する〔 ア 〕の集合は〔 イ 〕と呼ばれる。また,データは〔 ア 〕を分割した固定長の〔 ウ 〕という領域に格納される。なお,現在では〔 ウ 〕を特定する手段として〔 エ 〕と呼ばれる一意の通し番号が広く用いられている。


問1 空欄〔 ア 〕~〔 エ 〕に当てはまる適切な語句を答えよ。

問2 HDDへのアクセス手順の過程において,アームを移動させてヘッドを指定された〔 イ 〕に位置付けるのにかかる時間のことをなんというか。

問3 HDDの回転速度が5,400rpm (回転/分) のときの平均回転待ち時間を有効数字2桁でを求めよ。

問4 入出力要求から入出力完了までに要する時間をなんというか。また,その内訳について簡潔に説明せよ。


★解答・解説・コメント★

問1 [1点×4 = 4点]

ア:トラック イ:シリンダ ウ:ブロック エ:LBA (Logical Block Adressing) [難問]

問2 シーク時間 [2点]

問3 5.6 [ms] もしくは 0.0056 [s] [2点]

[途中式]

1分間に5,400回転するので、1秒あたり90回転する。

なので、1回転あたりにかかる時間は 1/90 秒となる。

ここで、平均回転待ち時間は、1/2 回転するのにかかる時間なので、\[ \frac{1}{90} \times \frac{1}{2} = \frac{1}{80} \fallingdotseq 0.0056 \]となるので  5.6 \times 10^{-3} [s] (5.6 [ms])と計算できる。

問4

[名称 1点 + 内訳 2点 = 3点]

名称:アクセス時間
内訳:シーク時間と回転待ち時間とデータ転送時間の和である。

8.ディレクトリ構造


以下のように階層的なディレクトリ構造が与えられているとする。このとき以下の問いに答えよ。(配点  5)

f:id:momoyama1192:20200214085002g:plain

※ □ がディレクトリ、〇がファイルを指す。

ただし、カレントディレクトリを public、ホームディレクトリを home とする。

問1 ファイル test.txt の絶対パス名を答えなさい。

問2 ファイル secret.c の場所を相対パスで答えなさい。

問3 階層的ディレクトリ構造を使うメリットを1つ答えなさい。


★解答・解説・コメント★

問1

解答:/home/public/math/test.txt

絶対パスは、ルートディレクトリ(起点)からの経路を表します。


問2

解答:../private/secret.c

相対パスは、カレントディレクトリからの経路を表します。

前のディレクトリに戻る .. を使うことに注意しましょう。


問3

  • 関連するファイルをグループ化できる(ファイルを整理できる)

など。

9.割り込み

割り込みについて述べられた次の文章の空欄〔 ア 〕~〔 ウ 〕に当てはまる適切な語句を答えなさい。(配点  3)


 割り込みとは,CPUの命令実行とは独立に,あるいはその実行結果として発生する事象をとらえる手段であり〔 ア 〕モードで動作する。割り込みの種類は大きく分けて〔 イ 〕割り込みと〔 ウ 〕割り込みに分けられる。両者の違いは命令の実行との関連性であり,実行と関連のある割り込みが〔 イ 〕割り込みと呼ばれる。


★解答 / 解説 / コメント★

[1点×3]

ア:特権
イ:内部
ウ:外部

内部割込みと外部割込みの違いを確認しましょう。詳しくはこちらから。

10.シャットダウン


コンピューターの電源を切ったことがない人はおそらくいないであろう。もしかしたら子供のころ、「電源をぶち切りしちゃだめですよ〜ちゃんとシャットダウンの操作しましょうね〜。」と注意された人もいるかもしれない。

ところでなぜ電源を切る前にシャットダウンの操作が必要なのか。理由をファイルシステムの一貫性の観点から述べなさい。(配点  4)


ファイルの書き込みはメインメモリ内のバッファに対して行われているため、全ファイルの書き込みが補助記憶にされてはいない。そのため、そのまま電源を切るとメインメモリ内のデータが消えてしまう。そこで、シャットダウン操作を行い、バッファ内のデータを補助記憶装置に書き出すことでファイルシステムの一貫性を維持する。

赤色要素に1点×2、青色要素に2点で合計4点

11.プロセス


プロセスに関する以下の問いに答えなさい。(配点  8)

問1 ready queue内の実行中でないプロセスの状態をなんと呼ぶか。次の1~3の中から選びなさい。

  1. 実行状態
  2. 実行可能状態
  3. 待ち状態

問2 割り当てられた定時間が経過するとready queueの最後尾へ移されるスケジューリングアルゴリズムをなんというか。またこのアルゴリズムの長所を答えよ。

問3 問2のアルゴリズムを用いて定時間を3としたプロセスのスケジューリングを行う。下の表が示す時刻に3つのプロセスがシステムに到着し、表に示す処理期間(△),CPUを割り当てられている時間(太線),終了時刻(▲)をそれぞれ記入し,各プロセスのターンアラウンド時間を求めよ。ただし,この間新たなプロセスの到着や入出力はなく,プロセス切り替えの時間は無視できるものとする。

プロセス 到着時間 処理時間
P 0 8
Q 1 11
R 5 10

問4 プロセスが切り替わる際に,以前中断したプロセスがあれば,そのプロセスが退避した状態を回復してから再開することになる。この作業をなんというか。


★解答・解説・コメント★

問1 実行可能状態 [1点] (待ち状態と間違えやすいので要注意!)

問2 

名称:ラウンドロビン [1点]
長所:各プロセスに公平に時間を割り当てられる点 [1点]

問3 [4点]

f:id:momoyama1192:20200214232613g:plain

問4 ディスパッチ [1点]
(ディスパッチにより実行可能状態のプロセスが実行状態になることも覚えておきましょう。)

12.仮想記憶


仮想記憶に関するつぎの問いに答えなさい。(配点 11)

問1 OSの機能の一つである仮想記憶方式の目的はどれか。つぎの1~4の中から正しい番号を選びなさい。
[ITパスポート平成21年秋期 問59]

  1. OSが使用している主記憶の領域などに、アプリケーションプログラムがアクセスすることを防止する。
  2. 主記憶の情報をハードディスクに書き出してから電力供給を停止することで、作業休止中の電力消費を少なくする。
  3. 主記憶の容量よりも大きなメモリを必要とするプログラムも実行できるようにする。
  4. 主記憶よりもアクセスが高速なメモリを介在させることによって、CPUの処理を高速化する。

問2 仮想記憶は何と何を組み合わせることで実現されるか。

問3 仮想アドレスが32bit, ページサイズが8KBの仮想記憶空間において,ページテーブルのエントリの大きさを4Bytesとすると,ページテーブルの大きさはいくらになるか。

問4 アドレス変換を行うハードウェアの名称を答えなさい。

問5 メインメモリ上にページテーブルを置くと,アドレス変換の実行速度が低下する。この現象が起こる原因を,メインメモリアクセスの観点から説明せよ。また,この現象の影響を受けにくくするために,問4のハードウェアにはどのような工夫がなされているか。

問6 ページフォルトが発生すると,通常アクセスはメインメモリアクセスであるがHDDアクセスへと移り,その結果プログラムの実行効率が著しく低下する。その理由を述べよ。


★解答★

問1 3

仮想記憶の目的には、2つあり

  • 主記憶の大きさにとらわれない大容量の記憶装置の提供
  • OS側によるメモリ管理

の2つがあります。

4つの選択肢の中で合致するのは3の記述なので、答えは3となります。

問2 メインメモリ(主記憶)と補助記憶装置

問3

解答:2 [MB]

計算過程

ページサイズ(8KB)すべてを表現するのに必要なビット数は\[ 8 \times 2^{10} = 2^{13} \]より、13ビットとなる。

つまり、32ビットのうちの13ビット(ページ内変異)を除いた残りの19ビットがページテーブルを表現するビットとなる。

19ビットで表現できるページテーブルの数は  2^{19} 個。ページテーブルのエントリの大きさは4バイトなので、ページテーブルの大きさは\[ 2^{19} \times 4 = 2^{20} \times 2 \]となり、2[MB]となることがわかる。

問4 MMU (Memory Management Unit)

問5

原因:1回の主記憶アクセス時に2回のアクセスが必要になるから
工夫:(MMU内に)TLBを備えることで高速化を行っている

問6 補助記憶装置のアクセス速度がメインメモリに比べて非常に遅いため。

13.仮想記憶


次の①~②のCプログラムの断片をコンパイルした結果,それぞれ右のようなMIPS アセンブリプログラムが得られるとする。 空欄〔 ア 〕,〔 イ 〕に入る1命令をニーモニックで示せ。ただし, int 型は 32 ビットの符号付き整数, unsigned int 型は 32 ビットの符号なし整数として扱うものとする. また, 変数 a, y の番地はレジスタ $fp に格納された基底番地にそれぞれ 0, 4 を加算して得られるものとする。(配点  4)


★解答★

[2点 × 2 = 4点]

ア: andi $s1, $s0, 63
イ: sll $s1, $s0, 4

★解説★

ア:変数 a ($s0) の値を64で割ったあまりは、2進数の下位6ビット部分以外にマスクを かけることで得られる。つまり、$s00b0000………000111111 の論理積を取ればよい。よって、

andi $s1, $s0, 63

が答え。

イ:変数 a ($s0) の値を34倍する処理を、

  1. ( なんらかの処理 )
  2. $s1$s0 を加算
  3. $s1 を2倍

の3処理で実現したい。

過程3で $s1 を2倍してるので、1, 2の処理で $s0 の17倍した値を入れる処理をすればよい。

ここで、$s1$s0 を加算する処理を行っているので、1で $s0 を16倍(  2^{4} 倍)したものを $s1 に代入する処理を入れれば1, 2の2行で「$s1$s0 を17倍したものを代入する」処理が完成する。

よって

sll $s1, $s0, 4

となる。

14.MIPSプログラム

次のMIPSのアセンブリ言語のプログラムに関して,以下の問いに答えよ。ただし,Nは10進の非負整数,レジスタ$s0, $s1, $s2に格納される値は32bit符号付整数とし,オーバーフロー等は起こらないものとする。(配点 13)


 1.      addi   $s0,  $zero,  N
 2.      addi   $s1,  $zero,  0
 3.      addi   $s2,  $zero,  1
 4.LOOP: slt    $t0,  $s0,    $s2
 5.      bne    $t0,  &zero,  L1
 6.      add    $s1,  $s1,    $s2
 7.      addi   $s2,  $s2,    1
 8.      j      LOOP
 9.  L1: sll    $s1,  $s1,    1
10.      sw     $s1,  -4($fp)

問1 32bit符号付整数で表現できる値の範囲を述べよ。ただし,解答に冪指数を用いてよい。

問2 4行目のニーモニックを2進数 or 16進数の機械語コードに変換せよ。

問3 5行目のニーモニックを2進数 or 16進数の機械語コードに変換せよ。

問4 4行目の命令の内容を簡潔に説明せよ。

問5 4行目の命令は何回実行されるか。Nを用いて10進数で答えよ。

問6 10行目の第1オペランド,第2オペランドのアドレシングモードをそれぞれ何と呼ぶか。

問7 8行目のオペランドのアドレシングモードをなんというか。

問8 この命令実行時の$fpの値が16進数で0xff000010であるとき,10行目の命令の第2オペランドの実行アドレスは何か。16進数で答えよ。

問9 N = 10のとき,10行目において,メモリに格納される値は何か。10進数で答えよ。

問10 このプログラムにおいて,最終的にメモリに格納されるのはどのような値か。Nを用いて10進数で答えよ。


★解答・解説★

問1: - 2^{31} から  2^{31} - 1 まで

32ビットのうちの1ビットを符号につかうので  2^{31} を正と負で使い分ける。さらに「0」を正のほうにあてるひつようがあるので、[ - 2^{31} \leqq x \leqq 2^{31} - 1 ]の範囲内の  x を表現できる。

問2:0b 000000 10000 10010 01000 00000 101010(0x0212402A)

問3:0b 000101 01000 00000 0000000000000011(0x15000003)

問4:$s0 < $s2 であれば1、そうでなければ0を $t0 に格納する命令。

ここからは、実際に N に小さめの数字を代入して動きをデバッグすることをおすすめする。

後ろの問題で N = 4 について聞かれているので、 N = 2, 3, 4 程度で試すといいだろう。


N = 2 の場合のデバッグ

f:id:momoyama1192:20200214085006g:plain


N = 3 の場合のデバッグ

f:id:momoyama1192:20200214085010g:plain


N = 4 の場合のデバッグ

f:id:momoyama1192:20200214085014g:plain


問5

解答:N + 1 回

N = 2のとき:3回
N = 3のとき:4回
N = 4のとき:5回

などと試していって、N + 1回実行されることを推測しましょう。

問6

第1オペランドは $s1、第2オペランドは -4($fp) を指している。

第1オペランド:レジスタアドレシング
第2オペランド:ベースアドレシング(レジスタ値と偏位からアクセス先を決めている)

問7

解答:疑似直接アドレシング

[確認]

即値アドレシング、レジスタアドレシング、ベースアドレシング、PC相対アドレシング、疑似直接アドレシングの5つの違いを確認しておきましょう。

問8

解答:0xff00000c

[計算過程]

第2オペランドはベースアドレシングなので、与えられた $fp のレジスタ値 0xff000010 と偏位 -4 を加算した値の合計で求められる。よって、答えは 0xff00000c となる。

問9

解答:20

N = 4 のときでデバッグしたときを参考にしてください。

問10

解答:N(N+1)

6行目の最後のループ時点の $s1 の値を見ていくと、

N = 2のとき:3 (1+2)
N = 3のとき:6 (1+2+3)
N = 4のとき:10 (1+2+3+4)

となっている。なので、Nのときに $s1 には、\[ \frac{1}{2} N (N+1) = \frac{1}{2} ( N^{2} + N ) \]が入っていることがわかる。

ループを抜けたあとに9行目で2倍されるので、最後に入っているのは N(N+1) となることがわかる。

さいごに

今回は計算機システム2本番レベル模試について解説しました。

採点基準が少し雑ですがご了承ください。

60点未満だった人はもう1度復習してからチャレンジしてみましょう!