2008-07-29

memo2

2007年度

問題1
Linuxのプロセス管理とメモリ管理の実装手法について、解答用紙1ページ程度で解説せよ。その際に、具体的にどのようなデータ構造やアルゴリズムを使用しているかが分かるようにせよ。

要参照:
http://homepage3.nifty.com/owl_h0h0/unix/job/UNIX/kernel/process.html
http://homepage3.nifty.com/owl_h0h0/unix/job/UNIX/kernel/memory.html


ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

問題2
Linux等のOSにおいて、なぜアプリケーションからカーネル空間のデータ構造をアクセスすることを許さないのか、その理由を説明せよ
カーネル空間とユーザ空間を分けることで、ユーザ空間を使ってカーネル空間の内容を書き換えられないようにすることが出来る。
これにより、悪意をもってカーネルを破壊しようとするプログラムから、カーネル空間におかれている内容を守ることが出来る。



問題3
次のようなCプログラムについて考える。
typedef struct comp{
int val1;
int val2;
} *comp_t, comp_val;


int main(int argc, char *argv[]){
comp_t ret;
ret = first();
second();
printf(“Val1 = %d, Val2 = %d\n”, ret->val1, ret->val2);
}
comp_t first(){
comp_val comp;
comp.val1 = 10;
comp.val2 = 20;
return ∁
}
void second() {
int a = -100;
int b = -200;
}
以上のようなプログラムを実行したが、当初想定した”Val1 = 10, Val2 = 20”という結果が表示されなかった。
以下の設問について答えよ。
(1)このプログラムを実行したとき、12行めのprintfの表示結果がどうなるかを示せ。
→ Val1 = -200, Val2 = -100

************** ※重要※*************
処理系がgccである場合を仮定する。

左端がスタックの底であるリストS=[]を考えると、
first()を呼び出したとき: S=[main(), firstの制御情報, [comp.val2 = 20, comp.val1 = 10] ]
となる。返り値は構造体compの番地になる。 (このとき、構造体compは変数を2個持っているので、変数2個分の長さを持っていることに注意!)

その後、
second()を呼び出したとき: S=[main(), secondの制御情報, a = -100, b = -200]
となる。最後に以前、comp.val1とcomp.val2があった番地を出力しているので、
ret->val1 == b == -200, ret-> val2 == a == -100
となる。
***********************************


(2) (1)の結果が、どのような理由で生じたのかについて説明せよ。
→ first()の返り値がローカル変数のアドレスを指しているため、first()終了後にfirst()内部で使ったローカル変数が解放された。
その後、second()で、その開放された変数の番地が割り当てられたため、(1)のような結果を返す結果となった。

(3) “Val1 = 10, Val2 = 20”という結果が出るためは、どのようにプログラムを変更すればよいのかを示せ。
  また、なぜ、(2)で述べた問題が解消したのかについても説明せよ。
"comt_t comp; → static comp_val comp;"
理由:first()関数内部で呼び出された変数が解放されないため、second()関数内部で再定義されることがなくなったから。

問題4
Linuxにおける標準入力、標準出力、標準エラー出力と、ファイルディスクリプタとの関係を説明せよ。また、shellなどのコマンドインタープリタを実現する際に、パイプやリダイレクションはどのように実現しているのか。特に、標準出入力、標準出力をどのように扱うことで、他のコマンドにデータを渡したり、出力結果をファイルに書き出したり、ファイルから入力データを読み出したりしているのか。具体的には、どのようなシステムコールを用いて上記の仕組みを実現しているのか説明せよ、


→ファイルディスクリプタはデフォルトでは以下のように定義されている。
0 = 標準入力, 1 = 標準出力, 2 = 標準エラー出力, (2以降 = openなどの関数を使ってユーザが定義したファイルディスクリプタ)
パイプやリダイレクション機能はdup()やdup2()の関数を用いて実現されている。
例えば、左リダイレクションであれば、まずはX = dup(STDIN_FILENO)と呼び出し、STDIN_FILENOのバックアップをXに退避させる。
その後、dup2(ユーザ定義のファイルディスクリプタ番号, STDIN_FILENO)とdup2関数を呼び出して標準入力の属性を事前にopenしたファイルディスクリプタに変更する。
これにより、ファイルの内容を標準入力として扱うことが出来る。右リダイレクションの場合も同様の処理を、標準出力に対して行えばよい。
 パイプを実現する場合は、以下の手順をとる。
