KOBESOFT | 組み込み・IoT開発

リアルタイム制御

デッドロック

互いに資源を待ち合い処理が止まる状態。

概要

デッドロック（Deadlock）とは、2つ以上のタスク（スレッド、プロセス）が互いに相手の保持するリソースを待ち続け、どのタスクも処理を進められなくなる状態を指す。例えばタスクAがリソース1を保持しながらリソース2を要求し、同時にタスクBがリソース2を保持しながらリソース1を要求すると、両タスクは永遠に待機状態から抜け出せなくなる。

組み込みリアルタイムシステムにおいてデッドロックは極めて深刻な問題だ。一般的なPCアプリケーションであれば再起動やプロセスキルで回復できることが多いが、組み込みシステムではシステム全体が停止する可能性があり、産業機器・医療機器・自動車制御では安全上の問題にもなりえる。ウォッチドッグタイマーによる自動リセットが最後の砦となる場合もあるが、根本的な対策はデッドロックが発生しない設計だ。

歴史・背景

デッドロックという概念は1965年にE.W. Dijkstraが論文「Some theorems about the hamming distance」で初めて形式化し、「Deadly Embrace（致命的な抱擁）」とも呼んだ。1971年にCoffmanらが「デッドロックが発生する必要十分条件（Coffman条件）」を定式化し、現在の教科書的な説明の基盤となっている。

1997年のNASA火星探査機Mars Pathfinderの不具合は、デッドロックに近い問題（優先度逆転によるシステムリセット）として広く知られ、リアルタイム組み込みシステムにおける排他制御問題への関心を高めた。2003年に発生した北米大停電（Blackout）の原因の一つもソフトウェアのデッドロック的状態だったと報告されており、組み込み・制御システムでの信頼性の重要性を示す事例となった。

技術仕様

Coffman条件（デッドロックの必要条件）

デッドロックが発生するには以下4つの条件がすべて同時に成立する必要がある。1つでも取り除けばデッドロックは発生しない。

条件説明回避策
相互排除（Mutual Exclusion）資源は1つのタスクのみが使用できる読み取り専用共有などで緩和
占有と待機（Hold and Wait）資源を保持したまま別の資源を要求する資源を一括取得、または一度解放してから再取得
非横取り（No Preemption）保持中の資源を強制的に奪われないタイムアウトで自発的に解放
循環待機（Circular Wait）タスク間で資源要求が循環している資源取得順序を統一する

デッドロックの種類

リソースデッドロック（最も一般的）

タスクA: Mutex1を保持 → Mutex2を待つ
タスクB: Mutex2を保持 → Mutex1を待つ
→ 循環待機でシステム停止

通信デッドロック

タスクA: キューへの書き込みでキューフル待ち
タスクB: キューからの読み取りでキューエンプティ待ち
（AがBにメッセージを送り、BがAにメッセージを送る設計が誤った場合）

ライブロック（Livelock）（デッドロックの亜種）

タスクAとBが互いに「相手に先に取らせようとして」
資源を取得→解放→取得→解放を繰り返す状態。
処理は動いているように見えるが進行しない。

動作原理

デッドロック発生のシナリオ

組み込みシステムでよく起きる典型的なデッドロックのパターンを示す。

パターン1：ネスト順序の不一致

// タスクA（例: センサー読み取りタスク）
void task_a(void *pvParam) {
    for (;;) {
        xSemaphoreTake(mutex_spi, portMAX_DELAY);   // SPI先取り
        xSemaphoreTake(mutex_uart, portMAX_DELAY);  // UARTを要求 ← ここで待つ
        // SPI+UARTを使う処理
        xSemaphoreGive(mutex_uart);
        xSemaphoreGive(mutex_spi);
    }
}

// タスクB（例: ログ出力タスク）
void task_b(void *pvParam) {
    for (;;) {
        xSemaphoreTake(mutex_uart, portMAX_DELAY);  // UART先取り
        xSemaphoreTake(mutex_spi, portMAX_DELAY);   // SPIを要求 ← ここで待つ
        // UART+SPIを使う処理
        xSemaphoreGive(mutex_spi);
        xSemaphoreGive(mutex_uart);
    }
}
// ★ タスクAがSPIを、タスクBがUARTを保持した瞬間、デッドロック発生

パターン2：割り込みハンドラとタスクの誤った同期

SemaphoreHandle_t mutex;

void ISR_Handler(void) {
    // 間違い: ISRでミューテックスを取得しようとする
    // xSemaphoreTake(mutex, portMAX_DELAY);  // ISRではブロック不可
    // 通常タスクがmutexを保持中→ISRがmutexを待てずクラッシュ
}

