竞争算法

LincZero大约 5 分钟

竞争算法

详细见：

线程冲突：../../03. 计算机系统 - 线性学习版/01. 图解系统/03. 线程冲突
Cache冲突：[../下层相关/Network/《NFV的基石_深入浅出DPDK》/02. Cache和内存/06. Cache一致性](../下层相关/Network/《NFV的基石_深入浅出DPDK》/02. Cache和内存/06. Cache一致性)

竞争冲突算法 vs 竞争调度算法

这两个词的前缀 “竞争” 我是加上的，这两个东西其实都是一种 “竞争”，但本质大有不同：

调度算法：多个任务去竞争一个处理器 / 多个数据去竞争一块内存。竞争的结果是用算法去计算竞争者的优先级。
竞争算法：多个处理器核/线程去竞争一个资源 (内存/Cache等)，和上面反过来。竞争的结果是错峰避免同时使用。
竞争算法也可以说是一致性算法 (Cache一致性或者是其他的什么一致性)

竞争冲突

情景

按多线程还是多核引起分类：

多线程冲突
- 普通内存冲突，可以是寄存器与内存不一致冲突
  - 锁：加锁、解锁操作（Test-and-Set 原子指令）
  - 信号量：P、V 操作（P、V 原子指令）
多核冲突
- **Cache与内存不一致 (Cache一致性)**问题。一致性算法：
  - 低性能错误方案：不独占Cache
  - DPDK方法：避免多个数据备份、避免多个核访问同一内存地址
    - 多个核同时需要一些数据结构，为每个核都单独定义一份
    - 多个核访问同一个网卡的接收队列/发送队列，为每个核都准备一个单独的接收队列/发送队列
  - 基于目录的协议（Directory-based protocol）：全局统一管理
  - 总线窥探协议（Bus snooping protocol）：利用总线进行的分布式的广播和被通知
  - Snarfing协议：在此不作讨论
- 寄存器与内存不一致冲突、即寄存器一致性问题？
  （不一定存在。如果寄存器和Cache的数据交换是原子性的，那么不存在这个问题。问题保留，待验证）
  如果存在，但本质上感觉和Cache一致性是一个原理。Cache一致性能用的，对于寄存器内存应该也能用。
  区别应该就只有对于三级Cache，不存在Cache一致性问题，只存在寄存器一致性问题。
- 内存冲突、内存一致性问题？
  （不一定存在。感觉应该不会出现多个内存去缓存同一个硬盘数据的情况，那么就不存在这个问题。问题保留，待验证） （搜了下好像是有这么个概念，但可能和我想象中的不同）
  - CPU Cache缓存的是内存数据，内存缓存的是硬盘数据
网络并发 (Server端多协程/线程/进程都有可能)
- MySQL的并发导致用户获取和数据库不一致 (事务隔离性)：MySQL 的 MVCC（Multi-Version Concurrency Control，多版本并发控制）
- Redis缓存和数据库保证一致性。并发以及缓存和数据库修改先后的问题，可能导致数据库和缓存不一致问题。
- Redis集群的一致性：主从模式、哨兵模式、切片集群模式

情景 - 总结

共同点：

几乎都是并发引起的
几乎都是两个存储空间的一致性问题
几乎都是双写一致性的问题（例外：读写一致性也可能有问题，这种一般通过过期时间来解决）

解决方法

多线程冲突
- 基本通过原子操作解决 (锁/信号量)，避免指令乱序
一致性冲突 (多个数据备份)
- 通过全局统一管理
- 分布式的广播/被广播
其他
- MySQL 的 MVCC（Multi-Version Concurrency Control，多版本并发控制）

解决方法 - 总结

共同点：

（待总结）

其他？杂项？

（GPT）

共享内存
总线
互斥锁
IO设备
其他共享资源
信号量
事件
队列
方法
锁优化： 使用更细粒度的锁、自旋锁、读写锁等技术来减少锁竞争。
无锁算法： 采用无锁或无等待的数据结构和算法，避免使用锁。
缓存优化： 使用缓存一致性协议、伪共享填充等技术来提高缓存利用率。
线程池： 通过线程池管理线程，避免线程频繁创建和销毁。
异步I/O： 使用异步I/O操作，避免线程阻塞。
负载均衡： 将任务均匀分配给各个核心，避免单个核心负载过重。

我有一个疑问，Cache一致性那里有三个前提条件。但这里不考虑寄存器的吗？为什么限制了那么多原因？我感觉非独占Cache也会出现问题啊，多核是独占寄存器的啊。
目前我个人的理解是，也会有冲突，但这种冲突不叫 “Cache一致性的竞争冲突”，而是别的冲突，姑且叫 “寄存器的竞争冲突” 好了。
不确定