EuDs

期末復習#

第 3 章 プロセス#

• オペレーティングシステムがタスクスケジューリングとリソース割り当てを行う基本単位
• プロセスには以下が含まれる：
  1. プログラムコード
  • テキストセクション
  2. プログラムカウンタとプロセッサのレジスタ
  3. スタック
  • 関数パラメータ
  • 戻りアドレス
  • ローカル変数
  4. データセクション
  • グローバル変数
  5. ヒープ
  • 動的に割り当てられたメモリ
• プロセス状態
  • 五状態モデル
    • new
    • ready: プロセッサに割り当てられるのを待っている
    • waiting: 何らかのイベントが発生するのを待っている
    • running
    • terminated
• プロセス制御ブロック（PCB）
  • 含まれる情報：
    • プロセス番号
    • プロセス状態
    • プログラムカウンタ
      • 次の命令のアドレス
    • CPU レジスタ
    • CPU スケジューリング情報
    • メモリ管理情報
    • 会計情報
    • I/O ステータス情報

プロセススケジューリング#

• スケジューリングキュー

  1. ジョブキュー
  • システム内のすべてのプロセスの集合
  • プロセス / ジョブがシステムに入ると、ジョブキューに入れられる
  2. レディキュー
  • "(メイン) メモリ" に存在し、実行の準備ができているプロセスの集合
  3. デバイスキュー
  • I/O デバイスを待っているプロセスの集合

• スケジューラ

  1. 長期スケジューラまたはジョブスケジューラ
  • ジョブキュー -> レディキュー
  • UNIX や Windows のようなタイムシェアリングシステムでは存在しない場合がある

    • 短期スケジューラのために新しいプロセスをメモリに配置する

  2. 短期スケジューラまたは CPU スケジューラ：プロセススケジューリング

  • 次に実行すべきプロセスを選択し、CPU を割り当てる

  • 実行が非常に頻繁であるため、毎回の選択に時間をかけてはいけない。さもなければオーバーヘッドが発生する

  3. 中期スケジューラまたはスワッピング
  • スワップアウト：メモリからディスクにプロセスを削除し、マルチプログラミングの度合いを減少させる
  • スワップイン：プロセスをメモリに導入する

• コンテキストスイッチ

  • CPU が別のプロセスに切り替わる

プロセスに対する操作#

1. fork()
   • 新しいプロセスは元のプロセスのアドレス空間のコピーで構成される
   • fork () の戻りコードは子プロセスに対してはゼロである
   • 子プロセスは親プロセスのアドレス空間とリソースをコピーするが、親プロセスのスレッドはコピーしない

プロセス間通信#

• 共有メモリ
• メッセージパッシング

名詞解説：#

• マルチプログラミング：常にいくつかのプロセスが実行されている状態で、CPU の利用率を最大化すること
• タイムシェアリング：ユーザーが各プロセスと相互作用できるように、CPU をプロセス間で非常に頻繁に切り替えること

第 4 章 スレッド#

• プロセス vs スレッド
  • スレッドは CPU の分配単位
  • プロセスはリソースの分配単位
  • スレッドはプロセス内の実行単位
    • 一つのプロセスは複数のスレッドを含むことができ、これらは同じアドレス空間とシステムリソース（オープンファイル、シグナルなど）を共有する。
    • 各スレッドは自分のスタック空間と実行コンテキストを持つが、同じプロセス内でコードセグメント、データセグメント、ヒープなどのリソースを共有する。
• マルチスレッドプログラミングの利点
  1. 応答性
  2. リソース共有
  3. 経済性
  4. マルチプロセッサアーキテクチャの利用

マルチスレッドモデル#

• 二種類のスレッド

  • ユーザースレッド
    • ユーザーレベルでスレッドライブラリによって提供される
  • カーネルスレッド
    • OS によって直接提供および管理される