1. 右リダイレクションの場合と同様に、標準出力の属性を一時ファイルに変更する。
2. コマンド処理により一時ファイルに結果が出力されたら、標準出力の属性を元に戻す。
3. 今度は、標準入力の属性を一時ファイルに変更する。
4. これにより、2回目のコマンドは1回目のコマンドの出力結果を入力データとして扱う。
5. 標準入力の属性を元に戻す。
上記の手順を踏むことで、パイプを実現することが出来る。


問題5
システムコールの標準化とアプリケーションプログラムの移植性との関係について説明せよ。例えば、Linux上のアプリケーションをWindowsに移植するためにはどのようなことを考えるべきか。
Linuxのシステムコールと互換性をもったOS(POSIXやそれに知買い物)に移植する場合と比べて議論せよ。

以下に、Windows⇔Linuxでアプリケーションを移植する際に躓く点を箇条書きで列挙する
引用:http://www.ibm.com/developerworks/jp/linux/library/l-devctrl-migration/
・デバイス・ファイル名とデバイス・パス名を比較する
・表 2. デバイス制御関数の対応
Windows Linux
CreateFile open
CloseHandle close
DeviceIoControl ioctl
ReadFile read
WriteFile write

・マイグレーションの例
表 3. #include ヘッダー・ファイル
Windows Linux
#include #include
#include
#include
#include #include
#include #include
など

-------------------------------------------------------------------------



問1
3つのプロセスA, B, Cが時間0, 5, 10秒に生成されたとする。今、Aの実行時間が10秒、Bの実行時間が15秒, Cの実行時間が15秒であるとする。
また、Aは優先度が最も低く、Bが中間の優先度、Cが最高の優先度とする。以上3つのプロセスについて、優先度順スケジューリングを用いた場合のそれぞれの終了時間を示せ(1)。
 またスケジューリングアルゴリズムとして完全に公平にプロセスをスケジューリングするアルゴリズムを用いた場合の各プロセスの終了時間を示せ。
公平なプロセススケジューリングアルゴリズムとは、実行可能なプロセスに対して公平にCPU資源を割り当てるアルゴリズムである。


(1) ※黄色く塗りつぶされたところが、現在処理中のプロセス
優先度 生成される時間 実行時間 終了時間(秒)
プロセスA 低 0 10 45
プロセスB 中 5 20 40
プロセスC 高 10 15 25

現在の時刻→ 0 5 10 15 20 25 30 35 40 45 50


(2) ※黄色く塗りつぶされたところが、現在処理中のプロセス
優先度 生成される時間 実行時間 終了時間(秒)
プロセスA 低 0 10 17.5
プロセスB 中 5 20 45
プロセスC 高 10 15 42.5

現在の時刻→ 0 5 10 17.5 27.5 37.5 42.5 45
プロセスA 5 7.5 10
プロセスB 2.5 5 10 15 17.5 20
プロセスC 2.5 7.5 12.5 15

問2 ???
20ビットのアドレス空間を持つプロセスを考える。本プロセスのコード部が20KB, データ部が40KB, スタックが60KBとする。コード部とデータ部は連続領域上に配置され、
アドレス空間の先頭から配置される。また、スタックに関してはアドレス空間の最後から配置される。
 仮想記憶システムが1KBページでページングを行っているとする。このとき、ページテーブルエントリのサイズを10Bとしたときのページテーブルのサイズを示せ。
 また、2段の階層型ページテーブルを使用する場合を考える。1段目のページテーブルが64エントリ、1段目、2段目のページテーブルエントリのサイズが10Bとする場合の
ページテーブルのサイズを示せ。



問3
デバイスドライバと割り込み処理の必要性に関して説明せよ。

