オペレーティングシステムでデッドロックを防ぐための最小リソース数を求めるC++プログラム

メモリ上に存在するプロセスの数を P、各プロセスが実行を完了するまでに必要なリソースの数を N とします。このとき、デッドロックが決して発生しないようにするために割り当てるべきリソースの最小数 R を求めるのが本記事のテーマです。

デッドロックとは

デッドロックとは、オペレーティングシステム上で複数のプロセスが互いに相手の持つリソースを待ち合い、誰も処理を先へ進められなくなる状態のことです。プログラムの実行に必要なリソースが、別のリソースの解放を待っているプロセスによって占有されているため、実行が永久に停止してしまいます。

たとえば、メモリ上に P1 と P2 という2つのプロセスがあり、P1 はリソース R1 を、P2 はリソース R2 を必要としているとします。ここで P1 が R2 を保持したまま R1 を待ち、同時に P2 が R1 を保持したまま R2 を待つと、デッドロックが発生します。

これは循環待ち（circular wait）と呼ばれる状態で、デッドロックが発生する代表的な原因のひとつです。したがって、デッドロックを未然に防ぐには、プロセス全体に対して最低限どれだけのリソースを用意しておけばよいのかを事前に計算しておくことが重要になります。

デッドロックが発生しないための条件

R >= P × (N − 1) + 1

• R：必要なリソースの総数
• P：プロセスの数
• N：各プロセスが必要とするリソースの数

この式の考え方は次のとおりです。各プロセスが最大でも N−1 個のリソースしか保持していなければ、どのプロセスにも実行を完了できる可能性が残ります。最悪のケースとして、P 個のプロセスすべてがそれぞれ N−1 個ずつのリソースを占有しても、あと 1 個のリソースがあれば、そのうちの 1 つのプロセスが実行を完了し、使用していたリソースを解放できます。解放されたリソースによって残りのプロセスも順次処理を進められるため、デッドロックは発生しなくなります。

入出力例

入力：プロセス数 = 5、必要リソース数 = 3
出力：必要な最小リソース数：11

入力：プロセス数 = 7、必要リソース数 = 2
出力：必要な最小リソース数：8

アルゴリズム

開始
ステップ1 → 最小リソース数を計算する関数を宣言する
    int min_resource(int process, int need)
    int calculate = 0 を宣言する
    calculate = process * (need - 1) + 1 を代入する
    calculate を返す
ステップ2 → main() 関数内で
    int process = 5、need = 3 を宣言する
    min_resource(process, need) を呼び出す
終了

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 必要な最小リソース数を計算する関数
int min_resource(int process, int need) {
    int calculate = 0;
    calculate = process * (need - 1) + 1;
    return calculate;
}

int main() {
    int process = 5, need = 3;
    cout << "必要な最小リソース数 : " << min_resource(process, need);
    return 0;
}

実行結果

必要な最小リソース数 : 11

まとめ

デッドロックを防ぐためには、プロセス数 P と各プロセスが必要とするリソース数 N から、「R ≥ P × (N − 1) + 1」という条件を満たすリソースを用意すればよいことが分かります。このシンプルな式を活用すれば、システム設計の段階で必要なリソース量を見積もり、循環待ちによる永久待機状態を回避できます。ぜひ実際にコードを実行して、さまざまな値での挙動を確認してみてください。