ShuWa

プロセス、スレッド、コルーチン#

プロセス、スレッド、コルーチンとは#

プロセス、スレッド、コルーチンの切り替え問題#

1. プロセス切り替え：プロセス切り替えはオペレーティングシステムによって管理され、スケジュールされる。オペレーティングシステムが別のプロセスに切り替えることを決定すると、** 現在のプロセスのコンテキスト（レジスタ値、プログラムカウンタなどを含む）** を保存し、次のプロセスのコンテキストをロードする。このプロセスはメモリマッピング、レジスタ、その他のリソースの切り替えを含むため、プロセス切り替えのコストは高い。プロセス切り替えにはオペレーティングシステムの介入が必要であり、そのためオーバーヘッドは比較的大きい。
2. スレッド切り替え：スレッド切り替えは同じプロセス内で行われ、オペレーティングシステムによってスケジュールされる。スレッド切り替えもレジスタ値、プログラムカウンタなどのコンテキスト情報を保存して復元する必要があるが、スレッドはプロセスのアドレス空間とリソースを共有しているため、切り替えコストは比較的低い。スレッド切り替えもオペレーティングシステムの介入が必要だが、プロセス切り替えのオーバーヘッドよりもはるかに小さい。
   性能オーバーヘッド：カーネルスタックの切り替え、ハードウェアコンテキストの切り替え、レジスタの内容の保存、以前の実行フローの状態の保存、CPU キャッシュの無効化
   ページテーブルの検索は非常に遅いプロセスであるため、通常はキャッシュを使用して一般的なアドレスマッピングをキャッシュし、ページテーブルの検索を加速する。このキャッシュが TLB である。プロセスが切り替わるとページテーブルも切り替えられ、ページテーブルの切り替え後に TLB が無効化され、キャッシュの無効化によりヒット率が低下し、仮想アドレスが物理アドレスに変換されるのが遅くなり、プログラムの実行が遅くなる。
3. コルーチン切り替え：コルーチン切り替えはアプリケーションレベルで行われ、コルーチンライブラリまたはプログラマによって明示的に管理される。コルーチン切り替えはオペレーティングシステムの介入を必要とせず、したがって切り替えコストは非常に低い。コルーチンの切り替えは通常、スタックポインタやローカル変数などの少量のコンテキスト情報の保存と復元に関わる。コルーチンの切り替えは協調的であり、他のコルーチンに制御を明示的に渡す必要があるため、コルーチン切り替えのオーバーヘッドはより良く制御できる。
   性能オーバーヘッド：
   現在のコルーチンの CPU レジスタ状態を保存し、切り替えが必要なコルーチンの CPU レジスタ状態を CPU レジスタにロードするだけで済む。また、完全にユーザーモードで行われるため、一般的に 1 回のコルーチンコンテキスト切り替えは最大で数十 ns のオーダーである。

コルーチン切り替えがスレッド切り替えよりも速い主な理由は 2 つ：

1. コルーチン切り替えは完全にユーザースペースで行われる；スレッド切り替えは特権モードの切り替えを伴い、カーネルスペースで完了する必要がある；
2. コルーチン切り替えはスレッド切り替えよりも行うことが少なく、スレッドはカーネルとユーザーモードの切り替え、システムコールプロセスを必要とする。

全体的に見て、プロセス切り替えのオーバーヘッドが最も高く、スレッド切り替えが次に高く、コルーチン切り替えのオーバーヘッドが最も低い。コルーチンはアプリケーションレベルで管理されるため、切り替えのタイミングをより柔軟に制御でき、効率と並行性能を向上させることができる。しかし、コルーチン内で切り替えポイントを適切に管理し、過度に頻繁な切り替えを避けることが重要である。

1 つのプロセスが最大でいくつのスレッドを作成できるか？

32 ビットシステムでは、ユーザーモードの仮想空間は 3G しかなく、スレッド作成時に割り当てられるスタックスペースが 10M であれば、1 つのプロセスが最大で約 300 のスレッドしか作成できない。
64 ビットシステムでは、ユーザーモードの仮想空間は 128T まで大きく、理論的には仮想メモリのサイズに制限されず、システムのパラメータや性能に制限される。

スレッドのクラッシュ、プロセスのクラッシュ