• カーネルスレッドとユーザースレッドの関係

  1. 多対一モデル
  2. 一対一モデル
  3. 多対多モデル
  4. 二層モデル
     • 主体は多対多モデル
     • ユーザースレッド（重要なタスク）はカーネルスレッドにバインドされることができる

• UNIX システムにおける fork () の二つのバージョン

  1. すべてのスレッドを複製する
     • fork () の後に exec () が呼ばれない場合、すべてのスレッドを複製する
  2. fork () システムコールを呼び出したスレッドのみを複製する
     • fork () の直後に exec () が呼ばれる場合、呼び出したスレッドのみを複製する

第 5 章 CPU スケジューリング#

基本概念#

• CPU スケジューリングの決定は、プロセスが以下の状態に切り替わるときに行われる：
  1. 実行中から待機状態に切り替わる
     • I/O 要求の結果
     • 子プロセスの一つの終了を待つための wait の呼び出し（例：wait (NULL);）
  2. 実行中からレディ状態に切り替わる
     • 割り込みが発生したとき
  3. 待機からレディに切り替わる
     • I/O の完了
  4. 終了する
• 非剥奪型
  • 一度 CPU がプロセスに割り当てられると、そのプロセスは CPU を解放するまで保持する
  • スケジューリングは状況 1 と 4 でのみ発生する
  • 簡単で、ハードウェア要求が低い
• 剥奪型

スケジューリング基準#

1. CPU 利用率
2. CPU スループット
   • 単位時間あたりに実行を完了するプロセスの数。
3. プロセスターンアラウンドタイム
   • プロセスの提出から完了までの時間、以下を含む
     • メモリに入るのを待つ時間
     • レディキューで待つ時間
     • CPU で実行する時間
     • I/O を行う時間
4. プロセス待機時間
   • プロセスがレディキューで待機していた時間。
5. プロセス応答時間
   • リクエストの提出から最初の応答 / 結果が生成されるまでの時間

スケジューリングアルゴリズム#

1. 先着順（FCFS）
   • 非剥奪型
   • 護衛効果
2. 最短ジョブ優先（SJF）
   • 最小平均待機時間
   • 種類
     1. 剥奪型 SJF は現在実行中のプロセスを剥奪することを許可する
     2. 非剥奪型
   • 長期スケジューリングに適している
3. 優先度スケジューリング
   • 問題：飢餓
   • 解決：エイジング – 時間が経つにつれてプロセスの優先度を上げる
4. ラウンドロビン（RR）
   • 特にタイムシェアリングシステム向けに設計されている
   • 剥奪型
   • タイムクォンタム
     • 80% の CPU バーストがタイムクォンタムより小さいことを保証する必要がある
   • 応答時間 = 2*(n-1)*q
5. マルチレベルキューアルゴリズム
6. マルチレベルフィードバックキューアルゴリズム
   • 最も一般的なスケジューリングアルゴリズム

マルチプロセッサスケジューリング#

• 同種 vs. 異種 CPU
  • 同種：各プロセッサが同じ
• マルチプロセッサスケジューリングへのアプローチ
  • 非対称マルチプロセッシング
    • 一つのプロセッサ（マスターサーバー）のみがすべてのスケジューリング決定、I/O 処理を行う
  • 対称マルチプロセッシング
    • 各プロセッサが自己スケジューリングを行う

第 6 章 プロセス同期#

• レースコンディション
  • 複数のプロセスが同時に共有データにアクセスし操作する状況。
  • 共有データの最終的な値は、どのプロセスが最後に終了するかに依存する。

クリティカルセクション問題#

• クリティカルセクション

  • 各プロセスには、共有データにアクセスするコードセグメントであるクリティカルセクションがある
  • 共有変数の数だけクリティカルセクションが存在する

• クリティカルセクション問題の解決基準

  1. 相互排除
  2. 進行
  3. 限定待機

• ピーターソンの解法

  • 手を挙げる + トークン

