2.1 进程与线程2.1.1 进程概述、进程与程序进程程序的一次执行过程是动态实体程序是存放在外存的静态指令集合。进程实体进程映像组成程序段存放可执行代码数据段存放全局变量、运行数据PCB进程控制块操作系统管理进程的核心数据结构 PCB 是进程存在的唯一标志操作系统依靠 PCB 感知进程。进程特性 —— 异步性异步性由并发性引发多个进程独立向前推进执行速度不可预测。2.1.2 进程状态及状态转换五大状态创建态、就绪态、运行态、阻塞态、终止态创建态操作系统初始化 PCB、分配资源资源紧张时进程长期停留在创建态。就绪态进程已获得除 CPU 以外的所有资源等待调度。运行态进程正在 CPU 上执行指令。阻塞态进程主动放弃 CPU等待外部事件或等待资源。阻塞态无法直接切换至运行态必须先转为就绪态。终止态进程正常结束或被强制撤销操作系统回收进程占用资源。僵尸进程与孤儿进程僵尸进程子进程先终止父进程未调用wait()/waitpid()回收PCB 保留持续占用 PID。 危害系统 PID 耗尽无法创建新进程。孤儿进程父进程先终止子进程由 init/systemd 进程自动收养对系统无危害。状态转换触发条件就绪态 → 运行态调度程序选中进程分配 CPU运行态 → 就绪态时间片耗尽高优先级进程抢占 CPU抢占调度运行态 → 阻塞态进程主动调用系统调用等待事件 / 资源阻塞态 → 就绪态等待事件完成进程被唤醒2.1.3 进程控制块 PCBPCB 五大功能作为进程独立运行的唯一标识无 PCB 则操作系统无法感知进程支撑进程间断运行上下文切换时保存旧进程现场、恢复新进程现场记录进程管理信息通过指针关联程序段、数据段、打开文件与各类资源保存调度所需信息为处理机调度提供依据支撑进程同步与通信存储消息队列、信号量相关指针。PCB 仅存放通信、同步数据结构指针不保存结构体本身。PCB 四类信息标识符信息进程 PID、父进程 PID、用户标识符区分不同进程处理机现场信息通用寄存器、程序计数器 PC、程序状态字 PSW、栈指针上下文切换使用进程调度信息进程状态、优先级、等待事件、调度计时参数进程控制信息程序段 / 数据段起始地址、文件描述符、资源清单、同步通信指针。2.1.4 进程控制进程控制依靠原语实现。原语定义由若干指令构成的原子操作执行过程不可中断指令要么全部执行要么全部不执行。进程创建场景用户登录高级调度作业由外存调入内存系统响应用户请求现有进程创建子进程提升并发度。创建原语执行流程①分配 PID②分配空白 PCB③分配内存、I/O 设备等软硬件资源④初始化 PCB资源充足进程加入就绪队列资源不足维持创建态父进程阻塞。终止原语执行流程根据 PID 查找 PCB → 修改进程状态为终止态 → 递归终止所有子进程 → 回收全部资源 → 将 PCB 移出系统队列。阻塞原语 唤醒原语成对出现阻塞主动行为进程自身调用阻塞原语让出 CPU进入阻塞队列唤醒被动行为由其他进程调用唤醒原语。 阻塞流程查找 PCB → 将运行态修改为阻塞态移入阻塞队列 → 执行上下文切换调度新进程运行。2.1.5 上下文切换与模式切换上下文切换保存并恢复 CPU 现场实现 CPU 在进程间切换上下文切换只能发生在内核态。 执行流程 ①保存当前进程寄存器上下文至 PCB②修改进程状态移入对应队列 ③调度程序选择新进程④读取新进程 PCB修改状态为运行态 ⑤更新内存管理相关数据⑥恢复新进程上下文从断点继续执行。模式切换用户态 ↔ 内核态由中断、陷阱、系统调用触发。模式切换不更换正在运行的进程仅切换 CPU 特权等级仍需要保存少量现场上下文切换更换运行进程系统开销更大。2.1.6 线程轻量级进程引入线程目标提高系统并发度充分发挥多处理器性能。进程与线程核心差异进程资源分配的最小单位进程地址空间相互隔离无法直接共享数据线程调度执行的最小单位同一进程内多个线程共享地址空间与全局数据无需内核参与即可交换数据开销线程创建、切换、撤销的开销远小于进程。TCB线程控制块管理线程保存 TID、寄存器信息、线程状态、优先级、栈指针。 用户栈线程用户态运行使用核心栈线程内核态运行使用。线程两种实现方式用户级线程 ULT操作系统内核无法感知线程调度单位依旧是进程。优点线程切换在用户态完成无需陷入内核开销低缺点进程内任意线程阻塞整个进程阻塞。内核级线程 KLT内核可感知线程线程创建、阻塞、切换、撤销均在内核态完成。优点单线程阻塞不影响同进程其他线程支持多核并行缺点线程切换伴随模式切换系统开销较高。三类线程映射模型多对一模型多个用户级线程映射至 1 个内核线程 优点切换开销小缺点一线程阻塞全部阻塞无法利用多核。一对一模型1 个用户线程映射 1 个内核线程 优点支持多核并行线程阻塞互不干扰缺点内核线程数量受限切换开销大。多对多模型M 个用户线程映射 N 个内核线程MN折中方案融合前两者优势。进程与线程独立性总结进程拥有独立地址空间隔离性强避免进程间相互破坏同一进程内线程共享全部资源牺牲隔离性换取并发效率。2.2 进程通信 IPCIPC进程间通信进程运行过程中相互协调、交换信息。通信机制信号量机制、共享存储、消息传递、管道通信、信号机制。共享存储机制共享数据结构共享全局变量位于用户空间程序员必须自行处理同步互斥共享存储区操作系统在内核开辟一块无格式共享内存多个进程可在用户空间直接读写。消息传递机制通过send、receive原语收发消息依赖操作系统内核。直接通信消息直接挂载到目标进程消息队列间接通信信箱通信设置信箱作为中间实体收发双方读写信箱。管道Pipe本质内核缓冲区实现的共享文件以字符流形式传输数据。 特性半双工通信双向通信需要建立两条管道同步约束管道为空不能读管道写满不能写读写操作互斥数据一经读出立即丢弃缓冲区大小固定通信双方必须同时存在否则进程阻塞。信号机制软中断提供单向事件通知信号可由用户、操作系统内核、其他进程产生。 内核处理信号三种方式①直接忽略②执行系统默认处理函数③执行自定义信号处理函数。2.3 处理机调度调度本质资源分配就绪队列存在多个进程时依靠调度算法选择进程占用 CPU。2.3.1 三级调度高级调度作业调度将作业从外存调入内存中级调度内存调度内存紧张时进程挂起至外存内存充足时重新调入内存参与调度低级调度进程调度选择就绪进程分配 CPU发生频率最高。2.3.2 调度时机约束中断处理过程、原语执行期间、进程访问内核临界区时不能立即执行调度与进程切换。2.3.3 调度方式抢占式调度可强行剥夺正在运行进程的 CPU非抢占式调度进程主动放弃 CPU才会发生切换。2.3.4 调度实现组件与流程调度三大步骤①保护旧进程现场②调度算法选出目标进程③恢复新进程现场。 配套组件排队器维护各类进程队列进程转为就绪态时加入就绪队列分配器将 CPU 分配给选中进程上下文切换器负责现场保存与恢复闲逛进程就绪队列无普通进程时运行运行在内核态优先级最低。2.3.5 CPU 调度算法先来先服务 FCFS不利于 I/O 密集型进程、短作业短作业优先 SJF平均等待时间、平均周转时间最优存在饥饿问题优先级调度算法静态优先级系统进程用户进程I/O 密集型计算密集型资源需求少资源需求多动态优先级运行过程动态调整优先级高响应比优先 HRRN非抢占式。多级队列调度就绪队列划分为多个独立队列队列间优先级固定多级反馈队列调度就绪队列划分为多级队列优先级逐级降低优先级越高分配时间片越小。 规则新进程加入最高优先级队列尾部进程用完时间片未完成降级至下一级队列。2.4 进程同步与互斥进程同步目标消除进程异步性带来的结果不确定性。2.4.1 基础概念临界资源同一时刻仅允许一个进程访问的资源例打印机、共享变量、消息队列。临界区访问临界资源的代码片段。 临界区四段式划分进入区、临界区、退出区、剩余区。同步互斥四大准则空闲让进、忙则等待、有限等待、让权等待。让权等待进程无法进入临界区时主动释放 CPU持续循环等待 CPU 称为自旋忙等。关系区分同步进程协作关系约束进程执行先后次序互斥进程竞争关系排他访问临界资源互斥信号量初值一般设置为 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; 剩余区代码;原理结合标志位意愿 轮转权完美解决双标志法漏洞可实现严格互斥。缺陷即使无法进入临界区也不放弃CPUwhile循环空转持续忙等不满足让权等待。方案 2硬件实现关中断原理单核系统关闭中断阻止进程切换实现临界区互斥。 缺陷 ①不能开放给用户进程滥用风险极高 ②阻碍程序交替执行CPU 与 I/O 无法并行 ③多处理器系统失效仅可在内核态使用。硬件原子指令TSL (Test-And-Set)、Swap (Exchange)依靠硬件保证指令原子性解决锁变量竞争问题。 ⚠共同缺陷忙等无法保证等待时限可能引发饥饿。2.4.3 信号量机制信号量绑定一类资源的数据结构信号量数值代表剩余资源数量。S0剩余可用资源数量S 0资源全部分配完毕S0|S | 为阻塞等待该资源的进程数量。整型信号量仅保存整数 SP 操作资源不足时发生忙等违反让权等待。记录型信号量整型数值 阻塞队列S0 时进程阻塞进入队列满足让权等待。P 原语wait申请资源 S--资源不足则阻塞进程V 原语signal释放资源 S唤醒阻塞队列中的进程。PV 操作为原子操作通常成对使用。PV 操作为原子操作通常成对使用。2.4.4 管程机制管程是操作系统提供的高级同步互斥工具是一组数据结构和能访问该数据结构的一组过程函数的集合用于管理临界资源实现进程同步与互斥解决信号量机制手动写PV操作易错、代码混乱的问题。1. 管程核心特性封装性将临界资源数据、访问资源的操作过程统一封装在管程内部外部进程无法直接修改管程内数据只能调用管程提供的过程访问资源。互斥性管程自带互斥机制同一时刻仅允许一个进程进入管程内部执行过程无需程序员手动编写互斥代码由操作系统自动实现。同步性管程内部设置条件变量及等待/唤醒原语解决进程同步问题协调进程执行顺序。2. 管程核心组成部分局部数据结构对应需要保护的临界资源数据若干过程函数对外提供访问、修改临界资源的接口是进程的唯一访问途径初始化代码初始化管程内的临界资源数据条件变量用于进程同步解决进程等待资源、等待事件的场景。区别于信号量仅表示阻塞原因不表示资源数量。3. 条件变量与核心原语条件变量依附于管程存在每个条件变量对应一类等待事件配套两个原子原语wait() 等待原语进程进入管程后若不满足执行条件调用该原语。进程主动释放管程互斥权限阻塞进入对应条件变量的等待队列让出CPU满足让权等待。signal() 唤醒原语当前进程执行完毕、满足等待进程的触发条件后调用该原语唤醒对应条件变量等待队列中的一个阻塞进程。2.5 死锁2.5.1 死锁定义多个进程竞争资源、相互通信引发永久阻塞若无外力干预进程无法继续推进。 死锁两大成因①竞争有限资源②进程资源请求与释放推进顺序不当。2.5.2 死锁四大必要条件四个条件同时满足才有可能发生死锁破坏任意一条一定不会产生死锁。互斥条件资源独占使用请求与保持进程持有资源同时申请新资源阻塞时不释放已有资源不可抢占资源仅能由持有者主动释放不允许强行抢夺循环等待形成资源等待环路链上每个进程等待相邻进程占用的资源。2.5.3 死锁四种处理策略死锁预防静态策略预先破坏四大必要条件之一。破坏互斥条件创建一个代理进程其余进程通过代理访问临界资源从而避免多个进程同时访问临界资源。如Spooling 技术将独占设备虚拟为逻辑共享设备破坏请求和保持一次性申请全部资源申请新资源前释放已有资源破坏不可抢占资源申请失败主动释放所持资源破坏循环等待所有资源统一编号进程严格按编号递增顺序申请资源。死锁避免动态策略核心思想系统始终维持安全状态。安全状态存在资源分配序列所有进程均可顺利执行完成一定无死锁不安全状态不存在安全序列有可能死锁发生死锁时系统必然处于不安全状态。 典型算法银行家算法执行流程进程发起资源申请 → 试探分配资源 → 安全性算法校验不安全则撤销分配进程等待。死锁检测通过化简资源分配图判断死锁定理系统发生死锁 ⇔ 资源分配图无法完全化简。死锁解除可选方案系统重启终止全部死锁进程逐个终止死锁进程直至消除死锁抢占资源重新分配。