デバイスドライバ:(教科書から引用)
デバイスドライバを用いることで、OSはデバイスを管理し、入出力を制御することができる。デバイスドライバの存在により、OSは単独でデバイスをサポートせずに、
同一のインターフェースで各周辺機器にアクセスすることが出来る。また、共通のインターフェースは、それを作るプログラマの負担を軽減させ、プログラムの再利用を促進させる働きがある。

割り込み処理:
キーボードからの文字入力やマウスからCPUに送られるデータは、他プロセスが終わるまでそのデータの処理を待ってるとユーザーにとって使いづらいOSとなってしまうため、
割り込み処理を用いて、他プロセスが動いていてもデバイスドライバから送られてくる重要なデータを処理出来るようにする必要がある。
例えば、ネットワークからデータをダウンロードするときは、連続的にパケットが送られてくるため、パケットを処理する割り込み処理が存在しないと、パケットを見逃してしまうことになる。


問4
メモリのバンド幅=100Mbps
I/OシステムのDMAの転送速度=1Gbps
アプリケーションが1Gbpsのネットワークにデータを転送する。
アプリケーションがいったんデータをカーネル空間のメモリにコピーしてから、DMAを用いてネットワークに転送する場合(1)と、
ユーザ空間から直接DMAを用いてデータ転送を行う場合(2)の通信性能の違いについて考察せよ。

(1)の場合では、データをカーネル空間のメモリにコピーする速度が、アプリケーションがネットワークにデータを転送する速度の1/10となるため、
カーネル空間のメモリへのデータのコピーには、ネットワークに転送する時間の10倍の時間が余計にかかり、ボトルネックとなってしまう。
このため、通信性能において(1)と(2)において比較すると、(1)の通信性能は(2)の通信性能の1/11倍となる。


問5
(a) システムコールを使う際に気をつけること:(教科書から引用)
システムコールを使うと、機械語命令のtrapにより割り込み処理を発生させ、ユーザモードでの実行からカーネルモードでの実行に切り替わり、その後再びユーザモードでのでの実行に戻る。
このため、システムコールではオーバーヘッドが大きくなりやすい。よって、システムコールを使用する際は、使用するシステムコールの数を最小限に抑え、1回の呼び出しでできるだけ多くの
作業をさせるように心掛ける。

(b) Linuxのシステムコールで出きることを5つ挙げ、名称とともにそれぞれ30文字程度で説明する。(教科書から引用)
名称 説明
open ファイルまたはデバイスをオープンする。
read オープンされたファイルまたはデバイスからデータを読み取る。
write ファイルまたはデバイスに書き込む。
close ファイルまたはデバイスをクローズする。
ioctl デバイスドライバに制御情報を渡す。
他にも、wait, fork, exec, killなど。


問6
(1)ソケットによるプロセス間通信を行う場合、クライアントとサーバーは、accept, bind, connect, listen, read, socket, writeといったシステムコールにより構成される。
クライアント側とサーバー側におけるこれらのシステムコールの順番を決め、それぞれの役割を説明せよ。そのとき、各システムコールの引数にsockfd等のようなソケット記述子を埋めなさい。
※ gethostbynameやgetservebyname等は省いても良い。エラー処理も省いてよい。

(ストリームソケットの場合) PPTから引用
時系列 Client Server
↓ ソケットの生成:socket(domain, type, protocol) ソケットの生成:socket(domain, type, protocol)
↓ [ソケットへの名前付け:bind(socketfd, my_addr, addrlen)] ソケットへの名前付け:bind(socketfd, my_addr, addrlen)
↓ 接続受け入れ準備:listen(socketfd, backlog)
↓ 接続要求の発信:connect(sockfd, serv_addr, addrlen) ----> 接続要求許可:accept(sockfd, client_addr, addrlen)
↓ データ送受信:read/write(sockfd, buf, nbytes) <---> データ送受信:read/write(sockfd, buf, nbytes)
↓ ソケットの除去:close() ソケットの除去:close()

