Microsoft PowerPoint fs

(1)

システムプログラム概論

Filesystem and storage management

2005/5/13

門林雄基（インターネット工学講座）奈良先端科学技術大学院大学

ディスク

zSurface

zTrack

zSector

zCylinder

ztrack caching controller surface sector track

ディスク・スケジューリング

Disk scheduling

zFCFS z到着順、fair だがシーク時間が長くなる可能性 zSSTF (shortest seek time first)

z現在のヘッド位置から最も近いブロックへの

アクセス要求を処理

zSCAN (Elevator algorithm)

z進行方向で、最も近いブロックへのアクセス

要求を処理

(2)

ディスク・スケジューリング

Disk scheduling

zQ. SSTF では飢餓状態 (starvation) になりうる。なぜか？ zQ. SCAN では飢餓状態にならない。なぜか？

二次記憶

Secondary storage

二次記憶 z 固定長ブロック単位での読み書き z セクタ番号でアクセス z アクセス制御なし z ディスククラッシュ時のデータ損失ファイルシステム z バイト単位での読み書き z 名前を指定してアクセス z アクセス制御あり z ディスククラッシュに強い

ファイルシステムの機能

Functions of file system

zディスクブロック管理 disk block management

z名前管理 namespace management zアクセス制御 access control z耐故障性 failure resilience

(3)

ディスクブロック管理

Disk block management

z空きブロックの管理にはビットマップを用いる z１ブロックあたり１ビット zリストを用いる方法もあるが... zMOS p. 413 zディスクの物理トポロジとビット配列のマッピングに気をつける zcylinder-major order

ディスクブロック管理のゴール

Disk block management goals

zminimize seeks, rotational delay

zminimize fragmentation

zfast sequential access

zfast random access

Linked files (Alto)

zブロックが次のブロックを指す z+ ファイルサイズの延長が容易 z+ 空きブロック管理が容易 z- ランダムアクセスが遅い z- 信頼性が低い zブロック破損 => ファイル末尾まで破損 end File header

(4)

Indexed files (VMS)

zユーザは最大ファイルサイズを宣言する。 zシステムはそれに相当するブロック数、ポインタが入るようにファイルヘッダを割り当てる。 z+ ファイルサイズの延長が容易（最大までなら） z+ ランダムアクセスが速い z- 最大ファイルサイズを越える延長が面倒 end

Multilevel indexed files (4BSD)

z goal: 小さいファイル、大きなファイル双方を効率よく扱う z ファイルヘッダ(i-node)で 13個のポインタをもつ。 z ポインタのうち、最初の10個はデータブロックを直接指す。 z (ファイルが10ブロック以下なら、残りのポインタは NULL) z 11番目のポインタは indirect block へのポインタ z indirect block: データブロックへのポインタを含むブロック z 256 ブロックまで z 267番目のブロックを割り当てるときは？ z double indirect block -- 12番目のポインタ

z indirect block へのポインタを含むブロック z さらに大きなファイルには 13番目のポインタを使う。

z triple indirect block

Multilevel indexed files

1 2 indirect 11 266 Double indirect indirect 267 indirect Double indirect Triple indirect i-node

(5)

Multilevel indexed files

z+ ファイルサイズの延長が容易 z+ ランダムアクセスが速い z+ 小さなファイルへのアクセスが特に高速 z- 大きなファイルでは、indirect block アクセスに時間を費す z- シークが多い

やってみよう

zQ. ブロックサイズが 1K の場合、前述の

multilevel indexed file におけるファイルサイズの上限をもとめよ。

名前管理 (Unix を例として)

Naming

z "/usr/bin/perl" → ディスクブロック番号系列 z システム内で、ファイルは (デバイス, i-node) で識別される z i-node: Unix におけるファイルヘッダ zデバイス内で一意な番号 (i-node 番号) により識別 zi-node にブロック番号系列が記録される z i-node は i-node ブロックに記録される。 z i-node ブロック数: ファイルシステム作成時に決定

(6)

名前管理

Naming