一般的に、スレッドが不正なメモリアクセスによってクラッシュした場合、プロセスは必ずクラッシュする。なぜシステムはプロセスをクラッシュさせるのかというと、プロセス内では各スレッドのアドレス空間が共有されているため、あるスレッドがアドレスに対して不正なアクセスを行うと、メモリの不確実性が生じ、他のスレッドに影響を与える可能性がある。この操作は危険であり、オペレーティングシステムはこれが一連の深刻な結果を引き起こす可能性が高いと考え、全体のプロセスをクラッシュさせることにした。

プロセスはどのようにクラッシュするのか、その背後のメカニズムはどうなっているのか、その答えはシグナル - kill (SIGSEGV)。

なぜスレッドのクラッシュは JVM プロセスのクラッシュを引き起こさないのか

JVM は独自のシグナルハンドラを定義し、SIGSEGV シグナルをインターセプトして、これらの 2 つがクラッシュしないようにしている。

通信方法にはどのようなものがあるか？#

プロセス間通信方法にはどのようなものがあるか？#

• パイプ / 匿名パイプ（Pipes）：親子プロセス間または兄弟プロセス間の通信に使用される。
• 名前付きパイプ（Named Pipes） : 匿名パイプは名前がないため、親子関係のプロセス間通信にしか使用できない。この欠点を克服するために、名前付きパイプが提案された。名前付きパイプは厳密に ** 先入先出（First In First Out）** を遵守する。名前付きパイプはディスクファイルの形式で存在し、ローカルの任意の 2 つのプロセス間の通信を実現できる。
• シグナル（Signal）：シグナルは比較的複雑な通信方法であり、受信プロセスに特定のイベントが発生したことを通知するために使用される；
• メッセージキュー（Message Queuing）：メッセージキューは特定の形式を持つメッセージのリストであり、メモリ内に保存され、メッセージキュー識別子によって識別される。パイプとメッセージキューの通信データは先入先出方式である。パイプ（無名パイプ：メモリ内にのみ存在するファイル；名前付きパイプ：実際のディスクメディアまたはファイルシステムに存在する）とは異なり、メッセージキューはカーネル内に保存され、カーネルが再起動される（つまり、オペレーティングシステムが再起動される）か、明示的にメッセージキューが削除されるまで、実際には削除されない。メッセージキューはメッセージのランダムクエリを実現でき、メッセージは必ずしも先入先出の順序で読み取る必要はなく、メッセージのタイプに応じて読み取ることもできる。FIFO よりも優れている。メッセージキューは、シグナルが情報量が少ない、パイプが無形式のバイトストリームしか扱えず、バッファサイズが制限されるなどの欠点を克服した。
• セマフォ（Semaphores）：セマフォはカウンターであり、共有データへのアクセスを多プロセスで制御するために使用され、セマフォの目的はプロセス間の同期である。この通信方法は主に同期に関連する問題を解決し、競合条件を回避するために使用される。
• 共有メモリ（Shared memory）：複数のプロセスが同じメモリ空間にアクセスできるようにし、異なるプロセスが共有メモリ内のデータの更新を即座に見ることができる。この方法は、ミューテックスやセマフォなどの何らかの同期操作に依存する必要がある。これは最も有用なプロセス間通信方法であると言える。
• ソケット（Sockets） : この方法は主にクライアントとサーバー間でネットワークを介して通信するために使用される。ソケットは TCP/IP をサポートするネットワーク通信の基本操作単位であり、異なるホスト間のプロセスが双方向通信を行うためのエンドポイントと見なすことができる。簡単に言えば、通信の両者の間の約束であり、ソケット内の関連関数を使用して通信プロセスを完了する。

マルチスレッド間の通信？#

マルチスレッド間ではプロセスのリソースを共有しているため、マルチスレッド間の通信はリソース使用中の競合問題の処理により多くの関心が寄せられる。

排他と同期#

単一コア CPU システムでは、複数のプログラムが同時に実行されているように見せるために、オペレーティングシステムは通常、タイムスライススケジューリングの方法で、各プロセスが毎回 1 つのタイムスライスを実行するようにする。タイムスライスが終了すると、次のプロセスに切り替わる。このタイムスライスの時間が非常に短いため、「並行性」の現象が生じる。複数のスレッドが共有リソースを競争する場合、効果的な対策を講じないと、共有データが混乱する可能性がある。

排他

