「リソーススタベーション」の版間の差分
en:Editing Starvation (computer science)(08:36, 11 January 2021 )の和訳 |
|||
2行目: | 2行目: | ||
リソーススタベーションは[[デッドロック]]によっても発生する。デッドロックは互いに相手が必要なリソースを獲得しあったふたつ以上のプロセスが存在して、どちらも自身の獲得したリソースを諦めない状態である。 |
リソーススタベーションは[[デッドロック]]によっても発生する。デッドロックは互いに相手が必要なリソースを獲得しあったふたつ以上のプロセスが存在して、どちらも自身の獲得したリソースを諦めない状態である。 |
||
スタベーションは、スケジューリングや相互排除アルゴリズムのエラーによって引き起こされることがあるが、リソースのリークによっても引き起こされるし、フォークボムなどのサービス妨害攻撃によって意図的に引き起こされることもある。 |
|||
並列アルゴリズムでスタベーションが発生しない場合、そのアルゴリズムはスタベーションフリー、ロックアウトフリー<ref>{{cite book |title=The Art of Multiprocessor Programming |first1=Maurice |last1=Herlihy |author-link1=Maurice Herlihy |first2=Nir |last2=Shavit |author-link2=Nir Shavit |publisher=Elsevier |year=2012 |page=24 |isbn=9780123977953}}</ref>、または有限バイパスと呼ばれる{{r|raynal}}。この特性は[[ライブネス]]の一例であり、相互排除アルゴリズムの2つの要件のうちの1つで、もう1つは正当性である。有限バイパスという名前は、アルゴリズムの任意のプロセス(コンカレント・パート)が、共有リソースへのアクセスを許可される前に、最大で有限回バイパスされることを意味する<ref name="raynal">{{cite book |title=Concurrent Programming: Algorithms, Principles, and Foundations |first=Michel |last=Raynal |author-link=Michel Raynal |publisher=Springer Science & Business Media |year=2012 |isbn=3642320279 |page=10–11}}</ref> |
|||
。 |
|||
リソーススタベーションの例として、[[エドガー・ダイクストラ]]の[[食事する哲学者の問題]]がある。 |
リソーススタベーションの例として、[[エドガー・ダイクストラ]]の[[食事する哲学者の問題]]がある。 |
||
問題の根本は[[スケジューリング]]方式にある。スケジューリングは[[カーネル]]の機能の一部だが、一般にリソースを平等に割り当てることを目指している。つまり、スケジューリングアルゴリズムは、どのプロセスも永久的に必要なリソースを得られないような状況にならないようリソースの配分を行わなければならない。 |
問題の根本は[[スケジューリング]]方式にある。スケジューリングは[[カーネル]]の機能の一部だが、一般にリソースを平等に割り当てることを目指している。つまり、スケジューリングアルゴリズムは、どのプロセスも永久的に必要なリソースを得られないような状況にならないようリソースの配分を行わなければならない。<!--英文翻訳部分はスケジューリングの項目に移動。多くのオペレーティングシステムのスケジューラはプロセスの優先順位という概念を持っている。高優先順位のプロセスAは低優先順位のプロセスBよりも先に動作する。高優先順位プロセス(A)がブロック(一時休止)しなければ、低優先順位プロセス(B)は(一部のシステムでは)決してスケジュールされないため、リソーススタベーション状態となる。さらに高優先順位のプロセスXがあって、その処理にプロセスBの結果が必要とされている場合、プロセスXは最高優先順位であるにも関わらず処理が完了しないことになる。このような状態を[[優先順位の逆転]]と呼ぶ。--> |
||
== スケジューリング == |
|||
スタベーションは、通常、単純すぎるスケジューリングアルゴリズムによって引き起こされる。例えば、マルチタスクシステムで、最初の2つのタスクが常に切り替わり、3つ目のタスクが実行されない場合、3つ目のタスクがCPU時間を奪われていることになる。カーネルの一部であるスケジューリングアルゴリズムは、リソースを公平に割り当てることを目的としている。つまり、どのプロセスも必要なリソースを永久に欠いてしまわないようにリソースを割り当てるべきである。 |
|||
⚫ | オペレーティングシステムのスケジューラーの多くは、プロセスの優先度という概念を採用している。優先度の高いプロセスAは、優先度の低いプロセスBよりも先に実行される。優先度の高いプロセス(プロセスA)がブロックして一度も収まらなかった場合、優先度の低いプロセス(B)は(システムによっては)スケジュールされることはなく、スタベーション状態に陥いる。さらに優先度の高いプロセスXがあって、それがプロセスBの結果に依存している場合、プロセスXはシステムの中で最も重要なプロセスであるにもかかわらず、決して終了しないかもしれない。このような状態を「優先順位の逆転」という。最近のスケジューリングアルゴリズムでは、どのプロセスもスタベーション状態に陥らないように、重要な資源(多くはCPU時間)を最低限確保することを保証するコードが含まれているのが普通である。 |
||
コンピュータ・ネットワーク、特にワイヤレス・ネットワークでは、スケジューリング・アルゴリズムがスタベーション状態に陥ることがある。例えば、最大スループットスケジューリングなどである。 |
|||
スタベーションは、通常、プロセスのフリーズを引き起こすデッドロックが原因である。2つ以上のプロセスがデッドロックになるのは、それぞれのプロセスが何もせず、同じセットの他のプログラムが占有するリソースを待っているときとなる。一方、あるプロセスが飢餓状態に陥るのは、他のプロセスに継続的に与えられているリソースを待っているときである。スタベーションフリーは、デッドロックがないことよりも強い保証である。2つのプロセスのうち1つをクリティカルセクションに入れることを選択しなければならず、任意に1つを選択する相互排除アルゴリズムは、デッドロックフリーではあるが、スタベーションフリーではない{{r|raynal}}。 |
|||
スタベーションの解決策として考えられるのは、エージング技術を併用した優先キューによるスケジューリングアルゴリズムである。エイジングとは、システム内で長時間待機しているプロセスの優先度を徐々に上げていく技術である<ref>{{cite book |title=Operating System Concepts |last=Galvin |first=Peter|year=2010 |publisher=Wiley India Edition |isbn=978-81-265-2051-0|page=193}}</ref>。 |
|||
==脚注== |
|||
⚫ | |||
{{reflist}} |
|||
{{Computer-stub}} |
{{Computer-stub}} |
2021年7月27日 (火) 07:40時点における版
リソーススタベーションまたはリソーススターベーション(英: resource starvation; 資源飢餓)とは、マルチタスクに関連した問題であり、プロセスが必要なリソースをほぼ永久的に獲得できない状況を言う。プログラムは、そのようなリソースが無ければ処理を完了できない。
リソーススタベーションはデッドロックによっても発生する。デッドロックは互いに相手が必要なリソースを獲得しあったふたつ以上のプロセスが存在して、どちらも自身の獲得したリソースを諦めない状態である。
スタベーションは、スケジューリングや相互排除アルゴリズムのエラーによって引き起こされることがあるが、リソースのリークによっても引き起こされるし、フォークボムなどのサービス妨害攻撃によって意図的に引き起こされることもある。
並列アルゴリズムでスタベーションが発生しない場合、そのアルゴリズムはスタベーションフリー、ロックアウトフリー[1]、または有限バイパスと呼ばれる[2]。この特性はライブネスの一例であり、相互排除アルゴリズムの2つの要件のうちの1つで、もう1つは正当性である。有限バイパスという名前は、アルゴリズムの任意のプロセス(コンカレント・パート)が、共有リソースへのアクセスを許可される前に、最大で有限回バイパスされることを意味する[2] 。
リソーススタベーションの例として、エドガー・ダイクストラの食事する哲学者の問題がある。
問題の根本はスケジューリング方式にある。スケジューリングはカーネルの機能の一部だが、一般にリソースを平等に割り当てることを目指している。つまり、スケジューリングアルゴリズムは、どのプロセスも永久的に必要なリソースを得られないような状況にならないようリソースの配分を行わなければならない。
スケジューリング
スタベーションは、通常、単純すぎるスケジューリングアルゴリズムによって引き起こされる。例えば、マルチタスクシステムで、最初の2つのタスクが常に切り替わり、3つ目のタスクが実行されない場合、3つ目のタスクがCPU時間を奪われていることになる。カーネルの一部であるスケジューリングアルゴリズムは、リソースを公平に割り当てることを目的としている。つまり、どのプロセスも必要なリソースを永久に欠いてしまわないようにリソースを割り当てるべきである。
オペレーティングシステムのスケジューラーの多くは、プロセスの優先度という概念を採用している。優先度の高いプロセスAは、優先度の低いプロセスBよりも先に実行される。優先度の高いプロセス(プロセスA)がブロックして一度も収まらなかった場合、優先度の低いプロセス(B)は(システムによっては)スケジュールされることはなく、スタベーション状態に陥いる。さらに優先度の高いプロセスXがあって、それがプロセスBの結果に依存している場合、プロセスXはシステムの中で最も重要なプロセスであるにもかかわらず、決して終了しないかもしれない。このような状態を「優先順位の逆転」という。最近のスケジューリングアルゴリズムでは、どのプロセスもスタベーション状態に陥らないように、重要な資源(多くはCPU時間)を最低限確保することを保証するコードが含まれているのが普通である。
コンピュータ・ネットワーク、特にワイヤレス・ネットワークでは、スケジューリング・アルゴリズムがスタベーション状態に陥ることがある。例えば、最大スループットスケジューリングなどである。
スタベーションは、通常、プロセスのフリーズを引き起こすデッドロックが原因である。2つ以上のプロセスがデッドロックになるのは、それぞれのプロセスが何もせず、同じセットの他のプログラムが占有するリソースを待っているときとなる。一方、あるプロセスが飢餓状態に陥るのは、他のプロセスに継続的に与えられているリソースを待っているときである。スタベーションフリーは、デッドロックがないことよりも強い保証である。2つのプロセスのうち1つをクリティカルセクションに入れることを選択しなければならず、任意に1つを選択する相互排除アルゴリズムは、デッドロックフリーではあるが、スタベーションフリーではない[2]。
スタベーションの解決策として考えられるのは、エージング技術を併用した優先キューによるスケジューリングアルゴリズムである。エイジングとは、システム内で長時間待機しているプロセスの優先度を徐々に上げていく技術である[3]。
脚注
- ^ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. p. 24. ISBN 9780123977953
- ^ a b c Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. p. 10–11. ISBN 3642320279
- ^ Galvin, Peter (2010). Operating System Concepts. Wiley India Edition. p. 193. ISBN 978-81-265-2051-0