6. 出 (I/O) 制御 概要 出 デバイスのハードウェア 出 デバイスの制御 出 デバイスのソフトウェア 2008/5/27 出 制御とファイルシステム 1 出 (I/O) デバイス I/O=Input/Output= 出 あいおー と呼ぶ モニタキーボード FDD HDD バス 2008/5/27 出 制御とファイルシステム 2 1
I/O デバイスのハードウェア I/O デバイスの種類 ブロックデバイス 固定サイズのブロック単位で読書 ランダムアクセスが可能例 ) ディスク キャラクタデバイス 字列 ( バイトストリーム ) として読み書き シーケンシャルアクセス例 ) プリンタ, ネットワーク I/F 参考 PCI Express 10G Ethernet 2.5Gbits/sec 10Gbits/sec 様々なデバイス, バス, ネットワーク 2008/5/27 出 制御とファイルシステム 3 デバイスコントローラ I/Oデバイスの構成 機械的な部品 ( デバイス自身 ) と電子的な部品 ( コントローラ ) から構成 デバイスコントローラ 複数のデバイスを同時にコントロール可能 例 )IDEコントローラは2つ,SCSIコントローラは7つのデバイスを同時に制御できる デバイスコントローラの仕事 ビット列 (bit stream) をデータの固まり ( ブロック ) に変換する ( コントローラ内にバッファリングする ) 読み取ったブロックに対し必要に応じてエラー訂正を う ブロックのデータを主記憶にコピーする 2008/5/27 出 制御とファイルシステム 4 2
Memory-Mapped I/O デバイスコントローラのレジスタ群に値を read/write することで I/O を制御 IBM 360 PDP-11 Pentium レジスタへのアクセスの方式は次の3つがある メモリアドレス空間とは別にI/Oのアドレス空間を用意 (a) Memory-mapped I/O( I/O 空間をメモリ空間の一部にマップ )(b) Hybrid( 上記 2つの混合 )(c) それぞれ一 一短あるが,(c) が主流 2008/5/27 出 制御とファイルシステム 5 ダイレクトメモリアクセス (DMA) I/OデバイスとのデータのやりとりにCPUを使うのはもったいない DMA:CPUを介さずI/Oデバイスと主記憶の間で転送可能 DMA を使ったデータ転送の手順 2008/5/27 出 制御とファイルシステム 6 3
割込みとは? 割込み I/Oデバイスのデータ転送速度は 較的遅いデバイスからのデータが到着するまでの間,CPUでは別のプロセスの処理を いたいまとまったデータが到着後,CPUで っている処理を割込んで処理 I/O 開始実 休 完了プロセスA プロセス B 実 中待機中 出 中 2008/5/27 出 制御とファイルシステム 7 割込み処理の 順 割込みに対するサービス処理を開始 ( デバイスドライバ ) 1. デバイスが I/O 処理を完了 3. Ack 返す 2. 割込み信号発 バス 各 I/O デバイスはバス上の割込み用信号線を使用し割込みを通知 コントローラは IRQ (Interrupt ReQuest) 番号をバス経由で CPU に通知 CPU は interrupt vector に登録された, 割込み処理ルーチン (Interrupt service procedure) を実 し, 処理完了後 Ack を返す 2008/5/27 出 制御とファイルシステム 8 4
割込み発生時の CPU の処理 割込みが発生 1. CPU が割込み発生を検出 2. CPU がカーネルモードへ自動的に移 3. OS 内の割込み処理手続きへジャンプ 4. OS 内手続きは, 現在実 中のプロセス ( レジスタ等 ) を退避 5. 割り込みの種類を判定して処理を う 6. OS が,CPU モードをユーザモードに変更 7. プロセスの処理に戻る 割込み処理への割込み 追加割込み禁 割込み処理中は, 他の割り込みを一切受け付けない 選択的割込み許可 現在処理中のものより優先度の いものだけ受付 2008/5/27 出 制御とファイルシステム 9 I/O の処理 式 Programmed I/O (PIO, プログラム I/O) Interrupt-driven I/O ( 割り込み駆動型 ) I/O using DMA (DMA) 2008/5/27 出 制御とファイルシステム 10 5
Programmed I/O (1) 各デバイスとメインメモリの間のデータ転送を CPU が管理する転送方式 ユーザプロセスから 字列 ABCDEDGH を印刷する場合の手順 openシステムコールを呼ぶ プリンタが利用可能になるまでブロック printシステムコールを呼ぶ OSがカーネルのバッファにコピー プリンタの状況をチェックしつつOSが一 字ずつプリンタにデータを送出 2008/5/27 出 制御とファイルシステム 11 Programmed I/O (2) busy waiting print システムコール呼び出し時に OS が実 するコード マルチタスク OS では非効率 2008/5/27 出 制御とファイルシステム 12 6
割り込み駆動型 I/O 一 字印刷が完了するたびに割込みにより呼び出される 他のプロセスに CPU が渡される print システムコール呼出し時に実 されるコード 割込み処理ルーチン 印字速度が 100 字 / 秒の時,1 字あたり 10 ミリ秒の待ち時間 待ち時間を他のプロセスの実 に有効利用できる 2008/5/27 出 制御とファイルシステム 13 DMA を使った I/O DMA の処理完了時に割込みが起こり, 呼び出される print システムコール呼び出し時に実 されるコード 割込み処理ルーチン バッファ内の 字列全部の印刷を (CPU から て )1 回の割込みで実現できるため, 効率が良い 実際には,CPU の代わりに DMA が Programmed I/O 方式で印字 2008/5/27 出 制御とファイルシステム 14 7
I/O ソフトウェアの目的 デバイス非依存性 任意のデバイスにアクセスできるようプログラムが書ける 例 ) sort < input > output (FDD, HDD, CD-ROMなど指定可 ) 一様な名前付け ファイルやデバイスの名前を, デバイスの種類に依存せずにつけれる エラー処理 ハードウェアに近い側で ( エラー発生時 : デバイスドライバの順に ) 解決 同期転送 vs. 非同期転送 呼び出し側をブロックするタイプ vs. 割込みで駆動するタイプ ほとんどのI/Oは非同期 ただし, プログラムを書く時は同期の方が楽 バッファリング デバイスから転送されるデータは, 最終的な場所に直接保存できない 例 ) パケット : 受信してポート番号を るどのプロセスに渡すか分かる 共有型デバイス vs. 占有型デバイス ディスクは共有型 : 多くのユーザから同時にアクセス可能 テープドライブは占有型 : 同じテープに多くのユーザから書き込み要求が あったらうまく動作しない スプーリング 2008/5/27 出 制御とファイルシステム 15 I/O ソフトウェアの階層 I/Oソフトウェアシステムの階層 隣接した層の間には, 利用可能な機能, インターフェースが明確に定義 新たなデバイスへの対応が容易 2008/5/27 出 制御とファイルシステム 16 8
割込みハンドラ ユーザプログラムデバイス非依存ソフトウェアデバイスドライバ割込みハンドラハードウェア 割込みハンドラの仕事 割込み種類の判別 割込み処理ルーチン ( デバイスドライバ ) への制御の移 最も単純な場合の制御 I/Oを開始し, 処理完了による割込みが起こるまでドライバをブロック 出 処理後, ドライバでの処理を再開 (unblock) 実際にはもう少し複雑 2008/5/27 出 制御とファイルシステム 17 デバイスドライバ ユーザプログラムデバイス非依存ソフトウェアデバイスドライバ割込みハンドラハードウェア デバイスの制御に必要な専用プログラムコード OSがカーネルモードで実 抽象度の いread/write 機能を提供 2008/5/27 出 制御とファイルシステム 18 9
デバイス非依存ソフトウェア ユーザプログラムデバイス非依存ソフトウェアデバイスドライバ割込みハンドラハードウェア デバイス非依存ソフトウェアが提供する機能 デバイスドライバに対する一様なインターフェースバッファリングエラーの報告占有型デバイスの確保と解放デバイス非依存なブロックサイズ デバイス毎に物理的なブロックサイズは異なる ディスクのセクタ等 物理的な違いを吸収し, 全てのデバイスを同一ブロックサイズで読み書きできる機能を提供する 2008/5/27 出 制御とファイルシステム 19 一様なインターフェース (a) 標準ドライバインターフェースがない場合 デバイスごとにインターフェースが異なるとプログラムが大変例 ) デバイスごとに操作が違う (open/close, connect/disconnect 等 ) (b) 標準ドライバインターフェースがある場合 ドライバ設計者, 利用者のどちらも, インターフェースが同じなので, プログラムが楽 2008/5/27 出 制御とファイルシステム 20 10
ユーザプログラムにおける I/O 処理 I/O system の階層と各層の主な機能 I/O ライブラリ関数の例 count=write(fd, buffer, nbytes); printf( The square of %3d is %6d n, i, i*i); 2008/5/27 出 制御とファイルシステム 21 出 制御のまとめ I/Oデバイスのハードウェア 割込み制御, 出 制御 I/Oデバイスのソフトウェア 2008/5/27 出 制御とファイルシステム 22 11
7. ファイルシステム 概要 ファイルとディレクトリ ファイルシステムの実現 ファイルシステムの実例 2008/5/27 出 制御とファイルシステム 23 ファイルシステムとは ファイルの必要性 プロセスは実 中に情報をアドレス空間に保存 仮想アドレス空間サイズより大きなサイズの情報を扱いたい プロセス終了時保存した情報は消失 期間保存したい 情報を複数のプロセスからアクセス可能にしたい ファイルシステム OS においてファイルを扱う部分 構造, 名前付け, アクセス方法など 2008/5/27 出 制御とファイルシステム 24 12
ファイルの名前付け ファイルは生成時に 字列による名前がつけられる OS により 字列の制限が異なる (UNIX: 255 字まで ) ファイル名は 2 つの部分で構成されることが多い 名前. 拡張子 拡張子でファイルの種類をあらわす 対応するアプリケーションソフトとの関連付け 拡張子部分が 2 つ以上あることも file.c.z src.tar.gz 2008/5/27 出 制御とファイルシステム 25 ファイルの種類 標準ファイル, ディレクトリ, デバイスファイル ( キャラクタ型 / ブロック型 ) 標準ファイル : テキストファイルまたはバイナリファイル ライブラリ手続きの集合 (a) 実 可能ファイル (b) アーカイブファイル 2008/5/27 出 制御とファイルシステム 26 13
ファイルへのアクセス シーケンシャルアクセス ファイル中の全ての 字またはレコードをファイルの先頭から順番に読込み スキップしたり, 順序を無視しての読込みはできないが, 巻き戻しは可能 媒体が磁気テープであればこの方式は便利 ランダムアクセス ファイル中の 字またはレコードは任意の順序で読込み可能 多くのアプリケーションで必要 ( 特にデータベースでは必須 ) 読込み開始位置の指定方法 (1) 各読込み操作終了後にファイル中の現在位置を返す (2) シーク 操作により, 読込み開始位置を設定後, 読込みを う 2008/5/27 出 制御とファイルシステム 27 ファイルの属性 各ファイルは名前, データ以外に属性情報を持つ どんな属性を持つかはOSによりまちまち 2008/5/27 出 制御とファイルシステム 28 14
ディレクトリ ファイルを収納する 箱 ( 別名 フォルダ ) ディレクトリ自体も特殊なファイル ディレクトリシステムの種類 単一レベルディレクトリ 2 階層ディレクトリ多階層ディレクトリ 省略 2008/5/27 出 制御とファイルシステム 29 多階層ディレクトリ 木構造からなる階層ディレクトリシステム ユーザがサブディレクトリを作ることが可能 ファイルの論理的なグループ分けができる 2008/5/27 出 制御とファイルシステム 30 15
パス名 (Path names) 木構造ディレクトリ上でのファイルの指定方法 絶対パス名と相対パス名 絶対パス名 unixの場合 /usr/ast/mailbox windowsの場合 usr ast mailbox 相対パス名 カレントディレクトリからの相対位置で指定. はカレントディレクトリ.. は親ディレクトリ 例 ) カレントディレクトリが /usr/astのとき cp mailbox mailbox.bak cp../lib/dictionary. UNIX のディレクトリツリー 2008/5/27 出 制御とファイルシステム 31 ファイルシステムの実現 ディスクはパーティションに分割される パーティション毎に異なるファイルシステムを保存可能 MBR (Master Boot Record) ディスクの最初のセクタ ( セクタ0) に保存 各パーティションの開始 終了アドレスのテーブルを保持 一つのパーティションだけがactive OSのブート BIOSがMBRを読み込み activeなパーティションのブートブロック ( 最初のブロック ) を読込み ブートブロックのプログラムがactiveパーティションのOSを読込み ファイルシステムに固有の情報 (FS の種類, ブロック数など ) 2008/5/27 出 制御とファイルシステム 32 16
ファイルの実現 (1) ファイルへのディスクブロックの割付 : 連続割付とリンク割付連続割付 (Contiguous Allocation) 50KBのファイルなら,50 個の連続した1KBブロックを割り付ける 利点 : 実装が容易 ( 開始アドレス, ブロック数のみ記憶 ), 読み込みが速い 欠点 : ディスク領域の外部断片化がおこる 外部断片化の例 2008/5/27 出 制御とファイルシステム 33 ファイルの実現 (2) (2) リンク割付 (Linked List Allocation) 各ブロックの最初のワードを次のブロックへのポインタに使用 すべてのブロックをファイルの保存に使用可能 欠点 : ブロックへのアクセスはランダムアクセスとなるため遅い 各ブロックでポインタを記憶する必要がある 2008/5/27 出 制御とファイルシステム 34 17
リンク割付における改善 FAT (File Allocation Table) をメモリ上に用意 各エントリは次のブロックの番号を記憶 どのブロックがどういう順番で連結されているかがメモリの参照で分かるので, ファイルの読み込みの 速化が可能 ここで終わり 欠点 : FATはディスクサイズに 例してメモリ容量を消費 20GBのディスクでFATのサイズは60 80MBになる 2008/5/27 出 制御とファイルシステム 35 ファイルの実現 (3) i-node (index-node) ファイルの属性 + 使用ブロックへのアドレスのリスト 利点 : i-nodeはファイルをオープンしている時だけ, メモリに読込まれる メモリ消費量は, ディスクの容量に関係なく,kn バイト (i-nodeのサイズがkバイト, 同時オープンファイル数がnのとき ) ファイルサイズが大きくなり i-node サイズを超えた場合 2008/5/27 出 制御とファイルシステム 36 18
ディレクトリの実現 ディレクトリ ディレクトリエントリのリストからなるファイル ディレクトリエントリ ファイル ( ディレクトリ ) 名, 属性, 先頭のディスクブロック /i-nodeへのポインタ,etcを含む i-node MS-DOS/Windows 各エントリは固定サイズ 属性とディスクアドレスとを持つ UNIX 各エントリが i-node を参照 4 つのファイル ( ディレクトリ ) を持つディレクトリの実現例 2008/5/27 出 制御とファイルシステム 37 ディスクの領域管理 ブロックサイズ ( 読み書きの単位 ) 大きいほどファイルへのアクセス時間が 速 読み書きするブロック数が減り, シークの回数が少なくなる さいほどディスク領域の利用効率が い 32KB ブロックで,1KB のファイルを保存する場合, 利用効率は 1/32 3% ディスク利用効率 ( 全ファイルサイズを 2KB と仮定 ) Block size データ転送速度 UNIX では 1KB Windows(FAT) では,512B 32KB( アドレス, ディスク容量に依存 ) 2008/5/27 出 制御とファイルシステム 38 19
未使用ブロックの管理 連結リスト法 未使用ブロックのアドレスリスト ( 固定数 ) の連結リストで表す ビットマップ法 ディスクの残り領域が少ないときは有利 各ブロックの使用状況を1ビット ( 空きを0) で表す 使用領域は, 連結リスト法より少ない これらの情報は空きブロックに保存される 2008/5/27 出 制御とファイルシステム 39 ファイルシステムの整合性 ファイルシステムの整合性が狂う要因 ディスクブロック ( ディレクトリエントリ,i-nodeなど) の書き込み完了前にシステムがクラッシュ ( あるいは電源オフなど ) ファイルシステムの不整合の検出 修正が必要 (fsck, scandisk 等を利用 ) 各ディスクブロックについて, ファイル中に何回出てくるか, 未使用ブロックリストに何回出てくるかをカウント ブロック番号 足すと 1 が正しい ブロック番号 矛盾のない状態 ディスクブロックがリストにない状態 ( 使用中でも未使用でもない ) 未使用ブロックリストに重複がある状態 ( ビットマップ法では起こらない ) データブロックに重複がある状態 ( 同じブロックが複数のファイルの一部に!) 2008/5/27 出 制御とファイルシステム 40 20
UNIX V7 ファイルシステム (1) DEC PDP-11 (1970 年 ) で使用されたファイルシステム 多階層ディレクトリ ( リンクも可 ),14 字のファイル名( 任意のASCII 字が使用可 ) ディスクブロックの割付はi-node 方式 i-nodeは, 属性情報 ( ファイルサイズ,3つの時間, 所有者 ID, グループID, アクセス権, リンクカウント ) を含む 最大ファイル数は 64K=65536 UNIX V7 のディレクトリエントリ 2008/5/27 出 制御とファイルシステム 41 UNIX V7 ファイルシステム (2) 大容量ファイルの保存方法 10 個の直接ブロックへのアドレス 直接ブロックだけでは不足するファイルは間接ブロックを使う さらに足りない場合は, 2 重間接ブロックを使う 間接ブロック 2 重間接ブロック 3 重間接ブロック へのポインタ それでも足りない場合は, 3 重間接ブロックを使う 2008/5/27 出 制御とファイルシステム 42 21
UNIX V7 ファイルシステム (3) パス /usr/ast/mbox の探索手順 ルートディレクトリからはじめる ディレクトリ ( ファイル ) の中身を て, 該当するディレクトリ ( ファイル ) の i-nodeを読み込む 上記の繰り返し. 2008/5/27 出 制御とファイルシステム 43 ファイルシステムのまとめ ファイルシステム ファイルとディレクトリの実現方法 ディスクの領域管理 ファイルシステムの実例 UNIX V7 2008/5/27 出 制御とファイルシステム 44 22
テスト 5 月 30 ( )2 限 参考書, 講義資料持込み可 試験内容 各概念が理解できているか プロセス, スレッド, コンテキストスイッチ, スケジューリング, 競合回避, スワッピング, 仮想記憶, ページング, セグメンテーション, 出 制御, 割込み制御, ファイルとディレクトリ, 外部断片化, 内部断片化, など各アルゴリズムが正確に再現できるか スケジューリング, ページング, ディスクブロック割付, 利用効率, など 2008/5/27 出 制御とファイルシステム 45 23