[オペレーティングシステム] 08. デッドロック：予防、回避、検出、復旧

[デッドロックの日常的な比喩]

狭い橋で両側から来た車が向かい合う：
  <--- 車 A      車 B --->
        [橋]
両方とも相手が引くのを待つ -> デッドロック

システムでの例：
スレッド 1: lock(A) -> lock(B) 試行（待機）
スレッド 2: lock(B) -> lock(A) 試行（待機）

// デッドロックを引き起こすコード例
#include <pthread.h>

pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_b = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    pthread_mutex_lock(&mutex_a);    // A獲得
    sleep(1);                         // タイミング問題を誘発
    pthread_mutex_lock(&mutex_b);    // B待機（デッドロック！）
    // ...
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&mutex_b);    // B獲得
    sleep(1);                         // タイミング問題を誘発
    pthread_mutex_lock(&mutex_a);    // A待機（デッドロック！）
    // ...
    pthread_mutex_unlock(&mutex_a);
    pthread_mutex_unlock(&mutex_b);
    return NULL;
}

[リソース割り当てグラフの要素]

プロセス：円 (O)
リソースタイプ：四角形内の点（インスタンス）
要求辺：Pi -> Rj（プロセスがリソースを要求）
割り当て辺：Rj -> Pi（リソースがプロセスに割り当て済み）

[デッドロックのあるリソース割り当てグラフ]

    P1 --要求--> R1 (1個) --割当--> P2
    ^                               |
    |                               |
  割当                            要求
    |                               |
    R2 (1個) <--要求-- P3 <--割当-- R3 (1個)

P1はR1を要求（P2が保有）
P2はR3を要求（P3が保有）
P3はR2を要求（P1が保有）
-> 循環が存在 -> デッドロック！

[デッドロックのないリソース割り当てグラフ - リソースインスタンスが複数]

    P1 --要求--> R1 (2個)  インスタンス1 --割当--> P2
                            インスタンス2 --割当--> P3

P2かP3のどちらかがR1を返せばP1が進行可能
-> 循環があってもデッドロックでない場合がある
   （リソースインスタンスが2個以上の場合）

方法A：実行前に必要なすべてのリソースを一度に要求
  利点：シンプル
  欠点：リソース利用率低下、飢餓の可能性

方法B：新しいリソース要求時に保持リソースをすべて返却後に再要求
  利点：柔軟
  欠点：実装が複雑

プロセスPがリソースAを保持しBを要求：
  Bが使用不可なら：
    Aを強制的に解放（プリエンプト）
    PをAとB両方を待つ状態に切り替え
    AとB両方が使用可能になったら再開

// 循環待ち予防：リソース順序規約
// リソース番号：mutex_a = 1, mutex_b = 2, mutex_c = 3

// 正しい使い方：常に小さい番号から獲得
void safe_function() {
    pthread_mutex_lock(&mutex_a);    // 番号 1
    pthread_mutex_lock(&mutex_b);    // 番号 2
    pthread_mutex_lock(&mutex_c);    // 番号 3

    // クリティカルセクション

    pthread_mutex_unlock(&mutex_c);
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
}

// 間違った使い方：逆順で要求するとデッドロックの危険
void unsafe_function() {
    pthread_mutex_lock(&mutex_c);    // 番号 3
    pthread_mutex_lock(&mutex_a);    // 番号 1（順序違反！）
}

[安全状態とデッドロックの関係]

+-------------------------------------------+
|              全体の状態                      |
|  +----------------------------------+     |
|  |          安全状態                  |     |
|  |                                  |     |
|  |                                  |     |
|  +----------------------------------+     |
|            非安全状態                      |
|       （デッドロック可能領域を含む）          |
|                 +------+                  |
|                 |デッド |                  |
|                 |ロック |                  |
|                 +------+                  |
+-------------------------------------------+

安全状態 -> デッドロックなし（保証）
非安全状態 -> デッドロック可能（必ずではない）

Available[m]:     各リソースタイプの利用可能インスタンス数
Max[n][m]:        各プロセスの最大要求量
Allocation[n][m]: 現在各プロセスに割り当てられた量
Need[n][m]:       各プロセスの残りの必要量（Max - Allocation）

[安全性チェックアルゴリズム]

1. Work = Availableをコピー
   Finish[i] = false（すべてのiに対して）

2. 以下の条件を満たすiを見つける：
   Finish[i] == false AND Need[i] <= Work

3. 見つかれば：
   Work = Work + Allocation[i]
   Finish[i] = true
   ステップ2に戻る

4. 見つからなければ：
   すべてのFinish[i]がtrueなら -> 安全状態
   そうでなければ -> 非安全状態

[銀行家アルゴリズムの例]

リソース：A(10), B(5), C(7)

        Allocation    Max        Need       Available
        A  B  C      A  B  C    A  B  C    A  B  C
P0      0  1  0      7  5  3    7  4  3    3  3  2
P1      2  0  0      3  2  2    1  2  2
P2      3  0  2      9  0  2    6  0  0
P3      2  1  1      2  2  2    0  1  1
P4      0  0  2      4  3  3    4  3  1

安全順序の探索：
1. Work = [3,3,2]
   P1のNeed[1,2,2] <= [3,3,2]？ はい！
   Work = [3,3,2] + [2,0,0] = [5,3,2], Finish[P1] = true

2. Work = [5,3,2]
   P3のNeed[0,1,1] <= [5,3,2]？ はい！
   Work = [5,3,2] + [2,1,1] = [7,4,3], Finish[P3] = true

