关键内容

调度算法

  1. O(n)
  2. O(1)
  3. CFS
  4. BFS

文件系统

  1. 日志文件系统的运行

互斥

  1. 临界区的三个原则
  2. 死锁的四个必要条件
  3. 管程的三种类型

7 进程管理与单处理器调度

7.1 进程管理

  1. 进程的抽象：独立的逻辑控制流和私有的地址空间
  2. 进程管理系统调用：fork exec exit waitpid getpid
  3. 僵尸进程、孤儿进程
  4. fork嵌套逻辑

7.2 单处理器调度

  1. 非抢占调度：必须等待当前进程主动放弃CPU；抢占调度相反
  2. 区分周转时间、就绪等待时间、响应时间
  3. FCFS：先来先服务
  4. SJF：短作业优先
  5. SRT：最短剩余时间，支持抢占
  6. HRRN：最高响应比优先，响应比为等待时间占总时间的比例
  7. RR：时间片轮转算法
  8. MQ：多级队列，按权限调度
  9. MLFQ：多级反馈队列，一个时间片内未完成的任务降低优先级
  10. FSS：公平共享调度

7.3 实时调度

  1. 实时体现在：任务有截止时间，例如周期性任务
  2. 静态优先级、动态优先级：同一任务的优先级是否会不同；一般可抢占
  3. RM：速率单调调度算法，周期越短优先级越高
  4. EDF：最早截止时间优先算法，执行离截止时间最近的任务
  5. LLF：最低松弛度优先，松弛度表示为截止时间-当前时间-还需运行时间
  6. 优先级反置现象：低优先级进程占据了高优先级进程需要的资源。解决：优先级继承、优先级天花板协议

8 多处理器调度

8.1 对称多处理与多核架构

  1. 超线程处理器：部分硬件共用，部分硬件可以并行
  2. 多核处理器、众核处理器
  3. 对称多处理器SMP、非一致内存访问系统NUMA
  4. 多处理器的缓存一致性问题

8.2 多处理器调度简述

  1. SQMS：单队列多处理器调度（所有进程在一个队列中，不同核心选择队列不同位置的进程）

    image-20250610141036689

  2. 缓存亲和性：尽可能让进程保持在同一个CPU上运行

  3. MQMS：多队列多处理器调度，每个CPU的调度队列独立

    1. 问题：2核3进程时，负载不均
    2. 解决：定期迁移进程，每个队列观测其他队列是否有更多进程，有则可以窃取，需要设置合理的窃取检查间隔

8.3 Linux O(1)调度

  1. O(n)调度算法
    1. 每个时间片开始时计算进程的动态优先级，按动态优先级执行
    2. 单队列，多个核竞争访问一个runqueue
  2. O(1)调度
    1. 每个CPU一个runqueue
    2. 140级全局优先级，实时进程优先级高于普通进程
    3. 维护140个优先级队列，和一个140长度的位图，通过位图最高1位查询来得知当前最高优先级的进程
    4. 优先级队列使用FIFO queue实现
    5. 每个优先级包括Active队列和Expired队列，进程执行完一个时间片重新计算自身优先级并进入Expired队列
    6. Active全空后与Expired交换
    7. 所有操作均为O(1)

8.4 Linux CFS 调度

  1. CFS：Completely Fair Scheduler
  2. 为每个进程维护vruntime，表示进程应该获得的CPU时间量，每次调度vruntime最小的进程
  3. 根据进程的nice值决定每次运行后vruntime的增长速度，nice越低，权重越高，vruntime增加越慢
  4. 类似stride策略
  5. 数据结构上采用红黑树记录vruntime
  6. 新进程vruntime设置为所在队列的最小值
  7. 休眠进程需要补偿vruntime
  8. 进程在多个CPU之间迁移时要对当前CPU的本地min_vruntime做适配

8.5 Linux/FreeBSD BFS 调度

  1. BFS：Brain F**k Scheduler
  2. 时间片轮转算法的变种
  3. 多处理机时使用单就绪队列，用双向链表实现
    1. 需要互斥访问
    2. 不需要负载均衡
  4. 每个进程有时间片大小和虚拟截止时间，虚拟截止时间表示在此时间到达前必须受到调度；每个时间片用完时重新计算虚拟截止时间
  5. EEVDF：最早可执行虚拟截止时间优先调度算法

9 文件系统

