2.1 进程与线程

2.1.1 进程概述、进程与程序

1. 进程：程序的一次执行过程，是动态实体；程序是存放在外存的静态指令集合。

2. 进程实体（进程映像）组成

   1. 程序段：存放可执行代码

   2. 数据段：存放全局变量、运行数据

   3. PCB（进程控制块）：操作系统管理进程的核心数据结构 ，PCB 是进程存在的唯一标志，操作系统依靠 PCB 感知进程。

3. 进程特性 —— 异步性 异步性由并发性引发；多个进程独立向前推进，执行速度不可预测。

2.1.2 进程状态及状态转换

五大状态：创建态、就绪态、运行态、阻塞态、终止态

1. 创建态：操作系统初始化 PCB、分配资源；资源紧张时进程长期停留在创建态。

2. 就绪态：进程已获得除 CPU 以外的所有资源，等待调度。

3. 运行态：进程正在 CPU 上执行指令。

4. 阻塞态：进程主动放弃 CPU，等待外部事件或等待资源。 阻塞态无法直接切换至运行态，必须先转为就绪态。

5. 终止态：进程正常结束或被强制撤销；操作系统回收进程占用资源。

僵尸进程与孤儿进程

1. 僵尸进程 子进程先终止，父进程未调用wait()/waitpid()回收；PCB 保留，持续占用 PID。 危害：系统 PID 耗尽，无法创建新进程。

2. 孤儿进程 父进程先终止，子进程由 init/systemd 进程自动收养；对系统无危害。

状态转换触发条件

• 就绪态 → 运行态：调度程序选中进程，分配 CPU

• 运行态 → 就绪态：时间片耗尽；高优先级进程抢占 CPU（抢占调度）

• 运行态 → 阻塞态：进程主动调用系统调用，等待事件 / 资源

• 阻塞态 → 就绪态：等待事件完成，进程被唤醒

2.1.3 进程控制块 PCB

PCB 五大功能

1. 作为进程独立运行的唯一标识，无 PCB 则操作系统无法感知进程；

2. 支撑进程间断运行，上下文切换时保存旧进程现场、恢复新进程现场；

3. 记录进程管理信息，通过指针关联程序段、数据段、打开文件与各类资源；

4. 保存调度所需信息，为处理机调度提供依据；

5. 支撑进程同步与通信，存储消息队列、信号量相关指针。

PCB 仅存放通信、同步数据结构指针，不保存结构体本身。

PCB 四类信息

1. 标识符信息：进程 PID、父进程 PID、用户标识符，区分不同进程；

2. 处理机现场信息：通用寄存器、程序计数器 PC、程序状态字 PSW、栈指针，上下文切换使用；

3. 进程调度信息：进程状态、优先级、等待事件、调度计时参数；

4. 进程控制信息：程序段 / 数据段起始地址、文件描述符、资源清单、同步通信指针。

2.1.4 进程控制

        进程控制依靠原语实现。

        原语定义：由若干指令构成的原子操作，执行过程不可中断；指令要么全部执行，要么全部不执行。

1. 进程创建场景 用户登录；高级调度（作业由外存调入内存）；系统响应用户请求；现有进程创建子进程，提升并发度。

2. 创建原语执行流程 ①分配 PID；②分配空白 PCB；③分配内存、I/O 设备等软硬件资源；④初始化 PCB；

   1. 资源充足：进程加入就绪队列；

   2. 资源不足：维持创建态，父进程阻塞。

3. 终止原语执行流程 根据 PID 查找 PCB → 修改进程状态为终止态 → 递归终止所有子进程 → 回收全部资源 → 将 PCB 移出系统队列。

4. 阻塞原语 & 唤醒原语（成对出现）

   1. 阻塞：主动行为，进程自身调用阻塞原语，让出 CPU，进入阻塞队列；

   2. 唤醒：被动行为，由其他进程调用唤醒原语。 阻塞流程：查找 PCB → 将运行态修改为阻塞态，移入阻塞队列 → 执行上下文切换，调度新进程运行。

2.1.5 上下文切换与模式切换

1. 上下文切换：保存并恢复 CPU 现场，实现 CPU 在进程间切换；上下文切换只能发生在内核态。 执行流程： ①保存当前进程寄存器上下文至 PCB；②修改进程状态，移入对应队列； ③调度程序选择新进程；④读取新进程 PCB，修改状态为运行态； ⑤更新内存管理相关数据；⑥恢复新进程上下文，从断点继续执行。

2. 模式切换（用户态 ↔ 内核态） 由中断、陷阱、系统调用触发。

   1. 模式切换：不更换正在运行的进程，仅切换 CPU 特权等级；仍需要保存少量现场；

   2. 上下文切换：更换运行进程，系统开销更大。

2.1.6 线程（轻量级进程）

        引入线程目标：提高系统并发度；充分发挥多处理器性能。

1. 进程与线程核心差异

   1. 进程：资源分配的最小单位；进程地址空间相互隔离，无法直接共享数据；

   2. 线程：调度执行的最小单位；同一进程内多个线程共享地址空间与全局数据，无需内核参与即可交换数据；

   3. 开销：线程创建、切换、撤销的开销远小于进程。

2. TCB（线程控制块）：管理线程，保存 TID、寄存器信息、线程状态、优先级、栈指针。 用户栈：线程用户态运行使用；核心栈：线程内核态运行使用。

线程两种实现方式

1. 用户级线程 ULT 操作系统内核无法感知线程，调度单位依旧是进程。

   1. 优点：线程切换在用户态完成，无需陷入内核，开销低；

   2. 缺点：进程内任意线程阻塞，整个进程阻塞。

2. 内核级线程 KLT 内核可感知线程；线程创建、阻塞、切换、撤销均在内核态完成。

   1. 优点：单线程阻塞不影响同进程其他线程；支持多核并行；

   2. 缺点：线程切换伴随模式切换，系统开销较高。

三类线程映射模型

1. 多对一模型：多个用户级线程映射至 1 个内核线程 优点：切换开销小；缺点：一线程阻塞，全部阻塞，无法利用多核。

2. 一对一模型：1 个用户线程映射 1 个内核线程 优点：支持多核并行；线程阻塞互不干扰；缺点：内核线程数量受限，切换开销大。

3. 多对多模型：M 个用户线程映射 N 个内核线程（M＞N），折中方案，融合前两者优势。

进程与线程独立性总结

        进程拥有独立地址空间，隔离性强，避免进程间相互破坏；同一进程内线程共享全部资源，牺牲隔离性换取并发效率。

2.2 进程通信 IPC

        IPC（进程间通信）：进程运行过程中相互协调、交换信息。

         通信机制：信号量机制、共享存储、消息传递、管道通信、信号机制。

1. 共享存储机制

   1. 共享数据结构：共享全局变量，位于用户空间；程序员必须自行处理同步互斥；

   2. 共享存储区：操作系统在内核开辟一块无格式共享内存，多个进程可在用户空间直接读写。

2. 消息传递机制 通过send、receive原语收发消息，依赖操作系统内核。

   1. 直接通信：消息直接挂载到目标进程消息队列；

   2. 间接通信（信箱通信）：设置信箱作为中间实体，收发双方读写信箱。

3. 管道（Pipe） 本质：内核缓冲区实现的共享文件，以字符流形式传输数据。 特性：

   1. 半双工通信；双向通信需要建立两条管道；

   2. 同步约束：管道为空不能读，管道写满不能写；读写操作互斥；

   3. 数据一经读出立即丢弃；缓冲区大小固定；通信双方必须同时存在，否则进程阻塞。

4. 信号机制（软中断） 提供单向事件通知；信号可由用户、操作系统内核、其他进程产生。 内核处理信号三种方式：①直接忽略；②执行系统默认处理函数；③执行自定义信号处理函数。

2.3 处理机调度

        调度本质：资源分配；就绪队列存在多个进程时，依靠调度算法选择进程占用 CPU。

2.3.1 三级调度

1. 高级调度（作业调度）：将作业从外存调入内存；

2. 中级调度（内存调度）：内存紧张时，进程挂起至外存；内存充足时重新调入内存参与调度；

3. 低级调度（进程调度）：选择就绪进程分配 CPU，发生频率最高。

2.3.2 调度时机约束

        中断处理过程、原语执行期间、进程访问内核临界区时，不能立即执行调度与进程切换。

2.3.3 调度方式

• 抢占式调度：可强行剥夺正在运行进程的 CPU；

• 非抢占式调度：进程主动放弃 CPU，才会发生切换。

2.3.4 调度实现组件与流程

        调度三大步骤：①保护旧进程现场；②调度算法选出目标进程；③恢复新进程现场。 配套组件：

• 排队器：维护各类进程队列，进程转为就绪态时加入就绪队列；

• 分配器：将 CPU 分配给选中进程；

