随想

仅用来记录一些学习过程中类比联想到的东西

• 中断 -> 上下文切换 -> 原子性无法保证

  • 中断的类型：
    • 被动中断：硬件导致（时钟，I/O ...）
    • 主动中断：系统调用
  • 硬件引入中断，则同样由硬件来支持原子性的保证
    • 尝试在问题的源头去寻找问题的解法

• 操作系统最早通过关闭中断 + 自旋的方式来实现互斥，但是这种方法存在非常大的问题，后来提出了从硬件层面上支持测试并设置指令（test-and-set instruction）的方式来实现互斥

  • 即：进入临界区前先检查一个特定的变量是否已经被占用（test），如果是则自旋等待（或做别的事情），如果不是则进入临界区，并设置该变量为已占用（set）。
  • 存在的问题为：在完成 test 后且还未执行 set 前，如果发生中断，则会出现多个线程/进程同时持有锁的现象。
  • 解法：硬件实现原子交换指令（x86系统中的 xchg），原子的实现测试旧值的同时设置新值
  • 类比：redis 的分布式锁实现：setnx 设置 flag，并为其添加超时，可能存在两条指令中间宕机，故改进了 setnx ，将设置 flag 和设置超时合成一步完成。自旋锁保证了正确性，但却没有保证公平性，可能导致其他线程/进程饿死，redis 通过设置超时来解决这个问题

• LRU 算法通常使用哈希表 + 双向链表的方式来实现。该方法的不足之处有：双向链表存储开销大；对多线程不友好，即使是读操作也要加锁来完成（修改链表，将最近访问的节点放到链表头部）。Redis 中使用了一种近似的方式来实现 LRU 算法，即：不维护双向链表，只为每个对象维护一个相对时间，淘汰时，随机选取 3 个或者更多的对象，找到其中最老的进行淘汰，同时解决了双向链表指针开销和读加锁的问题。