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

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

一、概説#

同時実行と並列処理#

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

共有#

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

仮想#

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

同期と非同期#

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

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

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

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

プロセス#

プロセスは実行中のプログラムのインスタンスであり、独自のプログラムカウンタと内部状態を持ち、システムがリソースの割り当てとスケジューリングを行うための独立した単位である。プロセス制御ブロック (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 加算または 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 は非常に似ており、ハードウェアも同じであるが、両者の違いは、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 は複数のソケットを管理し、ネットワークカードの I/O 割り込みが発生すると戻り、どの割り込みがどのソケット fd に対応するかはわからない。ユーザースレッドは遍歴して判断する必要がある。
epoll
epoll は I/O 割り込みが発生すると、どの割り込みがどのソケット fd に対応するかを調べる。
epoll 内では赤黒木（平衡二分木の一種）が構築され、赤黒木の検索は非常に効率的である。
ユーザーは興味のあるソケットイベントを登録し、そのソケット fd を赤黒木に挿入し、中断番号をキーとして使用することができる（中断番号、ソケット fd の二元組として理解できる）。
ユーザーがイベントを削除する場合は、木の特定のノードを削除する。

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

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