• ハードウェアベースの解法

  • 割り込みを無効にする
    • マルチプロセッサには適さない
  • 原子操作

セマフォ#

• セマフォ S – 整数変数

  • 非負の値で初期化可能
  • 二つの不可分（原子）操作：P () と V () を介してのみアクセスできる

• P (): wait () 操作

  Copy

  wait (S) { 
    while (S.value <= 0) ; 	// no-op
      S.value--;
  }
  

• V (): signal () 操作

  Copy

  signal(S){
    S.value++;
  }
  

• 主な問題：ビジーウェイティング（スピンロック）

  • 利点
    1. プロセスがロックを待つ必要があるとき、コンテキストスイッチは必要ない
    2. ロックが短時間保持されることが予想される場合、スピンロックは有用である
  • 欠点
    1. 他のプロセスが生産的に使用できる CPU サイクルを浪費する
  • 解決：wait () と signal () の定義を変更する マルチプロセッサシステムに適用
    • Wait (): プロセスはビジーウェイティングに従事するのではなく、block () することができる
    • Signal (): 待機状態のプロセスをレディ状態に変更する

• 実装

  1. 単一プロセッサ環境
  • 割り込みを無効にする
  2. マルチプロセッサ環境
  • クリティカルセクションが適用可能

第 7 章 デッドロック#

• 必要条件
  1. 相互排除
  2. 保持と待機
  3. 剥奪なし
  4. 循環待機

デッドロック処理の方法#

1. 予防

   • 必要条件のうち少なくとも一つが成立しないようにするための方法を提供する
   • 条件 2 に対して：すべてまたは何も；リソースがないときにのみ要求する
   • 条件 3 に対して：譲歩；奪取
   • 条件 4 に対して：順序実行
   • 欠点：デバイス利用率が低く、システムスループットを減少させる。

2. 回避

   • 追加情報を使用して、現在の要求が満たされるか、遅延しなければならないかを決定する
   • 方法：
     1. リソース割り当てグラフ
        • サイクルがある：unsafe 状態にある；デッドロック状態にある可能性がある
     2. バンカーのアルゴリズム

3. 検出と回復

   • 方法:
     • 待機グラフ
       • 各リソースタイプの複数のインスタンスを持つリソース割り当てシステムには適用できない
     • バンカーのアルゴリズム
   • 検出アルゴリズムをいつ、どのくらいの頻度で呼び出すかは以下に依存する：
     • デッドロックが発生する可能性がどのくらいあるか？
     • どのくらいのプロセスがロールバックする必要があるか？

4. 無視

第 8 章#

• アドレスは以下のように表現されることがある

  1. シンボリックアドレス
  2. 再配置可能アドレス
  3. 絶対アドレス

• アドレスバインディング

  • 変換：
    • シンボリックアドレス -> 再配置可能アドレス：コンパイラ
    • 再配置可能アドレス -> 絶対アドレス：リンケージエディタまたはローダ
  • 発生する時期
    1. コンパイル時
       • メモリ位置がコンパイル時に知られている場合、絶対コードを生成できる
       • メモリ位置がコンパイル時に知られていない場合、再配置可能コードを生成する必要がある
    2. ロード時（+ リンケージ時）
       • メモリ位置がロード時に知られている場合、この時に絶対コードを生成できる
    3. 実行時
       • メモリ位置がコンパイル時およびロード時に知られていない場合、バインディングは実行時まで遅延される
       • 実行時に絶対コードを生成する必要がある

論理アドレスと物理アドレス空間#

• 論理アドレス ：CPU

  • バーチャルアドレスとも呼ばれる
  • 再配置アドレスと論理アドレスには直接の関係はない

• 物理アドレス ：メモリユニット

• 論理（バーチャル）アドレスと物理アドレスは、実行時アドレスバインディングスキームで異なる

  • 再配置可能コードは CPU によって見られる
  • 絶対コードはメモリユニットによって見られる

