オペレーティングシステムのまとめ

オペレーティングシステムのまとめ#

一、概説#

同時実行と並列処理#

同時実行: 一つのプロセッサが同時に複数のタスクを処理すること、ここでの同時はマクロな概念であり、特定の時間内にこれらのタスクが交互に実行されることを指す
並列処理: 複数のプロセッサまたはマルチコアプロセッサが同時に異なるタスクを処理すること、ここでの同時は同一の瞬間に本当に複数のタスクを実行することを指す

共有#

共有とは、システム内のリソースが複数の同時実行プロセスによって共同で使用されることを指し、二つの共有方式がある：排他共有と同時共有
排他共有のリソースはクリティカルリソースと呼ばれ、例えばプリンタなど、同時に一つのプロセスのみがアクセスを許可され、クリティカルリソースへのアクセスを実現するために同期メカニズムが必要である

仮想#

仮想技術は、物理的な実体を複数の論理的な実体に変換するもので、主に二つの仮想技術がある：時分割多重化技術と空間分割多重化技術。例えば、複数のプロセスが同一のプロセッサ上で同時に実行されるために時分割多重化技術が使用され、各プロセスが順番にプロセッサを占有し、毎回小さなタイムスライスを実行し迅速に切り替える

同期と非同期#

同期とは、全体の処理過程が順次実行され、各プロセスがすべて完了し、結果を返すことを指す。これは線形実行の方法であり、実行の流れは跨ぐことができない。一般的に、ユーザーログインのようなプロセスに強く依存するプログラムに使用され、ユーザーの検証が完了するまでシステムにログインできない。
非同期は、呼び出しの指令を送信するだけで、呼び出し元は呼び出されたメソッドが完全に実行されるのを待つ必要はない；その代わりに、次のプロセスを続行する。これは並列処理の方法であり、プログラムが完了するのを待つ必要はなく、他のタスクを実行できる。例えば、ページデータの読み込みプロセスでは、すべてのデータが取得されるのを待ってからページを表示する必要はない。

カーネルモードとユーザーモード#

カーネルモード: CPU はメモリ内のすべてのデータにアクセスでき、周辺機器（例えばハードディスク、ネットワークカード）にもアクセスでき、CPU は自分自身を一つのプログラムから別のプログラムに切り替えることもできる。
ユーザーモード: メモリへの制限されたアクセスのみが許可され、周辺機器へのアクセスは許可されず、CPU の能力が剥奪され、CPU リソースは他のプログラムに取得される可能性がある。
ユーザーモードからカーネルモードへの切り替えの三つの方法: システムコール、例外、周辺機器の割り込み

二、プロセスとスレッド#

プロセス#

プロセスは実行中のプログラムのインスタンスであり、独自のプログラムカウンタと内部状態を持ち、リソースの割り当てとスケジューリングのための独立した単位である。プロセス制御ブロック (Process Control Block, PCB)はプロセスの基本情報と実行状態を記述しており、プロセスの作成と撤回はすべてPCBの操作を指す

スレッド#

スレッドは独立してスケジュールされる基本単位である。一つのプロセス内には複数のスレッドが存在し、これらはプロセスリソースを共有する。例えば、ブラウザのプロセス内には多くのスレッドが存在し、HTTP リクエストスレッド、イベント応答スレッド、レンダリングスレッドなどがある。スレッドの同時実行により、ブラウザで新しいリンクをクリックして HTTP リクエストを発起する際に、ブラウザは他のユーザーイベントにも応答できる。

違い#

リソースの所有
プロセスはリソース割り当ての基本単位であるが、スレッドはリソースを所有せず、スレッドは所属するプロセスのリソースにアクセスできる。
スケジューリング
スレッドは独立してスケジュールされる基本単位であり、同一プロセス内でのスレッドの切り替えはプロセスの切り替えを引き起こさないが、異なるプロセス内のスレッドに切り替えるとプロセスの切り替えが引き起こされる。
システムオーバーヘッド
プロセスを作成または撤回する際、システムはリソース（メモリ空間、I/O デバイスなど）を割り当てたり回収したりする必要があり、そのコストはスレッドを作成または撤回する際のコストよりもはるかに大きい。同様に、プロセスの切り替えを行う際には、現在実行中のプロセスの CPU 環境を保存し、新しいスケジュールされたプロセスの CPU 環境を設定する必要があるが、スレッドの切り替えでは少量のレジスタ内容を保存して設定するだけで済むため、オーバーヘッドは非常に小さい。
通信面
プロセス間通信 (IPC)は、データの一貫性を保証するためにプロセスの同期と排他手段を必要とする。一方、スレッド間では同一プロセス内のデータセグメント（例えばグローバル変数）を直接読み書きすることで通信が可能である。

プロセスの状態#

準備状態は、CPU の外部のすべてのリソースを取得し、プロセッサがリソースを割り当てればすぐに実行できる状態である。
実行状態は、プロセッサが割り当てたリソースを獲得し、プログラムが実行を開始する状態である。
ブロック状態は、プログラムの条件が不十分な場合に、条件が満たされるまで実行を待つ必要がある状態であり、例えば I/O 操作を待っているとき、この状態をブロック状態と呼ぶ。

スレッドの状態#

新規（New）：スレッドはプロセス内で派生し、プロセスから派生することも、スレッドから派生することもできる。
ブロック（Block）：スレッドが実行中に特定のイベントの発生を待つ必要がある場合、ブロックされる。
アクティブ（Unblock）：ブロックされたスレッドのイベントが発生した場合、そのスレッドはアクティブになり、準備キューに入る。
スケジュール（Schedule）：準備状態のスレッドの中から一つを選択して実行状態にする。
終了（Finish）：スレッドが実行を終了した場合、そのレジスタコンテキストやスタック内容などが解放される。

