跳到主要内容

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

标签：

Author​

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

Description​

(1) 整数表現​

(1-1) −15-15 の8 bit符号絶対値表現と1の補数表現を示せ。(1-2) 8 bitの2の補数で表せる最大・最小整数を十進・二進で示せ。(1-3-1) 43+(−5)43+(-5) を8 bitの2の補数で計算し、最上位桁の桁上げの扱いを示せ。(1-3-2) 2の補数を加算に用いる利点を述べよ。

(1-4) 同じビット長の整数 A,BA,B と和 SS の最上位ビットを a,b,sa,b,s、最上位桁からの桁上げを cc とする。符号なし／2の補数の符号付きの場合のオーバーフロー判定式を求めよ。

(2) 排他制御​

単一プロセッサのマルチタスク環境を考える。

(2-1) デッドロックと飢餓を説明せよ。

(2-2) 共有スタックには事前に d1,…,dnd_1,\ldots,d_n がアドレス x,…,x+n−1x,\ldots,x+n-1 に置かれ、top=x である。stack(addr) はアドレス addr のデータを表し、push_item は事前に値を設定済みである。スタックを操作するのはプロセス1、2だけとする。次の命令の実行順で、(ア)から始まりプッシュ／ポップの少なくとも一方が正しくなくなる例を示せ。

/* プロセス1 */
/* ア */ top = top - 1;
/* イ */ stack(top) = push_item;
/* プロセス2 */
/* ウ */ pop_item = stack(top);
/* エ */ top = top + 1;

(2-3) セマフォは0または1を取る。不可分操作 PP はセマフォが0なら呼出しプロセスを休止し、1なら0にする。不可分操作 VV は同じセマフォの PP で休止したプロセスがあれば起動し、なければセマフォを0から1にする。

(2-3-1) セマフォ aa と P,VP,V を使い、プロセス1、2へ命令を追加して上記の操作を正しくせよ。aa の初期値も示せ。

(2-3-2) 共有変数 m を扱うのはプロセス3、4だけとする。m=1 から、プロセス3が while(true){m=m+1;}、プロセス4が while(true){print(m);} を実行する。表示が順に 1,2,3,…1,2,3,\ldots となるよう、二値セマフォ b,cb,c を用いて同期し、初期値を示せ。

Kai​

(1)​

(1-1) 符号絶対値は 10001111\boxed{10001111}、1の補数は 11110000\boxed{11110000}。

(1-2) 最大は 01111111=127\boxed{01111111=127}、最小は 10000000=−128\boxed{10000000=-128}。

(1-3-1)

00101011+11111011=1 00100110.00101011+11111011=1\,00100110.

最上位からの桁上げ1を捨てて 00100110=38\boxed{00100110=38} を得る。

(1-3-2) 正負を区別する特別な加減算回路を設けず、同一の2進加算回路で符号付き加算を実行できる。

(1-4) 符号なしでは c=1\boxed{c=1}。符号付きでは同符号の数の和が逆符号になる条件

a‾ b‾ s+ab s‾=1\boxed{\overline a\,\overline b\,s+ab\,\overline s=1}

で判定する。

(2)​

(2-1) デッドロックは複数プロセスが互いの保有資源の解放を待ち、全員が先へ進めない状態である。飢餓は、他のプロセスが進む一方で、あるプロセスだけが資源や実行機会を無期限に得られない状態である。

(2-2) (ア)→(ウ)→(エ)→(イ)\boxed{(ア)\to(ウ)\to(エ)\to(イ)}。未書込みの stack(x-1) をポップし、その後 d1 の領域 stack(x) を上書きしてしまう。

(2-3-1) 初期値 a=1\boxed{a=1} とし、各操作全体を囲む。

/* プロセス1 */
P(a); top = top - 1; stack(top) = push_item; V(a);
/* プロセス2 */
P(a); pop_item = stack(top); top = top + 1; V(a);

(2-3-2) 初期値を b=0,c=1\boxed{b=0,c=1} とする。

/* プロセス3 */
while (true) { P(b); m = m + 1; V(c); }
/* プロセス4 */
while (true) { P(c); print(m); V(b); }

最初に1を表示し、その後「1増加→表示」を交互に行う。

本页目录