• メモリ管理ユニット（MMU）

  • 実行時にバーチャルアドレスを物理アドレスにマッピングするハードウェアデバイス

• 動的ロード

  • プロセスが実行されるために、プログラム全体とデータが物理メモリに存在する必要はない
  • 利点：
    1. メモリ空間の利用効率が向上
    2. オペレーティングシステムから特別なサポートは必要ない

• 動的リンク

  • リンクは実行時まで延期される
  • OS からの支援が必要

連続メモリ割り当て#

1. 固定サイズの連続パーティション
   • 強み（利点）
     • 実装が簡単
     • オーバーヘッドが少ない
   • 弱み（欠点）
     • 内部断片化
       • 割り当てられたメモリが要求されたメモリより大きい場合がある
     • 固定数のプロセス
2. 動的連続パーティション（可変パーティション）
   • ホール – 利用可能なメモリのブロック
   • 割り当てアルゴリズム
     1. ファーストフィット:
        • 最初から、または現在の位置から開始
     2. ベストフィット
        • サイズで順序付けられていない限り、リスト全体を検索する必要がある
        • 無駄になる可能性のある最小の残りのホールを生成する
     3. ワーストフィット
        • サイズで順序付けられていない限り、リスト全体を検索する必要がある
        • 小さなプロセスが多い場合に効果的
   • 問題：
     • 外部断片化

• 断片化の解決策

  1. コンパクション
     • 外部断片化を減少させる
     • すべての空きメモリを一つの大きなブロックにまとめるためにメモリ内容をシャッフルする
     • 実行時に行われ、動的再配置が可能な場合にのみ可能
     • プロセスとホールを移動するのに高価になる可能性がある
  2. ページング
  3. セグメンテーション

• 連続メモリ割り当ての欠点

  • 主メモリ内の断片化
  • ディスク上でのコンパクションは不可能

ページング#

• フレーム：物理メモリを固定サイズのブロックに分割

• ページ：論理メモリを固定サイズのブロックに分割

  • ページサイズはフレームサイズと等しい
  • サイズ n ページのプログラムをロードするために n 個の空きフレームを見つける

• 論理アドレスを物理アドレスに変換
  アドレス空間が 2^m でページサイズが 2^n の場合

  • CPU によって生成されるすべての論理アドレスは以下に分割される：
    1. ページ番号（p: ページ番号）
       • ページテーブルへのインデックスとして使用される
       • ページテーブルには、物理メモリ内の各ページのベースアドレス（f: ブロック番号）が含まれる
       • p =address/2^n はアドレスの m-n ビットに等しい
    2. ページオフセット（d: オフセット）
       • ベースアドレス（f: ブロック番号）と組み合わせて、メモリユニットに送信される物理メモリアドレスを定義する
       • d =address%2n はアドレスの n ビットに等しい
  • 物理アドレス
    1. フレーム番号（f: フレーム番号、ブロック番号）
    2. ページオフセット (d: ページオフセット、ブロックオフセット)

• ページサイズの選択

  • 大きい場合：
    • ディスク I/O がより効率的
    • ページテーブルサイズが小さくなる
  • 小さい場合：
    • 内部断片化が小さくなる

• フレームテーブル

  • 各物理ページフレームに対して一つのエントリを持つ
    • フレームが空いているか、どのプロセスに割り当てられているかを示す