スレッドの実装方式#

ユーザ空間でスレッドを実装
ユーザレベルスレッドは、カーネルのサポートを必要とせず、ユーザプログラム内で実装されたスレッドであり、オペレーティングシステムのコアに依存せず、アプリケーションプロセスはスレッドライブラリが提供する作成、同期、スケジューリング、管理の関数を利用してユーザスレッドを制御する。ユーザモード / カーネルモードの切り替えが不要で、速度が速く、オペレーティングシステムのカーネルはマルチスレッドの存在を知らないため、一つのスレッドがブロックされると、全体のプロセス（そのすべてのスレッドを含む）がブロックされる。ここでのプロセッサのタイムスライスの割り当てはプロセスを基本単位としているため、各スレッドの実行時間は相対的に減少する。
カーネル内でスレッドを実装
カーネルレベルスレッドはオペレーティングシステムカーネルによって作成および撤回される。カーネルはプロセスおよびスレッドのコンテキスト情報を維持し、スレッドの切り替えを行う。I/O 操作によってブロックされたカーネルスレッドは、他のスレッドの実行に影響を与えない。
ユーザ空間でスレッドを実装する利点
1. スレッドをサポートしていないオペレーティングシステムでも実装できる。
2. スレッドの作成と破棄、スレッド切り替えのコストなど、スレッド管理のコストはカーネルスレッドよりもはるかに少ない。
3. 各プロセスが独自のスケジューリングアルゴリズムをカスタマイズでき、スレッド管理が比較的柔軟である。
4. スレッドが利用できるテーブルスペースとスタックスペースはカーネルレベルスレッドよりも多い。
ユーザ空間でスレッドを実装する欠点
1. 同一プロセス内では同時に一つのスレッドしか実行できず、あるスレッドがシステムコールを使用してブロックされると、全体のプロセスが停止する。
2. ページフォールトも全体のプロセスが停止する原因となる。
3. カーネルスレッドの利点と欠点は、ユーザスレッドのそれと正反対である。実際、オペレーティングシステムはスレッドを実装するために混合方式を使用することができる。

コルーチン#

コルーチン（Coroutines）は、スレッドよりも軽量な存在である。プロセスが複数のスレッドを持つことができるように、スレッドも複数のコルーチンを持つことができる。最も重要なのは、コルーチンはオペレーティングシステムカーネルによって管理されず、完全にプログラムによって制御される（つまりユーザモードで実行される）。これにより、性能が大幅に向上し、スレッド切り替えのようにリソースを消費しない。コルーチンの本質はユーザ空間内のスレッドである（つまり、コンテキストスイッチは存在せず、ユーザとカーネルのアドレス空間の切り替えがあるが、コルーチンは単一スレッド内で実行される）。

コルーチンの応用#

Lua は 5.0 バージョンからコルーチンを使用し、拡張ライブラリ coroutine を通じて実現している。
Python は yield/send の方法でコルーチンを実現できる。Python 3.5 以降、async/await がより良い代替手段となった。
Go 言語はコルーチンの実装が非常に強力で簡潔であり、数百から数千のコルーチンを簡単に作成して同時に実行できる。
Java 言語はコルーチンのネイティブサポートを持たないが、いくつかのオープンソースフレームワークがコルーチンの機能を模倣している。Kilim フレームワークのソースコード

疑問と考察#

インターネット上のプロセスとスレッドの状態に関する説明は非常に雑多で、両者の関係を理解するのが難しい。私の理解では、プロセスには新規と終了も含まれるべきであり、これはスレッドと実際には同じである。また、私は実行、準備、ブロックの三つだけが基本状態であり、新規終了、ウェイクアップなどは切り替え状態の操作に過ぎないと考えている。
Java のスレッドには待機（Waiting）状態が追加されており、これは実際にはブロック状態をBLOCKEDとWAITINGの二つに細分化したものである。違いは、待機は能動的に待つことであり、ブロックは受動的にブロックされることである。つまり、待機状態では能動的にそれをウェイクアップしない限り、準備状態に入ることはできず、ブロック状態ではスレッド自体がロックを争っており、一度ロックを獲得すれば、他の誰かが能動的にウェイクアップする必要はなく、自動的に準備状態に切り替わる。

参考リンク#

三、プロセス間通信方式#

パイプ#

パイプは、データ交換を実現するために一つの読み取りプロセスと一つの書き込みプロセスを接続する共有ファイルである。

半二重であり（つまりデータは一方向にのみ流れる）、固定の読み取り端と書き込み端を持ち、同時に読み取り端と書き込み端が存在する場合にのみ、パイプは存在意義を持つ。
読み取り端がパイプが空であることを発見した場合、データが到着するまで待機する必要があり、書き込み端もパイプが満杯のときに待機し、データが到着するまで待つ。
特殊なファイルと見なすことができ、通常の read、write などの関数を使用して読み書きすることもできる。しかし、通常のファイルではなく、他のファイルシステムには属さず、メモリ内にのみ存在する。
排他：同時に一つのプロセスのみがパイプに対して読み書きできる。
無名パイプと名前付きパイプの二種類があり、前者は親プロセスと子プロセス間の通信に使用され、後者は同じマシン上の任意の二つのプロセス間の通信に使用される。

メッセージキュー#

メッセージのリンクリストであり、カーネル内に保存される。メッセージキューは一つの識別子（すなわちキュー ID）によって識別される。

メッセージキューはレコード指向であり、その中のメッセージは特定のフォーマットと特定の優先度を持つ。
メッセージキューは送信プロセスと受信プロセスから独立しており、プロセスが終了してもメッセージキューとその内容は削除されない。
メッセージキューはメッセージのランダムなクエリを実現でき、メッセージは必ずしも先入先出で読み取る必要はなく、メッセージのタイプに応じて読み取ることもできる。