(2)システムコールselect()はどのような場合に使われるのか。
Int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *errorfds, struct timeval *timeout)
※教科書P671より引用
selectシステムコールを使うと、同時に複数の低水準ファイルデスクリプタを対象に入力データの到着、または出力の完了を待つことが出来る。
これにより、端末エミュレータプログラムでselectを使えば、なにか処理すべきことが発生するまでの間、プログラムのブロックが可能になる。
同様に、クライアントサーバーシステムでは、オープンされた複数のソケットを対象に要求を待つことによって、1つのサーバーで複数のクライアントを処理できるようになる。


問7
将来のOSはどのように進化していくと考えられるか? 400持程度で自分の考えとその根拠を述べよ。
以下、エッセイの参考にでも。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1112635156?fr=rcmd_chie_detail
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1310902458
http://www.future-planning.net/x/modules/news/article.php?storyid=1724
http://www.emcp.com/intro_pc/reading4.html (英文)


---------------------------------------------------------------------------------


オペレーティングシステム
Report No.1


問題1 オペレーティングシステムがアプリケーションプログラムに対して提供するインターフェースの重要性を2つ述べよ。
一つ目の重要性は、プログラマがハードウェアのことをあまり意識しなくてもプログラミングできるようにすることである。これにより、プログラマがプログラミングするための手間を大幅に削減することが出来る。
 二つ目の重要性は、アプリケーションソフトの互換性を保障することである。具体的には、命令体系が同じであるようなマイクロプロセッサやOSを搭載したコンピュータ同士では、アプリケーションソフトを改変しなくては同じ動作をさせることである。具体的な具現化の方法としては、C言語の#defineを利用して、OS毎に実行するソースコードを変更させることで具現化できる。これにより、プログラマが、プログラムを移植する際に被る手間を削減することが出来る。



問題2 各自が聞いたことがあるOSの名前を4つ述べ、その特徴を説明せよ。
OSASK:OSの実行効率向上を追求したOS。実行効率を上げるため、低級言語を用いてプログラムされているところも比較的多い。
Ubunto:Wubiというインストーラを使うことで、UbuntoのファイルシステムをWindowsと同じものにすることが出来、パーティション等の作業を行わなくても、簡単にWindowsとUbuntoのデュアルブートを実現できるようになるOS。インストールやアンインストールもWindows側から行うことが出来る。
Knoppix:CDやDVDから起動することが出来る。また、ハードウェアを自動で認識してくれるので、例えば、Knoppixから他OSで生成したファイルにアクセスすることができる。
Windows:OS市場で最も高いシェア率を持つOS。新旧の互換性に優れている。
Macintosh:ハードウェア設計とOS開発を同時に手がけていて、ハードとソフトとの統一感に優れている。



問題3 もし、OSが使用できなかった場合、ユーザプログラマが記述する必要があるプログラムはどのように変わってくるのか200字程度で説明せよ。
 OSが使用できない場合は、OSが提供するAPIを使用することができないので、CPUの提供する機能以外は使用することができない。具体的には、外部ハードウェアを扱うことができなくなり、マウス操作を感知する関数や、キーボードからの入力を感知する関数、また、画面に文字を出力する関数などが使えなくなる。加えて、OSの提供するABIも使えなくなるため、例え命令体系が似ているマイクロプロセッサであった
としても、プログラムを移植することができなくなる。



問題4 C言語を実行する場合にスタックはどのように使用されるのか?特に、Cの関数を呼び出すときにスタックがどのように使用されるかに関して説明せよ。
 スタックは、現在レジスタに格納されている値を、FIFOなどの方式を用いて一時的に非難させるために用いられる。具体的な使用例を挙げると、C言語のプログラムを実行して、関数を呼ぶ処理が行われるとき、その関数が呼ばれる直前のレジスタをスタックに非難させ、関数を実行し終えた後に、スタックに入っている非難させた値をレジスタに戻してあげることになる。こうすることで、どのような関数を呼び出したとしても、使う予定のレジスタが書き換えられるというような危険性がなくなる。



問題5 キャッシュメモリと命令パイプラインに関してそれぞれ100字程度で説明せよ。
キャッシュメモリ:記憶装置の一つで、メインメモリとレジスタとのアクセス速度の格差を緩和させるためのメモリである。レジスタほどCPUに近くはないがメインメモリほど離れているわけではない。このため、アクセス速度は、レジスタ>キャッシュ>メインメモリとなり、記憶容量はメインメモリ>キャッシュ>レジスタという順になっている。