• ページテーブル

  • 各プロセスはページテーブルのコピーを維持する必要がある
  • 計算
    • ページテーブルエントリが 4 バイトの場合
      • 2^32 物理ページフレームの一つを指すことができる
      • フレームサイズ（= ページサイズ）が 4KB の場合、システムは 2^44 バイト（2^32×2^12=16TB）の物理メモリにアドレス指定できる
    • 32 ビット CPU の場合
      • ページサイズ: 4k (=2^12)
      • テーブルサイズ：2^32/2^12=1M
      • 各エントリのサイズ : 4 バイト
      • ページテーブルのサイズは： 4 MB
  • 位置
    1. 直接レジスタに保存：
       • 効率的で高価
       • ページテーブルが合理的に小さい場合に可能
    2. メインメモリに保存し、ページテーブルベースレジスタ（PTBR）でその位置を保存
       • プロセス切り替え時に、ページテーブルをロードするには PTBR を変更するだけで済む
       • 各データ / 命令アクセスには二回のメモリアクセスが必要
         • 一回はページテーブルのため
         • 一回はデータ / 命令のため
    3. 翻訳ルックアサイドバッファ（TLB）またはアソシエイトメモリ
       • 並行検索
       • ページテーブルエントリのごく一部を含む

ページテーブルの構造#

• 問題：ページテーブルが過剰に大きくなる可能性がある
• 解決策：ページテーブルを小さな部分に分割
  1. 階層ページング
  2. ハッシュページテーブル
  3. 反転ページテーブル

1. 階層ページング
   • 欠点：
   1. 遍歴が必要で、プロセスが多すぎる
   2. 共有が可能であるが、プロセス番号は一つしか埋められない
   3. 64 ビットには適さない
   • 利点：
     1. 必要なスペースが小さい
2. ハッシュページテーブル
   • ハッシュテーブル -> リスト内を遍歴してマッチング
3. 反転ページテーブル

• システム内に一つのページテーブルのみ
• メモリの各実際のページ（または物理フレーム）に対して一つのエントリ
• 欠点：
  • ページ参照が発生したときにテーブルを検索するのに必要な時間が増加する
  • メモリ共有の難しさを引き起こす

セグメンテーション#

• ユーザーのプログラムの見方：プログラムはセグメントの集合であり、セグメントは以下のような論理単位である：
  • メインプログラム
    • 手続き、関数、メソッド、オブジェクト
    • ローカル変数、グローバル変数
    • コモンブロック
    • スタック
    • シンボルテーブル
    • 配列

第 9 章 バーチャルメモリ#

• プログラム全体が物理メモリに存在する必要はない。この利点には以下がある：

  • プログラムのサイズがメモリによって制限されなくなる
  • より多くのプログラムが同時に実行可能
  • 各ユーザープログラムをメモリにロードまたはスワップするために必要な I/O が少なくなり、プログラムの実行が速くなる

• バーチャルメモリ管理

  • コンピュータが実際よりもはるかに多くのメモリを持っているように見える技術を説明するために使用される用語

• バーチャルメモリは以下を介して実装できる：

  • デマンドページング
  • デマンドセグメンテーション

デマンドページング#

• アイデア：必要なときにのみページをメモリに持ってくる

  • スワッピングを伴うページングシステムに似ている

• ハードウェア

  • ページテーブル。追加の有効–無効ビットが必要
    • v -》 ページは合法でメモリに存在する
  • 二次メモリ
    • 高速ディスク、スワップスペース
    • メモリに存在しないページを保持する

• ページフォルト

  • 無効とマークされたページへのアクセスはページフォルトトラップを引き起こす
  • 処理
    1. オペレーティングシステムは別のテーブル（PCB）を見て決定する：
       • 無効な参照 -> 中止
       • メモリに存在しないだけ（2 に進む）
    2. 空のフレームを取得する
    3. 必要なページをフレームにスワップする
    4. ページテーブルを修正し、検証ビットを v に設定する
    5. ページフォルトを引き起こした命令を再起動する
  • 特殊：
    1. 一つの命令が複数のページフォルトを引き起こすことがある
    2. 命令の再実行
    3. 命令実行中に中断される。
  • 通常の中断と比較：
    • 一つの命令が実行された後、中断要求があるかどうかを確認する
      • ある：中断を実行
      • ない：次の命令を実行

ページ置換#

置換アルゴリズム

1. FIFO ページ置換

   • ベラディの逆説：フレームが多いほど -> ページフォルトが増える

