オペレーティングシステム復習ノート

期末復習#

第 3 章プロセス#

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

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

スケジューリングキュー
1. ジョブキュー
- システム内のすべてのプロセスの集合
- プロセス / ジョブがシステムに入ると、ジョブキューに入れられる
1. レディキュー
- "(メイン) メモリ" に存在し、実行の準備ができているプロセスの集合
1. デバイスキュー
- I/O デバイスを待っているプロセスの集合
スケジューラ
1. 長期スケジューラまたはジョブスケジューラ
- ジョブキュー -> レディキュー
- UNIX や Windows のようなタイムシェアリングシステムでは存在しない場合がある
  - 短期スケジューラのためにすべての新しいプロセスをメモリに配置する
1. 短期スケジューラまたは CPU スケジューラ：プロセススケジューリング
- 次に実行すべきプロセスを選択し、CPU を割り当てる
- 実行が非常に頻繁であるため、毎回の選択に時間をかけることはできず、そうでなければオーバーヘッドが発生する
1. 中期スケジューラまたはスワッピング
- スワップアウト：メモリからディスクにプロセスを削除し、マルチプログラミングの度合いを減少させる
- スワップイン：プロセスをメモリに導入する
コンテキストスイッチ
- CPU が別のプロセスに切り替わる

プロセスに対する操作#

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 でのみ発生する
- 簡単で、ハードウェア要求が低い
剥奪型

スケジューリング基準#

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

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

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

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

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

第 6 章プロセス同期#

レースコンディション
- 複数のプロセスが同時に共有データにアクセスし操作する状況。
- 共有データの最終値は、どのプロセスが最後に終了するかによって決まる。

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

クリティカルセクション
- 各プロセスには、共有データにアクセスするコードセグメントであるクリティカルセクションがある
- 共有変数の数だけクリティカルセクションがある
クリティカルセクション問題の解決基準
1. 相互排除
2. 進行
3. 有限待機
ピーターソンの解法
- 手を挙げる + トークン
ハードウェアベースの解法
- 割り込みを無効にする
  - マルチプロセッサには適さない
- 原子操作

セマフォ#

セマフォ S – 整数変数
- 非負の値で初期化できる
- 二つの不可分（原子）操作：P () と V () を介してのみアクセスできる

P (): wait () 操作

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

V () signal () 操作
```
signal(S){
  S.value++;
}
```
主な問題：ビジーウェイティング（スピンロック）
- 利点
  1. プロセスがロックを待つ必要があるとき、コンテキストスイッチは必要ない
  2. ロックが短時間保持されることが期待される場合、スピンロックは有用
- 欠点
  1. 他のプロセスが生産的に使用できる CPU サイクルを浪費する
- 解決：wait () と signal () の定義を変更する マルチプロセッサシステムに適用
  - Wait (): プロセスはビジーウェイティングに従事するのではなく、block () することができる
  - Signal (): 待機状態からレディ状態にブロックプロセスを変更する
実装
1. 単一プロセッサ環境
- 割り込みを無効にする
1. マルチプロセッサ環境
- クリティカルセクションを適用できる

第 7 章デッドロック#

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

デッドロック処理方法#

予防
- 必要条件のうち少なくとも一つが成立しないようにするための方法を提供する
- 条件 2 に対して：すべてまたは何も；リソースがないときにのみ要求する
- 条件 3 に対して：譲歩；奪取
- 条件 4 に対して：順次実行
- 欠点：デバイス利用率が低く、システムスループットを減少させる。
回避
- 追加情報を使用して、現在の要求が満たされるか、遅延しなければならないかを決定する
- 方法：
  1. リソース割当グラフ
    - サイクルがある：安全でない状態にある；デッドロック状態にある可能性がある
  2. バンカーのアルゴリズム
検出と回復
- 方法:
  - 待機グラフ
    - 各リソースタイプの複数のインスタンスを持つリソース割当システムには適用できない
  - バンカーのアルゴリズム
- 検出アルゴリズムをいつ、どのくらいの頻度で呼び出すかは、以下に依存する：
  - デッドロックが発生する可能性がどのくらいあるか？
  - どのくらいのプロセスがロールバックする必要があるか？
無視

第 8 章#

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

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

論理アドレス：CPU
- 仮想アドレスとも呼ばれる
- 再配置アドレスと論理アドレスには直接の関係はない
物理アドレス：メモリユニット
論理（仮想）アドレスと物理アドレスは、実行時アドレスバインディングスキームで異なる
- 再配置可能コードは CPU によって見られる
- 絶対コードはメモリユニットによって見られる
メモリ管理ユニット（MMU）
- 実行時に仮想アドレスを物理アドレスにマッピングするハードウェアデバイス
動的ロード
- プロセスが実行されるために、プログラム全体とデータが物理メモリにロードされる必要はない
- 利点：
  1. メモリ空間の利用効率が向上
  2. オペレーティングシステムからの特別なサポートは必要ない