命令パイプライン:CPUの処理速度を高速化する方法で、LOAD命令やSTORE命令に必要なphaseを固定長にすることで、CPUが行う様々な命令を並列的に処理することができる。現在、ほとんどのCPUがこの方法を用いて命令を実行している。



問題6 コンテキストスイッチとプロセススケジューリングに関してそれぞれ100字程度で説明せよ。
コンテキストスイッチ:CPUの状態を保存・復元させて、複数のプロセスを1つのCPUに割り当てること。マルチタスクOSのように、複数のプロセスが存在するときには、複数のプロセスを同時進行しているかのように見せる必要がある。しかしながら、CPUは限られた数しかないため、1つのCPUで各プロセスを同時に扱うことができない。このため、CPUの状態を保存・復元させ、各プロセスを少しずつ処理していくことで、ユーザに対してあたかも複数のプロセスを同時進行しているかのように見せることができる。

プロセススケジューリング:CPUに効率よくプロセスを割り当てること。どのようなときにコンテキストスイッチを使い、次にどのプロセスをCPUに割り当てるのかによって、システム全体にスループットや、リアルタイム性に変化が生じる。具体的にいえば、ネットからの膨大な量のパケットを高速に処理しなくてはいけない場合、パケットの取りこぼしを避けるため、CPUに他のプロセスを割り当てることが困難になる。しかしながら、CPUに



問題7 プログラムを実行する上で、プログラムカウンタとスタックポインタの役割を100字程度で説明せよ。
プログラムカウンタ:CPU内部にあるレジスタの一つで、次に実行する命令のアドレスが入っている。1つの命令が終わると、固定された値を現在のプログラムカウンタに加算する。このとき、プログラムカウンタの指すアドレスが次に実行する命令のアドレスとなる。

スタックポインタ:CPU内部にあるレジスタの一つで、スタックポインタに格納されている値は、今扱っているスタックのトップの場所を指している。例えば、プログラムから違うプログラムを呼び出すとき、プログラムカウンタの値をスタックポインタに詰め込むことで、呼び出されたプログラムから元いた番地に戻ることが出来る。



問題8 プログラムを実行するときに、どのようにメモリ空間が利用されるかを100字程度で説明せよ。図を使用してもかまわない。
プログラムを実行するとき、メモリ空間からそのプログラムの実行に必要なメモリ容量を確保する必要がある。このとき、メモリ空間上でフラグメンテーションが起こっていた場合は、「連続して空いているメモリ空間≧確保したいメモリ容量」の場所をメモリ空間の中から探し出す。条件にあう場所を発見したら、その場所を使ってプログラムの実行を行う。



問題9 ユーザ空間とカーネル空間の2つのメモリ空間が存在する理由を100字程度で説明せよ。
カーネル空間とユーザ空間を分けることで、ユーザ空間を使ってカーネル空間の内容を書き換えられないようにすることが出来る。これにより、悪意をもってカーネルを破壊しようとするプログラムから、カーネル空間におかれている内容を守ることが出来る。



問題10 10年後のコンピュータがどうなっていると思われるか各自の意見を述べよ。また、そのコンピュータは20年後のコンピュータとはどう違うと予測するか?
ムーアの法則から、10年後にはマシンのスペックが少なくとも約7倍向上することが予想される。加えて、様々なモノに組み込み系の技術が使われ、色々なモノが電子化されていくと考えている。
20年後には、電流ではなく光を使ったCPUが使われ、CPUの処理速度は今よりも格段に向上すると考える。加えて、様々なモノに組み込まれるOSが規格化され、組み込み系ソフトの入っているモノ同士の通信が容易になると思う。



参考文献:
IT用語辞典 http://e-words.jp/
IT用語辞典バイナリ http://www.sophia-it.com/
babylon http://www.babylon.com/
Yahoo! Japan 知恵袋 ”どうなる予想!20年後のパソコンのスペック&OS…”
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1112635156

0 件のコメント: