行き詰まりを防ぐ！デッドロック徹底解説

行き詰まりを防ぐ！デッドロック徹底解説

デッドロックとは

複数の処理が、互いに必要な資源を握ったまま、相手が持つ資源を待ち続け、身動きが取れなくなる状態。これがデッドロックと呼ばれるものです。まるで、交差点で車が同時に進入し、譲り合うことなく、立ち往生してしまう状況のようです。

プログラムの世界で考えてみましょう。複数のプログラムの一部である処理や、処理をさらに細かく分割した作業単位が、共有されている資源にアクセスしようとする場面を考えてみてください。この時、ある特定の条件が重なると、デッドロックが発生します。例えば、二つの処理があるとします。一つ目の処理は資源Aを既に確保していて、資源Bを必要としています。同時に、二つ目の処理は資源Bを確保していて、資源Aを必要としています。この状態では、お互いに相手の持っている資源を待ち続けるため、どちらの処理も先に進むことができません。これがデッドロックです。

一度デッドロックが発生すると、関係する処理は永久に待ち続けることになり、システム全体が停止してしまう可能性も出てきます。これは非常に深刻な問題です。特に、多数のプログラムが複雑に連携する大規模なシステムや、リアルタイム性、つまり即座の応答が求められるシステムでは、デッドロックへの対策が欠かせません。

デッドロックを避けるためには、いくつかの方法があります。例えば、資源を必要とする順番をすべての処理で統一したり、資源を一定時間以上確保できない場合は解放する仕組みを導入したりすることで、デッドロックの発生を防ぐことができます。また、システムを設計する段階で、デッドロックが発生しないような構造を考えることも重要です。これらの対策を適切に組み合わせることで、システムの安定稼働を実現し、デッドロックによる深刻な問題を回避することができるのです。

発生の仕組み

複数の処理が同時に資源を利用しようとした際に、どの処理も先に進めなくなってしまう現象を、行き詰まり、つまりデッドロックと言います。このデッドロックが発生するには、４つの条件が同時に成立する必要があります。

まず１つ目の条件は、ある資源は一度に一つの処理しか利用できないという相互排除です。例えば、プリンターのような装置は、複数の処理が同時に使うと出力が混ざってしまうため、一度に一つの処理しか利用できません。

２つ目の条件は保持と待ちです。これは、すでにいくつかの資源を持っている処理が、さらに別の資源を要求して待ち状態になることです。例えば、処理Ａがプリンターをすでに使っており、さらにスキャナーを使おうとしているが、スキャナーは他の処理に使われているため待っている状態です。

３つ目の条件は循環待ちです。これは複数の処理が資源を要求する際に、環状の依存関係が発生している状態です。例えば、処理Ａはプリンターを持ってスキャナーを待ち、処理Ｂはスキャナーを持ってプリンターを待つというように、お互いに相手が持っている資源を待っている状態です。

４つ目の条件は先取り不能です。これはある処理が持っている資源を、他の処理が無理やり奪うことができない状態のことです。例えば、処理Ａがプリンターを使っている途中で、処理Ｂが無理やりプリンターの使用権を奪うことができない状態です。

これらの４つの条件、つまり資源を同時に一つしか使えない、資源を持ちながら別の資源を待つ、資源の要求が循環している、そして資源を奪えない、が全て満たされるとデッドロックが発生します。一度デッドロックが発生してしまうと、関係する処理は永久に待ち続けることになり、処理を進めることができなくなります。

デッドロックの例

複数の仕事が、限られた道具を取り合う状況を考えてみましょう。これをデータベースの管理に見立てて説明します。データベースには、表という情報のかたまりが複数存在し、それぞれの表にはデータが整理されて保管されています。ある仕事は、表あをまず借りて、その後で表いを借りようとしているとします。同時に、別の仕事は表いを借りてから、表あを借りようとしています。両方の仕事が、それぞれ必要な表を借りるまでは、他の仕事にその表を使わせないように鍵をかけています。ところが、仕事１は表あに鍵をかけながら表いを待っていて、仕事２は表いに鍵をかけながら表あを待っている状態です。これは、まるで二人がお互いの持ち物を握りしめ、相手がそれを離すまで自分の持ち物を渡さないような状況です。この状態が、まさしく行き詰まり、つまりデッドロックです。

印刷機のような共同で使う道具でも、同じことが起こります。例えば、印刷機と読み取り機を共有する場合を考えてみましょう。仕事１は印刷機に鍵をかけ、仕事２は読み取り機に鍵をかけています。次に、仕事１が読み取り機を、仕事２が印刷機を使おうとすると、どちらも相手の持っている道具が必要になり、お互いに譲らずに待ち続ける状態になります。これがデッドロックです。このように、複数の仕事が複数の道具を順番に使おうとする際に、鍵をかける順番がうまく調整されていないと、デッドロックが発生するのです。データベースや印刷機に限らず、共同で利用する資源と複数の仕事がある場面では、資源の利用順序を適切に管理することで、デッドロックを防ぐことが重要になります。

デッドロックへの対策

複数の処理が、互いに相手が保持している資源を待ち続け、永遠に処理が進まなくなる状態、いわゆる「行き詰まり状態」を解消するための対策はいくつかあります。

まず、「資源の順序付け」という方法があります。これは、全ての処理に対して、資源を要求する順番をあらかじめ決めておくというものです。例えば、資源A、資源B、資源Cがあるとします。全ての処理は、資源A → 資源B → 資源C の順番でしか資源を要求できないようにすることで、資源の奪い合いによる待ち状態、つまり「行き詰まり状態」を未前に防ぐことができます。

次に、「待ち時間制限」を設定する方法があります。これは、資源を要求してから一定時間経っても許可されない場合、その要求を取り下げて、最初からやり直すというものです。この方法であれば、ある処理が資源を待ち続けて「行き詰まり状態」に陥ることを防ぐことができます。ただし、何度も要求を繰り返すことになるため、処理全体の完了までに時間がかかる可能性があります。

さらに、「行き詰まり状態の発見と復旧」という方法もあります。システムが定期的に「行き詰まり状態」が発生していないかを確認し、もし発生していた場合は、特定の処理を強制的に中断させることで、システム全体を正常な状態に戻します。強制中断された処理は、最初からやり直すことになりますが、システム全体としては「行き詰まり状態」から脱出することができます。

これらの方法は、それぞれに利点と欠点があります。システムの特性や要求に応じて、どの方法を採用するのが適切なのかを慎重に検討する必要があります。例えば、リアルタイム性が求められるシステムでは、「待ち時間制限」は不向きかもしれません。また、「行き詰まり状態の発見と復旧」は、システムに負荷をかける可能性があります。どの方法が最適かは、システムの状況に合わせて判断することが重要です。

デッドロック検知

複数の処理が互いに相手が持つ資源を待ち続け、処理が進まなくなる状態を、行き詰まり、つまりデッドロックと呼びます。このデッドロックが発生しているかどうかを突き止める方法はいくつかあります。

まず、絵を使った方法で説明します。システムが管理している資源の利用状況を、点と線で表した絵に描いてみます。この絵をグラフと呼びます。資源は点で、資源の利用関係は線で表します。例えば、ある処理が資源Aを使っているなら、その処理を表す点から資源Aを表す点へ線を引きます。複数の処理が資源を奪い合うように使っている時、このグラフに輪っかのような線が現れることがあります。この輪っかを閉路と呼びます。もし閉路が見つかった場合、それは処理Aが処理Bを待ち、処理Bが処理Cを待ち、処理Cが処理Aを待つ、といった具合に、順番に待ち状態が繋がっていることを示しており、行き詰まり、つまりデッドロックが発生している可能性が高いことを意味します。

次に、システムが各処理の状態を監視する方法を見てみましょう。各処理が今どんな状態にあるか、例えば実行中なのか、それとも何かを待っているのかを常に見ているのです。もし、ある処理が何かを待っている時間が異常に長い場合、それはデッドロックが発生している可能性を示唆しています。なぜなら、デッドロック状態では、待っている処理は永遠に待ち続けることになるからです。

さらに、資源の種類や数、処理の優先順位といった情報もデッドロック検知に役立ちます。例えば、ある資源が一つしかなく、複数の処理がそれを必要としている場合、デッドロックが発生しやすくなります。また、処理に優先順位をつけることで、デッドロックを回避できる場合もあります。優先順位の高い処理に資源を優先的に割り当てることで、低い処理がいつまでも資源を待たされる、つまりデッドロック状態に陥るのを防ぐのです。

これらの検知方法を組み合わせることで、より確実にデッドロックを見つけ出すことができます。例えば、グラフによる方法で見つかった閉路が本当にデッドロックかどうかを、処理の待ち時間や資源の種類といった情報を使って詳しく調べることで、誤検知を減らすことができます。

デッドロックからの回復

複数の処理が互いに資源を待ち続け、永遠に処理が進まない状態、いわゆる行き詰まり状態からの脱出は、計算機の安定稼働を維持する上で極めて重要です。行き詰まり状態からの回復には、いくつかの方法があり、それぞれに利点と欠点が存在します。最もよく使われる方法は、行き詰まりに関わっている処理を一つ以上、強制的に停止させることです。停止させる処理の選定は慎重に行わなければなりません。システム全体への影響を最小限に抑える処理を選ぶ必要があります。たとえば、処理の重要度、処理の完了までの残り時間、処理が使用している資源量などを考慮して、どの処理を停止させるかを決めます。

処理が握っている資源を強制的に取り上げる方法も存在します。この方法は、資源を奪われた処理が中途半端な状態で停止するため、情報の正確さを損なう危険性があります。そのため、この方法は、情報の正確さがそれほど重要でない処理や、情報の損失を許容できる処理に対してのみ適用されるべきです。

また、計算機の状態を、行き詰まりが発生する前の状態に戻す方法もあります。これは巻き戻しと呼ばれ、データベースの処理などでよく使われています。巻き戻しを行うためには、処理の開始前に状態を記録しておく必要があります。行き詰まりが発生した場合、記録しておいた状態に戻すことで、行き詰まりを解消し、処理を再開することができます。巻き戻しは、状態の記録と復元に必要な手間と時間がかかるため、システムによっては大きな負担となる可能性があります。

どの方法を用いるのが適切かは、計算機の設計や、行き詰まりの発生状況、そして守るべき情報の重要度などによって変化します。状況に応じて最適な方法を選択することが、安定した計算機システムの運用には不可欠です。