シグナル (signal)#

比較的複雑な通信方式であり、受信プロセスに特定のイベントが発生したことを通知するために使用される。プロセス間通信メカニズムの中で唯一の非同期通信メカニズムである。

セマフォ（semaphore）#

既に紹介した IPC 構造とは異なり、カウンターである。セマフォはプロセス間の排他と同期を実現するために使用され、プロセス間通信データを保存するためではない。

セマフォはプロセス間の同期に使用され、データをプロセス間で伝達するには共有メモリと組み合わせる必要がある。
セマフォはオペレーティングシステムの PV 操作に基づいており、プログラムによるセマフォの操作はすべて原子操作である。
セマフォの PV 操作は、セマフォの値を 1 加算または減算することに限らず、任意の正の整数を加減することができる。
セマフォグループをサポートする。
注意⚠️: セマフォとシグナルは同じ概念ではなく、両者の違いは大きい。

共有メモリ（Shared Memory）#

二つ以上のプロセスが特定のストレージエリアを共有することを指す。

共有メモリは最も速い IPC であり、プロセスはメモリに直接アクセスする。
複数のプロセスが同時に操作できるため、同期を行う必要がある。
セマフォと共有メモリは通常一緒に使用され、セマフォは共有メモリへのアクセスを同期するために使用される。

ソケット#

ソケットもプロセス間通信メカニズムの一種であり、異なるホスト間のプロセス通信を実現できる。一つのソケットはプロセス間通信のエンドポイントと見なすことができ、各ソケットの名前は一意であり、他のプロセスがアクセス、接続、データ通信を行うことができる。

まとめ#

パイプ：速度が遅く、容量が限られている。
メッセージキュー：容量はシステムによって制限され、最初の読み取り時には前回の未読データの問題を考慮する必要がある。
セマフォ：複雑なメッセージを伝達できず、同期にのみ使用できる。
共有メモリ：容量を簡単に制御でき、速度が速いが、同期を維持する必要がある。例えば、一つのプロセスが書き込みを行っているとき、別のプロセスは読み書きの問題に注意する必要があり、これはスレッド内のスレッドセーフに相当する。もちろん、共有メモリもスレッド間通信に使用できるが、必要はない。スレッド間ではすでに同一プロセス内のメモリの一部を共有している。

四、同期メカニズム#

背景#

複数のプロセス（スレッド）が同時に実行されると、プロセス間で相互に制約が発生する場合がある。例えば、二つのプロセスが必要とする：
1. 唯一のハードウェアデバイスを共有する
2. 同一のメモリ領域を共有する
3. 一つのプロセスの実行が他のプロセスの共有リソースの実行結果に依存する

もし複数のプロセス間に時系列関係が存在し、協力してタスクを完了する必要がある場合、それは同期と呼ばれる；協力の条件が満たされず、排他性リソースを共有することによって生じる関係は排他と呼ばれ、排他は特別な同期である。

同期メカニズムには以下の四つのルールに従う必要がある。
1. 空いているときは入る：クリティカルセクションにプロセス / スレッドがないとき、どのプロセスでも入ることができる；
2. 忙しいときは待つ：クリティカルセクションにプロセス / スレッドがあるとき、他のプロセスはクリティカルセクションに入ることができない；
3. 限定待機：クリティカルセクションに入るのを待っているプロセス / スレッドは無期限に待つことができない；
4. 権利を譲る待機（オプション）：クリティカルセクションに入れないプロセス / スレッドは、CPU を解放するべきであり、例えばブロック状態に切り替える。

セマフォ#

セマフォとPV原語操作は Dijkstra によって発明され、最も広く使用される排他方法の一つである。
セマフォと PV 操作の原理：
1. プロセスが共有領域に入ろうとするとき、まず P 操作を実行し、S-1 を行う。
2. プロセスが共有領域を退出しようとするとき、V 操作を実行し、S+1 を行う。
3. プロセスが共有領域に出入りする操作は原子操作である（実行過程で中断されることは許可されない）。
欠陥：プログラムの可読性が相対的に低く、セマフォの管理が参加するオブジェクトに分散しているため、デッドロックやプロセスの飢餓などの問題を引き起こす可能性がある。

モニタ（プロセス同期独自）#

モニタはセマフォメカニズムの拡張と改善であり、より簡単な同期手段である。
モニタは複数のプロセス / スレッドが安全にアクセスできるオブジェクトまたはモジュールである。
モニタに集約されたメソッドは Mutex によって保護されており、同時に一つのアクセス者のみが使用できることを意味する。
特徴：安全性、排他性、共有性。

クリティカルセクション（スレッド同期）#

複数のスレッドによる公共リソースまたはコードの一部へのアクセスを直列化することによって、速度が速く、データアクセスの制御に適している。
任意の時点で一つのスレッドのみが共有リソースにアクセスでき、複数のスレッドが公共リソースにアクセスしようとすると、あるスレッドが入った後、他のスレッドはブロックされ、クリティカルセクションが解放されるまで待機し、クリティカルセクションが解放された後に他のスレッドが奪取できる。

排他#

排他は同一アプリケーションの公共リソースの安全な共有を実現するだけでなく、異なるアプリケーションの公共リソースの安全な共有も実現できる。
排他量はクリティカルセクションよりも複雑である。なぜなら、排他を使用することで同一アプリケーションの異なるスレッド間でリソースの安全な共有を実現できるだけでなく、異なるアプリケーションのスレッド間でもリソースの安全な共有を実現できるからである。

イベント（スレッド同期）#

通知操作の方法によってスレッドの同期を維持し、複数のスレッドの優先度比較操作を簡単に実現できる。