• 上下文切换器：负责现场保存与恢复；

• 闲逛进程：就绪队列无普通进程时运行；运行在内核态，优先级最低。

2.3.5 CPU 调度算法

1. 先来先服务 FCFS：不利于 I/O 密集型进程、短作业；

2. 短作业优先 SJF：平均等待时间、平均周转时间最优；存在饥饿问题；

3. 优先级调度算法

   1. 静态优先级：系统进程＞用户进程；

   2. I/O 密集型＞计算密集型；

   3. 资源需求少＞资源需求多；

   4. 动态优先级：运行过程动态调整优先级；高响应比优先 HRRN（非抢占式）。

4. 多级队列调度：就绪队列划分为多个独立队列，队列间优先级固定；

5. 多级反馈队列调度 就绪队列划分为多级，队列优先级逐级降低；优先级越高，分配时间片越小。 规则：新进程加入最高优先级队列尾部；进程用完时间片未完成，降级至下一级队列。

2.4 进程同步与互斥

进程同步目标：消除进程异步性带来的结果不确定性。

2.4.1 基础概念

1. 临界资源：同一时刻仅允许一个进程访问的资源；例：打印机、共享变量、消息队列。

2. 临界区：访问临界资源的代码片段。 临界区四段式划分：进入区、临界区、退出区、剩余区。

3. 同步互斥四大准则 空闲让进、忙则等待、有限等待、让权等待。

让权等待：进程无法进入临界区时主动释放 CPU；持续循环等待 CPU 称为自旋（忙等）。

1. 关系区分

• 同步：进程协作关系，约束进程执行先后次序；

• 互斥：进程竞争关系，排他访问临界资源；互斥信号量初值一般设置为 1。

2.4.2 临界区互斥实现方案

方案 1：软件实现（全部不满足让权等待，存在忙等）

  单标志法：共享 turn 变量，仅支持两个进程交替访问临界区；

int turn = 0;       // 共享标志变量，限定交替执行
// P0进程
while(turn != 0);   
临界区代码;
turn = 1;           
剩余区代码;

// P1进程
while(turn != 1);   
临界区代码;
turn = 0;           
剩余区代码;

       缺陷：强制进程交替执行，资源利用率低，不满足空闲让进。

  双标志先检查：可能两个进程同时进入临界区；

bool flag[2] = {false, false};  // 标记进程是否想要进入临界区

// P0进程
while(flag[1]);      
flag[0] = true;      
临界区代码;
flag[0] = false;     
剩余区代码;

// P1进程
while(flag[0]);      
flag[1] = true;      
临界区代码;
flag[1] = false;     
剩余区代码;

        缺陷：先检查后上锁，两进程可同时通过while判断，同时进入临界区，无法保证互斥。

双标志后检查：可能出现所有进程均无法进入临界区；

bool flag[2] = {false, false};

// P0进程
flag[0] = true;      
while(flag[1]);      
临界区代码;
flag[0] = false;     
剩余区代码;

// P1进程
flag[1] = true;      
while(flag[0]);      
临界区代码;
flag[1] = false;     
剩余区代码;

        缺陷：先上锁后检查，两进程同时置flag为true，会互相阻塞，都无法进入临界区，引发饥饿。

Peterson 算法：融合单标志、双标志思想；依旧存在忙等。

bool flag[2] = {false, false};
int turn;

// P0进程
flag[0] = true;
turn = 1;                // 谦让权交给对方
while(flag[1] && turn == 1);
临界区代码;
flag[0] = false;
剩余区代码;

// P1进程
flag[1] = true;
turn = 0;                // 谦让权交给对方
while(flag[0] && turn == 0);
临界区代码;
flag[1] = false;
剩余区代码;

        原理：结合标志位（意愿）+ 轮转权，完美解决双标志法漏洞，可实现严格互斥。

        缺陷：即使无法进入临界区，也不放弃CPU，while循环空转，持续忙等，不满足让权等待。

方案 2：硬件实现

1. 关中断 原理：单核系统关闭中断，阻止进程切换，实现临界区互斥。 缺陷： ①不能开放给用户进程，滥用风险极高； ②阻碍程序交替执行，CPU 与 I/O 无法并行； ③多处理器系统失效；仅可在内核态使用。

2. 硬件原子指令：TSL (Test-And-Set)、Swap (Exchange) 依靠硬件保证指令原子性，解决锁变量竞争问题。 ⚠共同缺陷：忙等；无法保证等待时限，可能引发饥饿。