2. 最適ページ置換（OPT）

   • 最も遅く使用されるページまたは後で最も長い時間使用されないページを置換する

3. 最も最近使用された（LRU）アルゴリズム

   • アイデア：最近の過去を近い未来の近似として使用する
   • 実装：
   • カウンター
   • スタック

4. LRU 近似アルゴリズム

   1. 追加参照ビットアルゴリズム
   2. セカンドチャンス（クロック）
   3. 拡張セカンドチャンスアルゴリズム

5. カウントベースのページ置換

   • 最も頻繁に使用される
   • 最も頻繁に使用される

6. ページバッファリングアルゴリズム

   • ページ置換アルゴリズムへの補助手続き

フレームの割り当て#

• 二つの主要な割り当てスキーム

  1. 固定割り当て
     • 等しい割り当て
     • 比率割り当て
  2. 優先度割り当て
     • サイズではなく優先度を使用して比率割り当てスキームを使用する

• グローバル vs. ローカル割り当て

  1. ローカル置換
     • プロセスが自分の割り当てられたフレームのセットからのみ選択できるようにする。
     • 割り当てられたフレームの数を増やすことはできない
     • 外部の状況に影響されない
  2. グローバル置換
     • プロセスがすべてのフレームのセットから置換フレームを選択できるようにする。たとえそのフレームが現在他のプロセスに割り当てられていても
     • 割り当てられたフレームの数を増やすことができる
     • ページフォルト率を制御することはできない。
  • 一般的に、グローバル置換が優れている。

スラッシング#

• プロセスが実行よりもページングに多くの時間を費やしている場合、スラッシング（揺れ動く）と呼ばれる
• アプローチ
  1. ローカル置換アルゴリズムを使用する
  2. ワーキングセット戦略
     • システム内の各プロセスのワーキングセットサイズを計算する
  3. ページフォルト頻度（PFF）スキーム
     • 実際の率が低すぎる場合、プロセスからフレームを削除する
     • 実際の率が高すぎる場合、プロセスに別のフレームを割り当てる
     • フレームが空いていない場合、プロセスを一時停止する

その他の考慮事項#

• ページサイズの選択には以下を考慮する必要がある：
  1. 内部断片化
  2. ページテーブルのサイズ
  3. I/O オーバーヘッド（シーク時間、レイテンシ時間、転送時間）
  4. ローカリティ
  5. ページフォルト率
     • 順次アクセス：ページサイズが大きいほど、ページフォルト率が小さくなる
     • ランダムアクセス：ページサイズが大きいほど、メモリに保持できるページが少なくなり、ページフォルトごとに転送されるデータが多くなるため、より多くのページングアクションが発生する可能性がある。
• より高速なハードディスクをインストールするか、複数のコントローラーと複数のハードディスクを使用する
  • ディスクのボトルネックがより高速な応答とより多くのスループットによって取り除かれると、CPU はより迅速にデータを取得できるようになる

第 10 章 ファイルシステムインターフェース#

• ファイル
  • ファイルは、二次記憶装置に記録された関連情報の名前付きコレクションである
  • 六つの基本操作
    1. 作成
    2. 読み取り / 書き込み / シーク
    3. 削除
    4. 切り詰め：ファイルの内容を消去するが、その属性は長さを除いて保持する
  • 補助操作
    • open(F):
      1. ディスク上のディレクトリ構造でエントリ F を検索する
      2. ディレクトリエントリをオープンファイルテーブルにコピーする
      3. ファイルディスクリプタを割り当てる
    • close(F):
      1. オープンファイルテーブルのディレクトリエントリをディスク上のディレクトリ構造にコピーする
      2. ファイルディスクリプタを解放する

アクセス方法#

• ファイル内の情報にアクセスする方法は以下の通り：
  1. 順次アクセス
  2. 直接アクセス
  3. その他のアクセス
     • ファイルのインデックスを構築することを含む

ディレクトリ構造#