プロセスとスレッド間の同期メカニズムの違い#

セマフォ、モニタ、排他はプロセスの同期メカニズムであり、セマフォと排他はスレッドの同期にも使用できるが、モニタはプロセスの同期にのみ使用される。
スレッドの同期はセマフォ、排他の他にクリティカルセクション、イベントがあり、これらの二つの方法がプロセスの同期方法として使用されることは見たことがない（知らない）。

古典的な同期問題#

生産者-消費者問題
哲学者の食事問題
読者-書き手問題

具体的な参考：

参考リンク#

五、デッドロック#

デッドロックは、複数のプロセスが実行中にリソースを奪い合うことによって生じる行き詰まりのことであり、外的な力が働かない限り、行き詰まったプロセスは実行を続けることができない。

デッドロックの原因#

システムリソースが不足している。
プロセスの実行の進行順序が不適切である。
リソースの割り当てが不適切であるなど。

デッドロックが発生するための四つの必要条件#

排他条件: プロセスは割り当てられたリソースを排他的に使用する。
要求と保持条件: プロセスがブロックされているとき、ロックを要求したリソースを解放しない。
奪取不可能条件: プロセスが既に要求したリソースを使用が完了するまで奪われない。
循環待機条件: デッドロックが発生したときに存在するプロセス - リソースの環状待機チェーン。

デッドロック処理#

デッドロックの予防：デッドロックが発生する四つの必要条件の一つまたは複数を破壊する；実装は比較的簡単だが、制限が厳しすぎるとシステムリソースの利用率やスループットが低下する。
デッドロックの回避：リソースの動的割り当てにおいて、システムが不安全な状態（デッドロックが発生する可能性のある状態）に入るのを防ぐ。- 銀行家アルゴリズムを参照。銀行家アルゴリズム
デッドロックの検出：システムが実行中にデッドロックが発生することを許可し、デッドロックが発生した後、特定のアルゴリズムを使用して検出し、デッドロックに関連するリソースとプロセスを特定し、検出されたデッドロックを解消するための関連方法を採用する。実装は難しい。
デッドロックの解除：デッドロック検出と組み合わせて、システムをデッドロックから解放する（プロセスを撤回するかリソースを奪う）。検出されたデッドロックに関連するプロセスやリソースを、撤回または一時停止の方法で解放し、いくつかのリソースを解放してブロック状態のプロセスに再割り当てし、準備状態に変える。実装は難しい。

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

`先来先サービスFCFS`#

作業スケジューリングアルゴリズムとしてもプロセススケジューリングアルゴリズムとしても使用できる；作業またはプロセスの到着順に従って順次スケジューリングされる；したがって、長い作業に対して比較的有利である。

`短作業優先SPF`#

作業スケジューリングアルゴリズムであり、アルゴリズムは準備キューから推定時間が最も短い作業を選択して処理し、結果が得られるまでまたは実行を続けられないまで処理を行う；欠点：長い作業には不利である；作業の重要性を考慮していない；実行時間は推定であり、信頼性がない。

`高優先度優先HRRF`#

作業スケジューリングとしてもプロセススケジューリングアルゴリズムとしても使用できる；作業をスケジューリングする際、準備キューから優先度が最も高い作業を選択して処理する；優先度が関与するため、先取型と非先取型に分けることができる；また、優先度の決定は静的優先度（事前にプロセスタイプ、プロセスのリソース要求、ユーザー要求などに基づいて固定値を決定する）と動的優先度（プロセスの進行や待機時間に応じて増加または減少する）に分けることができる。

`最高応答比優先HRN`#

FCFS は短作業のユーザーを不満にさせる可能性があり、SPF は長作業のユーザーを不満にさせる可能性があるため、HRN が提案され、応答比が最も高い作業を実行する。応答比 = 1 + 作業待機時間 / 作業処理時間。

`タイムスライスラウンドロビン`#

到着順にプロセスをキューに入れ、キューの先頭のプロセスに CPU タイムスライスを割り当て、タイムスライスが終了するとタイマーが割り込みを発生させ、現在のプロセスを一時停止し、キューの末尾に移動させ、循環する。

`多段フィードバックキュー`#

現在最も良いスケジューリングアルゴリズムとして認識されている；複数の準備キューを設定し、各キューに異なる優先度を設定する。最初のキューが最も高い優先度を持ち、残りは順次減少する。優先度が高いキューには短いタイムスライスが割り当てられ、プロセスが到着すると FCFS に従って最初のキューに入れられる。スケジューリング実行後に完了しない場合は、第二のキューの末尾に移動してスケジューリングを待機し、第二回目のスケジューリングでも完了しない場合は第三のキューの末尾に移動する…。前のキューが空である場合にのみ、次のキューのプロセスをスケジューリングする。

七、メモリ管理#

基本知識#

リンク#

生成されたモジュールをロードして完全な論理アドレスを形成する。
三つのリンク方式：

静的リンク: ロード前にリンクする。
ロード時動的リンク: 実行前にロードしながらリンクする。
実行時動的リンク: 実行時に必要なときにロードしてリンクする。

目的：完全な論理アドレスを決定すること。

ロード#

メモリにロードして物理アドレスを形成する。

三つのロード方式：

絶対ロード: コンパイル時に絶対アドレスを生成し、単道プログラム環境。
静的再配置: ロード時に論理アドレスを物理アドレスに変換し、多道バッチ処理オペレーティングシステム。
動的再配置: 実行時に論理アドレスを物理アドレスに変換し、位置決めレジスタを設定する、現代のオペレーティングシステム。

目的：最終的な物理アドレスを決定すること。

フラグメンテーション#

内部フラグメンテーション（割り当て済み）、特定のプロセスに割り当てられたメモリ領域の一部が未使用である。
外部フラグメンテーション（未割り当て）、メモリ内の特定の空きセクションが小さすぎて利用できない。