パターン3：再帰的なミューテックスロック（非再帰ミューテックスの場合）

SemaphoreHandle_t mutex = xSemaphoreCreateMutex();  // 非再帰

void process_data(void) {
    xSemaphoreTake(mutex, portMAX_DELAY);
    validate_data();  // ← この中でも同じmutexをTakeしようとする
    xSemaphoreGive(mutex);
}

void validate_data(void) {
    xSemaphoreTake(mutex, portMAX_DELAY);  // 自分自身がロック中→デッドロック
    // ...
    xSemaphoreGive(mutex);
}

リソース割り当てグラフ（RAG）

デッドロックの検出には「リソース割り当てグラフ」が使われる。タスクとリソースをノード、「保持」・「要求」をエッジで表したグラフで、サイクル（循環）が存在するとデッドロックが発生している。

[タスクA] → 要求 → [Mutex2]
[Mutex1]  → 保持 → [タスクA]
[タスクB] → 要求 → [Mutex1]
[Mutex2]  → 保持 → [タスクB]
★ サイクルあり → デッドロック確定

用途・ユースケース

検出と回避の実装例

デッドロックを根本から防ぐには、以下の設計パターンを採用する。

解決策1：資源取得順序の統一（循環待機を排除）

// 全タスクで mutex_spi → mutex_uart の順に取得する
// 逆順では絶対に取得しないというルールを設ける

// タスクA（修正後）
void task_a_fixed(void *pvParam) {
    for (;;) {
        xSemaphoreTake(mutex_spi, portMAX_DELAY);   // 常にSPI先
        xSemaphoreTake(mutex_uart, portMAX_DELAY);  // 次にUART
        // 処理
        xSemaphoreGive(mutex_uart);
        xSemaphoreGive(mutex_spi);
    }
}

// タスクB（修正後）
void task_b_fixed(void *pvParam) {
    for (;;) {
        xSemaphoreTake(mutex_spi, portMAX_DELAY);   // タスクBも同じ順序
        xSemaphoreTake(mutex_uart, portMAX_DELAY);
        // 処理
        xSemaphoreGive(mutex_uart);
        xSemaphoreGive(mutex_spi);
    }
}
// ★ タスクAがSPIを保持した状態でタスクBがSPIを要求→タスクBがブロック
//    → タスクAがUARTも取得 → 処理完了 → 解放 → 循環が発生しない

解決策2：タイムアウト付きロックと自発的解放（非横取りを緩和）

#define LOCK_TIMEOUT_MS  100

void task_with_timeout(void *pvParam) {
    for (;;) {
        if (xSemaphoreTake(mutex_spi, pdMS_TO_TICKS(LOCK_TIMEOUT_MS)) != pdTRUE) {
            log_warning("SPI mutex timeout - retrying");
            continue;  // 取得失敗→保持中の資源はないので安全にリトライ
        }

        if (xSemaphoreTake(mutex_uart, pdMS_TO_TICKS(LOCK_TIMEOUT_MS)) != pdTRUE) {
            log_warning("UART mutex timeout - releasing SPI and retrying");
            xSemaphoreGive(mutex_spi);  // 保持中の資源を解放してリトライ
            vTaskDelay(pdMS_TO_TICKS(10));  // 少し待つ（ライブロック防止）
            continue;
        }

        // 両方取得成功
        // 処理...
        xSemaphoreGive(mutex_uart);
        xSemaphoreGive(mutex_spi);
        vTaskDelay(pdMS_TO_TICKS(50));
    }
}

解決策3：一括取得パターン（占有と待機を排除）

// 必要な全資源を一度に確保するか、1つも確保しないかにする
bool acquire_all_resources(TickType_t timeout) {
    // 短時間でトライ（非ブロッキング）
    if (xSemaphoreTake(mutex_spi, 0) != pdTRUE) return false;
    if (xSemaphoreTake(mutex_uart, 0) != pdTRUE) {
        xSemaphoreGive(mutex_spi);  // 部分取得を解放
        return false;
    }
    if (xSemaphoreTake(mutex_i2c, 0) != pdTRUE) {
        xSemaphoreGive(mutex_uart);
        xSemaphoreGive(mutex_spi);
        return false;
    }
    return true;  // 全資源取得成功
}

ウォッチドッグによるデッドロック対策

デッドロックが発生した場合の最終手段としてウォッチドッグタイマーが有効だ。正常動作中は定期的にウォッチドッグをリフレッシュし、デッドロックでリフレッシュが停止するとシステムをリセットする。