上記の状況は競合条件（race condition）と呼ばれ、複数のスレッドが共有変数を操作する際に、運が悪く、実行中にコンテキストスイッチが発生し、誤った結果を得ることがある。実際、毎回の実行で異なる結果を得る可能性があるため、出力結果には不確実性（indeterminate）が存在する。
複数のスレッドが共有変数を操作するこのコードは競合状態を引き起こす可能性があるため、このコードを ** クリティカルセクション（critical section）と呼び、共有リソースにアクセスするコードの断片であり、複数のスレッドが同時に実行してはいけない。
このコードが排他（mutual exclusion）** であることを望み、つまり、クリティカルセクションで 1 つのスレッドが実行されている間、他のスレッドはクリティカルセクションに入ることを阻止されるべきである。言い換えれば、このコードが実行されている間、最大で 1 つのスレッドしか存在できない。

同期

排他は並行プロセス / スレッドのクリティカルセクションの使用問題を解決する。クリティカルセクション制御に基づく相互作用は比較的単純であり、1 つのプロセス / スレッドがクリティカルセクションに入ると、クリティカルセクションに入ろうとする他のプロセス / スレッドはすべてブロックされ、最初のプロセス / スレッドがクリティカルセクションを離れるまで待機する。
私たちは、マルチスレッド内では各スレッドが必ずしも順序通りに実行されるわけではなく、基本的にはそれぞれ独立して予測不可能な速度で進行するが、時には複数のスレッドが密接に協力して共通のタスクを実現することを望むことがある。
いわゆる同期とは、並行プロセス / スレッドがいくつかの重要なポイントで互いに待機し、メッセージを通じて通信する必要があることを指し、この相互制約の待機と情報の相互通信をプロセス / スレッドの同期と呼ぶ。

排他と同期の実装と使用#

ロック

ロック操作とアンロック操作を使用することで、並行スレッド / プロセスの排他問題を解決できる。
クリティカルセクションに入ろうとするすべてのスレッドは、まずロック操作を実行する必要がある。ロック操作が成功すれば、スレッドはクリティカルセクションに入ることができる；クリティカルリソースへのアクセスを完了した後、アンロック操作を実行してそのクリティカルリソースを解放する。
ロックの実装に応じて、「忙しい待機ロック」と「無忙しい待機ロック」に分けることができる。

忙しい待機ロック

「忙しい待機ロック」は原子操作命令に基づいており、テストとセット（Test-and-Set）命令を使用する。
ロックを取得できない場合、スレッドは常に while ループを実行し、何もせずに待機するため、「忙しい待機ロック」と呼ばれ、スピンロック（spin lock）とも呼ばれる。

無待機ロック

ロックを取得できない場合、現在のスレッドをロックの待機キューに入れ、スケジューラを実行して CPU を他のスレッドに渡す。

セマフォ

セマフォはオペレーティングシステムが提供する共有リソースへのアクセスを調整する方法である。

通常、セマフォはリソースの数を表し、対応する変数は整数（sem）変数である。

さらに、セマフォを制御するための 2 つの原子操作のシステムコール関数があり、それぞれ次のようになる：

• P 操作：sem を 1 減少させ、減少後に sem < 0 の場合、プロセス / スレッドはブロック待機に入る。そうでなければ、続行し、P 操作がブロックされる可能性があることを示す；
• V 操作：sem を 1 増加させ、増加後に sem <= 0 の場合、待機中のプロセス / スレッドを起こす。V 操作はブロックされないことを示す；

P 操作はクリティカルセクションに入る前に使用され、V 操作はクリティカルセクションを出た後に使用される。これらの操作は必ずペアで出現する必要がある。

セマフォを使用してクリティカルセクションの排他アクセスを実現する方法

各種類の共有リソースに対してセマフォ s を設定し、その初期値を 1 に設定する。これはそのクリティカルリソースが占有されていないことを示す。
クリティカルセクションに入る操作を P (s) と V (s) の間に置くだけで、プロセス / スレッドの排他を実現できる：

この時、クリティカルセクションに入ろうとするすべてのスレッドは、まず排他セマフォ上で P 操作を実行し、クリティカルリソースへのアクセスを完了した後に V 操作を実行する。排他セマフォの初期値が 1 であるため、最初のスレッドが P 操作を実行すると s の値は 0 になり、クリティカルリソースが空いていることを示し、そのスレッドがクリティカルセクションに入ることができる。

この時、もし別のスレッドがクリティカルセクションに入ろうとすると、最初に P 操作を実行し、結果として s が負の値になる。これはクリティカルリソースが占有されていることを意味し、したがって、2 番目のスレッドはブロックされる。