連続割り当て管理方式#

単一連続割り当て: メモリはシステム領域とユーザー領域に分かれ、ユーザープログラムは一つだけ存在する（外部フラグメンテーションはなく、内部フラグメンテーションがある）。
固定分割割り当て: ユーザー空間全体をいくつかの固定サイズの分割に分け、分割サイズは等しい場合もあれば異なる場合もある。各分割には一つの作業のみが装入でき、分割説明表で管理される（外部フラグメンテーションはなく、内部フラグメンテーションがある）。
動的分割割り当て: プロセスのサイズに応じて動的に分割を作成し、空き分割表または空き分割チェーンで管理し、動的分割アルゴリズムが適切な空き分割を選択して割り当てる（外部フラグメンテーションがあり、内部フラグメンテーションはない）。

動的分割割り当てアルゴリズム#

`最初の適合アルゴリズム（FF）`#

メモリを割り当てる際、空き分割表の先頭から検索を開始し、サイズが要求を満たす最初の空き分割を見つけるまで続ける。
このアルゴリズムは実装が簡単で、低アドレスの空き分割を優先的に利用するため、高アドレス部分の大きな空き分割を保持し、後で大きな作業に大きなメモリ空間を割り当てる条件を作るが、低アドレス部分が継続的に分割され、小さな空き分割が多く残され、毎回の検索がアドレス部分の先頭から始まるため、検索のオーバーヘッドが増加する。

`循環最初の適合アルゴリズム（NF）`#

最初の適合アルゴリズムとは異なり、プロセスにメモリ空間を割り当てる際、毎回低アドレスから検索するのではなく、前回見つけた空き分割の次の空き分割から検索を開始するため、次回の検索の開始位置を示す検索ポインタを設定する必要がある。最後の空き分割のサイズが要求を満たさない場合は、最初の空き分割に戻る。このアルゴリズムは空き分割の内部をより均等に分割し、空き分割を検索する際のオーバーヘッドを適度に減少させるが、大きな空き分割を分割しやすい。

`最適適合アルゴリズム（BF）`#

作業にメモリを割り当てる際、常に要求を満たすが最小の空き分割をプロセスに割り当てる。つまり、最小の値を持つ空き分割を探すことで、「大材小用」を避けることができるが、細かいフラグメンテーションが発生しやすい。

`最悪適合アルゴリズム（WF）`#

最適適合アルゴリズムとは逆に、常に要求を満たすが最大の空き区画をプロセスに割り当てる。つまり、最大の値を持つ空き分割を探すことで、フラグメンテーションの可能性を最小限に抑え、中小作業に有利である。

非連続割り当て管理方式#

基本ページングストレージ管理#

基本ページングストレージ管理ではページ置換機能がなく（すなわち仮想メモリ機能が実装されていない）、プログラムのすべてのページがメモリにロードされるまで実行できない。プログラムデータは異なるページに保存され、ページはメモリ内に離散的に分布しているため、ページ番号と実際のストレージアドレス間のマッピング関係を記録するためにページテーブルが必要であり、ページ番号から物理ブロック番号へのマッピングを実現する。ページテーブルもメモリに保存されるため、ページ管理を使用しないストレージ方式と比較して、ページシステム内のメモリデータにアクセスするには二回のメモリアクセスが必要である（一次はメモリからページテーブルにアクセスし、指定された物理ブロック番号を見つけ、ページ内オフセットを加えて実際の物理アドレスを得る；二回目は最初に得た物理アドレスに基づいてメモリにアクセスし、データを取得する）。

効率への影響を減少させるために、ページ管理ではキャッシュテーブル（または連想レジスタ）メカニズム（キャッシュメカニズムを連想させる）が導入され、キャッシュテーブルメカニズムを含むメモリ管理では、メモリデータにアクセスする際、最初にページ番号をキャッシュテーブルで検索し、見つかった場合はキャッシュテーブルから直接対応する物理ブロック番号を読み取る；見つからなかった場合は、メモリ内のページテーブルにアクセスし、ページテーブルから物理アドレスを取得し、ページテーブルのそのマッピングテーブル項目をキャッシュテーブルに追加する。キャッシュテーブルの置換アルゴリズムが存在する可能性がある。

利点と欠点：外部フラグメンテーションがなく、メモリ利用率が高い。しかし、各ページの内容は関連性がなく、プログラミングや共有に不利である。

補足概念：

ページフレーム = ページフレーム = メモリブロック = 物理ブロック = 物理ページ（メモリ分区）
ページ = ページ（プロセス論理アドレス空間の分区）
ページとページフレームは一対一で対応している（ページテーブル、ページテーブル項目は「ページ番号」と「ブロック番号」で構成され、ページ番号はメモリ空間を占有しない）。
ページテーブルの長さは、このページテーブルにいくつのページテーブル項目があるかを指し、つまりいくつのページがあるか。
ページテーブル項目の長さは、各ページテーブル項目がどれだけのストレージスペースを占有するかを指す。
ページサイズは、一つのページがどれだけのストレージスペースを占有するかを指す。

基本セグメントストレージ管理#

プログラムを内容またはプロセス（関数）関係に従ってセグメントに分け、各セグメントには独自の名前が付けられる。ユーザ作業またはプロセスに含まれるセグメントは、二次元の線形仮想空間に対応し、すなわち二次元の仮想ストレージである。セグメント管理プログラムはセグメント単位でメモリを割り当て、アドレス変換機構を通じてセグメントの仮想アドレスを実際のメモリ物理アドレスに変換する。

