操作系统
, , , , , ,

进程、线程与锁

多处理器

  • 需要借助进程和线程
    • 进程：资源分配的最小单位
    • 线程：任务调度的最小单位
  • 多处理器：实际上是并行，同一时间点上同时，因为现在已经是多核CPU的时代
  • 简单认为：一个程序n个线程，每个线程在不同的CPU核心上
    • 线程也有单独的状态机模型，“子状态机”
    • non-deterministic finite automaton（NFA），非确定性有限自动机，多线程的程序具有不确定性
  • 直观认识：thread.h
    • 基本步骤：create，生成并启动线程；join，等待所有线程返回；
    • gcc编译时：-l pthread，文档：man 7 pthreads
    • thread.h是可以修改的，实现各种不同的功能：超大线程栈、detach运行等
    • 实际上是POSIX API
  • 线程的特点：共享内存，独立堆栈
    • 当然也可以定义线程本地变量：__thread
    • __attribute__((noinline))

多线程带来的三个问题

  • 原子性：使某一条指令独占处理器执行
  • 实现原子性：
    • 临界区，上锁，解锁；
    • 使用队列解决，参照Windows API；
      • 要进行任务拆分，形成worker线程；
      • 线程池；
  • 执行顺序的丧失：
    • 一部分是由编译器优化造成的：内存读写次数的优化
  • 保护执行顺序：
    • 编译器屏障——内存屏障（memory barrier）
      • asm volatile ("" ::: "memory");
      • 保持编译后的代码（汇编的语义）与C语言代码的语义一致；
    • 为什么带有缓冲区的printf可以在多线程情况下正常调用？已经考虑到了线程安全；
      • 即不会出现 一个长字符串 插入到 另一个长字符串中 的情况
    • stdatomic.h
    • 可以手动进行内存同步：
      • 设置一个全局变量FLAG，取FLAG中的后两位bit
      • （主线程，或者main函数里）FLAG初始化为0
      • _sync_synchronize()进行全内存同步（确保线程看到的FLAG都是0）
      • 子线程通过异或修改FLAG的位
      • [[TODO]]
  • 多处理器情况下可见性的丧失
    • [[TODO]]

Peterson算法

  • 使用共享内存实现互斥
    • [[TODO]]

互斥

  • 原子指令
    • 什么叫原子化？：执行过程中不能被打断；
    • x86
      • lock指令前缀。为啥是前缀？因为要先去上锁；
      • xchg，实际上是exchange
    • 其实原子化和自旋锁问题早就有了
      • 双路CPU，谁可以访问内存？
      • 当时可以实现总线锁：CPU和缓存、内存间沟通都需要经过总线，总线加锁就安全了
    • 当代CPU
      • 缓存一致性
      • 会给处理器增加很大性能负担
    • 其实都是load（读取或载入数据） -> exec（执行一些步骤） -> store（把执行结果写回）
    • RISC-V：LR/SC，检测锁的拥堵
  • 自旋锁（spin lock）- 软件无法完美实现，就靠硬件来做
    • 一个线程加锁，其他线程重复询问锁，若仍获取不到锁则等待
    • 特点：循环等待，也叫忙等
    • 缺点：原子指令本身就有开销；忙等导致性能损失严重，处理器利用率低下；正在运行的线程可能会被调度，导致锁无法及时释放；
    • 适用场景
      • 争抢锁的概率很小，或者几乎没有；
      • 在抢占锁的时候禁止调度；
      • 几乎只在操作系统内核代码里应用；
  • 互斥锁（mutex lock） - 用户态无法完美实现，就靠内核态来做
    • 性能评价维度：伸缩性（Scalability）
    • 互斥锁的锁一般由操作系统控制
    • 一个线程加锁，其他线程询问锁，若获取不到则被调度；
    • 特点：循环等待，但不忙等；
    • 与自旋锁之间的区别
      • 自旋锁：下限很快（直接进临界区），上限很慢（忙等）
      • 互斥锁：下限没那么快（进出内核），上限没那么慢（不会忙等）
  • Futex：快速的互斥锁
    • futex = fast user mutex
    • 实际上是改良了的自旋锁和互斥锁
    • 原子指令上锁
      • 上锁成功即直接进入互斥区
      • 上锁失败自动调用内核API被调度
    • 二八定律
    • pthread_mutex
    • man futex
    • model checker?
  • “找到你依赖的假设，并大胆地打破它”

PV问题（大题考点）

  • 解题的一般流程
    • 检查有几类进程？一般每一类进程都对应着自己的函数
    • 先在函数内部用中文描述进程动作；注意执行次数
      • 只做一次
      • 不断重复：while(1)
    • 理清在执行进程前，要P什么
      • 注意：P和V是配对的，有P必有V；当发现需要P时，写完这个P必须先找它对应的V的位置，而不是去分析下一个P
      • 注意隐含的互斥问题，例如缓冲区访问
    • PV写完之后去定义信号量（和信号量本身的PV）
    • 如果存在很多个P，需要检查会不会发生死锁，会发生的话则想办法解决
      • 只有多个P存在时才可能发生死锁，因为需要请求和保持条件

CPU指令流水线

[[TODO]]

评论