• シンボルテーブル

  • ディレクトリはファイル名をそのディレクトリエントリに変換するシンボルテーブルとして見ることができる

• 基準

  1. 効率
  2. 名前付け
  3. グルーピング

• スキーム

  1. 単一レベルディレクトリ
  2. 二レベルディレクトリ
     • ポジティブ
       • 効率的な検索
     • ネガティブ
       • グルーピング機能がない
       • 異なるユーザー間でファイルを共有するのが難しい
  3. ツリー構造ディレクトリ
     • ポジティブ
       • 効率的な検索
       • グルーピング機能
     • ネガティブ
       • 異なるユーザー間でファイルを共有するのが難しい
  4. 非循環グラフディレクトリ
     • ツリー構造のディレクトリ + 共有サブディレクトリまたはファイル
     • 共有を実装するためにリンクと呼ばれる新しいディレクトリエントリを作成する
     • 新しいリンクが追加されるときにサイクルを避けることが難しい
  5. 一般的なグラフディレクトリ
     • 既存のツリー構造ディレクトリにリンクを追加する
     • 非循環グラフディレクトリがより良い

• ハードリンク

  • ln /usr/local/python3 python
  • ディレクトリにはファイルデータへのポインタのみが保存される
  • 一つのファイルが複数のディレクトリから参照されることを許可する。
  • ディレクトリをリンクすることはできず、ファイルシステムを越えることもできない
  • ls -iを使用してハードリンクかどうかを確認する

• ソフトリンク

  • “ショートカット”
  • ソフトリンクもファイルである
  • ln -s ../p24 p24
  • ディレクトリは “ツリー” から “グラフ” に変わり、依然として環状グラフである

• ACL: アクセス制御リスト

  • 各ファイルまたはディレクトリには ACL がある

ファイルシステムの実装#

• ファイルシステムは層に分かれている
  1. アプリケーションプログラム
  2. 論理ファイルシステム
     • FCB: ファイル制御ブロック
  3. ファイル組織モジュール
  4. 基本ファイルシステム
  5. I/O 制御
  6. デバイス

割り当て方法#

• 割り当て方法は、ファイルのためにディスクブロックがどのように割り当てられるかを指す

• 連続割り当て

  • 各ファイルはディスク上の連続ブロックのセットを占有する
  • 順次アクセスと直接アクセスの両方をサポートする
  • 問題：
    1. 外部断片化
    2. ファイルが成長できない

• リンク割り当て

  • 各ファイルはディスクブロックのリンクリストである：ブロックはディスク上のどこにでも散在する可能性がある
  • 利点
    1. 実装が容易
    2. 外部断片化がない
    3. ファイルの成長が容易
  • 欠点：
    1. ランダムアクセスができない
    2. 信頼性が低い
    3. 遅い（リンクリストはディスク上に保存されるため、複数回のクエリが必要）
  • 改善： ファイル割り当てテーブル（FAT）
    • リンクリスト情報を各データブロックではなく、単独の FAT テーブルに保存し、バックアップを行う

• インデックス割り当て

  • すべてのポインタを一つの場所にまとめる：インデックスブロック

  • 大きなファイルへの解決策

    1. リンクスキーム
       • インデックステーブルのブロックをリンクする
    2. マルチレベルインデックス
    3. 組み合わせスキーム
       • 一部は直接ポインタで、一部はマルチ間接ブロックである

  • 基準

    1. ストレージ利用効率
    2. データブロックアクセス時間
    • 連続割り当て：サイズが既知のファイルに適している
    • リンク割り当て：ストレージ利用に適している
    • インデックス割り当て：アクセス時間はインデックス構造、ファイルサイズ、ブロック位置に依存する

空きスペース管理#

