SCAN
C- SCAN (Elevator)
• Circular SCAN
• SCAN よりも待ち時間が均一になる傾向がある
• ヘッドが端にいったら逆方向に進まずに、ヘッドを逆方向の端 に移動させて処理を継続
第10回 オペレーティングシステム
LOOK and C-LOOK
• SCAN, C-SCAN の改良
• ヘッドを端までもっていかず、もし、ヘッドの移動方 向に I/O 要求がなければ、移動方向を変更
C-SCAN C-LOOK
2018/6/18 40
Disk Attachment
• ２つの方法
– コンピュータのI/Oポートに接続 – ネットワークに接続
1. NFSのような分散ファイルシステム
2. SCSIの延長
SAN(Storage Area Network) 分散ファイルシステム
第10回 オペレーティングシステム
ファイルシステム
• File Concept
• Access Methods
• Directory Structure
• File System Mounting
• File Sharing
• Protection
• File System Structure
• File System Implementation
• Directory Implementation
• Allocation Methods
• Free-Space Management
• Efficiency and Performance
• Recovery
• Log-Structured File Systems
ファイル
• ファイルとは
– 連続した論理的アドレス空間 – 内容 :
• データ
– 数値 – 文字
– バイナリ
• プログラム
• ファイル構造
– 構造なし
• 語あるいはバイト列
– 単純なレコード構造
• 行、固定長、可変長
– 複雑な構造
• 書式化されたドキュメント、
リロケータブルプログラム オブジェクト
– 誰が決める？ :
• Operating system
• Program
2018/6/18 第10回 オペレーティングシステム 42
ファイルとは
• プログラム中に保持する情報
– プロセス生成後に発生し、終了時に消滅 – アドレス空間の大きさに制限
もっと長期に大容量…
プロセス メモリ中 ファイル
CPU メモリ
2次記憶
ファイルとは
• 記憶装置の構造に依存しないデータ保持の単位
– データやプログラム
– 記憶装置は主に 2 次記憶（外部記憶）
• HDD, フラッシュメモリ, 磁気テープ, etc.
• 主記憶上にファイルを配置することも可能
• 統一的な取り扱いが可能な論理的存在
– 生成、オープン , 読み , 書き , クローズ , etc.
– 属性情報を保持
2018/6/18 第10回 オペレーティングシステム 44
ファイルの名前
• 情報の抽象化：保存しておいて後から読み出し
– ファイルに名前を付加
• 文字数・使える文字等の制限はファイルシステムにより差あり
– 8+3, 256, ... ; 大文字・小文字の区別
• 拡張子 ( ピリオド [.] より後ろの扱い )
– ファイルの種類の判定
• .txt, .tex, .doc, .ppt, .bat, .exe, .c, .h, .o, ...
– 単なる慣習の場合
– OS・アプリケーション解釈する場合
2018/6/18 46
ファイル属性とディレクトリ
• Name – 名前
• Type – ファイルのタイプ
• Location – デバイス上のどこにあるか
• Size – 大きさ
• Protection – 誰にread/write/deleteを許すか
• Time, date, and user identification
第10回 オペレーティングシステム
F 1 F 2
F 3 F 4
F n Directory
Files
これらの属性はディレクトリの中に保持
ファイル操作
• Create
• Write
• Read
• Seek
• Delete
• Truncate
• Open(F
i) ： F
iで示されるファイルをディスクから探索
– ファイルの中身をメモリ上で操作できるように
• Close (F
i) ：メモリ上で操作した内容をディスクに反映
2018/6/18 48
ファイルタイプ例
第10回 オペレーティングシステム
OS におけるファイルアクセス
• ファイル制御ブロック (FCB: File Control Block)
– ファイル記述子 (File Descriptor) とも
– ファイルシステム中の属性情報のうち必要なものを保持 – ファイルのアクセス状態の管理
– プロセスは FCB を通じてファイルを操作
• read, write の引数では FCB の配列のインデックスを指定
– ユーザプロセスは FCB の中味は変更が不可能
– Open の返り値として取得が可能
OS におけるファイル操作
• create/delete
– ファイルの生成・削除 – 生成時には属性の指定
• open
– ファイルの使用開始
– 必要な属性を FCB へコピー
• ファイルアクセスに関する状態情報も保持
– 操作属性の指定 (read only など )
2018/6/18 第10回 オペレーティングシステム 50
OS におけるファイル操作
• close
– バッファのフラッシュ、 FCB の削除 – 属性情報の更新
– プロセス終了時には全て自動的に close
• read/write
– データの読み出し・書き込み
– ある程度のまとまりを主記憶 ( バッファ ) に保持
OS におけるファイル操作
• append
– 追記、 write の限定版
• seek
– 読み・書きの場所の移動
• set/get attribute
– 属性値の取得 ( 時刻やら )
• rename
– ファイル名の変更
2018/6/18 第10回 オペレーティングシステム 52
ファイルの構造
• バイト列
– OSはファイルの中味に興味なし
– 構造的な解釈はアプリケーションが担当
• レコード列
– 論理レコード
• ファイルを構成するデータの集まりの単位 – 住所録 = 名前・住所・電話番号
– 改行まで (可変長)
– 物理レコード(ブロック)
• 記憶装置に入出力する際のデータの単位 – 内容は１つまたは複数の論理レコード
ファイルの構造
• 構造を持つファイル ( 論理構造 )
– 2 次記憶装置 ( 物理構造 ) に依らず扱う必要性 – ファイルの 2 次記憶への格納時
• 論理構造 ⇒ 物理構造へ変換し格納
– 2 次記憶からファイルの読み出し時
• 物理構造 ⇒ 論理構造へ変換し主記憶に配置
• ファイルアクセスの方法
– 2 次記憶での構造と入出力の効率化
2018/6/18 第10回 オペレーティングシステム 54
バッファリング
• 二次記憶を直接読み書き → 遅い
– メモリ中に一次蓄積
• バッファリング（ buffering ）
– 二次記憶からブロック単位でメモリに転送 – プロセスはバッファに読み書き
– 変更のあるバッファは定期的・解放時に二次記憶に書き戻す
– CPU と入出力の並行処理
ダブルバッファリング
• 二つのバッファ
– 一方のバッファを読み・書きしている間に他方に二次記憶から／へ転送
• プロセスのI/O待ちを最小化
入力レコード
出力レコード
レコード レコード レコード
レコード レコード レコード
レコード レコード レコード
レコード レコード レコード
レコード レコード
レコード レコード
レコード レコード
レコード レコード
レコード レコード
レコード
作業バッファ レコード
入力バッファ1
入力バッファ2
出力バッファ1
出力バッファ2
2018/6/18 第10回 オペレーティングシステム 56
ファイルアクセス手法
• 逐次ファイル (sequential file)
– レコードを書き込んだ順で配置
• 書き込んだ順でのみ読み出し可能
– 磁気テープ上のファイルはこの構造
• レコードの位置はレコード番号で指定
• 途中のレコードを読む場合
– 先頭から読みたいレコードの前までを読み飛ばす必要あり
ファイルアクセス手法
• 直接アクセスファイル (direct access file)
– ランダムアクセスファイル (random access) – 任意の位置のレコードを直接アクセス可能
• ファイルのブロックサイズの粒度(固定)
– 逐次アクセスの 2 次記憶装置では実現不可能
• 磁気テープ
• ランダムアクセス可能な２次記憶装置
• ランダムアクセス可能な割当て方式
2018/6/18 第10回 オペレーティングシステム 58
ファイルの管理
• ディレクトリ (directory) … フォルダ
– ファイルの情報を保持する管理実体
• 1つのディレクトリで複数ファイルを管理
• ２次記憶上に保持
• ファイルアクセスの際にディレクトリもアクセス
– 高速化が必要
– 一部を主記憶にキャッシュ
2018/6/18 60
ディレクトリ操作
• ファイルの探索
• ファイルの生成
• ファイルの削除
• ディレクトリの下のファイルをリスト化
• ファイル名を変更 Rename a file
• 他のファイルシステムに移動
– 例：
• LinuxファイルシステムからWindowsファイルシステムへ
– 貸与したLaptop上でWindowsファイルシステムを見ることが可能
• LinuxファイルシステムからNFSファイルシステムへ
第10回 オペレーティングシステム
ディレクトリ作成の指標
• Efficiency ：高速にファイルを探索可能
• Naming ： ユーザー利便性
– 複数のユーザーが異なるファイルに同じ名前 – 同じファイルに異なる名前
• Grouping ：ファイルの特徴による論理的な集合を定義可能
– 例： all Java programs, all games, …
ディレクトリエントリの管理
• 線形リスト
– 特定のエントリの検索 ⇒ 線形探索 – エントリをソート ⇒ ２分探索
• エントリの挿入・削除が複雑 (2次記憶)
• ２分木
– エントリの挿入・削除が容易 – 線形リストより領域が必要
• ハッシュ
– 高速，エントリの挿入・削除が容易 – 同一ハッシュ値の対策が必要
2018/6/18 第10回 オペレーティングシステム 62
ディレクトリの階層
• 単一レベルディレクトリ
– システムにディレクトリは１つ
– ファイル名をシステム全体でユニークにする必要あり
• ２階層ディレクトリ
– ユーザごとに独立
• 自分の空間のみ参照
• ユーザ間共有不可
・・・
File
File File ・・・
ディレクトリ ・・・
File
File File ・・・
user n user 2
user 1 ・・・
マスタファイルディレクトリ
ユーザファイルディレクトリ
ディレクトリの階層
• 木構造ディレクトリ
– ディレクトリの階層化を一般化
• ルートディレクトリ，サブディレクトリ
・・・
File
File File
File File
File File
File File
ルートディレクトリ
サブディレクトリ
2018/6/18 第10回 オペレーティングシステム 64
ディレクトリの階層
• パス名 (path name) … 木構造の中での指定法
– 絶対パス名 (absolute path name)
• ルートから指定
– 例： /usr/local/bin/
– 相対パス名 (relative path name)
• 作業ディレクトリ (working directory)から辿る際のパス
• カレントディレクトリとも (current directory)
• UNIX の場合
– / で区切り、. がカレント、.. が一つ上
• /usr/local/bin にいて ../../lib とすると /usr/lib
2018/6/18 66
単一レベルディレクトリ
• すべてのユーザーが同じディレクトリを使う
Naming problem Grouping problem
第10回 オペレーティングシステム
２レベルディレクトリ
• ユーザ毎にディレクトリを作る
•Path name
•Can have the same file name for different user
•Efficient searching
•No grouping capability
2018/6/18 68
木構造ディレクトリ
• 効率良い検索
• グループ化機能
• カレントディレクトリ やワーキングディレク トリの概念
– cd /spell/mail/prog – more list
– mkdir tmp – rmdir tmp
第10回 オペレーティングシステム
Acyclic-Graph ディレクトリ
• 異なる名前で同一の実体を参照 (aliasing)
• If dict deletes list dangling pointer.
解決方法 :
– Backpointers, so we can delete all pointers.
Variable size records a problem.
– Backpointers using a daisy chain organization.
– Entry-hold-count solution.
2018/6/18 70
Acyclic-Graph ディレクトリ
• Hard Link
– ディレクトリからファイルの実体を参照 – ファイル側は reference count を保持
– 参照しているファイルが削除されてもファイルの実体は残る
• reference countがゼロでないから
• Symbolic Link (Soft Link)
– ファイルのパス（文字列）でファイルを参照
– 参照しているファイルが削除されると、symbolic linkしているファイル名から の参照が不可能
第10回 オペレーティングシステム