9.1 文件和文件系统

  1. 文件操作的基本单位是数据块
  2. 文件的访问模式：顺序访问、随机访问、索引访问（例：数据库）
  3. 文件描述符：文件描述符表的索引值
  4. 每个进程有一个文件描述符表，指向整个内核维护的一个打开文件表，打开文件表指向i-node表，i-node表指向具体文件
  5. 目录：特殊的文件，是文件名的线性列表，每个文件名包含一个指针
  6. 硬链接：直接指向相同inode；不能跨文件系统，不能链接到目录
  7. 软链接：新建文件，文件内部存储了链接的文件的名称；可以跨文件系统，可以链接到目录
  8. 文件系统需要先挂载（将根节点与/关联）才能访问

9.2 文件系统的设计和实现

  1. 虚拟文件系统VFS：文件系统的统一接口
  2. 文件系统的存储视图
    1. 文件卷控制块（超级块）
    2. 文件控制块（inode）
    3. 目录项
    4. 数据块
  3. 文件数据块分配：连续分配与链式分配
  4. 索引分配：包括一个索引块，索引块记录了后续属于此文件的块
  5. 用位图记录空闲块表

9.3 支持崩溃一致性的文件系统

  1. 文件系统中很多写操作不是原子的（例如：写位图、写inode、写数据块），容易引发崩溃不一致

  2. fsck文件系统检查：

    1. 检查超级块
    2. 检查inode和位图是否匹配，不匹配以inode为准
    3. 检查inode，擦除损坏的inode
    4. 目录链接计数检查
    5. 重复指针检查
    6. 坏块检查

  3. 日志文件系统

    1. 日志写入：写入TxB（事务开始）、元数据、数据
    2. 日志提交：写入TxE
    3. 加检查点：将更新内容写入磁盘位置
    4. 通过日志超级块、周期清空日志来提高性能
    5. 元数据日志：日志只记录元数据，先写数据再写日志

    image-20250610150008104

    1. 三种模式：Journal Mode写全部日志，Ordered Mode只写元数据日志但保证先写数据后写日志，Writeback Mode只写元数据日志且不保证先写数据再写日志

10 进程间通信

10.1 进程间通信(IPC)概述

  1. 直接通信/间接通信：是否依赖内核中转
  2. IPC机制：
    1. 信号
    2. 管道
    3. 消息队列
    4. 套接字
    5. 文件
    6. 共享内存：唯一一种直接通信方法，其他均需要内核转达
  3. 缓冲区大小决定发送方是否需要等待接收方、需要等待多久
  4. 管道：有读写端的一定大小的字节队列，读端只读，写端只写，两端fd不同
  5. 命名管道：FIFO，可以通过mkfifo命令创建，命名管道可以支持任意两个进程间的通信，匿名管道只支持父子或兄弟进程（需要由某个进程显式创建）
  6. 消息队列：以消息的形式组织IPC信息，消息之间组成FIFO队列
    1. msgget msgsnd msgrcv msgctl
    2. msgget需要一个key，可以使用ftok生成
  7. 共享内存：将一个物理内存区域映射到多个进程的地址空间
    1. shmget shmat shmdt shmctl
  8. 信号
    1. 信号处理流程：先进入内核态，内核态将用户态返回地址指向预先定义的sig_handler函数，切入用户态执行，用户态执行完通过系统调用sigreturn陷入内核态，内核态再返回应用程序的正常上下文

11 线程与协程

11.1 线程

  1. 进程：资源分配的单位，线程：CPU调度的单位
  2. 线程的独有资源只有寄存器和栈
  3. 创建线程：pthread_create
  4. 等待线程：pthread_join，阻塞当前线程直到目标线程终止
  5. 线程的几种实现方式：
    1. 用户态管理、用户态运行
    2. 内核态管理、用户态运行
    3. 内核态管理、内核态运行（内核线程）
    4. 混合管理运行
  6. 用户态管理线程：使用用户函数而非系统调用管理线程，高效，TCB由用户管理
  7. 内核态管理的用户线程：TCB由内核管理，但运行的是用户代码
  8. 多线程程序使用fork可能出现问题
  9. 内核线程：处理内核问题，例如进行缓存写回、虚存交换、文件系统写日志
  10. LWP：轻量级线程或混合线程，用内核线程和用户级线程一一对应

11.2 协程

  1. 协程：子例程的推广，子例程只允许一个入口点、返回一次，协程可以多个入口点、在中途挂起和恢复（核心在于主动让出控制流）
  2. 无栈协程也可以看成一种异步函数
  3. 按控制传递机制分类：对称协程/非对称协程
  4. 无栈协程：可以挂起/恢复的函数；有栈协程：用户态管理并运行的线程
  5. First-Class协程：协程可以作为变量，可以用于数据结构、传参等；Second-Class协程无法作为实际对象
  6. 切换需求
    1. 进程：页表、堆、栈、寄存器
    2. 线程：栈、寄存器
    3. 协程：寄存器

