リソーススタベーション

リソーススタベーションはデッドロックによっても発生する。デッドロックは互いに相手が必要なリソースを獲得しあった複数のプロセスが存在して、どちらも自身が獲得したリソースを手放さない状態である。

スタベーションは、スケジューリングや相互排除アルゴリズムのエラーによって引き起こされることがあるが、リソースのリークによっても引き起こされるし、フォークボムなどのサービス妨害攻撃によって意図的に引き起こされることもある。

並列アルゴリズムでスタベーションが発生しない場合、そのアルゴリズムはスタベーションフリー、ロックアウトフリー^[1]、または有限バイパスと呼ばれる^[2]。この特性はライブネスの一例であり、相互排除アルゴリズムの2つの要件のうちの1つで、もう1つは正当性である。有限バイパスという名前は、アルゴリズムの任意のプロセス（コンカレント・パート）が、共有リソースへのアクセスを許可される前に、最大で有限回バイパスされることを意味する^[2] 。

リソーススタベーションの例として、エドガー・ダイクストラの食事する哲学者の問題がある。

問題の根本はスケジューリング方式にある。スケジューリングはカーネルの機能の一部だが、一般にリソースを平等に割り当てることを目指している。つまり、スケジューリングアルゴリズムは、どのプロセスも永久的に必要なリソースを得られないような状況にならないようリソースの配分を行わなければならない。

スタベーションは、通常、単純すぎるスケジューリングアルゴリズムによって引き起こされる。例えば、マルチタスクシステムで、最初の2つのタスクが常に切り替わり、3つ目のタスクが実行されない場合、3つ目のタスクがCPU時間を奪われていることになる。カーネルの一部であるスケジューリングアルゴリズムは、リソースを公平に割り当てることを目的としている。つまり、どのプロセスも必要なリソースを永久に欠いてしまわないようにリソースを割り当てるべきである。

オペレーティングシステムのスケジューラーの多くは、プロセスの優先度という概念を採用している。優先度の高いプロセスAは、優先度の低いプロセスBよりも先に実行される。優先度の高いプロセス（プロセスA）がブロックして一度も収まらなかった場合、優先度の低いプロセス（B）は（システムによっては）スケジュールされることはなく、スタベーション状態に陥いる。さらに優先度の高いプロセスXがあって、それがプロセスBの結果に依存している場合、プロセスXはシステムの中で最も重要なプロセスであるにもかかわらず、決して終了しないかもしれない。このような状態を「優先順位の逆転」という。最近のスケジューリングアルゴリズムでは、どのプロセスもスタベーション状態に陥らないように、重要な資源（多くはCPU時間）を最低限確保することを保証するコードが含まれているのが普通である。

コンピュータ・ネットワーク、特にワイヤレス・ネットワークでは、スケジューリング・アルゴリズムがスタベーション状態に陥ることがある。例えば、最大スループットスケジューリングなどである。

スタベーションは、通常、プロセスのフリーズを引き起こすデッドロックが原因である。2つ以上のプロセスがデッドロックになるのは、それぞれのプロセスが何もせず、同じセットの他のプログラムが占有するリソースを待っているときとなる。一方、あるプロセスが飢餓状態に陥るのは、他のプロセスに継続的に与えられているリソースを待っているときである。スタベーションフリーは、デッドロックがないことよりも強い保証である。2つのプロセスのうち1つをクリティカルセクションに入れることを選択しなければならず、任意に1つを選択する相互排除アルゴリズムは、デッドロックフリーではあるが、スタベーションフリーではない^[2]。

スタベーションの解決策として考えられるのは、エイジング技術を併用した優先キューによるスケジューリングアルゴリズムである。エイジングとは、システム内で長時間待機しているプロセスの優先度を徐々に上げていく技術である^[3]。