3. Work = [7,4,3]
   P4のNeed[4,3,1] <= [7,4,3]？ はい！
   Work = [7,4,3] + [0,0,2] = [7,4,5], Finish[P4] = true

4. Work = [7,4,5]
   P2のNeed[6,0,0] <= [7,4,5]？ はい！
   Work = [7,4,5] + [3,0,2] = [10,4,7], Finish[P2] = true

5. Work = [10,4,7]
   P0のNeed[7,4,3] <= [10,4,7]？ はい！
   Finish[P0] = true

安全順序：P1 -> P3 -> P4 -> P2 -> P0
現在のシステムは安全状態！

[P1がリソース(1,0,2)を追加要求した場合]

1. Request[1] = [1,0,2] <= Need[1] = [1,2,2]？ はい（有効な要求）
2. Request[1] = [1,0,2] <= Available = [3,3,2]？ はい（リソースあり）
3. 仮定的に割り当て：
   Available = [3,3,2] - [1,0,2] = [2,3,0]
   Allocation[1] = [2,0,0] + [1,0,2] = [3,0,2]
   Need[1] = [1,2,2] - [1,0,2] = [0,2,0]

4. 安全性チェック実行：
   新しいAvailable = [2,3,0]で安全順序の存在を確認
   -> 安全なら要求許可、そうでなければ拒否

// 銀行家アルゴリズムのJava実装
public class BankersAlgorithm {
    private int[][] max;
    private int[][] allocation;
    private int[][] need;
    private int[] available;
    private int numProcesses;
    private int numResources;

    public BankersAlgorithm(int[][] max, int[][] alloc,
                             int[] avail) {
        this.max = max;
        this.allocation = alloc;
        this.available = avail;
        this.numProcesses = max.length;
        this.numResources = avail.length;
        this.need = new int[numProcesses][numResources];

        for (int i = 0; i < numProcesses; i++)
            for (int j = 0; j < numResources; j++)
                need[i][j] = max[i][j] - allocation[i][j];
    }

    public boolean isSafe() {
        int[] work = available.clone();
        boolean[] finish = new boolean[numProcesses];
        int count = 0;

        while (count < numProcesses) {
            boolean found = false;
            for (int i = 0; i < numProcesses; i++) {
                if (!finish[i] && canAllocate(need[i], work)) {
                    // リソース回収
                    for (int j = 0; j < numResources; j++)
                        work[j] += allocation[i][j];
                    finish[i] = true;
                    count++;
                    found = true;
                    System.out.println("P" + i + " 実行可能");
                }
            }
            if (!found) return false;
        }
        return true;
    }

    private boolean canAllocate(int[] need, int[] work) {
        for (int j = 0; j < numResources; j++)
            if (need[j] > work[j]) return false;
        return true;
    }
}

[待ちグラフ]

リソース割り当てグラフからリソースノードを除去し
プロセス間の直接依存関係のみを表示

P1 --> P2 --> P3
 ^            |
 |            v
 +---- P4 <--+

循環が存在：P1->P2->P3->P4->P1 -> デッドロック！

[デッドロック検出アルゴリズム]

1. Work = Available
   Allocation[i] != 0 なら Finish[i] = false
   Allocation[i] == 0 なら Finish[i] = true

2. Finish[i] == false AND Request[i] <= Work である i を見つける

3. 見つかれば：Work = Work + Allocation[i]
               Finish[i] = true
               ステップ2に戻る

4. Finish[i] == false のプロセスがあれば
   -> そのプロセスがデッドロック状態

[リソースプリエンプション時の考慮事項]

1. 犠牲者選択：どのプロセスからリソースを奪うか？
   コスト最小化基準で選択

2. ロールバック：リソースを奪われたプロセスを安全な状態に戻す
   - 完全ロールバック：最初からやり直し
   - 部分ロールバック：デッドロックを脱するのに十分な時点まで戻す

3. 飢餓防止：同じプロセスが常に犠牲者に選ばれないように
   ロールバック回数をコスト要素に含める

// trylockを使用したデッドロック防止
int try_acquire_both(pthread_mutex_t *a, pthread_mutex_t *b) {
    while (1) {
        pthread_mutex_lock(a);

        if (pthread_mutex_trylock(b) == 0) {
            return 0;  // 成功：両方のロックを獲得
        }

        // bを得られなければaも解放してリトライ
        pthread_mutex_unlock(a);
        usleep(rand() % 1000);  // しばらく待ってリトライ
    }
}

// JavaのtryLockを使用したデッドロック防止
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.TimeUnit;

public class DeadlockFree {
    private final ReentrantLock lockA = new ReentrantLock();
    private final ReentrantLock lockB = new ReentrantLock();

    public void safeMethod() throws InterruptedException {
        while (true) {
            boolean gotA = lockA.tryLock(100, TimeUnit.MILLISECONDS);
            boolean gotB = lockB.tryLock(100, TimeUnit.MILLISECONDS);

            if (gotA && gotB) {
                try {
                    // 両方のロック獲得 - 安全に作業
                    System.out.println("両方のリソースを獲得！");
                    break;
                } finally {
                    lockA.unlock();
                    lockB.unlock();
                }
            }

            // どちらか失敗したら保持しているロックを解放
            if (gotA) lockA.unlock();
            if (gotB) lockB.unlock();

            // ランダム待機後にリトライ（ライブロック防止）
            Thread.sleep((long)(Math.random() * 100));
        }
    }
}