マルチスレッドの概念 パート スタベーション

マルチスレッド シリーズのパート 2 へようこそ!パート 1 では、原子性 と 不変性 について調査しました。

このパートでは、飢餓を理解するためにさらに深く掘り下げていきます。

飢餓は公平性とシステムパフォーマンスを保証するため、エンジニアにとって不可欠です。飢餓のリスクを認識することで、エンジニアは公平性を優先し、リソースの独占を防ぎ、すべてのスレッドが最適に機能するために必要な CPU 時間とリソースを確保できるシステムを設計できます。

ゲームロビーでの終わりのない待ち時間

オンライン マルチプレイヤー ゲームをプレイしていて、チーム戦などの人気のゲーム モードのロビーに参加しようとしていると想像してください。しばらくロビーで待っていましたが、試合が始まるたびに、より高速なインターネット環境またはより高いスキル ランキングを持つ新しいプレーヤーが優先され、あなたの前にゲームに追加されます。何度も試合が始まるのに、一向に試合に参加できないようです!

あなたは厳密にはキューにいますが、応答時間が速いかランクが高い他のプレイヤーが先にゲームに参加し続けるため、あなたはロビーにいつまでも残されたままになります。完璧に機能するシステムがあるにもかかわらず、マッチメイキング アルゴリズムが他のシステムを不当に優先するため、プレイする機会が与えられません。

1. 飢餓

飢餓とは、プロセスが続行するために必要なリソースへのアクセスを、それらのリソースが利用可能であるにもかかわらず継続的に拒否される状況です。優先度の高いプロセスまたは他のリソース割り当てポリシーによって必要なリソースを取得できないため、プロセスは待機状態のままになります。デッドロックとは異なり、リソースが完全に利用できないわけではありませんが、不公平なスケジューリングによりプロセスはリソースにアクセスできません。

2. 原因

• 優先度の逆転

  : 優先度の高いプロセスが優先度の低いプロセスが保持するリソースを待っているとき、他のより優先度の高いプロセスが CPU 時間を枯渇させる可能性があります。プロセスは到着し続けます。

• リソース割り当てポリシー

  : 一部のスケジューリング アルゴリズムでは、特定のプロセス (通常は優先度が高いプロセス) が優先されるため、優先度の低いプロセスにリソースがほとんど割り当てられない状況が発生します。

• 不適切に設計されたアルゴリズム

  : リソース割り当てアルゴリズムのバランスが取れていない、または公平ではない場合、特定のプロセスが継続的に見落とされる可能性があります。

• 高いリソース需要

  : いくつかのプロセスが過剰な量のリソースを要求すると、それらのリソースを独占することで他のプロセスが枯渇する可能性があります。

• 長い待機時間: 頻繁にプリエンプトされるプロセスや、限られたリソースをめぐって競合するプロセスでは、飢餓が発生する可能性があります。

3. 飢餓を防ぐ

• 公平性を備えた ReentrantLock の使用

Java の ReentrantLock は、公平性を強制するオプションを提供します。 true 引数を指定して ReentrantLock コンストラクターを使用すると、スレッドが先着順 (FCFS) 方式でロックを確実に取得し、飢餓を防ぐことができます。

private final Lock lock = new ReentrantLock(true); // Fair lock

• 公平なリソース共有のためのセマフォの使用

セマフォは、限られた数のリソースへのアクセスを制御するために使用されます。公平性を有効にしてセマフォを使用することで、スレッドが公平な順序で許可を取得し、飢餓を回避できます。

private final Semaphore sp = new Semaphore(1, true); // Fair semaphore

セマフォ(1, true) は、許可と公平性が 1 つだけ有効になっているセマフォです。

• 生産者と消費者の問題における飢餓の回避 (BlockingQueue の使用)

