マルチタスク システムでは、いくつかの異常な状態によって、実行中のプロセスまたはスレッドの進行が妨げられます。プロセスとスレッドの両方を単に「プロセス」と呼びます。これらの状態のうちの 2 つは、デッドロックとライブロックと呼ばれます。
前者は、互いにブロックしているプロセスを指し、どちらかの実行を妨げます。後者は、互いの進行を妨げるプロセスを指しますが、実際には実行をブロックしません。たとえば、お互いに継続的にトランザクションをロールバックさせ、どちらもトランザクションを完了することができない場合があります。
もう 1 つの状態は、プロセスの進行に必要な 1 つまたは複数の有限のリソースがプロセスによって枯渇し、プロセスが進行しない限り復元できない、リソース スターベーションとして知られています。これもライブロックの特殊なケースです。
「リソース飢餓」に限定されない「飢餓」の他の定義、特に学術的な定義があるかどうかを知りたいです。参考文献は特に歓迎します。
いいえ、これは宿題ではありません。:-)
妊婦が優先されるレストランで食品を購入するために列に並んでいると想像してください。そして、常にたくさんの妊婦が到着しています。
あなたはすぐに飢えます。;)
ここで、あなたが優先度の低いプロセスであり、妊婦が優先度の高いプロセスであると想像してください。=)
リソース不足がライブロックの特殊なケースだとは言いません。いつもの：
ライブロックでは、スレッドは進行しませんが、実行を続けます。(デッドロック状態では、実行を続けることさえできません)
枯渇すると、一部のスレッドは進行し、一部のスレッドは実行されません。
良い説明: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html。しかし、用語の選択が異なる場合があることは理解しています。
飢餓に関しては、私が聞いた定義は次のとおりです。
仮定 (セマフォのセマンティクス、OS スケジューラの動作など) と一致する無限の実行パス (インターレース) を指定できると仮定して、スレッド T が何らかのリソースを待機して中断され、再開されることはありません。 . このとき、T は飢餓と呼ばれます。
しかし、練習はそれに一致しません。2 つのスレッドが無限ループで同じクリティカル セクションを実行するとします。同期コードにより、最初のスレッドは 1 時間に 1 回クリティカル セクションに入ることができます。飢餓ですか？両方のスレッドの進行が許可されていますが、最初のスレッドはその作業を非常にゆっくりと行っています。
飢餓の最も単純な原因は弱いセマフォです。同様に動作する同期プリミティブを使用している (または独自に構築している) 場合、飢餓が発生します。
飢餓がよく知られている古典的な問題:
読み書き問題。(1) リーダーがライターを飢えさせることができる (2) ライターがリーダーを飢えさせることができる (3) 飢餓が発生しないように、スレッドを同期することが可能です ( http://en.wikipedia. org/wiki/Readers-writers_problem )
食事の哲学者 ( http://en.wikipedia.org/wiki/Dining_philosophers_problem )
詳細については、The Little Book of Semaphores (無料): http://www.greenteapress.com/semaphores/を心からお勧めします。
すべての飢餓が何らかのリソースを待っているために引き起こされているかどうかを尋ねています。そうです。
スレッドは中断できます。
(1) ブロッキング システム コールで - ミューテックス、セマフォ、条件変数の待機/取得。write()、poll() など。
(2) いくつかのノンブロッキング操作 - 計算の実行など。
(1) の飢餓は、リソース (ミューテックス、バッファなど) の飢餓です。
(2) の飢餓は、CPU の飢餓です。これはリソースと見なすことができます。発生する場合、問題はスケジューラにあります。
HTH
スタベーションまたは「無期限のブロック」が通常出てくるもう 1 つの領域は、プライオリティ スケジューリング アルゴリズムについて話すときです。優先度スケジューリング アルゴリズムでは、優先度の低いプロセスが無期限に待機する可能性があります。優先度の高いプロセスの安定した流れにより、優先度の低いプロセスが実行されるのを防ぐことができます。
優先スケジューラの場合、解決策は「エージング」です。エージングとは、システム内で長時間待機するプロセスの優先度を徐々に上げていく手法です。
飢餓とは、システムにデッドロックがない場合でも、プロセスまたはサービスが提供されていない場合です。
これは、明確にするために作成した例です。
コンピュータから WAN へのアクセスなどを制御するアルゴリズムを想像してみてください。このアルゴリズムは、「より少ない帯域幅を使用するコンピュータに優先アクセスを提供する」というポリシーを持つことができます.数GBをどこかに送信します。このポリシーだけでは、アルゴリズムがそのコンピューターを選択しないため、そのコンピューターは枯渇します。これは、より小さな帯域幅の使用を要求する他のコンピューターが常に存在するためです。
それを飢餓といいます。
仕事も一種の資源です。プロデューサとコンシューマのセットアップにおける作業の分散が公平ではない (または理想的でない) 場合、一部のスレッドは十分な作業項目を取得せず、常にビジー状態にしておくことができません。
プロセスは、1 つまたは複数のリソースを長時間取得しません。1 つのプロセスが問題なく実行されるため、これはデッドロックではありません。エージングを使用してこの問題を解決できます。各リクエストにはエージング係数が使用されます。