# 系統程式設計 - Classic Deadlock Solutions

[TOC]

如果你真的很想要知到有什麼既有的 deadlock 檢測機制，可以先看看 Linux 中的 [`lockdep`](https://www.kernel.org/doc/html/latest/locking/lockdep-design.html)。不過即使是如此，跟據文件中的說法，這個演算法的複雜度是 $O(N^2)$，會使效能大大地衰退。所以實際上野只有在除錯時使用：

> *The above rules require massive amounts of runtime checking. If we did that for every lock taken and for every irqs-enable event, it would render the system practically unusably slow. The complexity of checking is O(N^2), so even with just a few hundred lock-classes we’d have to do tens of thousands of checks for every event.*

## 課程內容

### Recursive Read Deadlocks and Where to Find Them - Boqun Feng, Huawei

{%youtube BtHndERzCUY %}

### Banker's algorithm源於51年前（我於2019年寫這段話）。考試常常考這題。

{%youtube IeDXC9kZ10A %}

### ECE 252 Lecture 17: Deadlock

{%youtube y1iDjVuGPSk %}

### ECE 252 Lecture 18: Deadlock Avoidance

{%youtube QU8PK97SeQE %}

### ECE 252 Lecture 19: Deadlock Detection and Recovery

{%youtube vZPLbMFXOHU %}