12 同步互斥

12.1 概述

  1. 临界区：

    1. 进入去：检查能否进入临界区的代码
    2. 临界区：访问临界资源，需要互斥执行
    3. 退出区：清除正在进入临界区的标志
    4. 剩余区

  2. 临界区三原则：空闲则入，忙则等待，有限等待，（可选）让权等待

  3. 实现互斥的方法之一：禁用硬件中断

  4. Peterson算法：孔融让梨

    image-20250610160944458

  5. Dekkers算法

    image-20250610161325305

  6. n线程：

    image-20250610161519885

    image-20250610161534445

    image-20250610161823283

  7. 更高级的原语：

    1. 锁
    2. 原子测试置位指令TaS：测试一个值是否是1，无论是否都置1，返回原始值，可用来请求锁（是1就忙等，是0就置1）
    3. 原子交换指令CaS：判断值是否是old，如果是则改为new返回true，否则什么也不做，返回false

12.2 信号量

  1. P：请求，减少；V：释放，增加
  2. 两种使用模式
    1. 临界区：先P再V
    2. 条件同步：我P你V
  3. 生产者-消费者问题：设置3个信号量，一个用于临界区限制，一个用于计数当前满槽数，一个用于计数当前空槽数

12.3 管程和条件变量

  1. 管程：一种用于多线程互斥访问共享资源的程序结构，使用面向对象方法，任意时刻最多一个线程执行管程代码

  2. 条件变量：没有实际变量语义，但有阻塞/唤醒功能，允许线程在条件变量处被阻塞、等待条件变量唤醒

  3. 管程各原语的语义：

    image-20250610163821619

  4. Hoare/Hansen/MESA管程

    image-20250610164003192

    1. Hoare：消费者进入，消费者入等待队列，生产者进入，生产者生产，生产者通知消费者后进入紧急队列，消费者消费，消费者离开，生产者离开
    2. Mesa：消费者进入，消费者入等待队列，生产者进入，生产者生产，生产者通知消费者可用，生产者离开，消费者离开队列重新进入管程，消费者消费（允许竞争）
    3. Hausen：消费者进入，消费者等待，生产者进入，生产者生产，生产者离开，生产者通知，消费者消费，消费者离开

  5. 生产者-消费者问题的Java条件变量实现分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class BoundedBuffer {
    private Queue<Integer> buffer;
    private int capacity;
    private Lock mutex;
    private Condition notFull;  // 缓冲区不满的条件
    private Condition notEmpty; // 缓冲区不空的条件

    public BoundedBuffer(int cap) {
        buffer = new LinkedList<>();
        capacity = cap;
        mutex = new ReentrantLock();
        notFull = mutex.newCondition();
        notEmpty = mutex.newCondition();
    }

    // 生产者方法
    public void produce(int item) throws InterruptedException {
        mutex.lock();
        try {
            while (buffer.size() == capacity) {
                notFull.await();  // 缓冲区满，等待
            }
            buffer.add(item);
            notEmpty.signal();    // 唤醒消费者
        } finally {
            mutex.unlock();
        }
    }

    // 消费者方法
    public int consume() throws InterruptedException {
        mutex.lock();
        try {
            while (buffer.isEmpty()) {
                notEmpty.await();  // 缓冲区空，等待
            }
            int item = buffer.remove();
            notFull.signal();      // 唤醒生产者
            return item;
        } finally {
            mutex.unlock();
        }
    }
}

这里的consume和produce函数均为管程，二者同时只有一个可以执行，这是为了防止二者同时进入，依赖各自的条件变量导致死锁

12.4 同步互斥实例问题

  1. 哲学家就餐

    image-20250610165827836

    1. 解决方案：AND型信号量集

  2. 读者—写者问题：读优先/写优先？

12.5 死锁

  1. 资源：可重用资源、可消耗资源

  2. 资源分配图

    1. 顶点：进程和资源
    2. 边：进程指向资源为请求，资源指向进程为分配

  3. 形成死锁的必要条件：互斥，持有并等待，非抢占，循环等待

  4. 死锁预防：破坏死锁四个条件之一

  5. 死锁避免

    1. 需要先验信息：进程声明所需资源的最大数目

    2. 系统安全状态：存在安全执行序列，沿此序列，每个进程释放资源后，下一个进程一定可以满足需求

    3. 不安全状态不一定会出现死锁，但安全状态一定无死锁

    4. 银行家算法

      image-20250612102413742

      image-20250612102534671

      image-20250612102616722

  6. 死锁检测：同银行家算法

  7. 死锁恢复

    1. 中止一些进程直到死锁消除
    2. 资源抢占