TODO
实现
“受限直接执行”机制
- 多个进程共享 CPU 需要解决的问题
- 性能：不增加系统开销
- 安全：系统应该可以接管
- 实现
- 用户模式和内核模式分离
- 用户模式通过 Trap 指令陷入内核模式
- 系统启动时注册 Trap 表，指定发生各种中断/系统调用时执行什么命令
并发与并行
- 并发：一个核心上频繁切换不同任务
- 并行：多个核心上同时执行不同任务
进程的状态
- 挂起：可能由进程调度、Ctrl-Z (SIGTSTP) 或者内存过低导致，但是挂起状态的进程未必被换出到硬盘上！
PCB 进程控制块
- 定义在
<include/linux/sched.h>中 - 组成（还需学习：
task_struct中的具体内容- 进程状态（RUNNING/STOPPED/ZOMBIE 等）
- 进程标识符 PID
- 进程内核栈（不是用户空间栈，包括用户空间栈指针，系统调用参数等）
- 进程调度信息（动态优先级，调度策略等）
- Program Counter
- CPU 寄存器
- 内存管理信息（页表信息）什么是页表信息？
- 已执行的时间，时间限制等
- 进程相关的 IO 设备
- PCB 通过链表组织起来
- 就绪状态的进程链在一起，叫做就绪队列
- 等待状态的进程链在一起，叫做阻塞队列
进程控制
- 创建进程
- 写入 PCB 信息
- 分配资源
- 插入就绪队列
- 终止进程
- 找到 PCB
- 停止运行
- 将子进程交给 1 号进程
- 回收资源
- 从队列（不管是哪个）中删除
- 阻塞进程
- 找到 PCB
- 状态改为阻塞
- 插入阻塞队列
- 唤醒进程
- 找到 PCB
- 状态改为就绪
- 插入就绪队列
线程
- 解决的问题
- 进程上下文切换开销较大
- 进程之间通信开销较大（怎么通信？）
- 同一个进程的不同线程之间共享地址空间和文件，但是寄存器和栈是独立的
- 线程与进程的比较（可能是常见八股）
- 进程是资源分配的单位，线程是 CPU 调度的单位
- 进程的所有资源都是独享的，但线程只独享必需的资源（寄存器和栈）
- 线程和进程都有不同状态（就绪、执行、阻塞）和状态之间的转换
- 线程可以减少并发执行的时空开销（resource + overhead）
- 线程的创建比进程快，因为很多东西（页表，文件）都不需要分配，不需要加载程序
- 线程的终止比进程快，因为需要释放的资源少（同上一点）
- 同一个进程的线程之间切换比进程之间切换快，因为不需要切换页表
- ITC 比 IPC 快（例如，同步操作不需要经过内核）
线程实现
- 用户线程
- 一个内核线程对应多个用户线程
- 线程的管理和调度在用户态完成，内核不直接参与
- 优点
- TCB 由用户态线程库维护，就算内核不支持线程，也可以实现线程
- 用户线程的切换不经过内核，速度快
- 缺点
- 如果某个线程发起系统调用，则会阻塞所有线程
- 线程无法打断正在执行的线程，只能等待它自己交出 CPU 使用权
- 时间片是按进程为单位分配的，这样每个线程得到的运行时间就更少，少中少
- 内核线程
- 一个内核线程对应一个用户线程
- 线程的管理和调度完全由内核完成
- 优点
- 如果某个线程发起系统调用，并不会阻塞其他线程
- 多线程的进程得到的运行时间较多
- 缺点
- 用户线程的切换必须经过内核，速度慢
- 轻量级进程
- 多个内核线程对应多个用户线程
- 结合用户线程和内核线程的优点
调度
调度的原因
- 上下文切换的原因
- 多任务：在多个进程之间切换
- 中断处理
- 用户和内核态之间切换
IMPORTANT
当出现高优先级进程时，打断当前进程执行的行为依然需要依靠中断，例如 Round Robin 策略下通过时钟中断实现。
调度时机
- 调度算法的分类
- 非抢占式：让一个进程一直运行到阻塞/退出，才进行调度
- 抢占式：让一个进程运行一段时间，然后挂起，然后进行调度。通过时钟中断实现
- 每次进程的运行状态发生改变时，都会触发调度
调度原则
- CPU 利用率：越高越好
- 系统吞吐量：单位时间内 CPU 完成进程的数量，越高越好
- 周转时间：运行时间 + 阻塞时间 + 等待时间，越小越好
- 等待时间：就绪时间，越小越好
- 响应时间：从用户提交请求到系统产生第一次响应的时间（？）
调度算法
- FCFS 先来先服务：非抢占式，最简单，字面意思
- SJF 最短作业有限：非抢占式，最简单，字面意思
- HRRN 高响应比优先：非抢占式，优先执行 最大的进程
- RR 时间片轮转：抢占式，每个进程执行时间为固定的时间片，应当权衡设置的时间片大小
- HPF 最高优先级：抢占式或非抢占式，先执行优先级高的进程
- MFQ 多级反馈队列
- 不同的队列优先级从高到低，优先级越高时间片越短
- 第一级队列中没执行完的放到第二级队列中
- 永远优先执行高优先级队列中的进程
IPC
- 管道
- 读/写会阻塞
- 虽然说具名管道是文件，但是也不存储在磁盘上，而是内核缓冲区
- 消息队列
- 不会阻塞，写完就行了，不用等着另一端读
- 内核中的消息链表
- 共享内存
mmap- 需要通过信号量实现同步/互斥
- 信号量的值如果为负，则表示等待的线程个数
- 信号
- 例如 SIGINT、SIGTSTP、SIGKILL
- 来源可以是硬件或软件
- SIGKILL 和 SIGSTOP 无法忽略
- 套接字 Socket
- 协议族 AF_LOCAL 表示本机内部通信
- UNIX domain socket 绑定到文件（例如“/tmp/mysocket.sock”）而不是 IP 地址
线程同步
- 互斥：不能有两个线程操作同一个资源
- 同步：不同功能的线程之间（例如生产者消费者）操作同一个资源时，需要有固定的先后顺序
- 锁
- 自旋锁：占满 CPU 不断查询是否无人占用锁
- 无等待锁：没获取到锁时，把线程加入等待队列，当其他人释放锁时，唤醒一个正在等待的线程
- 信号量
- P 操作把信号量减 ，然后当信号量 时线程进入等待状态；
- V 操作把信号量加 ，然后当信号量 时唤醒一个正在等待的线程（就绪状态）
- 信号量可以实现互斥和同步（锁可不可以实现同步？）
- 初值为 实现互斥（基本用法）
- 两个初值为 的信号量，可以实现同步（等待对方，保证执行顺序）
- 常见问题
- 生产者-消费者模型，用两个信号量分别表示空缓冲区和满缓冲区的个数
- 哲学家就餐问题
- 用信号量表示每个哲学家的资源： 表示左右两人都不在吃东西， 表示至少有一人在吃东西，即当前哲学家不能吃东西
- 每次有人放下餐具时，都会重新检查左右的人是否需要吃东西，如果是，则唤醒对应进程
- 读写锁问题：可以同时有多个人读，或者一个人写
- 读者会获取写信号量（互斥信号量），并且有新读者时会加入计数器，只有在计数器为 会释放写信号量
- 写者会获取写信号量，同时获取“读者加入计数器”信号量（互斥信号量），阻止更多的读者加入计数器，直到当前写操作完成