従来の生産者と消費者の問題では、生産者が消費者を圧倒した場合、または消費者が共有リソースへのアクセスを拒否された場合に、飢餓が発生する可能性があります。 BlockingQueue は、プロデューサーとコンシューマー間の同期を自動的に処理するため、これを防ぎます。キューがいっぱいの場合、またはキューが空の場合、プロデューサーとコンシューマーの両方がブロックされます。これにより、2 つの間の公平なバランスが確保され、一方が他方を圧倒することがなくなり、飢餓が回避されます。

• 公平なタスク スケジューリングのための Java の ForkJoinPool の使用

複数のタスクがフォークされて結合されるシナリオでは、Java の ForkJoinPool は、スレッド間で作業のバランスを公平に保つ方法を提供します。これにより、ワークスチールが確実に行われ、アクティブ度の低いスレッドの枯渇が防止されます。 Java の ForkJoinPool はタスクの分割とバランシングを効率的に処理し、スレッドが作業に飢えることを防ぎます。これは、アイドル状態のスレッドがビジー状態のスレッドからタスクを盗み、すべてがスムーズに進むようにするワークスチール アルゴリズムを使用して実現されます

4. オペレーティング システムが飢餓を防ぐ仕組み

オペレーティング システム (OS) は、スターベーション、つまり優先度の高いタスクが独占するために、特定のプロセスまたはスレッドが必要なリソース (CPU 時間、メモリ、I/O アクセスなど) を長期間拒否される状況を回避するためにさまざまな技術を使用します。 OS が飢餓を防ぐ一般的な方法のいくつかを次に示します。

No.	Method	Description	Prevents Starvation By
1	Aging	Gradually increases priority of waiting processes.	Prevents long waits by adjusting priority based on wait time.
2	Round-Robin Scheduling	Allocates CPU time in a fixed cyclic order.	Ensures all processes get CPU time, avoiding starvation.
3	Completely Fair Scheduler	Allocates CPU based on fairness, independent of priority.	Ensures fair distribution of CPU time.
4	Priority Boosting	Temporarily raises the priority of starved processes holding important resources.	Prevents priority inversion and ensures high-priority tasks get needed resources.
5	Multilevel Feedback Queues	Dynamically adjusts process priorities based on behavior.	Promotes long-waiting processes to higher-priority queues.
6	Semaphores with Fairness	Ensures fair access to resources through FIFO queues.	Prevents low-priority tasks from being perpetually blocked by higher-priority tasks.
7	Fair Resource Allocation	Distributes system resources like CPU and memory based on process demand and need.	Prevents resource-hogging processes from starving others.
8	Fair I/O Scheduling	Prioritizes I/O requests to ensure timely completion for all processes.	Prevents disk I/O starvation for processes making low-priority requests.

これらの戦略を実装することにより、オペレーティング システムは、リソースが無期限に不足するプロセスやスレッドが存在しないことを保証し、システム リソースのより公平かつ効率的な使用を促進できます。

ソフトウェア エンジニア向けの重要なポイント

• 飢餓は、プロセスがリソースへのアクセスを拒否され続ける進行上の問題ですが、必ずしも他のプロセスがデッドロック サイクルでブロックしているとは限りません。多くの場合、不公平なスケジュールまたはリソース割り当てが原因で発生します。
• 飢餓は、必要な資源が利用可能であっても、それを獲得する機会が得られない場合でも発生します。
• 飢餓は、システムにデッドロックがない場合でも発生します。
• 飢餓は、デッドロック防止 (デッドロックを回避するために特定のプロセスを優先するなど) の副作用である可能性があるため、公平性とデッドロック回避戦略のバランスをとることが重要です。

参照

この記事の作成を可能にしたオンライン ドキュメント、コミュニティ、利用可能なすべてのリソースに多大な感謝を申し上げます。

1. マルチスレッドの概念 パート 1: 原子性と不変性
2. スタックオーバーフロー
3. インフォグラフィック

以上がマルチスレッドの概念 パート スタベーションの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。