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

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

一、概説#

同時実行と並列#

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

共有#

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

仮想#

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

同期と非同期#

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

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

カーネルモード: 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 フレームワークのソースコード

疑問と考察#

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

参考リンク#

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

パイプ#

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

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

メッセージキュー#

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

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

シグナル（signal）#

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

セマフォ（semaphore）#

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

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

共有メモリ（Shared Memory）#

2 つ以上のプロセスが特定のストレージ領域を共有することを指す。

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

ソケット#

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

まとめ#

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

四、同期メカニズム#

背景#

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

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

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

セマフォ#

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

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

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

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

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

排他#

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

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

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

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

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

古典的な同期問題#

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

具体的な参考：

参考リンク#

五、デッドロック#

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

デッドロックが発生する原因#

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

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

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

デッドロック処理#

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

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

`先来先サービスFCFS`#

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

`短作業優先SPF`#

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

`高優先度優先HRRF`#

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

`最高応答比優先HRN`#

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

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

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

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

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

七、メモリ管理#

基本知識#

リンク#

生成装入モジュールが完全な論理アドレスを形成する。
3 つのリンク方式：

静的リンク: 装入前にリンクする。
装入時動的リンク: 実行前に装入しながらリンクする。
実行時動的リンク: 実行時に必要なときに装入しリンクする。

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

装入#

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

3 つの装入方式：

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

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

フラグメンテーション#

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

連続割り当て管理方式#

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

動的パーティション割り当てアルゴリズム#

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

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

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

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

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

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

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

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

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

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

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

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

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

補足概念：

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

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

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

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

利点と欠点：

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

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

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

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

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

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

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

メモリ空間の拡張#

オーバーレイ技術#

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

スワッピング技術#

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

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

仮想メモリが使用する原理：局所性の原理（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 の 2 つのページがある場合、LRU を使用すると淘汰されるのは pa であり、LFU を使用すると淘汰されるのは pb である）。

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

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

ページ割り当て戦略#

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

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

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

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

ページをいつ装入するか：事前装入戦略（実行前）；要求装入戦略（実行時）。

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

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

ワーキングセット：特定の時間間隔内にプロセスが実際にアクセスするページの集合（常駐集のサイズは通常ワーキングセットのサイズよりも大きく設定され、チラつき現象を防ぐ）。

補足：

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

八、ファイルシステム#

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

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

九、I/O モデル#

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

デバイス間の I/O#

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

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

ブロッキング
ユーザースレッドが特定のシステム関数を呼び出してカーネルからデータを取得する際、データがカーネルキャッシュに到達するまで、そのスレッドはブロック状態になり、データの到着を待つ。
非ブロッキング
ユーザースレッドがデータを取得しようとする際、カーネルキャッシュにデータがあるかどうかに関係なく、直接戻り、データを取得できる場合もあれば、取得できない場合もある。スレッドをブロック状態にすることはない。
I/O多重化
多重化は 1 つのスレッドが複数の 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 を追加する。