死锁
Deadlock，多个线程或进程因相互等待对方释放资源而无法继续执行的状态
必要条件
（不是充分条件）
如果以下任何一个条件不满足，那么就不会发生死锁。
但全部同时满足时，并不能保证一定会发生死锁。
互斥
Mutual Exclusion: At least one resource must be held in a non shareable mode.
请求与保持
Hold and Wait: A process must have at least one resource and be waiting for more.
不剥夺条件
No Preemption: Resources cannot be preempted. Resources are not released until process does so voluntarily.
循环等待
Circular Wait: There must exist a set of waiting processes such that waits for a resource held by waits for ... and waits for a resource held by .
解决方法
死锁预防
Deadlock Prevention
通过某种方式对资源请求进行限制，从而使至少一个必要条件不满足，例如
- The Hold and Wait condition could be broken by
- requesting all resources at once
- releasing existing resources before requesting more
⚠️ 这些方法也可能导致进程饥饿，特别是那些需要大量资源或被频繁请求的进程。因此，在设计系统时需要权衡这些因素，采取适当的策略。
- The Circular Wait condition could be broken by
- insisting processes request resources according to some predefined numeric sequence .
⚠️ 这个方法也可能导致进程受限于请求顺序而无法并行执行，使设备利用率和系统吞吐量降低。
死锁避免
Deadlock Avoidance
通过对系统进行资源分配的预测和分析，使所有进程在最坏情况下都能完成执行。
银行家算法 (The Bankers Algorithm)
🔔Lecture 17 系统中的每个进程在运行之前都必须申请它所需的资源，而系统必须根据当前的资源分配状态来判断是否可以满足该进程的资源需求。如果系统可以满足该进程的需求，并且分配资源后系统仍然处于安全状态，那么资源将被分配给该进程；否则，进程将等待直到资源可用。
死锁检测
Deadlock Detection: Allow system to enter deadlock and then recover
It requires analgorithms:
- One examines the state of the system to determine if deadlock has occurred.
Deterministic algorithms for detecting graph cycles require
for detecting graph cycles require time at best. E.g. Tarjan’s Algorithm Algorithm.
- One recovers from the deadlock by process termination or resource preemption
- Aborting all processes
- Aborting one at a time until the deadlock is broken.
- Rollback of processes to earlier checkpointed states and replaying subsequent events from a log.
死锁忽略
Ignore the problem altogether (as in Unix).
经典例子
生产者消费者问题
🔔 Lecture 14 / Lab 7Producer Consumer Problem，也被称为有界缓冲问题 (Bounded Buffer Problem)
涉及到多个生产者和消费者同时访问一个共享的有限缓冲区的情况。生产者负责生成数据并将其放入缓冲区，而消费者负责从缓冲区中取出数据并进行消费。
- 当缓冲区满时，生产者线程等待。
- 当缓冲区为空时，消费者线程等待。
哲学家就餐问题
🔔 Lecture 15 / Lab 8Dining Philosophers Problem
限制最多四个人坐在桌边
Method 1 Deadlock Avoidance by Restricting Concurrency
即至少有一个哲学家总是可以进餐，而当他吃完离开后，另一个新的哲学家进餐。
检查筷子是否可用
Method 2 Deadlock Prevention of Hold and Wait
一个哲学家是否有所需的两只筷子。如果两只筷子都可用，那么修改拿走并筷子状态。如果不可用，则等待。
给哲学家设置编号
Method 3 Prevention of Hold and Wait
读者写者问题
🔔 Lecture 16 / Lab 9Readers Writers Problem
多个读者可以同时访问共享资源，只允许一个写者往文件写信息。
但在有读者访问时，写者必须等待。
读者优先
First Readers Writers - Prioritising Readers
写者优先
Second Readers Writers