プロセスのアドレス空間：プログラム自身の論理関係に従っていくつかのセグメントに分けられ、各セグメントにはセグメント名があり、各セグメントは 0 から始まる。
論理アドレス構造：セグメント番号とセグメント内アドレス（セグメント内オフセット）。
メモリ割り当てルール：セグメント単位で割り当て、各セグメントはメモリ内で連続した空間を占有し、各セグメントは隣接しない。
セグメントテーブルのセグメントテーブル項目は、セグメント番号（暗黙的で、ストレージスペースを占有しない）、セグメント長、基準アドレスで構成される。
ページテーブルアドレス変換の異なる点は、セグメントテーブルに記録されたセグメント長に基づいてセグメント内アドレスが越境していないかを確認する必要があること。

利点と欠点：

異なるタイプのセグメントに対して異なる保護を適用できる。
セグメント単位での共有が可能であり、動的リンクを通じてコードの共有が可能である。
内部フラグメンテーションは発生しないが、外部フラグメンテーションが発生し、メモリ利用率はページングよりも低い。

セグメントとページングの違い#

ページは情報の物理単位であり、システムのメモリ利用率の観点から提案された離散的な割り当てメカニズムである；セグメントは情報の論理単位であり、各セグメントは意味のある情報のグループを含み、ユーザーの観点から提案されたメモリ管理メカニズムである。
ページのサイズは固定されており、システムによって決定される；セグメントのサイズは不確定であり、ユーザーによって決定される。
ページングの論理アドレス構造は一次元（オフセット）であり、セグメントは二次元（セグメント名 + オフセット）である。

セグメントページングストレージ管理#

プロセスを論理モジュールに分割した後、各セグメントをページングする。外部フラグメンテーションは発生せず、少量の内部フラグメンテーションのみが発生する。
論理アドレス構造（二次元）：セグメント番号、ページ番号、ページ内オフセット + ページ番号、ページが保存されているブロック番号。

アドレス変換：論理アドレスからセグメント番号、ページ番号、ページ内オフセットを得る→セグメント番号とセグメントテーブルレジスタ内のセグメント長を比較し、越境していないかを確認→セグメントテーブルの開始アドレス、セグメント番号から対応するセグメントテーブル項目を見つける→セグメントテーブルに記録されたページテーブル長に基づいて、ページ番号が越境していないかを確認→セグメントテーブルのページテーブルアドレス、ページ番号からページテーブル項目を検索→ブロック番号とページ内オフセットから物理アドレスを得る→ターゲットユニットにアクセスする。

簡単に言えば、プロセスは三回のメモリアクセスを行う：セグメントテーブルを検索→ページテーブルを検索→ターゲットユニットにアクセス（キャッシュテーブルが設定されている場合は一回のメモリアクセスで済む）。

メモリ空間の拡張#

オーバーレイ技術#

オーバーレイ技術は、固定領域（領域内のプログラムセグメントは実行中にロードされず、アンロードされない）といくつかのオーバーレイ領域（領域内のプログラムセグメントは実行中にロードされ、アンロードされる必要がある）を含み、ユーザーには透明で、ユーザーのプログラミング負担を増やす。同一のプログラムまたはプロセス内で行われる。

スワッピング技術#

スワッピング技術は、メモリが不足しているときに、いくつかのプロセスをスワップアウトしてメモリ空間を空け、いくつかのプロセスをスワップインするものであり、外部ストレージのディスクはファイル領域とスワップ領域に分かれ、スワップアウトされたプロセスはスワップ領域に置かれ、異なるプロセス（または作業）間で行われる。

仮想ストレージ技術（仮想メモリ）#

仮想メモリの使用原理：局所性原理（MySQL で B ツリーをインデックスデータ構造として使用する理由を連想させる）
1. 時間局所性：現在アクセスしている命令やデータは、近い将来に再度アクセスされる可能性が高い。
2. 空間局所性：現在アクセスしているメモリユニットの周囲のメモリ空間は、近い将来に再度アクセスされる可能性が高い。
3. 高速キャッシュ技術：頻繁に使用されるデータをより高速なストレージに配置する。

局所性原理に基づき、プログラムがロードされるとき、プログラムの一部をメモリにロードし、残りの部分を外部ストレージに留めておくことで、プログラムの実行を開始できる。プログラムの実行中に、アクセスされる情報がメモリにない場合、オペレーティングシステムが必要な部分をメモリにロードし、プログラムの実行を続ける。一方、オペレーティングシステムはメモリ内で一時的に使用されていない内容を外部ストレージにスワップアウトし、メモリにロードされる情報を保存するためのスペースを空ける。こうして、システムはユーザーに実際のメモリよりもはるかに大きなストレージを提供するように見える。これを仮想ストレージと呼ぶ。

仮想メモリの定義：プログラムはすべてをロードする必要がなく、実行時に動的にロードされ、メモリが不足すると置換が行われる。
仮想メモリの特徴
1. 多回性：作業が実行される際に一度にすべてをメモリにロードする必要はなく、複数回に分けてロードすることが許可される。
2. スワッピング性：作業が実行される際に常にメモリに常駐する必要はなく、作業の実行中に作業をスワップインおよびスワップアウトすることが許可される。
3. 仮想性：論理的にメモリ容量を拡張し、ユーザーが見るメモリ容量は実際の容量よりもはるかに大きい。
仮想メモリ技術の実装：要求ページングストレージ管理、要求セグメントストレージ管理、要求セグメントページングストレージ管理。
仮想メモリを使用するコスト
1. 仮想メモリの管理には多くのデータ構造を構築する必要があり、追加のメモリを占有する。
2. 仮想アドレスから物理アドレスへの変換が、命令実行時間を増加させる。
3. ページのスワップインおよびスワップアウトにはディスク I/O が必要であり、時間がかかる。
4. 一ページ内に部分的なデータしかない場合、メモリが無駄になる。

