オペレーティングシステム ファイルシステムその２ ファイルシステムの構造 「オペレーティングシステム」（第６回目） 今井慈郎（[email protected]） ファイルシステムの構造 1. 2. 3. 4. 5. 補助記憶装置（ディスク）の構造 ボリュームとファイルの管理 ディレクトリとネーミング関数 領域割当（外部断片化と内部断片化） 領域管理（ UNIXとMS-DOS（Windows）で の実際） 補助記憶装置（ディスク）の構造 ファイルの格納～磁気ディスク装置（その１） 樹脂製の薄い円盤(ディスク)に磁性体を塗った記憶 媒体． 磁性体の磁化状態を電気的に変化させることにより， データを記憶・消去． 読み書きを行なう際には，ディスクを高速回転（毎秒 数千回転）させ，磁気ヘッドを近づけて表面の磁界 を制御． 光ディスクなどに比べ，高速アクセス可能． ファイルの格納～磁気ディスク装置（その２） ハードディスクでは大容量化が進み，直径3.5イン チのディスク片面に最大30GB程度の記録が可能． (注)磁気ヘッドとディスク表面は1000分の1mm以下 と非常に接近するため，振動に弱い． 振動に弱い 回転速度：例）7200rpm 1分間あたりの回転数 RPM （revolutions per minute） ファイルの格納～磁気ディスク装置（その３） ３つのキーワード：トラック，セクタ，シリンダ トラック： データを記録する線状に連なった部分． 「トラック（track）」とは，（車などが通っ た後の）「轍」(わだち) という意味．トラッ クの上をデータを読み書きするための ヘッド機構部がなぞることにより記録・ 再生． トラックの形状は，同心円状，らせん状 に配置． ファイルの格納～磁気ディスク装置（その４） ３つのキーワード：トラック，セクタ，シリンダ 同心円状： ハードディスクなど接触型の磁気ヘッドを 使う記録装置に多い．目的のトラックまで一気にヘッ ドを移動（seek）し，その下にあるトラックのデータを読 み書き．連続してデータを読み書きするためには，ヘッ ドをシークして次のトラックへ移動する必要あり． らせん状： CDなど，光学的な記録方式を使うメディ アに多い．光をトラック上に正確に収束させるため， 細かく光軸を微調整する「トラッキング」という操作を 常に行っている．らせん状トラックにすればトラック間 をシークしなくても連続的にデータを読み書き可能． ファイルの格納～磁気ディスク装置（その５） ３つのキーワード：トラック，セクタ，シリンダ セクタ： データを読み書きする単 位．「セクタ（sector）」とは 領域とか区画という意味． 一般にトラック内には複 数のセクタが配置． ファイルの格納～磁気ディスク装置（その６） ３つのキーワード：トラック，セクタ，シリンダ シリンダ： 同じ位置にあるトラックヘッドを動 かさずにアクセスできるトラックの 集合．概念的には筒状と考えられ， 「シリンダ（cylinder ）と呼称．ハー ドディスクなどの補助記憶装置で は，データを読み書きするために はヘッドを目的のトラックへ移動す る必要あり．同じシリンダ上にある トラックならばシークせずに連続し て高速にアクセス可能． ファイルの格納～磁気ディスク装置（その７） ３つのキーワード：トラック，セクタ，シリンダ セクタ(sector) メモリ 磁気ヘッド トラック (track) セクタ： データ転送の単 位 シリンダ (cylinder) 計算問題のための情報を・・・ 但し，情報処理技術者試験などには頻出の 問題かもしれないので対策を・・ ハードディスクドライブの記憶容量計算 記憶容量＝１トラックの記憶容量×１シリンダあたりのトラック数（磁気ヘッド の個数）×シリンダ数 例）記憶容量を求める計算 ・１トラックの記憶容量＝20,000バイト ・１シリンダあたりのトラック数＝30トラック ・シリンダ数＝600シリンダ 記憶容量＝20,000×30×600＝360,000,000バイト＝360Mバイト １トラックあたりの記憶容量＝１セクタの記憶容量×１トラックあたりのセクタ数 例）１トラックあたりの記憶容量を求める計算 ・１セクタの記憶容量＝512バイト ・１トラックあたりのセクタ数＝40セクタ ・１トラックあたりの記憶容量＝512×40＝20,480バイト 磁気ディスク装置へのアクセス手順（その１） １）ディスク上の情報の物理アドレス： (Cylinder No, Head No（or Track No）, Sector No) で一意に決定 ２）ディスク上の情報へのアクセス： 1. 指定されたシリンダにヘッドを移動（ヘッドアームを 移動）．この操作をシークと呼び，その所要時間を シーク時間（seek time）と呼ぶ． 2. 指定されたヘッドを選択（電気的に切替）．所要時 間はゼロと近似 磁気ディスク装置へのアクセス手順（その２） 4. ヘッドが位置するトラック上の指定された物理レコー ド（ブロック）がヘッドまで回転するのを待つ．その 所要時間を回転待ち時間（latency）と呼ぶ． 5. 指定の物理レコード内の情報を転送する．その所 要時間をデータ転送時間(transfer time) アクセス時間＝ 「平均シーク時間＋平均回転待ち時間 ＋データ転送時間」 磁気ディスク装置へのアクセス手順（その３） ディスク上のアドレスを任意に指定することで， 所定の物理レコード（ブロック）にアクセス可能 このような性質を有する補助記憶装置をランダ ムアクセス記憶装置（random access storage device）あるいは直接アクセス装置（direct access storage device）と呼ぶ 計算問題のための情報を・・・ 但し，情報処理技術者試験などには頻出の 問題かもしれないので対策を・・ 次のハードディスクドライブから２０００ バイトのデータを，メモリに読み込む 時間は，次のように計算する・・ 【仕様】 回転速度：３０００回転／分 トラック容量：２００００バイト／トラック 平均シーク時間：５０ミリ秒 データのメモリ転送時間計算（その１） ① 平均回転待ち時間の計算 １回転：６０秒÷３０００＝０．０２秒＝２０ミリ秒 半回転：２０÷２＝１０ミリ秒 ・・・・平均回転待ち時間 ② データ転送時間の計算 １回転（２０ミリ秒）間に１トラック分の情報（２００００バ イト）が転送される 従って，１バイトの転送に要する時間：２０÷２００００ ＝０．００１ミリ秒 指定された２０００バイトの転送時間：２０００×０．００ １＝２ミリ秒 データのメモリ転送時間計算（その２） ③ 合計の所要時間は 「平均シーク時間＋平均回転待ち時間＋データ転送 時間」なので ５０＋１０＋２＝６２ミリ秒 答） 所要時間は ６２ミリ秒 ファイルシステムの構造 1. 2. 3. 4. 5. 補助記憶装置（ディスク）の構造 ボリュームとファイルの管理 ディレクトリとネーミング関数 領域割当（外部断片化と内部断片化） 領域管理（ UNIXとMS-DOS（Windows）で の実際） ボリュームとファイルの管理（その１） 情報を記憶する媒体：storage medium 「ボリューム（volume）」とは媒体の総称 ファイルシステムの役割には ■ ボリュームの管理 ■ボリューム内での領域割当の実施 などがある ボリュームとファイルの管理（その２） 各ボリュームには次のような情報が含まれる， ¾ 初期プログラムローダ（IPL)： システム立ち上げ IPL) 時に起動されるプログラム．最初に起動される装 置の固定領域に配置．起動後は使用されない． ¾ ボリューム管理情報： ボリューム名，ボリューム ボリューム管理情報 構成情報，領域割当状況，不良ブロック情報など， ボリューム管理に必要な諸情報 ¾ ファイル管理情報： ファイル名，型，ファイルサイ ファイル管理情報 ズなど個々のファイルに関する情報 ¾ ファイルデータ： ファイルの内容 ファイルデータ ボリュームとファイルの管理（その３） UNIX：論理ボリューム UNIX ブートブロック スーパーブロック シリンダブロック MS-DOS：物理ボリューム DOS ＩＰＬ ＦＡＴ ルートディレクトリ ｉノードリスト データ領域 データ領域 UNIXとMS-DOS（Windowsの前身）との比較 ボリュームとファイルの管理（その４） UNIXの場合： １つの物理ボリュームをいくつかの区画（パーティ ション）に区切り，これを論理的なボリュームとし て扱う． 論理ボリュームの管理情報は，スーパーブロッ クと呼称． ファイルの管理情報は，iノードリストに配置． ボリュームとファイルの管理（その５） UNIXの場合（つづき）： iノード（i ノード node ）は，ファイルごとの管理情報 を記録する一定サイズのデータ構造であり， その配列がiノードリスト． 各のiノードはiノード番号によって指定． ファイルを論理ボリュームとiノード番号の対 によって識別． ボリュームとファイルの管理（その６） MS-DOSの場合： 各物理ボリュームごとにFAT（File Allocation FAT Table）と呼ばれる管理表を有し，ボリューム内の 領域管理に使用． フォーマット処理により，使用に先立ち，トラックや セクタのような構造を磁気的に作成する必要あり （不良箇所を記録し，トラック／セクタ単位で隔離）． ファイルを作成するためのデータ構造（IPLからデー タ領域まで）を磁気的に作成する必要あり（フォー マット処理の後半）． ボリュームとファイルの管理（その７） = FATファイルシステム VS NTFSファイルシステム = FATファイル・システムは，MS-DOSにおけるファイ ル管理方式として広く普及． Windows 9x系列のWindows（Windows 95／Windows 98 SE／Windows Me） ファイル・システムとして， このFATのみが利用可能． MS-DOSの時代に開発されたFAT16から進化した FAT32では，大容量ディスクへの対応，ロング・ファイ ル名への対応などの機能追加 基本的構成は従来通り． ボリュームとファイルの管理（その８） = FATファイルシステム VS NTFSファイルシステム = Windows NTでは，FATに代わる新しいファイル・ システムとしてNTFSが開発． FAT16/32はあくまで個人利用を前提として設計 NTFSでは，よりミッション・クリティカルな用途にも 耐えるように，セキュリティ強化や信頼性向上など を目的とした新機能を追加． WindowsXPにも踏襲 ボリュームとファイルの管理（その９） = FATファイルシステム VS NTFSファイルシステム = NTFSでは，アクセス制御機能を強化． FATファイル・システムの問題点：集中管理を前提 とする企業用途に耐えるアクセス制御機能の提供 が不可能． NTFSでは，完全な強制力を持ったファイル・アクセ ス制御機能を提供． ドメインなどを単位として，ファイル・アクセスを集中 管理可能． ボリュームとファイルの管理（その１０） = FATファイルシステム VS NTFSファイルシステム = Windows NT，Windows 2000，Windows XP， XP Windows Server 2003でNTFSが利用可能． 上記OSを搭載した業務用途のコンピュータ（パソコン ではない位置づけ） 通常，NTFSファイル・システムの利用が前提 但し，これらのOSからも，以前のFATボリューム利用 は可能． ファイルシステムの構造 1. 2. 3. 4. 5. 補助記憶装置（ディスク）の構造 ボリュームとファイルの管理 ディレクトリとネーミング関数 領域割当（外部断片化と内部断片化） 領域管理（ UNIXとMS-DOS（Windows）で の実際） ディレクトリとネーミング関数（その１） = Windows VS UNIX = ■ Windows（含むMS-DOS）でのファイル管理： ¾ ファイル管理はボリューム単位． ¾ ファイルの識別はボリューム名＋パス名． ボリューム名は装置名（ドライブ名）であり，省略時 （default）ドライブ指定可能（ドライブ名：ファイルの パス名）． パス名 ¾ ディレクトリ： 以下の情報などが登録 ファイル名，ファイル型，ファイル作成・変更時刻， 領域を管理するFATのインデックス，ファイルサイズ ディレクトリとネーミング関数（その２） = Windows VS UNIX = ■ Windows（含むMS-DOS）でのファイル管理（続き）： ¾ ルートディレクトリ ディスクの固定領域に割り当てられる． サイズも固定． ボリュームラベル（ドライブを表すボリューム名）など を登録． ¾ 他の（サブ）ディレクトリ ディスクの任意の領域に割当可能． ディレクトリとネーミング関数（その３） = Windows VS UNIX = ■ UNIX（Linux）でのファイル管理： ¾ 典型的な木構造ディレクトリでのファイル管理（論理 ボリューム単位で，階層型ディレクトリを構成し，ファ イルを登録）． ¾ ディレクトリもファイルとして実装．ファイル（含むディ レクトリ）名と iノード番号との対が登録．・・・１つの ファイルと１個のiノード（i-node）が対応 ¾ 論理ボリューム単位で個別のファイルシステムが存 在し，それを１本の木構造に統合・管理． ディレクトリとネーミング関数（その４） = Windows VS UNIX = ■ UNIX（Linux）でのファイル管理（続き）： ¾ 「ルートファイルシステム」はシステムブート時に起 動される論理ボリュームのファイルシステムの呼称． このルートファイルシステムの既存ディレクトリに， 他のファイルシステムの個別のルートを結合し，シ ステムで１本の論理的階層（木構造）ディレクトリを 構成． ¾ 「マウント（mount）」はディレクトリの結合操作の呼 称．逆操作は「アマウント（umount）」 UNIX：論理ボリューム UNIX ブートブロック スーパーブロック UNIX：物理ボリューム UNIX ルート パーティション シリンダブロック ｉノードリスト データ領域 ブートブロック スーパーブロック シリンダブロック ｉノードリスト データ領域 １本の木構造 ブートブロック スーパーブロック シリンダブロック ｉノードリスト データ領域 マウント UNIXにおけるiノード（リスト）とデータ（領域）の関係 iノードリスト ファイル名（パス名： /home/imai/test.c ）へのアクセス手順 ネーミング関数の実体 1. 2. ２ ４ ｉノードの検索とデ ータブロックの決 定：ネーミング関 数で物理レコード のアドレスを確定 ８ 前述の方法を用い て，当該物理レコ ードへアクセス １１ データブロック（データ領域） ルート ディレクトリ ２ ・ ２ ３ ・・ bin ４ home ４ /home ディレクトリ ８ ・ ・・ imai ８ ・ ４ ・・ test.c /home/imai ディレクトリ ２ １１ test.c main(){・・} 目的のファ イル UNIXのファイルシステムの特徴 UNIXでは１つのファイルに複数の名前を設定可 能．同じiノード番号を有する複数のディレクトリエ ントリが作成．「リンク（ハードリンク）」はこれらの特 殊エントリの呼称．ファイルシステムを横断すること は不可． 他のファイルのパス名を保持するファイルを作成 可能．「シンボリックリンク（ソフトリンク）」がこのよう なファイルの呼称．異なるファイルシステムをまた いでリンク可能． 各ディレクトリには，「・」（自身のディレクトリ）と「・・」 （１つ上位の，親のディレクトリ）が登録可能 ファイルシステムの構造 1. 2. 3. 4. 5. 補助記憶装置（ディスク）の構造 ボリュームとファイルの管理 ディレクトリとネーミング関数 領域割当（外部断片化と内部断片化） 領域管理（ UNIXとMS-DOS（Windows）で の実際） 領域割当（外部断片化と内部断片化～その１） 外部断片化とは ファイルをデータ領域に割り当てる場合， 連続領域への割当が最も簡単な方法 データを編集する場合，ファイルサイズ が動的に伸縮することになる． その結果，予め割り当てた領域に対し て，（小さくなれば隙間が生じ，大きくな れば本体全体が移動するので）空き領 域が発生する． 縮小 伸張のため移動 領域割当（外部断片化と内部断片化～その２） 外部断片化とは このようにディスクのデータ領域のあちこちに断片化 した空き領域が発生 領域全体の使用効率が低下 「外部断片化（external fragmentation）」と呼ぶ． 空き領域 外部断片化 領域割当（外部断片化と内部断片化～その３） 内部断片化とは 連続した領域を割り当てる方式 外部断片化により，分散した空き領域が発生． これらを１つの大きな空き領域にまとめれば，再利用も 容易． その操作は「詰め直し（compaction）」と呼び，多大な所 要時間を要する（メモリ内での大量データ移動のため） ． 領域割当（外部断片化と内部断片化～その４） 内部断片化とは ブロックなど固定サイズの領域を単位として，割り当て る方式が有効（ブロック割当方式）． 連続割当方式と比較し，ファイルの伸縮に対応でき，外 部断片化を回避可能． ◆連続割当（１つのファイルに関するデータ領域が集約） ＶＳ ブロック割当方式（１つのファイルに対する データ領域がディスク全体に散在） アクセス効率の低下（シリンダをまたいだ場合，毎 回のアクセスにシーク時間まで含まれることになる）． 領域割当（外部断片化と内部断片化～その５） 内部断片化とは 一般には，いくつかのブロックをクラスタ（cluster）として まとめ，散逸を回避する． しかし，この方法で領域を割り当てても，最後のブロック 内には基本的に無駄な空き領域が発生する可能性あり． 「内部断片化（internal fragmentation）」と呼ぶ． 一般に，内部断片化は避けにくく，ブロックサイズを調 整し（初期設定時に），システムの最適化を図ることが 必要． 領域割当（外部断片化と内部断片化～その６） 内部断片化とは 各ファイルの領域 割当後のイメージ ファイル ブロック割当で各ファイルの領域 割当を行う：確かに，外部断片化 は発生しないが・・・ ブロック内に未使用部分：内部断片化 の発生 ファイルシステムの構造 1. 2. 3. 4. 5. 補助記憶装置（ディスク）の構造 ボリュームとファイルの管理 ディレクトリとネーミング関数 領域割当（外部断片化と内部断片化） 領域管理（ UNIXとMS-DOS（Windows）で の実際） 領域管理（その１） 領域割当とその管理（領域管理）の基本的考え方 領域割当で最も簡単な手法は連続領域割当である． しかし，以下のような問題点も発生 ファイルの大きさを事前に宣言 事前確定は困難 領域の外部断片化の発生 ファイルを編集する ことで（領域割当と解放を繰返すことで）ディスク領 域などに空き領域が発生 連続領域割当の使用効率を改善 詰め直し （Compaction）が必要 ブロック割当の妥当性 内部断片化の発生は不可避 どれだけ効率化するかが問題 領域管理（その２） （主流である）ブロック割当方式での領域管理方式 使用（中の）領域管理と空き（未使用の）領域管理 使用領域の管理：使用中である領域の効率的管理 リスト方式 リストであれば頭からサーチ 索引（インデックス）方式 空き領域の管理：未使用である領域の効率的管理 リスト方式 リストであれば頭からサーチ ビットマップ方式 使用領域の管理（その１）：リスト方式 特徴： ファイル名 T ファイルを構成するブロック を先頭から順にリストして保 持 T 各ブロックには次のブロック へのポインタが存在 ポインタ ・・ ディレクトリに格納 ２ ５ ０ １ ２ ７ ３ １０ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ T ディレクトリには先頭ブロッ クへのポインタが登録 T 途中のポインタが破壊され ると修復が困難 T 順アクセスには効果的だが， 直接アクセスには不向き データブロック 使用領域の管理（その２）：索引方式 特徴： ・・ ディレクトリに格納 ファイル名 T 索引が存在．各ブロッ クへのポインタを表形 式で保持（これを索引 indexと呼称） T ファイル事に索引が生 成，ディレクトリに索引 （or索引へのポインタ） が格納 T 直接アクセスも容易（リ スト方式の改善）．但し， 索引のための領域が 別途必要 ２ ５ ７ ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ １０ 索引 データブロック 空き領域の管理（その１）：リスト方式 空き領域の先頭 特徴： T 空き領域を構成するブロック 群を順にリストして保持 T 各未使用ブロックには次の ブロックへのポインタが存在 ポインタ T １つの空きブロックを得るの に１回のディスクアクセスが 必要 ０ １ ３ ０ １ ６ ４ ２ ３ ８ ４ ５ ９ １１ ８ ９ ６ ７ １０ １１ データブロック 但し，空き領域管理には複雑なアクセス手順は不要で，必要 なブロックだけリストを手繰って確保すればリストの更新は容 易・・ディスクアクセスを低減するためキャッシュなどを活用 空き領域の管理（その２）：ビットマップ方式 特徴： T ディスク中のブロックを１ビットに 対応させ，対応するブロックが使 用中なら「０」に，未使用なら「１」 にセット T ビットマップ用のデータを１つの 領域に確保 １ １ ０ １ １ ０ １ ０ １ １ ０ １ Bitmap ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ データブロック ＵＮＩＸの領域管理（その１）：索引方式 ■ＵＮＩＸでは，ブロックを単位 に領域割当 i-node ■ファイル領域は索引で保持 直接 ■巨大なファイルの総てのブ ロックを一元的な索引で登録 するのは非常に大きな索引 を必要とするので効率が悪い ■間接ブロック（単一，二重， 三重）を活用してブロックを管 理 ・・・ 巨大なファイル容量 を実現（使用頻度は多くないが） 単一間接 二重間接 三重間接 ＵＮＩＸの領域管理（その２）：索引方式 ×1024 ×1024 ×1024 i-node ブロック容量×12 ×1024 ×1024 ×1024 理論上のファイル容量は・・・ ×1024 ×1024×1024 ＭＳ－ＤＯＳの領域管理（その１）：ＦＡＴ方式 ■ＭＳ－ＤＯＳでは，ディスクをクラスタに分割し，クラ スタ単位に領域割当 ■ディスク領域の管理はＦＡＴを利用．ＦＡＴのエントリ は各クラスタ（のインデクッス）に対応 ■ディスク領域のクラスタには順に番号が付与．ＦＡＴ でその番号をインデックスとする表を管理 ■１つのファイルに使用されるクラスタをポインタで繋 ぎ，保持．使用中のクラスタに対応するＦＡＴ上のイン デックスには，次のクラスタ番号が記載 ■ＦＡＴが欠損すればファイルへのアクセスは不能 ＭＳ－ＤＯＳの領域管理（その２）：ＦＡＴ方式 ＦＡＴ ディレクトリ Ａ １ Ｂ ４ ３ Ｆｒｅｅ ５ ファイル 位置 ファイルごとにリスト化 されたブロック群 ６ Ａ： １ ３ ５ Ｂ： ４ ６ ７ ９ ＥＮＤ ７ ９ Ｆｒｅｅ ＥＮＤ Ｆｒｅｅ ＦＡＴが欠損すればファイ ルを構成するブロック間 の接続情報が失われ， ＯＳなどがファイルにアク セスできない状況に陥る
© Copyright 2024 ExpyDoc
