システムプログラム概論 Filesystem and storage management ディスク

システムプログラム概論
Filesystem and storage management
2005/5/13
門林 雄基 （インターネット工学講座）
奈良先端科学技術大学院大学
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
ディスク
z
z
z
z
Surface
Track
Sector
Cylinder
surface
sector
track
z
track caching controller
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
ディスク・スケジューリング
Disk scheduling
z
z
FCFS
z 到着順、fair だがシーク時間が長くなる可能性
SSTF (shortest seek time first)
現在のヘッド位置から最も近いブロックへの
アクセス要求を処理
SCAN (Elevator algorithm)
z 進行方向で、最も近いブロックへのアクセス
要求を処理
MOS p. 319～
z
z
z
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
1
ディスク・スケジューリング
Disk scheduling
z
Q. SSTF では飢餓状態 (starvation) になりうる。
なぜか？
z
Q. SCAN では飢餓状態にならない。なぜか？
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
二次記憶
Secondary storage
二次記憶
z 固定長ブロック単位での
読み書き
z セクタ番号でアクセス
z アクセス制御なし
z ディスククラッシュ時の
データ損失
ファイルシステム
バイト単位での読み書き
z
z
z
z
名前を指定してアクセス
アクセス制御あり
ディスククラッシュに強い
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
ファイルシステムの機能
Functions of file system
z
ディスクブロック管理
disk block management
z
名前管理
namespace management
アクセス制御
access control
z
z
耐故障性
failure resilience
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
2
ディスクブロック管理
Disk block management
z
z
z
空きブロックの管理にはビットマップを用いる
z １ブロックあたり１ビット
リストを用いる方法もあるが...
z MOS p. 413
ディスクの物理トポロジとビット配列のマッピング
に気をつける
z cylinder-major order
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
ディスクブロック管理のゴール
Disk block management goals
z
minimize seeks, rotational delay
z
minimize fragmentation
z
fast sequential access
z
fast random access
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
Linked files (Alto)
z
z
z
z
z
ブロックが次のブロックを指す
+ ファイルサイズの延長が容易
+ 空きブロック管理が容易
- ランダムアクセスが遅い
- 信頼性が低い
z
ブロック破損 => ファイル末尾まで破損
File header
end
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
3
Indexed files (VMS)
z
z
z
z
z
ユーザは最大ファイルサイズを宣言する。
システムはそれに相当するブロック数、ポインタが
入るようにファイルヘッダを割り当てる。
+ ファイルサイズの延長が容易（最大までなら）
+ ランダムアクセスが速い
- 最大ファイルサイズを越える延長が面倒
end
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
Multilevel indexed files (4BSD)
z
z
z
z
z
z
z
goal: 小さいファイル、大きなファイル双方を効率よく扱う
ファイルヘッダ(i-node)で 13個のポインタをもつ。
ポインタのうち、最初の10個はデータブロックを直接指す。
z (ファイルが10ブロック以下なら、残りのポインタは NULL)
11番目のポインタは indirect block へのポインタ
z indirect block: データブロックへのポインタを含むブロック
z 256 ブロックまで
267番目のブロックを割り当てるときは？
double indirect block -- 12番目のポインタ
z indirect block へのポインタを含むブロック
さらに大きなファイルには 13番目のポインタを使う。
z triple indirect block
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
Multilevel indexed files
i-node
1
2
indirect
11
266
Triple
indirect
267
Double
indirect
indirect
Double
indirect
indirect
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
4
Multilevel indexed files
z
z
z
z
z
+ ファイルサイズの延長が容易
+ ランダムアクセスが速い
+ 小さなファイルへのアクセスが特に高速
- 大きなファイルでは、indirect block アクセスに
時間を費す
- シークが多い
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
やってみよう
z
Q. ブロックサイズが 1K の場合、前述の
multilevel indexed file におけるファイルサイズの
上限をもとめよ。
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
名前管理 (Unix を例として)
Naming
z
z
"/usr/bin/perl" → ディスクブロック番号系列
システム内で、ファイルは (デバイス, i-node) で
識別される
z
i-node: Unix におけるファイルヘッダ
z デバイス内で一意な番号 (i-node 番号) により識別
z i-node にブロック番号系列が記録される
z
i-node は i-node ブロックに記録される。
i-node ブロック数: ファイルシステム作成時に決定
z
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
5
名前管理
Naming
z
ディレクトリ
z (ファイル名, i-node) の系列を含むファイル
z OS で特別扱い -- 通常のファイルのような
書き込みは禁止
z
MOS p. 406
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
Unix における名前解決
Name resolution in Unix
z
"/usr/bin/perl" の名前解決:
z "/" -> i-node 番号 2 (固定)
z i-node 2 が指すディスクブロック読み込み
z
z
z
z
z
z
z
ディレクトリ /
"usr" をディレクトリ / にて検索 -> i-node 番号 100
i-node 100 が指すディスクブロック読み込み
ディレクトリ /usr
"bin" をディレクトリ /usr にて検索 -> i-node 番号 500
...
"perl" をディレクトリ /usr/bin にて検索 -> i-node 番号
9000
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
アクセス制御
Access control
z
z
z
ファイルヘッダにアクセス制御情報を保存
z i-node (Unix)
OSがアクセス制御情報にもとづいて読み込み、
書き込み、実行などを許可/禁止
OS固有のアクセス制御モデル
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
6
アクセス制御モデルの例
Access control models
z
Unix: (owner, group, rwxrwxrwx)
z 読み込み、書き込み、実行
z オーナ、グループ、その他の三階層に分け、
アクセス制御
z
VMS, NT 等: (user/group, action...)
z 読み込み、書き込み、実行、ファイル生成、
ファイル消去、...
z 複数のグループを指定可能
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
システム資源の名前付けとアクセス制御
Naming resources
z
ファイルだけでなく、デバイスもアクセス制御したい。
z マウス、キーボードはデスクトップ利用者のみ
z ディスクのバックアップは管理者のみ
z プリンタは特定のシステムプログラムのみ
z ...
z
Unix ではデバイスもファイル、ディレクトリと同様のアクセ
ス制御を行う
z "/dev/kbd0", "/dev/da0"...
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
耐故障性
Failure resilience
z
z
z
バックアップ
誤り訂正符号 (Error Correcting Codes)の活用
SMART
z
システムクラッシュからの復帰
z Fsck
z MOS p. 421
z Journaling filesystem
z
LVM (logical volume management)
RAID
z
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
7
LVM
Logical volume management
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
RAID
Redundant Array of Inexpensive Disks
z
z
z
z
大容量ストレージを安いディスクで実現する技術。
構成を工夫すれば、信頼性も提供できる。
ディスクより大きなファイル、データベースを扱い
たいときどうするか？
concatenation
z disk 1: block 1 ... block N
z disk 2: block N+1 ... block 2N
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
RAID-0: striping
z
z
z
z
z
z
z
(ディスク k 本を束ねたとして)
disk 1: block 1, k+1, 2k+1, ...
disk 2: block 2, k+2, 2k+2, ...
disk k: block k, 2k, 3k, ...
+ ディスクアクセスの負荷分散が可能。
+ 大きなファイルの転送が、ディスク転送速度の
総和で行える。
- 信頼性が低い。ディスクが一つでも潰れたら
データ損失。
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
8
RAID-5: bitwise parity
z
z
z
z
z
disk 1: block 1, k+1, 2k+1, ...
disk 2: block 2, k+2, 2k+2, ...
...
parity disk: parity(1..k), parity(k+1..2k), ...
+ ディスクがどれか一つ潰れても、他のディスクからデータ
復旧が可能。たとえば:
z disk 1: 1001
z disk 2: 0101
z disk 3: 1000
z parity: 0100
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
RAID-5: bitwise parity
z
- データ更新のさいに、データブロックとパリティブ
ロックを更新しなければならない。パリティ更新中
にクラッシュしたら間違ったデータを復旧してしまう
危険性がある。
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
RAID-1: mirroring
z
z
z
まったく同じ内容を複数のディスクにもつ。
+ 信頼性が最も高い
- 速くならない、SCSI や IDE のバス帯域を k倍
占有する
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
9
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 - バスへの負荷が大きい
z
SCSIコントローラ等が隘路となる可能性
Copyright(C)2005 Youki Kadobayashi. All rights reserved.
10