仅用来记录一些学习过程中类比联想到的东西
-
中断 -> 上下文切换 -> 原子性无法保证
- 中断的类型：
- 被动中断：硬件导致（时钟，I/O ...）
- 主动中断：系统调用
- 硬件引入中断，则同样由硬件来支持原子性的保证
- 尝试在问题的源头去寻找问题的解法
- 中断的类型：
-
操作系统最早通过关闭中断 + 自旋的方式来实现互斥，但是这种方法存在非常大的问题，后来提出了从硬件层面上支持测试并设置指令（test-and-set instruction）的方式来实现互斥
- 即：进入临界区前先检查一个特定的变量是否已经被占用（test），如果是则自旋等待（或做别的事情），如果不是则进入临界区，并设置该变量为已占用（set）。
- 存在的问题为：在完成 test 后且还未执行 set 前，如果发生中断，则会出现多个线程/进程同时持有锁的现象。
- 解法：硬件实现原子交换指令（x86系统中的 xchg），原子的实现测试旧值的同时设置新值
- 类比：redis 的分布式锁实现：setnx 设置 flag，并为其添加超时，可能存在两条指令中间宕机，故改进了 setnx ，将设置 flag 和设置超时合成一步完成。自旋锁保证了正确性，但却没有保证公平性，可能导致其他线程/进程饿死，redis 通过设置超时来解决这个问题
LRU 算法通常使用哈希表 + 双向链表的方式来实现。该方法的不足之处有：双向链表存储开销大；对多线程不友好，即使是读操作也要加锁来完成（修改链表，将最近访问的节点放到链表头部）。Redis 中使用了一种近似的方式来实现 LRU 算法，即：不维护双向链表，只为每个对象维护一个相对时间，淘汰时，随机选取 3 个或者更多的对象，找到其中最老的进行淘汰，同时解决了双向链表指针开销和读加锁的问题。
