线程活性问题 ​

死锁活锁和饥饿是破坏系统活跃性的主要三种问题.

死锁 ​

多个线程在执行过程中，因争夺资源而造成的一种互相等待的现象。若无外力干涉，它们都将无法推进

死锁的存在有四大必要条件 ——

• 互斥 (Mutual Exclusion): 资源在同一时刻只能被一个线程占用。
• 占有并等待 (Hold and Wait): 线程在持有至少一个资源的同时，请求获取其他被占用的资源。
• 非抢占 (No Preemption): 资源不能被强制从占用它的线程中剥夺，只能由占有它的线程主动释放。
• 循环等待 (Circular Wait): 存在一个线程等待环路，如 T1 等待 T2 占用的资源，T2 等待 T1 占用的资源。

在发生死锁的时候,大部分情况我们无能为力.所以更重要的是设计出不会发生死锁的代码 —— 对发生死锁的四大条件下手

1. 破坏循环等待 —— 强制全局锁排序 —— 强制系统中的所有线程按照固定的、统一的顺序获取锁（例: 始终先加锁标识符小的，再加锁标识符大的）
2. 使用定时锁
3. 等

双缓冲 ​

(思想很不错,所以再说说,在图形那块保证没有画面撕裂也是使用类似的思想)

维护了两个 Buffer块 A 和 B, 同时指定 A 为”只读“; B 为“只写”. 用这样的操作把读写操作解耦.在旧的模型中,数据只有一份,所以在读取数据的时候需要加锁;在写入数据的时候也需要加锁;就可能出现死锁问题.现在完全分离 —— 保证不会出现生产者和消费者抢夺同一资源的问题.

只读内存块 A 表示当前最新的数据,不妨定义其为t时刻的数据,那么同一时间,我们让只写内存块B被刷入数据,同时记作t+1时刻的数据(未来人这块).

然后在t时刻结束的时候, 我们强制等待B块的数据也写入完毕,此时只需要交换A和B的地址,就可以使得t+1时刻的数据作为下一帧的最新用来读取的数据

活锁 ​

活锁发生时，多个并发线程并没有被操作系统挂起（阻塞），它们仍在不断地执行代码、响应其他线程的状态变化，并尝试推进任务。然而，由于所有涉及的线程都在执行绝对对称的重试逻辑，导致它们的状态不断发生碰撞和回退。系统作为一个整体，有效吞吐量（Goodput）降为零。

看到比较形象的例子 —— 狭路,迎面有人,此时双方都在左右避让(正常运行),但是怎么移动都刚好碰到一起(无法成功获得资源)而无法往前继续行进.

特征也非常明显 ——

• CPU 占用率极高： 陷入活锁的线程通常处于极速的自旋循环（Spin Loop）中，单核或多核占用率飙升至 100%。
• 状态高频震荡： 线程内部的状态机在“尝试获取资源”与“释放资源并退避”之间高频切换。
• 无确定性进展： 与死锁的绝对静止不同，活锁是动态的，但在宏观上任务毫无进度。

所以,解决活锁的核心思想是打破对称性 (Break Symmetry) 并降低争抢频率 (Reduce Contention)

(实际上感觉都是利用引入随机性等来打破对称)

比如截断二进制指数退避, 当一个线程第c次尝试 CAS 失败时，它不能立刻重试，而是必须等待一段随机时间.(通过随机性来引入非对称性,同时这个随机性随时间指数增长)

饥饿 ​

饥饿是指一个处于就绪状态的线程，因为所需资源的分配策略不公平，导致其等待时间无限期延长，甚至永远无法进入临界区执行。

简单来说,就是线程一直等待执行,但是由于优先级不够高,一直处于等待调度器分配等过程中而无法进入执行.

可以通过优化调度器算法进行解决 —— 比如不是单纯的看优先级,也要结合线程发起的时间戳来进行判断.

或者使用公平锁 / 比较公平的调度方式 —— 但是可能会降低效率.

综上所述 ​

|异常类型 (Liveness Hazard)|宏观表现 (Macro View)|微观 CPU 状态 (Micro View)|核心成因 (Core Cause)|破局核心哲学 (Resolution Philosophy)| |

红黑树 ​

一种自平衡的BST，具有如下性质——

1. 每个节点不是红色就是黑色
2. 根节点必须是黑色。
3. 叶子节点（NIL 节点）被视为黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色。
5. 从任一节点到其所有后代 NIL 节点的简单路径都包含相同数目的黑色节点。

在插入的时候，如果插入节点为黑色，必然违反性质5，所以只能是红色——但是如果它的父节点是红的，就违反性质4。

为了维护它的性质，需要引入修改颜色和左旋、右旋的操作—— 在脑子中可以想象为一个长度为4的链绕中间的节点旋转了一下（左右旋就是方向不同而已）

改色就是把黑色节点改成红色节点；红色节点改成黑色节点，问题不大。

论左右旋 ——

左旋 ​

将节点的右子节点上提为局部根，原根下移为左子

下面假设对x处进行左旋

   x                    y
  / \                  / \
 α   y      左旋       x   γ
    / \