2008/06/17
・ファイル名
ファイルを識別するためのString名からID名へ変換する
/a/b/c→101020
・ファイル内のポインタ
論理アドレスから物理アドレスへの変換
↑上記の二つをどうやって実現するのか？
・フ
ァイルシステム概要
ファイルの詰め込み方には異論の方法がある
例：
1. 頭からファイルを詰め込んでいく方法
→deflagmentationが起こるのであまり使われない。
2. 固定長のブロックに分けてファイルを詰め込んでいく方法、各ブロックは次のブロックを指すポインタを持っている
→しかしsequencialにしかアクセスできない！
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 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したときに、現在オープンしたファイルディスクリプタは共有される。
オフセット：現在書き込みしているところの次はどこに書き込むのか、という情報が格納されている。
・スーパーブロック
スーパーブロックはファイルシステム全体を管理するデータ構造。
一番最初に読み込まれる。
-ブロックサイズをどうするか？４K?１K?
-どのブロックが現在使われているか？
新しくブロックを割り当てる場合、空いているところをビットマップから判断し、割り当てる。
名前をどうやってi-nodeに変換するか？
i-nodeが分かったとき、その後どうやってファイルにアクセスするか。
・read/write
ファイルをオープンすると、今アクセスしようとしているi-nodeを認識する。
それをi-node tableのコピーする。
ファイルデータ構造にallocationして、
プロセスデータ構造からファイルデータ構造に書き込む。
ファイルデータ構造のoffsetを見て、i-nodeテーブルを見て、i-nodeの何バイト目を見るかを決める。
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は次のブロックを指していたら、その次のブロックがアクセスされる場合が多いので、事前にメモリ上に呼び出しておく。
タイムスタンプ：いつアクセスされていたか。
キャッシュの管理アルゴリズムは、タイムスタンプをつけてLRUで管理している。
・ディスクの書き出し
バッファキャッシュで変更する場合、３０秒から１分待つ。これにより、同じバッファブロックに対して何度も何度も書き出すことを制限することが出来る。
30秒に一回変更されているブロックをディスクに書き出す。
ディレクトリやスーパーブロック, i-nodeの変更はすぐにディスクに書き出す。
→システムがファイルへ書き出す前にクラッシュしたとき、ファイルシステム全体が壊れる可能性がある。
→ファイルのデータ構造をいじくるときは、常にファイルシステムの一貫性を保てるようにする。
・ディスクスケジューリング
FIFOスケジューリングは行ったり来たりする。
メカニカル動く。
アームの動く速度は遅いので、アームの動く量を最小にしたい。
→C-SCANというアルゴリズムがある。
C-SCAN:
いくつかのタスクを溜めておいて、ソートして
頭から尾に向かって順番にアクセスしていく。
その後、アームを頭の位置に戻す。
他のもディスクスケジューリングアルゴリズムがある。
今は、もうちょっと頭のいいアルゴリズムも存在する。
☆ハードディスクのアクセスには物理メモリと違って、
トラックがどこにあるかによってアクセス時間が大幅に違う。
自分のアクセスしたいデータがトラックのどこにあるのかを認識して、
最小限のアームの動きでアクセスする必要がある。
・分散ファイルシステム
リモートにあるマシンに対して同じプログラムを使いたいときは
アクセス透過性と位置透過性を考える必要がある。
アクセス透過性：リモートファイルもローカルファイルも同一のAPIを用いてアクセス可能
位置透過性：ファイル名にマシン名が含まれていない。
→どこのマシンにあるかを気にせずアクセスできる。
・NFS
network file systemの略称。しかしnetwork file systemとは滅多に言わない。
☆プログラマーから見て、あたかも普通にディレクトリをアクセスできるかのようにすることが大切。
→OS空見れば、ネットワーク上の複雑な処理を隠蔽することが大事！
・I/Oの種類
プログラム⇔デバイスドライバ⇔デバイス
デバイスの種類はたくさんある！
デバイスドライバが出来るだけ隠蔽してあげることが大切。
・バスの種類
PCI
ISA
SCSI
…たくさん！
・デバイスドライバ
デバイス独自のプロトコルの使用にあわせて作り、出来るだけ簡略化し、隠蔽する・
デバイスドライバは、各デバイスのアクセスプロトコル(デバイスの制御手順)を実装する。
デバイスドライバはデバイスを自動的に発見し、どのようにアクセスするかを自動的にけっている。
cf:USBの挿入
USBを差し込む→OSが認識→
デバイスドライバがない場合：デバイスドライバをインストールする。
デバイスドライバがある場合：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);
mem = dataPort;
dataPort:どっかのレジスタ
ｲﾍﾞﾝﾄの発生などをポーリングで待つことはCPUの無駄遣い
他の処理の合間にポーリングをすることが可能だが、システム全体の構造がクリアではなくなる
よって、ポーリングを使用するときは、結果が分かるまでの時間が短い場合のみ。
20μsならよいが20nsでは無駄。
・割り込み interrupt
CPU→要求(I/O port, memory)→デバイス
CPU← 割り込み ←デバイス
↑ポーリングによるCPUの無駄遣いを防ぐことが出来る
割り込みは、デバイスからCPUに対して何かを呼び出したいとき、
今実行しているプログラムを中断して割り込んだデバイスの処理をさせるときに使う。
・割り込みハンドラ
以下のような処理が割り込み処理に当たる
-新しく入力された
-エラー処理
-デバイスからの通知処理
番号ごとに違う番号を登録する
例：割り込みベクタ↓
IRQ0 = clock handler
IRQ1 = disk handler
IRQ2 = network handler
IRQ3 = trap handler: page fault, system call, bus error etc.
各デバイスはIRQの何番を用いるか知っている。
場合によっては、割り込みベクタを複数のデバイスで共有することが出来る。
→割り込み処理で貰ってきた値を評価して、どのデバイスの割り込みかを認識する。
・多重割り込み
割り込みが複数個ある。
割り込み処理が実行されたときに、違う割り込みが来た場合はどうするのか？
割り込みには優先度が付いている。
例：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()
{
割り込み禁止
排他リソースのアクセス
割り込み可能
}
注意：割り込みを禁止している時間はなるべく短くするように心がける。
・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の"付録"にデバイスドライバのサンプルソースコードがあるので目を通しておく。
0 件のコメント:
コメントを投稿