Deadlock

Introduction

Deadlock 是一組 processes 都在等待 event，而該 event 只能由同一組裡的其他 process 造成。

在 synchronization 中，這個 event 通常是 lock / semaphore 被釋放。

Semaphore Example

兩個 semaphores S、Q 初始值都是 1：

P0: wait(S);        P1: wait(Q);
    wait(Q);            wait(S);
    ...                 ...
    signal(S);          signal(Q);
    signal(Q);          signal(S);

若 P0 取得 S、P1 取得 Q，接著 P0 等 Q、P1 等 S，兩邊都等對方 release，形成等待循環。

Effect

Deadlock 代表 progress 完全停止，不只是變慢。完整處理通常屬於 resource allocation、deadlock prevention / avoidance / detection 的主題。