C++面接総括のオペレーティングシステム(三):デッドロック
3734 ワード
デッドロック、デッドロック発生条件、デッドロックの処理方法、デッドロックの予防方法
デッドロック:2つ以上の同時プロセスで、各プロセスが何らかのリソースを持っていて、他のプロセスがそれまたは現在保持しているリソースを解放するのを待っている場合、この状態を変更する前に前進することはできません.このプロセスのセットがデッドロックを発生したと言います.通俗的には、2つ以上のプロセスが無期限にブロックされ、互いに待機している状態である.
1.デッドロックの原因は主に:
2.デッドロックの必要条件:
3.デッドロックを解決する方法:デッドロックの予防、回避、検出と回復の3種類に分けられ、もちろんダチョウアルゴリズムのような問題を無視し、デッドロックが発生することが極めて少ない場合に適用することができる.
(1)デッドロックの予防(静態)
デッドロックの予防は、システムがデッドロック状態に入らないことを保証する戦略です.その基本思想は、プロセスがリソースを申請する際に何らかのプロトコルに従うことを要求し、それによってデッドロックを生成する4つの必要条件のうちの1つまたは複数を破り、システムがデッドロック状態に入らないことを保証することである.
〈1〉反発条件を破壊する.つまり、プロセスが特定のリソースに同時にアクセスできるようにします.ただし、プリンタなどの同時アクセスが許可されていないリソースもあります.これは、リソース自体のプロパティによって決まります.だから、この方法は実用的な価値がない.
〈2〉剥奪不可条件を破壊する.すなわち、プロセスが占有者からリソースを強制的に奪うことを許可します.つまり、プロセスがいくつかのリソースを占有している場合、新しいリソースを申請しますが、すぐに満たされない場合は、占有しているすべてのリソースを解放してから再申請する必要があります.解放されたリソースは、他のプロセスに割り当てることができます.このデッドロックを予防する方法は実現が困難であり,システム性能を低下させる.
〈3〉破壊要求と保持条件.リソースの事前割り当てポリシーを実行できます.すなわち、プロセスは、実行前に必要なすべてのリソースを一度にシステムに申請する.プロセスに必要なすべてのリソースが満たされない場合は、リソースは割り当てられません.このプロセスは実行されません.システムが現在のプロセスのすべてのリソース要件を満たすことができる場合にのみ、申請されたリソースを一度にプロセスにすべて割り当てます.実行中のプロセスは、必要なすべてのリソースを占有しているため、リソースを占有してリソースを申請する現象は発生しません.そのため、デッドロックは発生しません.しかし、この戦略には次のような欠点があります.
A.多くの場合、1つのプロセスが実行される前に必要なすべてのリソースを知ることはできません.これは、プロセスが実行時に動的で予測できないためです.
B.資源利用率が低い.分割されたリソースがいつ使用されるかにかかわらず、1つのプロセスは、必要なすべてのリソースを占有した後にのみ実行されます.一部のリソースが最後にプロセスに使用されたとしても、そのプロセスは生存期間中ずっとそれらを占有し、長期にわたって使用されない状況をもたらしています.これは明らかに大きな資源の浪費である.
C.プロセスの同時性を低下させる.資源が限られているうえに浪費があるため、必要なすべての資源に割り当てるプロセスの数は必然的に少なくなる.
サイクル待機条件を破壊し、資源の秩序ある分配戦略を実行する.このような戦略を採用して、つまり資源を事前に分類して番号によって分配して、プロセスが申請して、資源を占有する時ループを形成しないようにします.すべてのプロセスのリソースに対する要求は、リソースシーケンス番号の増加順に厳格に提出する必要があります.プロセスは小さなリソースを占有してこそ、大きなリソースを申請することができ、ループが発生せず、デッドロックを予防することができます.このポリシーは、前のポリシーと比較して、リソースの使用率とシステムのスループットが大幅に向上していますが、次のような欠点もあります.
A.プロセスの資源に対する要求を制限し、同時にシステム中のすべての資源に合理的な番号を付けることも困難であり、システムのオーバーヘッドを増加した.
B.番号付け申請の順序に従うために、しばらく使用しない資源も事前に申請する必要があり、それによってプロセスの資源に対する占有時間を増加させる.
(2)デッドロックの回避(動的)
デッドロックの回避は、プロセスがリソースを申請するコマンドを制限するのではなく、プロセスが発行した各申請リソースコマンドを動的にチェックし、検査結果に基づいてリソース割り当てを行うかどうかを決定します.
<1>安全シーケンス
まず、セキュリティシーケンスの定義を導入します.システムとはセキュリティであり、システム内のすべてのプロセスが何らかの順序でリソースを割り当て、順次実行できることを意味します.このプロセスシーケンス{P 1,P 2,...,Pn}はセキュリティシーケンスです.
セキュリティシーケンスが存在する場合は必ずデッドロックは発生しませんが、システムが不安全な状態(4つのデッドロックの必要条件が同時に発生する)に入ってもデッドロックが発生するとは限りません.もちろん、デッドロックが発生すると、システムは必ず安全ではありません.
<2>銀行家アルゴリズムDijstra
メリット:
銀行家アルゴリズムはデッドロックの必要条件の中の反発条件を許可し、占有し、申請条件を占有し、占有できない条件の存在を許可し、このように、デッドロックを予防するいくつかの方法と比較して、制限条件が少なく、資源利用の程度が向上した.
欠点:
〈1〉このアルゴリズムは,クライアント数を一定に保つことが要求され,マルチプログラムシステムでは困難である.
〈2〉このアルゴリズムは、すべての顧客が限られた時間内に満足することを保証するが、リアルタイムの顧客は迅速な応答を要求するため、この要因を考慮しなければならない.
〈3〉セキュリティシーケンスを探すため、実際にシステムのオーバーヘッドが増加する
(3)デッドロック検出と復旧(実際に使用した、資源配分図)
この検出には、リソース割り当て図(デッドロックの検証)、プロセス待機図がよく用いられる.システムには、デッドロックが発生すると、デッドロックが発生する位置と原因を検出し、外力によってデッドロックが発生する必要条件を破壊し、同時プロセスをデッドロック状態から回復させる専門的な機構が設けられている.
〈1〉再起動ですが、この方法はコストがかかります.
〈2〉プロセスを取り消し、資源を奪う.デッドロックに関与するプロセスを終了し、占有するリソースを回収し、デッドロックを解除します.この場合、デッドロックに参加するすべてのプロセスを一度に取り消し、すべての資源を奪うという2つの状況があります.または、デッドロックに参加するプロセスを徐々に取り消し、デッドロックプロセスが占有するリソースを徐々に回収します.一般的に、逐次取り消すプロセスを選択するときは、プロセスの優先度によってプロセスの代価を決定するなど、最もコストの小さいプロセスを取り消すことを目的として、一定の原則に従って行わなければならない.プロセス実行時のコストや、このプロセスに関連する外部ジョブのコストなどの要因を考慮します.
〈3〉プロセスロールバックポリシー(チェックポイント)は、デッドロックが発生しない前のポイントにデッドロックに関与するプロセスをロールバックさせ、そのポイントから実行を継続し、再実行時にデッドロックが発生しないようにする.これは理想的な方法ですが、操作するとシステムのオーバーヘッドが大きく、スタックのような機構がプロセスの各ステップの変化を記録し、今後のロールバックができない場合があります.
デッドロック:2つ以上の同時プロセスで、各プロセスが何らかのリソースを持っていて、他のプロセスがそれまたは現在保持しているリソースを解放するのを待っている場合、この状態を変更する前に前進することはできません.このプロセスのセットがデッドロックを発生したと言います.通俗的には、2つ以上のプロセスが無期限にブロックされ、互いに待機している状態である.
1.デッドロックの原因は主に:
（1） 。
（2） 。
（3） 。2.デッドロックの必要条件:
（1） ：
（2） ： ，
（3） ： ， ，
（4） ： 3.デッドロックを解決する方法:デッドロックの予防、回避、検出と回復の3種類に分けられ、もちろんダチョウアルゴリズムのような問題を無視し、デッドロックが発生することが極めて少ない場合に適用することができる.
(1)デッドロックの予防(静態)
デッドロックの予防は、システムがデッドロック状態に入らないことを保証する戦略です.その基本思想は、プロセスがリソースを申請する際に何らかのプロトコルに従うことを要求し、それによってデッドロックを生成する4つの必要条件のうちの1つまたは複数を破り、システムがデッドロック状態に入らないことを保証することである.
〈1〉反発条件を破壊する.つまり、プロセスが特定のリソースに同時にアクセスできるようにします.ただし、プリンタなどの同時アクセスが許可されていないリソースもあります.これは、リソース自体のプロパティによって決まります.だから、この方法は実用的な価値がない.
〈2〉剥奪不可条件を破壊する.すなわち、プロセスが占有者からリソースを強制的に奪うことを許可します.つまり、プロセスがいくつかのリソースを占有している場合、新しいリソースを申請しますが、すぐに満たされない場合は、占有しているすべてのリソースを解放してから再申請する必要があります.解放されたリソースは、他のプロセスに割り当てることができます.このデッドロックを予防する方法は実現が困難であり,システム性能を低下させる.
〈3〉破壊要求と保持条件.リソースの事前割り当てポリシーを実行できます.すなわち、プロセスは、実行前に必要なすべてのリソースを一度にシステムに申請する.プロセスに必要なすべてのリソースが満たされない場合は、リソースは割り当てられません.このプロセスは実行されません.システムが現在のプロセスのすべてのリソース要件を満たすことができる場合にのみ、申請されたリソースを一度にプロセスにすべて割り当てます.実行中のプロセスは、必要なすべてのリソースを占有しているため、リソースを占有してリソースを申請する現象は発生しません.そのため、デッドロックは発生しません.しかし、この戦略には次のような欠点があります.
A.多くの場合、1つのプロセスが実行される前に必要なすべてのリソースを知ることはできません.これは、プロセスが実行時に動的で予測できないためです.
B.資源利用率が低い.分割されたリソースがいつ使用されるかにかかわらず、1つのプロセスは、必要なすべてのリソースを占有した後にのみ実行されます.一部のリソースが最後にプロセスに使用されたとしても、そのプロセスは生存期間中ずっとそれらを占有し、長期にわたって使用されない状況をもたらしています.これは明らかに大きな資源の浪費である.
C.プロセスの同時性を低下させる.資源が限られているうえに浪費があるため、必要なすべての資源に割り当てるプロセスの数は必然的に少なくなる.
サイクル待機条件を破壊し、資源の秩序ある分配戦略を実行する.このような戦略を採用して、つまり資源を事前に分類して番号によって分配して、プロセスが申請して、資源を占有する時ループを形成しないようにします.すべてのプロセスのリソースに対する要求は、リソースシーケンス番号の増加順に厳格に提出する必要があります.プロセスは小さなリソースを占有してこそ、大きなリソースを申請することができ、ループが発生せず、デッドロックを予防することができます.このポリシーは、前のポリシーと比較して、リソースの使用率とシステムのスループットが大幅に向上していますが、次のような欠点もあります.
A.プロセスの資源に対する要求を制限し、同時にシステム中のすべての資源に合理的な番号を付けることも困難であり、システムのオーバーヘッドを増加した.
B.番号付け申請の順序に従うために、しばらく使用しない資源も事前に申請する必要があり、それによってプロセスの資源に対する占有時間を増加させる.
(2)デッドロックの回避(動的)
デッドロックの回避は、プロセスがリソースを申請するコマンドを制限するのではなく、プロセスが発行した各申請リソースコマンドを動的にチェックし、検査結果に基づいてリソース割り当てを行うかどうかを決定します.
<1>安全シーケンス
まず、セキュリティシーケンスの定義を導入します.システムとはセキュリティであり、システム内のすべてのプロセスが何らかの順序でリソースを割り当て、順次実行できることを意味します.このプロセスシーケンス{P 1,P 2,...,Pn}はセキュリティシーケンスです.
セキュリティシーケンスが存在する場合は必ずデッドロックは発生しませんが、システムが不安全な状態(4つのデッドロックの必要条件が同時に発生する)に入ってもデッドロックが発生するとは限りません.もちろん、デッドロックが発生すると、システムは必ず安全ではありません.
<2>銀行家アルゴリズムDijstra
メリット:
銀行家アルゴリズムはデッドロックの必要条件の中の反発条件を許可し、占有し、申請条件を占有し、占有できない条件の存在を許可し、このように、デッドロックを予防するいくつかの方法と比較して、制限条件が少なく、資源利用の程度が向上した.
欠点:
〈1〉このアルゴリズムは,クライアント数を一定に保つことが要求され,マルチプログラムシステムでは困難である.
〈2〉このアルゴリズムは、すべての顧客が限られた時間内に満足することを保証するが、リアルタイムの顧客は迅速な応答を要求するため、この要因を考慮しなければならない.
〈3〉セキュリティシーケンスを探すため、実際にシステムのオーバーヘッドが増加する
(3)デッドロック検出と復旧(実際に使用した、資源配分図)
この検出には、リソース割り当て図(デッドロックの検証)、プロセス待機図がよく用いられる.システムには、デッドロックが発生すると、デッドロックが発生する位置と原因を検出し、外力によってデッドロックが発生する必要条件を破壊し、同時プロセスをデッドロック状態から回復させる専門的な機構が設けられている.
〈1〉再起動ですが、この方法はコストがかかります.
〈2〉プロセスを取り消し、資源を奪う.デッドロックに関与するプロセスを終了し、占有するリソースを回収し、デッドロックを解除します.この場合、デッドロックに参加するすべてのプロセスを一度に取り消し、すべての資源を奪うという2つの状況があります.または、デッドロックに参加するプロセスを徐々に取り消し、デッドロックプロセスが占有するリソースを徐々に回収します.一般的に、逐次取り消すプロセスを選択するときは、プロセスの優先度によってプロセスの代価を決定するなど、最もコストの小さいプロセスを取り消すことを目的として、一定の原則に従って行わなければならない.プロセス実行時のコストや、このプロセスに関連する外部ジョブのコストなどの要因を考慮します.
〈3〉プロセスロールバックポリシー(チェックポイント)は、デッドロックが発生しない前のポイントにデッドロックに関与するプロセスをロールバックさせ、そのポイントから実行を継続し、再実行時にデッドロックが発生しないようにする.これは理想的な方法ですが、操作するとシステムのオーバーヘッドが大きく、スタックのような機構がプロセスの各ステップの変化を記録し、今後のロールバックができない場合があります.