// FreeRTOSタスクウォッチドッグパターン
static volatile bool task_alive[MAX_TASKS] = {false};

void critical_task(void *pvParam) {
    uint32_t task_id = (uint32_t)pvParam;
    for (;;) {
        // 通常処理
        do_work();

        // 生存確認フラグをセット
        task_alive[task_id] = true;
        vTaskDelay(pdMS_TO_TICKS(100));
    }
}

void watchdog_task(void *pvParam) {
    for (;;) {
        bool all_alive = true;
        for (int i = 0; i < MAX_TASKS; i++) {
            if (!task_alive[i]) {
                all_alive = false;
                log_error("Task %d not responding!", i);
            }
            task_alive[i] = false;  // リセット
        }
        if (!all_alive) {
            // ハードウェアウォッチドッグをリフレッシュしない → システムリセット
        } else {
            IWDG_Refresh();  // ウォッチドッグリフレッシュ
        }
        vTaskDelay(pdMS_TO_TICKS(1000));
    }
}

実装・開発のポイント

静的解析ツールの活用

デッドロックは実行時にしか発覚しないことが多いが、静的解析ツールで潜在的なロック順序の問題を検出できる。

  • ThreadSanitizer（TSan）: GCC/Clangに組み込まれた動的データ競合・デッドロック検出ツール。Linuxベースの組み込みアプリのテストに有効。
  • MISRA C: 組み込み向けコーディング規約で、排他制御の誤用を防ぐルールが含まれる。
  • Polyspace/Klocwork: 商用静的解析ツールでデッドロックパターンを検出できる。

ロック階層の文書化

プロジェクト内でミューテックスの取得順序を文書化し、コードレビューで必ず確認する。順序違反はビルド時のアサートやランタイムチェックで検出できる。

// ロック階層の定義（ヘッダに明記）
// Level 1（最初に取得）: mutex_spi
// Level 2: mutex_uart
// Level 3（最後に取得）: mutex_i2c
// 規則: 番号の小さい順にのみ取得すること

#ifdef DEBUG
static int current_lock_level = 0;
#define TAKE_MUTEX(m, level) do { \
    configASSERT(level > current_lock_level); \
    xSemaphoreTake(m, portMAX_DELAY); \
    current_lock_level = level; \
} while(0)
#else
#define TAKE_MUTEX(m, level) xSemaphoreTake(m, portMAX_DELAY)
#endif

デッドロック発生時の診断

FreeRTOSでは vTaskList() や uxTaskGetSystemState() を使って全タスクの状態を取得できる。デッドロック発生時はすべての疑わしいタスクが「Blocked」状態になっている。

// FreeRTOS タスク状態のデバッグダンプ
void debug_dump_tasks(void) {
    char task_list_buf[512];
    vTaskList(task_list_buf);
    printf("Task Name\tState\tPri\tStack\tNum\n");
    printf("%s\n", task_list_buf);
    // Blocked状態のタスクが複数あればデッドロックを疑う
}

他技術との比較

手法デッドロック防止効果オーバーヘッド実装コスト
ロック順序統一高い（循環待機を排除）なし設計・レビューコスト
タイムアウト付きロック中程度（ライブロックリスクあり）小低い
一括取得高い（占有待機を排除）中（トライ＆リリースの繰り返し）中
デッドロック検出アルゴリズム検出のみ（予防ではない）高い高い
銀行家アルゴリズム完全な回避非常に高い非常に高い（組み込みでは非現実的）

ライブロックとの違い

デッドロックはタスクが完全に停止するが、ライブロックはタスクが動作しているように見えながら進展がない状態だ。タイムアウト付きリトライが適切に実装されていないと（ランダム待機なし、同一タイミングで再試行など）ライブロックになりやすい。EthernetのCSMA/CD（衝突後のランダム待機）はライブロックを防ぐ良い設計例だ。

優先度逆転との関係

デッドロックは「永遠に進まない」のに対し、優先度逆転は「遅延して進む（最終的には完了する）」という違いがある。どちらもミューテックスの不適切な使用が原因になりえるが、問題の性質と対策が異なる。ミューテックスの優先度継承機能は優先度逆転を緩和するが、デッドロックは防げない。

関連用語

ミューテックス セマフォ クリティカルセクション 優先度逆転 RTOS（リアルタイムOS） FreeRTOS タスク / スレッド スケジューラ ウォッチドッグタイマ

参考リンク

デッドロック（Wikipedia） FreeRTOS デッドロック防止ガイドライン Operating Systems: Deadlock（OSDev Wiki） Coffman Conditions（CS Lecture Notes）
用語辞典トップへ戻る