Deadlock とは？すべてが永遠に待つとき

deadlock は、2 つ以上のタスクがそれぞれ相手の必要とするリソースを保持し、互いを永遠に待ち合い、どれも前進できなくなる膠着状態です。

並行性はタスクにリソースを共有させますが、共有には調整が必要です。deadlock は、調整が循環的な形で間違ったときに起こります。thread A が lock 1 を保持して lock 2 を欲しがり、thread B が lock 2 を保持して lock 1 を欲しがります。どちらも手放さず、どちらも進めず、プログラムはハングします。

古典的な deadlock

2 つの thread、2 つの lock を、逆の順序で取得します。それぞれが 1 つの lock をつかみ、相手が保持しているもう 1 つを待ってブロックします。介入がなければ、無期限に凍りついたままです。プログラムは crash しません。単に応答をやめるだけです。

deadlock の条件

Mutual exclusion: リソースは一度に 1 つのタスクだけが保持できます。
Hold and wait: タスクは 1 つのリソースを保持しつつ別のを待ちます。
No preemption: リソースを強制的に取り上げることはできません。
Circular wait: それぞれが次を待つタスクの循環。

deadlock を避ける方法

4 つの条件のうち 1 つを崩してください。最も一般的な戦術は、lock を常に一貫したグローバルな順序で取得することで、これが circular wait を防ぎます。timeout、lock-free なデータ構造、共有状態の削減も役立ちます。

deadlock と livelock と starvation

deadlock ではタスクは待ちで固まります。livelock では互いに反応し続けますが進捗がありません。starvation では 1 つのタスクが、他が取り続けるために必要なリソースを決して得られません。3 つとも作業を停止させますが、異なる形でです。

簡単な例

行 lock を保持したまま、別のトランザクションが lock した 2 つ目の行を待つデータベーストランザクション（およびその逆）は deadlock します。多くのデータベースはこれを検出し、循環を断つために一方のトランザクションを abort します。

CI における deadlock

deadlock したテストは速く fail しません。job が制限時間に達するまでハングし、分と費用を浪費します。修正はコードにあり、retry ではありません。Latchkey は timeout を強制するのでハングした job は速やかに打ち切られ、本当に一時的に見える失敗だけを retry します。

重要なポイント

deadlock は、タスクがそれぞれ他が必要とするものを保持する循環的な待ちです。
mutual exclusion、hold-and-wait、no preemption、circular wait を必要とします。
deadlock した CI job は timeout までハングするので、retry ではなく locking を修正してください。