----- OS 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の状態を保存・復元させて、複数のプロセスを１つのCPUに割り当てること。マルチタスクOSのように、複数のプロセスが存在 するときには、複数のプロセスを同時進行しているかのように見せる必要がある。しかしながら、CPUは限られた数しかないため、１つのCPUで各プロセス を同時に扱うことができない。このため、CPUの状態を保存・復元させ、各プロセスを少しずつ処理していくことで、ユーザに対してあたかも複数のプロセス を同時進行しているかのように見せることができる。
プロセススケジューリング：CPUに効率よくプロセスを割り当てること。どのようなと きにコンテキストスイッチを使い、次にどのプロセスをCPUに割り当てるのかによって、システム全体にスループットや、リアルタイム性に変化が生じる。具 体的にいえば、ネットからの膨大な量のパケットを高速に処理しなくてはいけない場合、パケットの取りこぼしを避けるため、CPUに他のプロセスを割り当て ることが困難になる。
問題7 プログラムを実行する上で、プログラムカウンタとスタックポインタの役割を100字程度で説明せよ。
プログラムカウンタ：CPU内部にあるレジスタの一つで、次に実行する命令のアドレスが入っている。１つの命令が終わると、固定された値を現在のプログラムカウンタに加算する。このとき、プログラムカウンタの指すアドレスが次に実行する命令のアドレスとなる。
スタックポインタ：CPU内部にあるレジスタの一つで、スタックポインタに格納されている値は、今扱っているスタックのトップの場所を指している。例えば、 プログラムから違うプログラムを呼び出すとき、プログラムカウンタの値をスタックポインタに詰め込むことで、呼び出されたプログラムから元いた番地に戻ることが出来る。
問題8 プログラムを実行するときに、どのようにメモリ空間が利用されるかを100字程度で説明せよ。図を使用してもかまわない。
プログラムを実行するとき、メモリ空間からそのプログラムの実行に必要なメモリ容量を確保する必要がある。このとき、メモリ空間上でフラグメンテーションが 起こっていた場合は、「連続して空いているメモリ空間≧確保したいメモリ容量」の場所をメモリ空間の中から探し出す。条件にあう場所を発見したら、その場所を使ってプログラムの実行を行う。
問題9 ユーザ空間とカーネル空間の2つのメモリ空間が存在する理由を100字程度で説明せよ。
カーネル空間とユーザ空間を分けることで、ユーザ空間を使ってカーネル空間の内容を書き換えられないようにすることが出来る。これにより、悪意をもってカーネルを破壊しようとするプログラムから、カーネル空間におかれている内容を守ることが出来る。
問題10 10年後のコンピュータがどうなっていると思われるか各自の意見を述べよ。また、そのコンピュータは20年後のコンピュータとはどう違うと予測するか？
ムーアの法則から、10年後にはマシンのスペックが少なくとも約7倍向上することが予想される。加えて、様々なモノに組み込み系の技術が使われ、色々なモノが電子化されていくと考えている。
20年後には、電流ではなく光を使ったCPUが使われ、CPUの処理速度は今よりも格段に向上すると考える。加えて、様々なモノに組み込まれるOSが規格化され、組み込み系ソフトの入っているモノ同士の通信が容易になると思う。
---------C言語の復習とOS概要---------
問題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の状態を保存・復元させて、複数のプロセスを１つのCPUに割り当てること。マルチタスクOSのように、複数のプロセスが存在 するときには、複数のプロセスを同時進行しているかのように見せる必要がある。しかしながら、CPUは限られた数しかないため、１つのCPUで各プロセス を同時に扱うことができない。このため、CPUの状態を保存・復元させ、各プロセスを少しずつ処理していくことで、ユーザに対してあたかも複数のプロセス を同時進行しているかのように見せることができる。
プロセススケジューリング：CPUに効率よくプロセスを割り当てること。どのようなと きにコンテキストスイッチを使い、次にどのプロセスをCPUに割り当てるのかによって、システム全体にスループットや、リアルタイム性に変化が生じる。具 体的にいえば、ネットからの膨大な量のパケットを高速に処理しなくてはいけない場合、パケットの取りこぼしを避けるため、CPUに他のプロセスを割り当て ることが困難になる。
問題7 プログラムを実行する上で、プログラムカウンタとスタックポインタの役割を100字程度で説明せよ。
プログラムカウンタ：CPU内部にあるレジスタの一つで、次に実行する命令のアドレスが入っている。１つの命令が終わると、固定された値を現在のプログラムカウンタに加算する。このとき、プログラムカウンタの指すアドレスが次に実行する命令のアドレスとなる。
スタックポインタ：CPU内部にあるレジスタの一つで、スタックポインタに格納されている値は、今扱っているスタックのトップの場所を指している。例えば、 プログラムから違うプログラムを呼び出すとき、プログラムカウンタの値をスタックポインタに詰め込むことで、呼び出されたプログラムから元いた番地に戻ることが出来る。
問題8 プログラムを実行するときに、どのようにメモリ空間が利用されるかを100字程度で説明せよ。図を使用してもかまわない。
プログラムを実行するとき、メモリ空間からそのプログラムの実行に必要なメモリ容量を確保する必要がある。このとき、メモリ空間上でフラグメンテーションが 起こっていた場合は、「連続して空いているメモリ空間≧確保したいメモリ容量」の場所をメモリ空間の中から探し出す。条件にあう場所を発見したら、その場所を使ってプログラムの実行を行う。
問題9 ユーザ空間とカーネル空間の2つのメモリ空間が存在する理由を100字程度で説明せよ。
カーネル空間とユーザ空間を分けることで、ユーザ空間を使ってカーネル空間の内容を書き換えられないようにすることが出来る。これにより、悪意をもってカーネルを破壊しようとするプログラムから、カーネル空間におかれている内容を守ることが出来る。
問題10 10年後のコンピュータがどうなっていると思われるか各自の意見を述べよ。また、そのコンピュータは20年後のコンピュータとはどう違うと予測するか？
ムーアの法則から、10年後にはマシンのスペックが少なくとも約7倍向上することが予想される。加えて、様々なモノに組み込み系の技術が使われ、色々なモノが電子化されていくと考えている。
20年後には、電流ではなく光を使ったCPUが使われ、CPUの処理速度は今よりも格段に向上すると考える。加えて、様々なモノに組み込まれるOSが規格化され、組み込み系ソフトの入っているモノ同士の通信が容易になると思う。
---------C言語の復習とOS概要---------
システムコール = OSを呼び出すための関数
普通は、OSのデータ構造にはアクセスできない。
システムコールを介してのみ、アクセス可能。
Index
・カーネルの中身
・C言語の復習
-header, structについて
C言語とは
OSを作るのに適切な言語。
低水準programming
assembly言語はCPU毎にソースコードが違う
→移植するときは全部変更しなくてはいけない。
C言語の場合、大抵使いまわせる。
→移植するときの楽。
C言語には予約語が一杯ある。
→JAVAに似ているが、CLASSの概念はない。
C言語は分割しても一括してもどちらでも大丈夫。
→どの関数をどのファイルに置くかを考える必要がある。
Structure
-宣言部
-main関数
-そのほかの関数
C言語を使うときは、型のbyte数を把握する必要がある。
JAVAの"NEW"に近いallocateをするためには、
sizeof(型）をやって自分でbyte数を確保する必要がある。
・auto(自動変数）
関数内部の変数とか。
関数から出たら、解放する。
・static(静的変数)
呼び出すかどうかに関わらず、いつでも存在する。
EX:staticで大きい配列はダメ
・Register(レジスタ変数）
register上に置くので、早くなるかもしれない。
現在は、compilerが勝手にやってくれるので、
使っても無視されることがしばしばある。
・exterm(外部参照変数)
プログラムの外に変数を書く。
グローバル変数 = static変数
main()内はauto変数
関数内の変数をstaticにすると、以前使ったときの
結果が残っている。
int foo(void)
int main()
引数の数は自分で数える。
GNU gccは良いが、他のコンパイラには
引数をカウントしないものもある。
→clashしてdownする可能性がある。
・prototype宣言
int foo(int);
compilerがcheckしてくれる。
Ex：型のミス
void foo(void);
int x = foo;
---------------------------------
・C言語のsequence
C sourve(*.c)
↓
↓ preprocessor
↓
preprocessor後のsource(*.i)
↓
↓ C compiler
↓
Object file
↓ linker
↓←←←←←←library
↓
実行ファイル
・header
#include "queue.h"
↓
preprocessorがlibraryの中にある"queue.h"を
ソースファイル内に展開する。
・マクロ展開
#define MAX 10
MAXを10に置き換える
#define putchar(x) fputc(x, stdout)
xは引数としてマクロ展開する。
用途：何行も使うものをまとめるときに使う。
「何故methodにしないのか」
methodの呼び出しのために、サイクルカウント値を消費してしまい、
動作が遅くなるから。
OSでは、致命的。C言語では重要な部分。
→overflowはなるべく少なくする。
・他の記号
#include"hoge.h"
#if DEBUG == TRUE
print("value = %d\n", val);
→hoge.hが
#define DEBUG TRUEならば
print文がマクロ展開される。
→#include"hoge.h"の文があるかどうかで
実行の有無がわかる。
↓
debugに便利！
・gcc -DTEST ~~~
オプションの-DTESTがあれば
#ifdef TEST以下の文が展開
そうでなければ
#else以下の文が展開される。
用途：
#ifdef LINUX #else WINDOWS
Linux用とwindows用にわけてマクロ展開させることが可能。
・#incledeファイルの場所
→/usr/include/
or
/usr/include/sys/
and
/usr/include/linux/
・include fileのpathを指定したいとき
gcc -I/usr/local/hoge.h
・ifdef~else~endif
#ifdef MAIN
/* MAIN が #define してあったらここの部分がコンパイルされる。#define されていなかったらここの部分は無視される */
#else
/* MAIN が #define されていなかったらここの部分がコンパイルされる。#define してあったらここの部分は無視される */
#endif
・Compilerとlink
実行ファイルの中身
hm -g a.out | grep't'
00001c64 T __darmin_~~~
00001d44 T _main
0000166c T start
プログラムが実行させるときは、まず最初にstartを探す！
startの位置をprogram counterに設定する。
※start -> _mainまでに
色々と初期化している。
mainかんすを呼ぶためにlibraryの中で、
色々と初期化されている。
・動的リンク
必要になったときにlibraryを呼ぶ
複数のプログラムから同じlibraryを使う場合、
共有ライブラリにする
*.so (shared object)
・コンパイラの最適化
program -> binaryにする場合
defaultで -O2 optionが入る。
→-O3以上にしても、あまり結果は変わらない。
・library
-lnew 自分が定義したもの？
-L/usr/local/mylibs
↑このdirectoryの中から優先的に探しだしてlinkする。
・libraryを作る場合
gcc -c newlib.c
ar rcs libnew.a newlib.o
で"new"ライブラリにnewlibを追加
nm/usr/lib/libc
・静的リンク
全部取り込む
→programが大きくなりやすい！注意！
・構造体
データ構造のみを定義。
struct tag名{
type member1;
type member2;
};
struct log{
char time[10];
long ch0;
long ch1;
};
↑この場合
1 structure = 10B+4B+4B = 18B
struct log logger1, logger2;
typedef struct{
~~
~~
~~
}LOG;
↓
LOG logger1;
LOG logger2;
→structを宣言しないで済む。
typedefが主流。
・Pointer
※2000番地に10が入っているものとする。
int a;
int *p;
p=2000;
p=&a;
int *p;
int c = *p;
→integer型のpointerに10が入る。
func(&val);
→OSがCで書かれている理由の一つ
→pointer
予断：javaの場合classはcall-by-referenceになる
☆文字列の最後は必ず'0'が入っている。
"abcd"
↓
'a'+'b'+'c'+'d'+'0'
while(*str) str++;
→文字列を読み終わったら0が入る
→偽になる→while文終了
予断：NULL = 0
・配列とポインタ
&array[0] と arrayは同じ意味
++arrayとすると
array[1]から読み込まれる。
↓
データ構造の文だけincrementされるから。
→箱のサイズは気にしなくてもよい。
・character型の場合
char str[] ⇔ char *str
同じ
一般的に、*pには乗算や除算は使わない
structureをコピーするかpointerで指定するかで、
作業効率が大幅に変わってくる。
struct hm_time{
int hour;
int minute;
};
アクセスするには２つの方法がある。
①time.hour or time.minute
②void addtime(struct hm_time *t1, struct hm_time *t2){
t1->hour += t2->hour; ←メンバーアクセスと呼ぶ
t1->minute += t2->minute;
}
・command line
javaとはちょっと違う。
main(int argc, char argc[]){~~~
argc = コマンド(1)+引数の数
argv[] = コマンド及び引数へのポインタ
・pointerの危険性
異常終了or迷子のポインタ
エラーのとき
int *p;
int c = *p;
malloc <- 動的に領域を割り当てる。 malloc(10) = 10byte確保する ↑うまく確保できない場合は0を返すので if文を使ってエラー処理することも可能！ ☆確保したものはfree()で解放すること！ 解放し忘れると、メモリがﾄﾞﾝﾄﾞﾝ減ってくる！
-----------------------
memo@file system, device driver etc. 2008/06/17
・ファイル名
ファイルを識別するためのString名からID名へ変換する
例：/a/b/c→101020
・ファイル内のポインタ
論理アドレスから物理アドレスへの変換
↑上記の二つをどうやって実現するのか？
・ファイルシステム概要
ファイルの詰め込み方にはいろんな方法がある
例：
Case 1. 頭からファイルを詰め込んでいく方法
→deflagmentationが起こるのであまり使われない。
Case 2. 固定長のブロックに分けてファイルを詰め込んでいく方法、各ブロックは次のブロックを指すポインタを持っている
→しかしsequencialにしかアクセスできない！
Case 3. 自分のファイルがどこに保存されているかを格納しているところがあり、それを参照して、ファイルの格納場所を知る(←これをディレクトリという。)
→これが最も一般的なやり方
cf.ページテーブル
☆directoryをどうやってストレージデバイスにおいていくか、が実現上大きな問題にある。よって、それぞれのファイルとdirectoryをどうやって実現していくか、をこれから説明する。
・Unix file system
API概要(OSが実現するAPI)
fd = open((file,mode)
read/write(fd, buf, size)
…とか色々
・ファイルシステム全体の概要
全体の構造：
スーパーブロック→inode list→ファイルブロック(固定長に分けたブロックのこと)
- 各用語の意味
i-node table: i-nodeを表形式にまとめたもの？
i-node: 各ファイルごとに一対一対応するデータ構造。
スーパーブロック： ファイル全体を管理するデータ構造
i-node list： 全体の数とかを管理する
ファイルへのアクセスはメモリへのアクセスと比べると時間がかかる。
一度オープンしたファイルに関しては一旦メモリ上にコピーされる。
ファイルデータ構造というのは、readすると順番にブロックが呼び出されていく。どこから呼び出されていくかはOSが知っている。
プロセスデータ構造：プロセスごとに存在し、ファイルデータ構造にある内容をファイルディスクリプタ内の情報に変換する？つまり、ファイルディスクリプタの番号はプロセスごとに閉じている。
ストレージは非常に大きい。よって、メモリ上に持っていくことは出来ない。
しかし、一部のファイルに関してはメモリにコピーしていることがある。
ストレージデバイスで、良く使う部分のみがメモリ上にコピーされる。
・i-nodeとブロックの関係
i-node内部構造：
内部構造は固定長で、
"所有者、アクセス権、アクセスタイム、変更時間、10個のエントリ、3個のエントリ"
が含まれている。ファイルシステムは何年も使われて、安全が保障されてから人に使われる。
よって、開発から実用まで10年ぐらいのスパンがある。
１０個のエントリ：それぞれが独立に10個のブロックを指している。
３個のエントリ：それぞれが独立に３個の間接ブロック(=中身はエントリ)を指していて、そのブロックはそれぞれまた別なブロックを指している。
一つのブロックには256個のエントリが入る。よって、
10K + 256*1K + 256*256*1K + 256*256*256*1K
よって、ファイルのサイズが大きくなればなるほど深い層までもぐりこまなければならないのでperformanceは低下する。
i-nodeの数だけファイルが作られるので、ファイルの上限はi-nodeの数に制限される。
・Unix filesystem(4)
ファイルデータ構造は、複数のプロセスから共有されることがある。
例：プロセスAがオープンしたファイルデータ構造はプロセスBからも共有される
forkしたときに、現在オープンしたファイルディスクリプタは共有される。
オフセット：現在書き込みしているところの次はどこに書き込むのか、という情報が格納されている。
(ちなみに、Windowsでは、fork関数は使えない)
・スーパーブロック
スーパーブロックはファイルシステム全体を管理するデータ構造。
一番最初に読み込まれる。
スーパーブロックを読み込むことで分かること：
- ブロックサイズをどうするか？４K?１K?
- どのブロックが現在使われているか？
- 新しくブロックを割り当てる場合、空いているところをビットマップから判断し、割り当てる。
- 名前をどうやってi-nodeに変換するか？
- i-nodeが分かったとき、その後どうやってファイルにアクセスするか。
・read/writeとファイルシステムの関係
ファイルをオープンすると、今アクセスしようとしているi-nodeを認識する。
それをi-node tableのコピーする。
ファイルデータ構造にallocationして、プロセスデータ構造からファイルデータ構造に書き込む。
よって、処理の手順は以下のようになる
1. ファイルデータ構造のoffsetを見て、次に読み込む場所を認識。
2. i-nodeテーブルを見て、i-nodeの何バイト目を見るかを決める。
3. [10Kより小さかった場合] ブロックを発見。
[10Kより大きかった場合] 間接ブロックを辿っていく。
rooter i-node
[例] i-node:3,5,7,19,17と書いてあるとする。
頭は"/"から始まる
"/" "usr"=3
. ＝自分
..＝親のディレクトリ
"vmunix" = 10
→ファイルを直接アクセスしている。
ファイルのブロックが順番にアクセスされる。
usr = 3
usrと認識すると i-node 3を見る。
3は"."を指しているので、親のディレクトリに行く。
例：/usr/readmeをopenする
ディスクからi-node tableの必要なブロックを全部呼び出す。
readmeを探し、7が見つかったので、
i-node 7の指すファイルを全部呼び出して、
前から順々にアクセスしていく。
よって、
ファイル名から、
i-nodeの指すファイルを探して、
ファイルをopenする。
・ハードディスクが複数合った場合はどうするのか？
ディレクトリ+ブロックが入っている。
あるハードディスクのあるディレクトリを、他のハードディスクをマウントするようにする。
mount table
mntはディスクテーブルにある。
mntを見つけたら、ディスクBをアクセスし始める。
mnt=mount
ディレクトリ自体は一つのtree構造であることには変わらない。
・物理的なディスクの構造
ハードディスク上にファイルシステムを作る場合を考える。
ディスクは複数ある。
ディスクは同心円の円がたくさん入っていて、そこにデータがたくさん入っている。
その輪の中にデータを入れていく。
それぞれの輪の部分をトラックという。
トラックを固定長に分割した部分をセクタという。
各ディスクのことをシリンダという。
シリンダ->トラック->セクタ
アームで読み込む。アームは前後に動く。
ディスクが回っていて、アームと接触した部分を読み込む。
よって、読み込むまでの時間は、アームのところに読み込みたいセクタまでディスクを回してあげて、完了するまでの時間。
→読み込み時間＝アームの前後に動く時間 ＋ セクタを指定した位置に持っていくまでの時間
よって、ハードディスクの読み込みは比較的遅い。
・バッファキャッシュ
キャッシングとプリフェッチ。
prefetch:次に読み込むものが分かっている場合は、事前にフェッチしておくこと。
ファイル全体をメモリにコピーしていくことが多い。
使用例：ファイルは頭から順番にアクセスしていくことが多いことを利用する。
具体例：Unixは次のブロックを指していたら、その次のブロックがアクセスされる場合が多いので、事前にメモリ上に呼び出しておく。
→CPUの処理効率が向上する。
タイムスタンプ：いつアクセスされていたか。
キャッシュの管理アルゴリズムは、タイムスタンプをつけてLRUで管理している。
・ディスクの書き出し
通常、バッファキャッシュで変更する時間間隔は３０秒から１分に１回。
これにより、同じバッファブロックに対して何度も何度も書き出すことを制限することが出来る。
30秒に一回変更されているブロックをディスクに書き出す。
ディレクトリやスーパーブロック, i-nodeの変更はすぐにディスクに書き出す。
→システムがファイルへ書き出す前にクラッシュしたとき、ファイルシステム全体が壊れる可能性がある。
→ファイルのデータ構造をいじくるときは、常にファイルシステムの一貫性を保てるようにする。
・ディスクスケジューリング
FIFOスケジューリングは行ったり来たりする。
メカニカルに動く。
アームの動く速度は遅いので、アームの動く量を最小にしたい。
→C-SCANというアルゴリズムがある。
C-SCAN:
1. いくつかのタスクを溜めておいて、ソートする。
2. ディスクへ書き出す時間になったら、頭から尾に向かって順番にアクセスしていく。
3. その後、アームを頭の位置に戻す。
他のもディスクスケジューリングアルゴリズムがある。
今は、もうちょっと頭のいいアルゴリズムも存在する。
☆ハードディスクのアクセスには物理メモリと違って、
トラックがどこにあるかによってアクセス時間が大幅に違う。
自分のアクセスしたいデータがトラックのどこにあるのかを認識して、
最小限のアームの動きでアクセスする必要がある。
・分散ファイルシステム
リモートにあるマシンに対して同じプログラムを使いたいときは
アクセス透過性と位置透過性を考える必要がある。
アクセス透過性：リモートファイルもローカルファイルも同一のAPIを用いてアクセス可能
位置透過性：ファイル名にマシン名が含まれていない。
→どこのマシンにあるかを気にせずアクセスできる！
・NFS
network file systemの略称。しかしnetwork file systemとは滅多に言わない。
☆プログラマーから見て、あたかも普通にディレクトリをアクセスできるかのようにすることが大切！
→OSは、ネットワーク上の複雑な処理をユーザから隠蔽することが大事！
・I/Oの種類
各I/Oの関係↓
プログラム⇔デバイスドライバ⇔デバイス
デバイスの種類はたくさんある！
デバイスドライバが出来るだけ隠蔽してあげることが大切。
・バスの種類
PCI
ISA
SCSI
…たくさん！
・デバイスドライバ
デバイス独自のプロトコルの使用にあわせて作り、出来るだけ簡略化し、隠蔽する。
デバイスドライバ：各デバイスのアクセスプロトコル(デバイスの制御手順)を実装する。
デバイスドライバはデバイスを自動的に発見し、どのようにアクセスするかを自動的に決定する。
cf:USBの挿入
USBを差し込む→OSが認識→if文分岐
1. [デバイスドライバがない場合] デバイスドライバをインストールする。
2. [デバイスドライバがある場合] USBを読み込む
昔は数百行だったが、今は数千行必要になる。
→デバイスドライバを作る人はこれから増えるかもしれない。
☆重要なこと
デバイスとデバイスドライバのやり取りをどうするかを決めること。
・デバイスアクセスの方法
I/Oｲﾍﾞﾝﾄの通知
- error通知、利用可能データ通知、状態通知
- ポーリング：CPUからデバイスに対して使用可能か調べる？
- 割り込み
・データの転送
デバイスとCPUのデータ転送方法を決定する。
- read/write
- programmable I/O
- DMA(Direct Memory Access)： ある程度の長さのデータを一括して転送する
・I/O port
- メモリ空間と異なるI/O空間
- 各デバイスはI/O空間上にポートを割り当てられる
- ポートをアクセスすることによりデバイスとメモリ間のデータ転送が行われる
- I/Oポートをアクセスするための特注名命令が必要
→x86の場合、in, out命令
・Memory mapped I/O
- デバイスの一部をメモリとしてみることが出来る。
- メモリアクセスとして実現されるが、アクセスコストが異なる。
・ポーリング CPUからデバイスに対して以下のことを確認する。
- データの入力が可能となる
- データの出力が可能となる
- 処理の終了
あるデータの書き出すが起きているときには、それが終わるまでは次の書き出しを禁止する。
ポーリングを使って、"毎回毎回処理が終わったかどうか"を聞く。
例：
while(flagPort != READY); // データの書き出しが終わるまでwhile文でループし続ける
mem = dataPort; // データの書き出しが終わったらデータをメモリ領域に移す
dataPort:どっかのレジスタ
注意：ｲﾍﾞﾝﾄの発生などをポーリングで待つことはCPUの無駄遣い
他の処理の合間にポーリングをすることが可能だが、システム全体の構造がクリアではなくなる
よって、ポーリングを使用するときは、結果が分かるまでの時間が短い場合のみ。
例： 20μsならよいが、20nsでは無駄。
・割り込み interrupt
割り込みの流れ
1. (通常の場合) CPU→要求(I/O port, memory)→デバイス
2. (割り込みの場合) CPU← 割り込み ←デバイス
↑ポーリングによるCPUの無駄遣いを防ぐことが出来る
割り込み:
デバイスからCPUに対して何かを呼び出したいとき、
今実行しているプログラムを中断して割り込んだデバイスの処理をさせるときに使う。
・ 割り込みハンドラ
以下のような処理が割り込み処理に当たる
- 新しく入力された
- エラー処理
- デバイスからの通知処理
番号ごとに違う番号を登録する
例：割り込みベクタ↓
IRQ0 = clock handler
IRQ1 = disk handler
IRQ2 = network handler
IRQ3 = trap handler: page fault, system call, bus error etc.
各デバイスはIRQの何番を用いるか知っている。
場合によっては、割り込みベクタを複数のデバイスで共有することが出来る。
→割り込み処理でもらってきた値を評価して、どのデバイスの割り込みかを認識する。
これにより、IRQの数以上のデバイスを管理することが出来る。
・多重割り込み
割り込みが、同時系列に、複数個存在している状態のこと。
Q: 割り込み処理が実行されたときに、違う割り込みが来た場合はどうするのか？
A: 割り込みには優先度が付いている。優先度を見て割り込み処理の順序を判断。
例：(←優先度低)level2, level3, level4,...,level7(優先度高→)
levelの値が高い方が優先して処理する。
デバイスによっては、あまり長い時間放置されると破綻するものもある。
例：network driverは連続的にパケットが送信されるので、データが来たときにすぐ処理しなければならない。
・時間制約によって勝手に割り込んでくる処理がある。
割り込みの数が多いと、今実行されているプログラムは実行できなくなる。
☆未だに解決できていない課題
時間を測定する関数を使った場合、割り込み処理によって正確な値が測定できない。
割り込みハンドラを実行後レジスタを回復する必要がある。
例：
handler(){
save_register();
process_interrupt();
restore_register();
}
割り込みは割り込みようのスタックを用いる。
これにより、スタックがオーバーフローすることを避けている。
・割り込みのオーバーヘッド
割り込み処理のコストは結構大きい。ポーリングより大きいので、ポーリングを使った方が良いときも多い。
例：
web serverはデータが来る毎に割り込みが発生する。
昔は10MB/bpsだったので、そんなにCPUが早くなくても取りこぼさない。
今は10GB/bpsなので、パケット量が圧倒的に増えて、割り込みが毎回発生する。
最悪の場合、web serverが実行できずに割り込み処理しか実行されない。
→原因：割り込みハンドラの呼ばれる頻度が高い。
結果：10GB/bpsぐらいだと、CPUは有意義な計算を行うことが出来ない。 対処例：割り込みハンドラの呼ばれる頻度が高くなったら、ポーリングに切り替える。
・割り込みの禁止 システムコールの処理と割り込みハンドラ間の排他制御
cf.複数のスレッドを実行するときは排他制御する必要がある。
例：readやwriteがデータ構造をいじっているときは割り込みを禁止する。
例：
syscall()
{
割り込み禁止
排他リソースのアクセス
割り込み可能
}
注意：割り込みを禁止している時間はなるべく短くするように心がける。
→割り込み禁止期間が長いと、マウスが動かなかったり、画面が表示されなかったりと、UIに悪影響を及ぼすから。
・Direct Memory Access
各デバイスはメモリから直接データをやり取りする。
bufPort: buffer size
sizePort:送るべきデータのサイズ
cmdPort: WRITEスタート
CPUとは関係なく実行される
・サイクルスティーリングとは？
メモリとCPUを繋ぐバスがある
DMAデバイスはバスを使う。
→バスは共有されている。同時には使えない。
→DMAが動いているときはパイプラインが使えない
結果：DMAはCPU上で動いているプログラムのパフォーマンスを低下させる可能性を持っている。
かつ、CPUとは無関係に動いているので、どのくらい低下するのか予想するのが難しい。
デバイスからDMAを使ってデータを物理メモリの呼び出されたとき、キャッシュの中をクリアする必要がある。
→DMAをたくさん使うとパフォーマンスが低下する。
・物理空間か仮想空間か
デバイスが、MMUを解さずメモリをアクセスする場合に、デバイスにバッファのアドレスを教えるときは物理メモリアドレスを教える必要がある。
CPUから見えるアドレスとデバイスから見えるアドレスは違うので、マッピングする必要がある。
・TLB管理 経緯：ページテーブルによる仮想アドレスと物理アドレスの変換のオーバーヘッドを減少するため、TLBが導入された。
☆割り込みを考えるとTLBもパフォーマンスを低下させる可能性を持っている。
TLBはコンテキストスイッチが起こるたびにクリアする必要がある。
ページテーブルの変更はTLBに影響を及ぼさない。
以下の場合において、TLBをクリアする必要がある。
- I/Oデバイスが新しくマップかアンマップされたとき
- 新しい仮想エリアが新しくマップかアンマップされたとき
- プロセスのコンテキストスイッチが発生したとき
・ユーザから見たI/Oインターフェース
/dev/device0 10 1
↑このファイルをオープンするとメジャー番号(10)とマイナー番号(1)に変換する。
よって、オープンするときは、
fd = open("/dev/device", mode);
close(fd);
read/write(fd, buf, size);
ioctl(fd, cmd, arg);
何でもかんでもI/Oコマンドを定義していくと移植性が低下するので、
I/Oコマンドの定義は最小限にした方が好ましい。
・/proc
特別なデバイス。各プロセスの色んな情報を取り出すことが出来る。
例：
"文字列" 意味
"/proc/1/fd/3" プロセス1のfd3の情報を取る。
"/proc/1/mem" プロセス1のメモリ
"/proc/pci" PCIに関する情報
"/proc/modules" カーネル内にロードされたモジュールの情報
・非同期I/O readシステムコールはデータが来るまで待っている。
signalを使って非同期化する？
例：
{
signal(SIGIO,..&input_handler)..
fcntl(0, F_SETWON,..getpid());
oflag = fcntl(0, F_GETFL);
fcntl(0, f_SETFL, oflag | FASYNC);
}
・付録
PDFの"付録"にデバイスドライバのサンプルソースコードがあるので目を通しておく。
---------ファイルシステムの講義はここまで---------
---------プロセスについての講義-------
2008/06/24
プロセスとは？
・プログラムの実行形
・独立したアドレス空間とPC, SP, レジスタのセット
・現在使用中のNWソケットや読み書き中のファイルなどのI/Oデバイスの利用状況のセット。
・シグナルにより別プロセスにメッセージを送ることが可能
上記中にあるプログラム自体は単純な動作の集合に過ぎない。
単純な動作の集合から、複雑な動作になっている。
・exec族
例： execlでプロセスが変わる。
→execlのあとにプログラムを書いても意味がない。
p = path
execle = 環境変数を指定して呼び出す。
signal
interupt
signal -> required #inlude
sigaction(SICINT, &act, 0);
// just registerd
act.sa_flags = 0;
act.sa_handler = ouch(function);
例：
while(1){
printf("Hello World!\n");
sleep(1);
}
意味：1 printout per sec
脱出方法：
if you press Ctrl+c, the function ouch is called.
----------------------------
(ここらへんから突如日本語入力に不具合 orz)
pipeline： 8 bit
register： 16bit
cache： 32 or 16 it
例： "ls > aaa"
意味：output ls data into aaa
std output change dup2
opposite cat
"cat <> [understand fork and exec]
understand system call getpid, getppid getued, geteuid,...,and so on.
"ps": confirm process information running
UID = indicate who calls process.
each process have unique ID
PID = unique ID of each Process
[Flow of program]
1, "init" is called by OS(root)
-> forced to allocate memory space
almost Linux has this init program
In config file, there are a lot of programs about init.
2, init calls login program (UID = 0)
then user should input ID and password
Ex: yohei has 515 UID
3, seeing inputed ID, shell command is called
this UID is 515
if sshd has bug, root has possibility to be stolen.
※private address has more safety than global IP.
*the programs under init are supporting init program
GID is represented by 16bit integer.
getpid, getppid, getuid, getgid have no parameter.
you can fetch each ID using functions above.
・fork
implement multi process eniviroment.
copy process image when it is called.
file descriptor is also copied.
usage: "pid_t fork(void);"
including sys/types.h and unistd.h is required!
recognize program itself is parent or child
ex
pid_t new_pid;
new_pie = fork(); // stack is already copied,
if(new_pid) == -1){
// error
}else if(new_pid == 0){
// execution as a child process
}else{
// execution as a general process
}
* if fork return -1, it shows error.
* which is occurred earlier depends on then environment.
* this above means debug work is very hard!
copy on right makes cost less
wait call
how do we synchronize child process and parent process?
while shell command is running, is shell sequential?
wait = wait for finishing of whose process.
waitpid = wait for finishing of certain process.
required #include
wait function has 3 parameters.
ex
waitpid(child, &stat_val, 0);
// "child" contains child process ID.
// if child process is not finished yet, wait for finishing child process!
// if you forget to command "&", you get 0 instead of &stat_val, then you hold or system down.
// so, it is difficult to find out where is bug.
// c++ has exception function, but c does not such a exception.
// if using language has the exception function, you should use it!
// if possible, you should not call system call, because it makes bugs lower.
* OS is still a little weak, so you pay careful attention to write arguments!
*
wait: wait for the status of child is available by family
exit: By child, configure status code, and then notice what parent has finished!
-----------------------------------------
kill
kill -kill 1234
you have killed process having PID of 1234
signal; waiting for pressing any of keyboard and something like that.
alarm(5)
signal is occurred per 5 seconds.
act.sa_handler = ding;
clock_t times(struct tms *buf)
examine how much time program spends.
int system(const char *command)
forced to call command.
In homework, you must not use the system command!
putenv, getenv
reconfigure your envinment variables.
inter communication between processes
pipe, socket
pipe
In shell command
ps -Af | grep hoge
you can move result anywhere.
int pipe(int file_descriptor[2]);
[0]; // for reading
[1]; // for writing
return
0: successful
-1; failure
Case1
Parent <----> child
parent --- file_pipes[1] | file_pipes[0] --- child
parent --- file_pipes[0] | file_pipes[1] --- child
some source codes
int file_pipes[2];
if(pipe(file_pipes) == 0){
fork_result = fork()l
...
}
close(file_pipes[1]); = pipe
data_o = read(file_pipes[0], buffer, BUFSIZ); = file_pipes[0] yu child
// reading data put into buffer
you do not have to close pipe, but it has possibility to occur bugs!
so, you should close it ASAP.
let's consider PS -As | grep hoge (== 1 | 0)
grep is fetching data from 2nd parameter to end parameter.
Using dup2,
dup2(1, p[1])
Meaning: fetching pipeline[1]
dup2(0, p[0]);
Meaning: fetching pipeline[0]
kind of "ls > aaa"
cat <>
From System Call
int mkfifo(const char * filename, mode_t mode);
* this pipe is hardly used.
pipe system can be call if only two programs are related to family-child.
・setjump/longjump
#include
jump_buf ma;
// required and should be put in global domain!
longjmp(ma, -1);
// return value is -1
Ex:
key = setjmp(ma)
// key == -1
EX:
func(){
longjmp
}
main(){
sigaction
setjmp
printf("prompt = ")
read(ls, -1)
fork
wait
exec
}
"ls > a"
cat <= a ls|grep - , cntl.c fork| | | sigaction exec| dup2 | pipe | setjmp/longjmp wait| | | /bin /usr/bin ex. ls -l // search files from upper to bottom in directory. if you find out it, execute it,
---------ここまでプロセスについての講義--------
---------ソケットについての講義---------
2008/07/01
・本日の話 = ネットワークに関するシステムコール
- ソケット
- Client/Server型システムの形態
- システムコール
- 標準ライブラリ
・ソケット
※PDF参照
・クライアント・サーバ型(もっとも基本的な型)
UNIXにはもともとスレッドという概念がない。
スレッド使えるようになったのは5年前の話
プロセスをフォークすることは難しい。
cf： "Copy on Write"
→毎回毎回プロセスをフォークするとコストが大きい
→スレッド使ったり別の方式を使ったりする。
・反復サーバ型
サーバがクライアントのリクエストをリプライする。
受け取った順に処理する。
→もし、サーバの待ち時間が長い場合はサーバが無駄に動いてしまう。
→多くのクライアントからのリクエストを処理する時には向いていない。
・並行サーバ型
ファイルの流れ↓
クライアント → サーバー → (フォーク)Chile Process → クライアント
→サーバはリクエストを受け付けて、子プロセスを生成するだけですむ
→ほとんどのサーバはこの形で作られている。
ただし、スレッドに変えてもそんなにオーバーヘッドが減る分けではない。
実際にはもうちょっと複雑な処理をして、オーバーヘッドを減らしている。
・同期通信、非同期通信
- 同期通信
リクエストが帰ってくるまで動かない
ex.失いたくない貴重な情報の時
- 非同期通信
リクエストが帰ってくるかどうかにかかわらず動きつづける。
割り込みのような形でリプライを受け取る。
ex.音楽再生とか
・Unicast, Broadcast, Multicast
- unicast
1 on 1通信
- broadcast
ネットワーク上の全マシンに対して送信
e.g. DHCP
「僕はあなたのアドレスを知らないけど、あなたのIPアドレスが欲しい！」
- multicast
特定のグループへの加入者に対する同報
・ソケット通信の手順(ストリームソケット)
-Client側
socket // ソケットの生成
bind // ソケットへの名前付け
connect
read/write
close
-Server側
socket
bind
listen
accept
read/write
close
・UBPの場合
-Client側
socket // ソケットの生成
bind //ソケットへの名前付け
sendto //データ送信
recvdrom //データ受信
close //ソケットの除去
-Server側
socket
bind
recvfrom
sendto
close //ソケットの除去
・ソケットの生成
-書式
int socket(int domain, int type, int protocol)
int domein:
使用するドメイン種別
int type:ソケットタイプ
UDPを使いたい場合 SOCK_DGRAM
int protocol: 下位プロトコルの指定
0=default
・ソケットの名前付け：bind
取ってきたファイルディスクリプタに対して名前をつける。
int bind(int socketfd, struct sockaddr(自分のアドレスの定義) *my_addr(データスタラクチャの長さ), sockelen_t addrlen)
・バイトオーダーとホストオーダー
BIG-endianとLittle-endianの違い
→各マシンごとに違うフォーマットを使っている場合は、意識して直す必要がある。
→CPUなどのアーキテクチャを使用する必要がある。
簡素化ため、変数変換用の関数が用意されている
- htonl, htons: host->nw
- ntohl, ntohs: nw->host
h to nl
n to hl
・ソケットアドレスの構造体
-port
送り側と受け手側で違うポート番号を使う必要があるので、要注意。
bzero((void *)&server, sizeof(server));
server sin_family = AF_INET;
・IPアドレスの与え方
- バイナリで与える場合(e.g. 0Xac105504)←バイトオーダーで考える必要がある。
- ドット区切り10進表記で与える場合(e.g. 172.16.85.4)
- hostnameで与える場合
gethostbyname ライブラリ関数を使用(後述)
引数にホスト名が入る。
hostentから、アドレスが返ってくる。
IPaddressを知ることができる。いf
・listen:接続受け入れ準備
接続要求を格納するキュー
→いくつ、接続を格納するキューを確保するか、のために使う。
・connect:接続要求発信
- streamsocket使用時における通信路確立
あとで例題
・accept:接続要求許可
int sockfd:
struct sockaddr:相手のアドレス
この関数が返す引数が使うファイルディスクリプタになる。
・read/write:データ送受信
・ストリームソケットが他の通信手順
・無線デバイスドライバのインストール
Linuxのデバイスドライバをダウンロード→インストール