動的リンキング
- リンキングは実行時まで延期される
- OS からの支援が必要

連続メモリ割当#

固定サイズの連続パーティション
- 強み（利点）
  - 実装が簡単
  - オーバーヘッドが少ない
- 弱み（欠点）
  - 内部断片化
    - 割り当てられたメモリが要求されたメモリより大きい場合がある
  - 固定数のプロセス
動的連続パーティション
- ホール – 利用可能なメモリのブロック
- 割当アルゴリズム
  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. 遍歴が必要で、プロセスが多すぎる
2. 共有が可能で、プロセス番号は一つしか指定できない
3. 64 ビットには適さない
- 利点：
  1. 必要なスペースが小さい
ハッシュページテーブル
- ハッシュテーブル -> リスト内を遍歴してマッチング
反転ページテーブル

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

セグメンテーション#

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

第 9 章仮想メモリ#

プログラム全体が物理メモリに存在する必要はない。このような利点がある：
- プログラムのサイズはもはやメモリに制限されない
- より多くのプログラムが同時に実行できる
- 各ユーザープログラムをメモリにロードまたはスワップするために必要な I/O が少なくなるため、プログラムはより速く実行されるようになる
仮想メモリ管理
- コンピュータが実際に持っているよりもはるかに多くのメモリを持っているように見える技術を説明するために使用される用語
仮想メモリは以下を介して実装できる：
- デマンドページング
- デマンドセグメンテーション

デマンドページング#

アイデア：必要なときにのみページをメモリに持ってくる
- スワッピングを伴うページングシステムに似ている
ハードウェア
- ページテーブル。有効 - 無効ビットを追加する必要がある
  - v -》ページは合法でメモリに存在する
- 二次メモリ
  - 高速ディスク、スワップスペース
  - メモリに存在しないページを保持する
ページフォルト
- 無効としてマークされたページへのアクセスはページフォルトトラップを引き起こす
- 処理
  1. オペレーティングシステムは別のテーブル（PCB）を見て決定する：
    - 無効な参照 -> 中止
    - メモリに存在しないだけ（2 に進む）
  2. 空きフレームを取得
  3. 希望するページをフレームにスワップする
  4. ページテーブルを修正し、検証ビットを設定 = v
  5. ページフォルトを引き起こした命令を再起動する
- 特殊：
  1. 一つの命令が複数のページフォルトを引き起こす可能性がある
  2. 命令の再実行
  3. 命令実行中に中断。
- 通常の中断との比較：
  - 一つの命令が実行された後、割り込み要求があるかどうかを確認する
    - ある：割り込みを実行
    - ない：次の命令を実行

ページ置換#

置換アルゴリズム

FIFO ページ置換
- ベラディの逆説：フレームが増えるとページフォルトが増える
最適ページ置換（OPT）
- 最も遅く使用されるページまたは後で最も長い時間使用されないページを置換する
最少最近使用（LRU）アルゴリズム
- アイデア：最近の過去を近い未来の近似として使用する
- 実装：
- カウンター
- スタック
LRU 近似アルゴリズム
1. 追加参照ビットアルゴリズム
2. セカンドチャンス（時計）
3. 拡張セカンドチャンスアルゴリズム
カウントベースのページ置換
- 最少頻度使用
- 最多頻度使用
ページバッファリングアルゴリズム
- ページ置換アルゴリズムへの補助手続き

フレームの割当#

二つの主要な割当スキーム
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. 回転遅延
  - ディスクが所望のセクタをディスクヘッドに回転させるのを待つ時間
ディスク帯域幅
- 転送されたバイトの総数 / サービスの最初の要求から最後の転送の完了までの総時間

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

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

C-SCAN（循環 SCAN）

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

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 : 脱ぐ；条

オペレーティングシステム復習ノート

期末復習#

第 3 章 プロセス#

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

プロセスに対する操作#

プロセス間通信#

名詞解説：#

第 4 章 スレッド#

マルチスレッドモデル#

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

基本概念#

スケジューリング基準#

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

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

第 6 章 プロセス同期#

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

セマフォ#

第 7 章 デッドロック#

デッドロック処理方法#

第 8 章#

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

連続メモリ割当#

ページング#

ページテーブルの構造#

セグメンテーション#

第 9 章 仮想メモリ#

デマンドページング#

ページ置換#

フレームの割当#

スラッシング#

その他の考慮事項#

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

アクセス方法#

ディレクトリ構造#

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

割当方法#

空きスペース管理#

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

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

ディスク管理#

RAID 構造#

よく使われる単語#

第 3 章プロセス#

第 4 章スレッド#

第 6 章プロセス同期#

第 7 章デッドロック#

第 9 章仮想メモリ#

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