2.4.3 信号量机制

信号量：绑定一类资源的数据结构；信号量数值代表剩余资源数量。

• S＞0：剩余可用资源数量；

• S = 0：资源全部分配完毕；

• S＜0：|S | 为阻塞等待该资源的进程数量。

1. 整型信号量：仅保存整数 S；P 操作资源不足时发生忙等，违反让权等待。

2. 记录型信号量：整型数值 + 阻塞队列；S＜0 时进程阻塞进入队列，满足让权等待。

   1. P 原语（wait）：申请资源 S--；资源不足则阻塞进程；

   2. V 原语（signal）：释放资源 S++；唤醒阻塞队列中的进程。

PV 操作为原子操作，通常成对使用。

PV 操作为原子操作，通常成对使用。

2.4.4 管程机制

        管程是操作系统提供的高级同步互斥工具，是一组数据结构和能访问该数据结构的一组过程（函数）的集合，用于管理临界资源，实现进程同步与互斥，解决信号量机制手动写PV操作易错、代码混乱的问题。

1. 管程核心特性

• 封装性：将临界资源数据、访问资源的操作过程统一封装在管程内部，外部进程无法直接修改管程内数据，只能调用管程提供的过程访问资源。

• 互斥性：管程自带互斥机制，同一时刻仅允许一个进程进入管程内部执行过程，无需程序员手动编写互斥代码，由操作系统自动实现。

• 同步性：管程内部设置条件变量及等待/唤醒原语，解决进程同步问题，协调进程执行顺序。

2. 管程核心组成部分

1. 局部数据结构：对应需要保护的临界资源数据；

2. 若干过程（函数）：对外提供访问、修改临界资源的接口，是进程的唯一访问途径；

3. 初始化代码：初始化管程内的临界资源数据；

4. 条件变量：用于进程同步，解决进程等待资源、等待事件的场景。区别于信号量，仅表示阻塞原因，不表示资源数量。

3. 条件变量与核心原语

        条件变量依附于管程存在，每个条件变量对应一类等待事件，配套两个原子原语：

• wait() 等待原语：进程进入管程后，若不满足执行条件，调用该原语。进程主动释放管程互斥权限，阻塞进入对应条件变量的等待队列，让出CPU（满足让权等待）。

• signal() 唤醒原语：当前进程执行完毕、满足等待进程的触发条件后，调用该原语，唤醒对应条件变量等待队列中的一个阻塞进程。

2.5 死锁

2.5.1 死锁定义

        多个进程竞争资源、相互通信引发永久阻塞；若无外力干预，进程无法继续推进。 死锁两大成因：①竞争有限资源；②进程资源请求与释放推进顺序不当。

2.5.2 死锁四大必要条件

        四个条件同时满足才有可能发生死锁；破坏任意一条，一定不会产生死锁。

1. 互斥条件：资源独占使用；

2. 请求与保持：进程持有资源，同时申请新资源；阻塞时不释放已有资源；

3. 不可抢占：资源仅能由持有者主动释放，不允许强行抢夺；

4. 循环等待：形成资源等待环路，链上每个进程等待相邻进程占用的资源。

2.5.3 死锁四种处理策略

1. 死锁预防（静态策略） 预先破坏四大必要条件之一。

   1. 破坏互斥条件：创建一个代理进程，其余进程通过代理访问临界资源，从而避免多个进程同时访问临界资源。如Spooling 技术，将独占设备虚拟为逻辑共享设备；

   2. 破坏请求和保持：一次性申请全部资源；申请新资源前释放已有资源；

   3. 破坏不可抢占：资源申请失败主动释放所持资源；

   4. 破坏循环等待：所有资源统一编号，进程严格按编号递增顺序申请资源。

2. 死锁避免（动态策略） 核心思想：系统始终维持安全状态。

   1. 安全状态：存在资源分配序列，所有进程均可顺利执行完成，一定无死锁；

   2. 不安全状态：不存在安全序列；有可能死锁；发生死锁时系统必然处于不安全状态。 典型算法：银行家算法 执行流程：进程发起资源申请 → 试探分配资源 → 安全性算法校验；不安全则撤销分配，进程等待。

3. 死锁检测 通过化简资源分配图判断；死锁定理：系统发生死锁 ⇔ 资源分配图无法完全化简。

4. 死锁解除 可选方案：系统重启；终止全部死锁进程；逐个终止死锁进程直至消除死锁；抢占资源重新分配。