ページ置換アルゴリズム#

`最適ページ置換アルゴリズム(OPT)`#

理論的な意味を持つアルゴリズムであり、他のページ置換アルゴリズムを評価するために使用される。置換戦略は、現在のページの中で将来最も長い間アクセスされないページを置換することである。

`先入先出置換アルゴリズム(FIFO)`#

オペレーティングシステムがメモリ内のすべてのページのリストを維持し、最新に入ったページはリストの末尾に、最初に入ったページはリストの先頭に置かれる。ページフォールトが発生したとき、リストの先頭のページを排除し、新しくロードされたページを末尾に追加する。単純で粗雑な置換アルゴリズムであり、ページアクセス頻度情報を考慮していない。

`最近最少使用アルゴリズム(LRU)`#

アルゴリズムは各ページにアクセスフィールドを与え、ページが最後にアクセスされてから現在までの時間 t を記録する。置換時には t 値が最も大きいページを置換する（実装面ではレジスタまたはスタックの方式を使用できる）。

`時計置換アルゴリズム（最近未使用アルゴリズムNRUとも呼ばれる）`#

ページにアクセスビットを設定し、ページがアクセスされるとアクセスビットが 1 に設定される。すべてのページは循環キューに保存され、ポインタは最も古いページを指す。ページ置換時には、現在のポインタが指すページのアクセスビットが 0 であれば置換し、そうでなければ 0 に設定し、アクセスビットが 0 のページに出会うまで循環する。

`改良型Clockアルゴリズム`#

Clock アルゴリズムの基礎の上に修正ビットを追加し、置換時にはアクセスビットと修正ビットを総合的に判断する。アクセスビットと修正ビットの両方が 0 のページを優先的に置換し、次にアクセスビットが 0 で修正ビットが 1 のページを置換する。

`最少使用アルゴリズム(LFU)`#

ページがアクセスされた回数を記録するレジスタを設定し、置換時には現在のアクセス回数が最も少ないページを置換する。問題は、アクセスレジスタが実際のページアクセス回数を正確に反映できないことである。なぜなら、アクセス速度が速いため、レジスタの更新間隔内でのアクセスは 1 回でも 100 回でも同じであるからである。また、LFU と LRU は非常に似ており、サポートされるハードウェアも同じであるが、両者の違いは、一方が時間を基準にし、もう一方が回数を基準にすることである（例えば、レジスタ pa 001111 と pb 111000 の二つのページがある場合、LRU を使用すると淘汰されるのは pa であり、LFU を使用すると淘汰されるのは pb である）。

`ページバッファアルゴリズム(PBA)`#

置換時に、ページが修正されているかどうかに関わらず、ディスクに置換されることはなく、まずメモリ内のページリスト（修正されたページリストと未修正ページリスト、または区別しないことも可能）に保持される。再度アクセスされると、これらのリストから直接取得でき、ディスク I/O を行う必要がない。リスト内の修正されたページの数が一定数に達した場合、順次ディスク操作を行う（複数の I/O を一度の操作にまとめることに相当する）。

ページ割り当て戦略#

常駐集：要求ページングストレージ管理においてプロセスに割り当てられた物理ブロックの集合（すなわち、システムがプロセスに割り当てた物理ブロック数）。

固定割り当て局所置換：プロセスが実行される前に常駐集が割り当てられ、ページフォールトが発生した場合、プロセス自身のページのいずれかをスワップアウトすることしかできない。

可変割り当て全局置換：ページフォールトが発生すれば新しい物理ブロックが割り当てられ、空き物理ブロックからも、他のプロセスのページをスワップアウトすることも可能である。

可変割り当て局所置換：ページフォールトの発生頻度に応じてプロセスの物理ブロックを動的に増減させる。

ページをいつロードするか：予測ページ戦略（実行前）；要求ページ戦略（実行時）。

ページをどこから呼び出すか：UNIX 方式：最初に使用されるページはすべてファイル領域からロードされ、スワップアウトされたページはスワップ領域に書き戻され、再度使用されるときはスワップ領域からロードされる。

チラつき（スラッシング）現象：プロセスに割り当てられた物理ブロックが不足しているため、スワップアウトされたページがすぐにスワップインされ、スワップインされたページがすぐにスワップアウトされる ------> ページ置換戦略の誤りによるものであれば、置換アルゴリズムを修正することで解決できる；もし実行中のプログラムが多すぎて、すべての頻繁にアクセスされるページを同時にメモリにロードできない場合は、多道プログラムの数を減らす必要がある；さもなければ、そのプロセスを終了させるか、常駐集のサイズを増やす。

ワーキングセット：特定の時間間隔内にプロセスが実際にアクセスしたページの集合（常駐集のサイズは通常ワーキングセットのサイズ以上であるべきで、チラつき現象を防ぐため）。

補足：

ページフォールト（またはページエラー）: プログラムが物理メモリに存在しないアドレス空間の一部を参照したとき、オペレーティングシステムが欠落部分を物理メモリにロードし、失敗した命令を再実行する。
ページフォールトを計算する例題
Belady異常：FIFO アルゴリズムを使用する際、プロセスに要求されたすべてのページが割り当てられていない場合、割り当てられたページ数が増加しても、ページフォールト率が逆に上昇する異常現象が発生することがある。

八、ファイルシステム#

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