• 空きスペースリストの実装
  1. ビットベクタ
     • 利点
       • 実装が簡単
       • 最初の空きブロックを見つけるのが効率的
     • 欠点
       • ビットマップは追加のスペースを必要とする
       • メインメモリに全体のベクタを保持しない限り非効率的
  2. リンクリスト（空きリスト）
     • 利点
       • スペースの無駄がない
     • 欠点
       • リストを遍歴する際に非効率的
  3. グルーピング
  • 最初の空きブロックが n 個の空きブロックのアドレスを保存する
  • 大量の空きブロックを見つけるのが容易

大容量ストレージシステム#

• 磁気ディスクの構造

  • ディスクプレート
  • トラック
  • セクター
    • 各トラックは複数のセクターに細分化される
  • シリンダー
    • 一つのアーム位置にあるトラックのセット

• CLV vs. CAV

  1. ClV : 定常線速度
     • CD-ROM， DVD-ROM
     • 最外層のトラックはより多くのセクターを保持する
  2. CAV : 定常角速度
     • 磁気ディスク
     • ビットの密度は内側のトラックから外側のトラックにかけて減少し、データレートを一定に保つ

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

• アクセスタイム
  1. シークタイムは、ディスクアームが目的のセクターを含むシリンダーにヘッドを移動させるのにかかる時間
     • シークタイム  シーク距離
  2. 回転遅延
     • ディスクが目的のセクターをディスクヘッドに回転させるのを待つ時間
• ディスク帯域幅
  • 転送されたバイトの総数 / サービスの最初の要求から最後の転送の完了までの総時間

1. FCFS スケジューリング
2. SSTF：最短シークタイム優先（SSTF）
   • 最短シークタイム優先
   • 問題：
     • 往復走行 --- 距離は短いが、速度が速いとは限らない
     • 一部の要求の飢餓を引き起こす可能性がある
3. SCAN

• 時にはエレベーターアルゴリズムと呼ばれる

4. C-SCAN（循環 SCAN）

• ヘッドはディスクの一端から他端に移動し、要求を処理しながら進む
• しかし、他端に達すると、戻る際には要求を処理せずにすぐにディスクの先頭に戻る
• 帰り道では乗客を乗せない

5. LOOK / C-LOOK

• SCAN/C-SCAN に似ている

• アームは各方向の最後の要求までしか行かず、その後すぐに方向を反転し、ディスクの端まで行くことなく戻る。

• 選択
  パフォーマンスは要求の数と種類に依存する

  • SCAN と C-SCAN は、ディスクに重い負荷がかかるシステムでより良いパフォーマンスを発揮する
  • SSTF または LOOK のいずれかがデフォルトアルゴリズムとして合理的な選択である

ディスク管理#

• ディスクフォーマット
  • 低レベルフォーマット（物理フォーマット）
    • ディスクをディスクコントローラが読み書きできるセクターに分割する
  • 論理フォーマット
    • ファイルシステムの作成
    • ファイルシステムのメタデータ構造を構築する

RAID 構造#

• 安価なディスクの冗長アレイ（過去）

• 独立したディスクの冗長アレイ（現在）

  • より高い信頼性とより高いデータ転送率（パフォーマンス）のために使用される

• レベル

  1. RAID 0
     • データストライピングのレベルでブロックのディスクアレイだが、冗長性はない
  2. RAID 1
     • ディスクミラーリング
  3. RAID 2
     • ビットレベルストライピングまたはバイトレベルストライピング
     • メモリスタイルのエラー訂正コード（ECC）
  4. RAID 3
     • ビットインタリーブパリティ
  5. RAID 4
     • ブロックインタリーブパリティ組織
  6. RAID 5
     • ブロックインタリーブ分散パリティ

よく使われる単語#

• simultaneously : 同時に
• idle : 空いている、怠けている
• reside : 位置する、住む
• uni-processor : 単一プロセッサ
• interleave: 交互に配置する
• allocation : 割り当て
• dashed line ： 破線
• minuscule : 微小な
• concrete : 具体的な
• mandatory: 強制的な
• mediate : 調停する
• strip : 脱ぐ；条