Loading article…
コンピュータサイエンスにおいて、リソース不足は並行コンピューティングで発生する問題であり、プロセスが作業を処理するために必要なリソースを永続的に拒否される。 [1]不足は、スケジューリングまたは相互排除アルゴリズムのエラーによって引き起こされる場合もありますが、リソースリークによっても引き起こされ、フォーク爆弾などのサービス拒否攻撃によって意図的に引き起こされる場合もあります。
並行アルゴリズムで飢餓が不可能な場合、そのアルゴリズムは飢餓フリー、ロックアウトフリー[2]または有限バイパスを持つと呼ばれます。[3]この特性は活性の一例であり、相互排他アルゴリズムの2つの要件の1つです。もう1つは正確性です。「有限バイパス」という名前は、アルゴリズムの任意のプロセス（並行部分）が共有リソースへのアクセスを許可されるまでに、最大で有限回数バイパスされることを意味します。[3]
スケジュール
資源不足は、通常、過度に単純化されたスケジューリング アルゴリズムによって発生します。たとえば、(設計の悪い)マルチタスク システムが最初の 2 つのタスクを常に切り替えている一方で、3 番目のタスクがまったく実行されない場合、3 番目のタスクはCPU 時間が不足していることになります。カーネルの一部であるスケジューリング アルゴリズムは、公平にリソースを割り当てることになっています。つまり、アルゴリズムは、必要なリソースが常に不足するプロセスがないようにリソースを割り当てる必要があります。
多くのオペレーティング システムのスケジューラは、プロセス優先度の概念を採用しています。優先度の高いプロセス A は、優先度の低いプロセス B よりも先に実行されます。優先度の高いプロセス (プロセス A) がブロックして譲歩しない場合、優先度の低いプロセス (B) は (一部のシステムでは) スケジュールされず、スタベーションが発生します。プロセス B の結果に依存する、さらに優先度の高いプロセス X がある場合、プロセス X はシステムで最も重要なプロセスであるにもかかわらず、終了しない可能性があります。この状態は優先度の逆転と呼ばれます。現代のスケジューリング アルゴリズムには通常、プロセスがスタベーションに陥らないように、すべてのプロセスが各重要なリソース (ほとんどの場合は CPU 時間) を最小限の量だけ受け取ることを保証するコードが含まれています。
コンピュータ ネットワーク、特にワイヤレス ネットワークでは、スケジューリング アルゴリズムがスケジューリング不足に悩まされることがあります。一例として、最大スループット スケジューリングが挙げられます。
飢餓状態は通常、デッドロックによってプロセスがフリーズすることで発生します。2 つ以上のプロセスがデッドロック状態になるのは、各プロセスが同じセット内の別のプログラムが占有しているリソースを待機している間、各プロセスが何も行わないときです。一方、プロセスが他のプロセスに継続的に提供されるリソースを待機している場合、プロセスは飢餓状態にあります。飢餓状態にならないことは、デッドロックがないことよりも強力な保証です。2 つのプロセスのうち 1 つをクリティカル セクションに入れるかどうかを選択し、そのうちの 1 つを任意に選択する相互排他アルゴリズムはデッドロックにならないものの、飢餓状態にならないわけではありません。[3]
飢餓状態を解決するには、優先キューとエージング技術を組み合わせたスケジューリングアルゴリズムを使用するのが考えられます。エージングとは、システム内で長時間待機するプロセスの優先度を徐々に上げていく技術です。[4]
参照
参考文献
- ^ Tanenbaum, Andrew (2001).現代のオペレーティングシステム. Prentice Hall. pp. 184–185. ISBN 0-13-092641-8。
- ^ Herlihy, Maurice ; Shavit, Nir (2012). The Art of Multiprocessor Programming . Elsevier. p. 24. ISBN 9780123977953。
- ^ abc Raynal, Michel (2012).並行プログラミング: アルゴリズム、原理、基礎. Springer Science & Business Media. pp. 10–11. ISBN 978-3642320279。
- ^ Galvin, Peter (2010).オペレーティングシステムの概念. Wiley India Edition. p. 193. ISBN 978-81-265-2051-0。