zディレクトリ z(ファイル名, i-node) の系列を含むファイル zOS で特別扱い -- 通常のファイルのような書き込みは禁止 zMOS p. 406

Unix における名前解決

Name resolution in Unix

z "/usr/bin/perl" の名前解決: z"/" -> i-node 番号 2 (固定) zi-node 2 が指すディスクブロック読み込み zディレクトリ / z"usr" をディレクトリ / にて検索 -> i-node 番号 100 zi-node 100 が指すディスクブロック読み込み zディレクトリ /usr

z"bin" をディレクトリ /usr にて検索 -> i-node 番号 500

z...

z"perl" をディレクトリ /usr/bin にて検索 -> i-node 番号 9000

アクセス制御

Access control

zファイルヘッダにアクセス制御情報を保存 zi-node (Unix) zOSがアクセス制御情報にもとづいて読み込み、書き込み、実行などを許可/禁止 zOS固有のアクセス制御モデル

(7)

アクセス制御モデルの例

Access control models

zUnix: (owner, group, rwxrwxrwx)

z読み込み、書き込み、実行 zオーナ、グループ、その他の三階層に分け、アクセス制御 zVMS, NT 等: (user/group, action...) z読み込み、書き込み、実行、ファイル生成、ファイル消去、... z複数のグループを指定可能

システム資源の名前付けとアクセス制御

Naming resources

z ファイルだけでなく、デバイスもアクセス制御したい。 zマウス、キーボードはデスクトップ利用者のみ zディスクのバックアップは管理者のみ zプリンタは特定のシステムプログラムのみ z... z Unix ではデバイスもファイル、ディレクトリと同様のアクセス制御を行う z"/dev/kbd0", "/dev/da0"...

耐故障性

Failure resilience

z バックアップ

z 誤り訂正符号 (Error Correcting Codes)の活用 z SMART

z システムクラッシュからの復帰

zFsck

zMOS p. 421

zJournaling filesystem

z LVM (logical volume management) z RAID

(8)

LVM

Logical volume management

RAID

Redundant Array of Inexpensive Disks

z大容量ストレージを安いディスクで実現する技術。

z構成を工夫すれば、信頼性も提供できる。

zディスクより大きなファイル、データベースを扱いたいときどうするか？

zconcatenation

zdisk 1: block 1 ... block N

zdisk 2: block N+1 ... block 2N

RAID-0: striping

z(ディスク k 本を束ねたとして) zdisk 1: block 1, k+1, 2k+1, ... zdisk 2: block 2, k+2, 2k+2, ... zdisk k: block k, 2k, 3k, ... z+ ディスクアクセスの負荷分散が可能。 z+ 大きなファイルの転送が、ディスク転送速度の総和で行える。 z- 信頼性が低い。ディスクが一つでも潰れたらデータ損失。

(9)

RAID-5: bitwise parity

z disk 1: block 1, k+1, 2k+1, ... z disk 2: block 2, k+2, 2k+2, ... z ...

z parity disk: parity(1..k), parity(k+1..2k), ...

z + ディスクがどれか一つ潰れても、他のディスクからデータ復旧が可能。たとえば: zdisk 1: 1001 zdisk 2: 0101 zdisk 3: 1000 zparity: 0100

RAID-5: bitwise parity

z- データ更新のさいに、データブロックとパリティブロックを更新しなければならない。パリティ更新中にクラッシュしたら間違ったデータを復旧してしまう危険性がある。

RAID-1: mirroring

zまったく同じ内容を複数のディスクにもつ。 z+ 信頼性が最も高い z- 速くならない、SCSI や IDE のバス帯域を k倍占有する

(10)

RAIDの実現方法：

Software RAID vs Hardware RAID

z Hardware RAID z+ RAID-5 の実現が容易 z+ バスへの負荷が軽い z- ディスク構成に制限 z同じロットのディスクは同時期に壊れる z Software RAID z+ RAID-0, RAID-1 の実現は容易 z+ 柔軟なディスク構成 z- バスへの負荷が大きい zSCSIコントローラ等が隘路となる可能性