先来先サービス（FCFS）
最短待機時間優先（SSTF）：現在のトラックに最も近い要求者がディスクドライブを起動するようにし、つまり最も短い検索時間の作業を最初に実行し、要求者の到着順序を考慮しない。これにより、先来先サービススケジューリングアルゴリズムでの磁気アームの移動が大きすぎる問題を克服する。
スキャンアルゴリズム（SCAN）またはエレベーター調整アルゴリズム：常に磁気アームの現在位置から開始し、磁気アームの移動方向に沿って現在の磁気アームに最も近い柱面の要求者を選択する。磁気アームの方向に要求がない場合は、磁気アームの移動方向を変更する。このスケジューリング方法では、磁気アームの移動はエレベーターのスケジューリングに似ているため、エレベーター調整アルゴリズムとも呼ばれる。
循環スキャンアルゴリズム（CSCAN）：循環スキャンスケジューリングアルゴリズムは、スキャンアルゴリズムを基に改善されたものである。磁気アームは単方向に移動し、外側から内側へ。現在の位置から磁気アームの移動方向に沿って現在の磁気アームに最も近い柱面の要求者を選択する。磁気アームの方向に要求がない場合は、最外部に戻り、柱面番号が最小の作業要求にアクセスする。
NStepSCANアルゴリズム: N ステップ SCAN アルゴリズムは、ディスク要求キューを長さ N のいくつかのサブシーケンスに分割し、ディスクスケジューリングは FCFS アルゴリズムに従ってこれらのサブキューを順次処理し、各サブキューの内部は SCAN アルゴリズムに従って処理される。N が非常に大きい場合、アルゴリズムは SCAN アルゴリズムに近づき、N=1 の場合は FCFS アルゴリズムに退化する。N ステップ SCAN アルゴリズムは「磁気アームの粘着」現象を効果的に回避できる。

九、I/O モデル#

参考：オペレーティングシステムにおける I/O、および高性能 I/O モデル

デバイス間の I/O#

ポーリング方式
CPU が積極的にさまざまなデバイスの状態をポーリングし、データがあれば I/O を行う。
割り込み方式
デバイスにデータがあるとき、割り込みを発生させ、CPU がその割り込みに応答するかどうかを決定し、割り込みを処理してデバイスの I/O を行う。CPU はデバイスの状態を頻繁にポーリングする必要がない。受動的に割り込みを受け取るだけで済む。
直接メモリアクセス（DMA）方式
1 バイトのデータで 1 回割り込みが発生する場合、1KB のデータを転送するには 1024 回割り込みが発生するため、CPU の時間を浪費する。そこで DMA 方式が導入され、CPU は開始アドレスと終了アドレスを DMA に伝えるだけで、中間のデータ I/O は DMA が行う。CPU はバイト単位の干渉からデータブロックの干渉に解放される。
チャネル制御方式
DMA 方式は一つのデバイスの一つのデータブロックを制御できるが、複数のデータブロックを制御するには CPU が何度も干渉する必要がある。そこで、I/O を制御するためのチャネルが導入され、DMA よりも強力で、複数のデータブロックや複数のデバイスの I/O を制御し、CPU の I/O プロセスへの関与をさらに解放する。

ユーザープロセス間の I/O#

ブロッキング
ユーザースレッドが特定のシステム関数を呼び出してカーネルからデータを取得する際、データがカーネルキャッシュに到達するまで、そのスレッドはブロック状態になり、データの到着を待つ。
非ブロッキング
ユーザースレッドがデータを取得する際、カーネルキャッシュにデータがあるかどうかに関わらず、直接戻り、データを取得できる場合もあれば、取得できない場合もある。スレッドはブロック状態にはならない。
I/O多重化
多重とは、一つのスレッドが多重 I/O を管理することであり、スレッドはブロック呼び出しを行い、そのうちの一つまたはいくつかの I/O にデータがあれば戻る。スレッドはすべての I/O を遍歴し、どの I/O にデータがあるかを判断する必要がある。
例えば、ソケットの select () 関数では、スレッドが select () を呼び出すとブロック状態になり、いずれかの I/O にデータがあれば、スレッドはブロック状態を終了し、再び実行を続ける機会を得る。
シグナル駆動I/O
I/O にシグナルとシグナルがトリガーされたときのコールバック関数を登録し、シグナルがトリガーされると、コールバック関数がデータを読み取る。
例えば、ソケットに「読み取り可能」シグナルを登録すると、データが到着し、読み取り可能なときにシグナルがトリガーされ、コールバック関数がカーネルキャッシュからユーザースペースにデータをコピーする。
非同期I/O
非同期 I/O では、オペレーティングシステムがカーネルからユーザースペースへのデータコピーを完了した後、シグナルの形でユーザースレッドに次の操作を行うよう通知する。ユーザースレッドがデータをコピーする過程でブロックされる必要がなくなる。

select、epoll、kqueue の原理#

select
select は複数のソケットを管理し、select がネットワークカードの I/O 割り込みを受け取ると戻り、どの割り込みがどのソケット fd に対応しているかはわからない。ユーザースレッドは遍歴して判断する必要がある。
epoll
epoll は I/O 割り込みを受け取ると、どの割り込みがどのソケット fd に対応しているかを調べる。
epoll では赤黒木（平衡二分木の一種）を構築し、赤黒木の検索は非常に効率的である。
ユーザーが興味のあるソケットイベントを登録する際、そのソケット fd を赤黒木に挿入し、中断番号をキーとして使用することができる（中断番号、ソケット fd の二項組として理解できる）。
ユーザーがイベントを削除する際は、木の特定のノードを削除する。

次に、I/O 割り込みを受け取ると、epoll はネットワークカードのデータをカーネルキャッシュにコピーし、中断番号に基づいて赤黒木で対応する fd を検索し、fd を準備完了リストに追加してユーザースレッドに戻す。ユーザーは直接準備完了の fd を得る。

kqueue
ソケット I/O 割り込みを受け取ると、ハッシュテーブルで対応するソケット fd を検索し、それをリストに追加して戻る。
ユーザーが興味のあるイベントを登録する際、ハッシュテーブルに fd を追加する。