さらに、最初のスレッドが V 操作を実行してクリティカルリソースを解放し、s の値が 0 に戻るまで、2 番目のスレッドはブロックされたままであり、クリティカルセクションに入ることができない。2 番目のスレッドがクリティカルリソースへのアクセスを完了した後、再び V 操作を実行し、s を初期値 1 に戻す。

2 つの並行スレッドに対して、排他セマフォの値は 1、0、-1 の 3 つの値のみを取る。それぞれ次のように示す：

• 排他セマフォが 1 の場合、クリティカルセクションに入っているスレッドはない；
• 排他セマフォが 0 の場合、1 つのスレッドがクリティカルセクションに入っている；
• 排他セマフォが - 1 の場合、1 つのスレッドがクリティカルセクションに入っており、別のスレッドが入るのを待っている。

排他セマフォを使用することで、クリティカルセクションには常に 1 つのスレッドしか実行されないことが保証され、排他効果が達成される。

セマフォを使用してイベントの同期を実現する方法

同期の方法は、初期値が 0 のセマフォを設定することであり、「食事 - 料理」の同期の例を挙げる：
母親が最初に息子に料理をするかどうか尋ねるとき、P (s1) を実行し、息子が食事を必要とするかどうかを尋ねることに相当する。s1 の初期値が 0 であるため、この時 s1 は - 1 になり、息子が食事を必要としないことを示すため、母親スレッドは待機状態に入る。

息子が空腹になると、V (s1) を実行し、s1 のセマフォが - 1 から 0 に変わり、息子が食事を必要としていることを示すため、待機中の母親スレッドを起こす。母親スレッドは料理を始める。

次に、息子スレッドが P (s2) を実行し、母親に料理が終わったかどうかを尋ねる。s2 の初期値が 0 であるため、この時 s2 は - 1 になり、母親がまだ料理を終えていないことを示し、息子スレッドは待機状態に入る。

最後に、母親が料理を終えたら、V (s2) を実行し、s2 のセマフォが - 1 から 0 に戻り、待機中の息子スレッドを起こす。起こされた後、息子スレッドは食事をすることができる。

古典的な同期問題#

プデューサー - コンシューマー問題#

プデューサー - コンシューマー問題の説明：

• プデューサーはデータを生成した後、バッファに置く；
• コンシューマーはバッファからデータを取り出して処理する；
• どの時点でも、バッファにアクセスできるのは 1 つのプデューサーまたはコンシューマーのみである；

問題を分析すると、次のことがわかる：

• どの時点でも 1 つのスレッドのみがバッファを操作できるため、バッファ操作はクリティカルコードであり、排他が必要である；
• バッファが空のとき、コンシューマーはプデューサーがデータを生成するのを待たなければならない；バッファが満杯のとき、プデューサーはコンシューマーがデータを取り出すのを待たなければならない。これはプデューサーとコンシューマーが同期する必要があることを示している。

したがって、3 つのセマフォが必要であり、それぞれ次のようになる：

• 排他セマフォ mutex：バッファへの排他アクセスに使用され、初期値は 1；
• リソースセマフォ fullBuffers：コンシューマーがバッファにデータがあるかどうかを確認するために使用され、データがあれば読み取る。初期値は 0（バッファが最初は空であることを示す）；
• リソースセマフォ emptyBuffers：プデューサーがバッファに空きがあるかどうかを確認するために使用され、空きがあればデータを生成する。初期値は n（バッファサイズ）；

哲学者の食事問題#

哲学者の食事問題の説明：

• 5 人の哲学者が、何もせずに円卓を囲んで面を食べる；
• 面白いことに、このテーブルには 5 本のフォークしかなく、各哲学者の間に 1 本のフォークが置かれている；
• 哲学者たちはまず考え、考えている途中で空腹になったら食事をしたくなる；
• 奇妙なことに、これらの哲学者は食事をするために 2 本のフォークが必要であり、つまり左右のフォークを取らなければならない；
• 食べ終わったら、2 本のフォークを元の場所に戻し、考え続ける；

各哲学者の 3 つの状態を記録するために、state という配列を使用し、それぞれ食事中、考え中、空腹（フォークを取ろうとしている）である。

したがって、ある哲学者は隣の 2 人が食事をしていないときにのみ、食事状態に入ることができる。

第 i の哲学者の左隣と右隣は、マクロ LEFT と RIGHT によって定義される：

• LEFT : ( i + 5 - 1 ) % 5
• RIGHT : ( i + 1 ) % 5

例えば、i が 2 の場合、LEFT は 1、RIGHT は 3 となる。

読者 - 書き手問題#

読者 - 書き手問題の説明：

• 「読 - 読」は許可されている：同時に複数の読者が同時に読むことが許可されている
• 「読 - 書」は排他：書き手がいないときにのみ読者が読むことができ、読者がいないときにのみ書き手が書くことができる
• 「書 - 書」は排他：他の書き手がいないときにのみ書き手が書くことができる

公平な戦略：

• 優先度は同じ；
• 書き手と読者は排他アクセスを行う；
• クリティカルセクションには 1 つの書き手のみがアクセスできる；
• 複数の読者が同時にクリティカルリソースにアクセスできる；

デッドロック#

デッドロックが発生する条件#

デッドロックは以下の 4 つの条件が同時に満たされるときにのみ発生する：

• 排他条件；
• 保持と待機条件；
• 奪取不可能条件；
• 循環待機条件；

デッドロックを検出する方法#

Java - jstack
C++ - Valgrind
Python - サードパーティライブラリ deadlock-detector と deadlocks
Go - go tool trace

デッドロックを回避する方法#

リソースの順序付き割り当て法を使用して、循環待機条件を破る。

では、リソースの順序付き割り当て法とは何か？

スレッド A とスレッド B がリソースを取得する順序は同じでなければならない。スレッド A が最初にリソース A を取得し、その後リソース B を取得しようとする場合、スレッド B も同様に最初にリソース A を取得し、その後リソース B を取得しようとする。つまり、スレッド A とスレッド B は常に同じ順序で自分が欲しいリソースを要求する。

リソースの順序付き割り当て法を使用して、前にデッドロックが発生したコードを修正することができ、スレッド A のコードを変更する必要はない。

まず、スレッド A がリソースを取得する順序を明確にする必要がある。彼は最初にミューテックス A を取得し、その後ミューテックス B を取得する。

したがって、スレッド B を同じ順序でリソースを取得するように変更するだけで、デッドロックを打破することができる。

楽観的ロック、悲観的ロック#

悲観的ロックは、複数のスレッドが同時に共有リソースを変更する可能性が高いと考え、衝突が発生しやすいため、共有リソースにアクセスする前にロックをかける必要がある。

楽観的ロックは、衝突の可能性が非常に低いと仮定し、次のように機能する：まず共有リソースを変更し、その後この期間に他のスレッドがリソースを変更していないかを検証する。他のスレッドがリソースを変更していなければ操作は完了し、他のスレッドがすでにリソースを変更していた場合は、今回の操作を放棄する。
シナリオの例：オンライン文書：
複数のユーザーが同時に編集できるようにするために、実際には楽観的ロックが使用されている。複数のユーザーが同じ文書を開いて編集し、編集が完了した後にのみ変更内容に衝突がないかを検証する。

衝突が発生したと見なされるのはどういう場合か？ここで例を挙げると、ユーザー A がブラウザで文書を編集し、その後ユーザー B がブラウザで同じ文書を開いて編集したが、ユーザー B がユーザー A よりも早く提出した。この過程でユーザー A は知らない。ユーザー A が変更を提出すると、ユーザー A とユーザー B の間で並行して変更された部分に衝突が発生する。

サーバーはどのように衝突を検証するのか？通常の方法は次の通り：

衝突が発生する可能性が低いため、最初にユーザーに文書を編集させるが、ブラウザは文書をダウンロードする際にサーバーから返された文書のバージョン番号を記録する；
ユーザーが変更を提出すると、サーバーに送信されるリクエストには元の文書のバージョン番号が含まれ、サーバーはそれを現在のバージョン番号と比較する。バージョン番号が一致しない場合は提出が失敗し、一致する場合は変更が成功し、サーバーのバージョン番号が最新のバージョン番号に更新される。
実際には、私たちがよく見る SVN や Git も楽観的ロックの考え方を使用しており、最初にユーザーにコードを編集させ、提出時にバージョン番号を通じて衝突が発生したかどうかを判断し、衝突が発生した部分は自分で修正して再提出する必要がある。

楽観的ロックはロックとアンロックの操作を排除するが、衝突が発生した場合、再試行のコストは非常に高いため、衝突の可能性が非常に低く、ロックのコストが非常に高いシナリオでのみ楽観的ロックを使用することを考慮する。