【知识总结】 第二章-进程管理

进程

进程基本概念

• 进程的定义
  • 具有独立功能的程序在一个数据集合上的一次执行过程（活动）
  • 资源分配和调度的基本单位
• 进程控制块PCB
  • 描述进程基本情况和运行状态的数据结构
  • 系统通过PCB感知进程、控制和管理进程
  • 创建进程时创建PCB，撤销进程时撤销PCB，PCB是进程存在的唯一标志
  • PCB包括进程的描述信息、控制管理信息、资源分配清单、处理机有关信息
  • 状态相同的各进程的PCB可以用索引表统一管理，每个表项指向一个PCB
• 进程的特征
  • 动态性：有动态的生命周期，比如：创建、活动、暂停、终止
  • 并发性：多个进程实体在同一段时间内，在内存中运行，并发是引入进程的目的
  • 独立性：进程实体能独立运行、获得资源、调度
  • 异步性：各进程按不可预测的速度推进
  • 结构性：每个进程一个PCB，进程实体包括程序段、数据段、PCB

进程状态和转换

状态

• 运行态：进程正在处理机上运行，单处理机同时刻最多只能支持一个进程运行
• 就绪态：进程获得了除了处理机外的一切资源，等待处理机资源
• 阻塞态：进程等待某资源（不是处理机）或输入输出完成
• 创建态：进程被创建时的状态，创建过程：申请空白PCB、填写控制信息和管理信息、系统给进程分配资源、进程转入就绪态
• 结束态：进程被结束时的状态，结束过程：把进程设置为结束态、资源释放和回收

转换

• 新建态->就绪态：创建进程的过程
• 就绪态->运行态：就绪的进程获得CPU资源后开始运行
• 运行态->就绪态：进程时间片用完后只能让出CPU，进入就绪态，进程被动的中断
• 运行态->阻塞态：运行的进程需要申请等待某非CPU资源，或等某事件发生，进程主动的中断（系统调用）
• 阻塞态->就绪态：进程等待的时间到来，中断处理程序把进程状态改为就绪

进程的组织

• 进程控制块：详见前面进程基本概念
• 程序段：由进程调度程序调度到CPU执行的代码，可被多个进程共享
• 数据段：进程对应程序的原始数据、中间数据或最终结果

进程的控制

• 原语：进程控制的程序段，执行期间不可中断、不可分割的执行单位
• 进程创建
  • 子进程由父进程创建，拥有父进程的资源
  • 父进程撤销前先撤销所有子进程；子进程撤销后归还资源给父进程
  • 创建原语
    • 分配进程标识号
    • 申请空白PCB，没PCB则创建失败
    • 分配资源，没资源则创建完进入阻塞态
    • 初始化PCB
    • 插入就绪队列
• 进程阻塞
  • 进程因为等待某非CPU资源，主动的从运行态转换到阻塞态
  • 阻塞原语（block）
    • 找到正在运行的待阻塞进程的PCB
    • 保护现场，状态设置为阻塞态，停止运行
    • 把PCB插入阻塞等待队列
    • CPU资源调度给其他就绪进程
• 进程唤醒
  • 阻塞的进程等待的事件发生，该进程重新进入就绪态
  • 唤醒原语（wakeup）
    • 找到PCB
    • PCB移出等待队列，状态设置为就绪态
    • PCB插入就绪队列
• 进程切换
  • 根据处理机的调度决策，用就绪队列中的进程替换正在运行的进程的操作
  • 切换过程
    • 保存处理机上下文到该进程的内核堆栈中，包括PC和其他寄存器
    • 更新当前运行的进程PCB
    • 把进程PCB移入就绪或阻塞队列
    • 选择另一个进程执行，更新其PCB
    • 更新内存管理的数据结构
    • 从新进程的内核堆栈中恢复处理机上下文
• 进程终止
  • 终止的情况
    • 正常终止：进程任务完成
    • 异常终止：进程过程异常
    • 外界干预终止：用户请求、父进程请求、父进程终止
  • 撤销原语
    • 检索PCB读进程状态
    • 进程在执行则停止执行并释放CPU
    • 有子进程则终止子进程
    • 释放所有资源
    • 从队列中移除PCB

进程间通信

• 共享内存
  • 含义
    • 进程间存在共享的存储空间
    • 进程对该空间读写来交换信息
    • 操作系统提供同步互斥工具
  • 分类
    • 低级共享：对数据结构共享
    • 高级共享：对存储区共享
• 消息传递
  • 含义
    • 进程通过操作系统提供的发送消息、接收消息原语进行数据交换
    • 消息是格式化的
  • 分类
    • 直接通信：发送进程把信息放到接收进程的消息缓冲区
    • 间接通信（信箱通信）：发送进程把信息放到中间实体（信箱）
• 管道通信
  • 管道是连接读进程和写进程的共享文件
  • 管道通信是共享内存方式的改进
    • 管道本质是固定大小的缓冲区
    • 同步、互斥功能由管道本身提供
    • 半双工通信，同一时刻只能单向传输
  • 当管道为空，读进程阻塞，等待写进程把管道写满
  • 当管道写满，写进程阻塞，等待读进程把管理读空

线程

线程基本概念

• 线程的定义
  • 进程中的实体，同进程内可以有多个线程共享进程资源
  • 引入线程后，进程是资源分配的基本单位，线程是处理机调度分配的基本单位
• 线程和进程的比较
  • 调度
    • 同进程内的线程切换的开销较小
    • 不同进程的线程切换引起进程切换
    • 引入线程后，线程是调度基本单位
  • 资源拥有
    • 进程拥有资源，是资源分配的单位
    • 线程不拥有资源，同进程的线程共享进程的资源，这些线程切换开销小
  • 并发性
    • 进程和线程都可以并发，操作系统并发现提高
  • 系统开销
    • 进程创建、切换、撤销开销大
    • 同进程的线程切换开销小（因为不拥有资源）
    • 同进程的线程同步通信容易（因为共享进程的地址空间）
  • 地址空间
    • 不同进程的地址空间独立
    • 同进程的线程的地址空间共享
  • 通信
    • 进程间存在通信，通过系统调用，由操作系统考虑同步、互斥
    • 同进程的各线程不存在通信，直接读写进程数据段即可，但是也需要考虑同步和互斥

线程状态和转换

状态

• 运行态：在处理机上运行
• 就绪态：已获得除CPU外所有资源，等待CPU
• 阻塞态：执行时因为某事件受阻，暂停

转换

同进程转换

线程实现

• 内核级线程KLT
  • 内核支持的线程
  • 内核进行线程管理，线程表在内核态
  • 一对一模型
    • 一个用户级线程通过编程接口对应一个内核级线程
    • 优点：一个线程阻塞后，同进程的其他线程可以运行；多处理器系统中同进程的多个线程可以并行执行
    • 缺点：线程管理在内核空间，开销大
• 用户级线程ULT
  • 线程库支持的线程
  • 用户进行线程管理，内核意识不到线程的概念，线程表在用户态
  • 多对一模型
    • 多个用户级线程通过由用户支持的线程库对应一个内核级进程
    • 优点：线程管理在用户空间，开销小；调度算法用户自行实现，进程专用
    • 缺点：一个线程阻塞后，整个进程都被阻塞；多处理器系统只分配一个处理器给进程，进程内线程无法并行
• 混合多线程
  • 内核与线程库组合支持的线程
  • 用户完成线程创建、同步、调度，线程的切换、撤销需要内核参与
  • 多对多模型
    • m个用户级线程通过由内核支持的线程库对应n个内核级线程（n不大于m）
    • 优缺点是一对一和多对一模型的折中

线程组织和控制

• 线程控制块TCB包括
  • 线程标识符
  • 程序计数器、状态寄存器、通用寄存器
  • 线程状态
  • 优先级
  • 线程切换时保存现场的专用存储区
  • 堆栈指针
• 线程创建
  • 由初始化线程调用线程创建函数创建新线程
  • 线程创建函数需要提供参数，比如入口地址、堆栈大小、线程优先级
  • 线程创建函数返回线程标识符
• 线程终止
  • 由终止线程调用线程终止函数**终止线程
  • 线程终止后通常不释放资源
  • 同进程其他线程执行分离函数，被终止线程与资源分离，其他线程才可用释放后资源

处理机调度

调度基本概念

• 调度：资源请求者数多于资源数时，资源请求者竞争资源的排队过程
• 进程调度：进程数多于处理器数时，进程竞争处理器的排队过程
• 调度层次
  • 作业调度
    • 高级调度
    • 后备队列：连向就绪队列（作业调度）；资源请求者是外存作业；资源有内存、IO设备等
  • 内存调度
    • 中级调度
    • 挂起操作：进程从内存移到外存
    • 激活操作：进程从外存移到主存
    • 就绪挂起队列：连向就绪队列（内存调度、激活操作）；资源请求者是被挂起的就绪进程；资源是内存（在内存紧张时，内存调度把不能运行的进程移到外存，提高内存利用率）
    • 阻塞挂起队列：连向就绪挂起队列；资源请求者是被挂起的阻塞进程；资源是非处理器资源或等待某事件的发生
  • 进程调度
    • 低级调度
    • 就绪队列：连向处理器（进程调度）和就绪挂起队列（挂起操作）；资源请求者是就绪进程；资源是处理器
    • 阻塞队列：连向就绪队列和阻塞挂起队列（挂起操作）；资源请求者是阻塞进程；资源是非处理器资源或等待某事件的发生
• 调度从高级到低级频率递增

调度的目标

• CPU利用率：CPU使用时间比总时间
• 系统吞吐量：单位时间完成作业数量
• 周转时间：作业从提交到完成的时间
• 平均周转时间：多个作业周转时间的均值
• 带权周转时间：作业周转时间比作业实际运行时间
• 平均带权周转时间：多个作业带权周转时间的均值
• 等待时间：作业等待处理机的时间
• 响应时间：作业提交到首次响应的时间

调度的实现

调度器

• 又叫调度程序（scheduler），是操作系统中用于调度CPU的组件
• 包括
  • 排队器：把就绪进程插入就绪队列
  • 分派器：从就绪队列中取出新进程，分配CPU
  • 上下文切换器
    • 保存当前进程上下文，装入分派器进程的上下文，分派程序执行
    • 移出分派器进程的上下文，装入新进程的上下文，新进程执行

调度时机

• 不可调度的情况
  • 中断处理时
  • 进程访问内核的临界区时，为了尽快释放临界区资源，需要加锁阻止并行
  • 进行原子操作时，需要屏蔽中断，显然不可调度
• 应进行调度的情况
  • 满足调度条件，且当前进程无法继续运行
  • 调度采用剥夺方式，且出现更高优先级的进程
  • 中断或自陷处理结束后，中断返回前，发现置上了请求调度标志

调度方式

• 调度方式：根据高优先级进程进入就绪队列后，对当前进程的处理
• 非抢占式（非剥夺调度方式）：当前进程继续运行直至进入阻塞态，高优先级进程才运行
• 抢占式（剥夺调度方式）：当前进程停止运行进入就绪态，高优先级进程运行

闲逛进程

• 定义：当就绪队列为空时，使用CPU的进程
• 特点：
  • 无阻塞态：不需要除了CPU的其他资源
  • 优先级最低：就绪队列不空立刻让出CPU

内核级线程和用户级线程调度

• 详见前面线程实现小节的笔记

典型调度算法

先来先服务调度

• 简称：FCFS
• 适用范围：作业调度、进程调度
• 算法思想：先进入队列的先分配资源
• 调度方式：非抢占式
• 特点
  • 算法简单
  • 效率低
  • 有利于长作业，不利于短作业
  • 有利于CPU繁忙型作业，不利于IO繁忙型作业

短作业优先调度

• 简称：SJF
• 适用范围：一般默认是作业调度；进程调度的版本叫短进程优先调度SPF
• 算法思想：队列中预估运行时间最短的先分配资源
• 调度方式：一般默认是非抢占式；抢占式的版本叫做最短剩余时间优先调度SRTF
• 特点
  • 有利于短作业，不利于长作业，有饥饿现象
  • 未考虑任务的紧迫性
  • 运行时间的预估不一定准确
  • 平均等待时间和平均周转时间最少

时间片轮转调度

• 简称：RR
• 适用范围：进程调度
• 算法思想：按先来先服务的顺序，每个进程只能运行一个时间片，然后释放处理器给下一个进程
• 调度方式：抢占式
• 时间片大小设置应适当
  • 时间片很大时，算法退化为先来先服务算法
  • 时间片很小时，频繁切换进程的开销很大

优先级调度

• 又叫优先权调度
• 适用范围：作业调度、进程调度
• 算法思想：选优先级最高的进程执行
• 调度方式：抢占式、非抢占式
• 按优先级是否可变分类
  • 静态优先级：不可变
  • 动态优先级：可变
• 优先级设置原则
  • 系统进程>用户进程
  • 交互型进程>非交互型进程
  • IO型进程>计算型进程

高响应比调度

• 简称：HRRF
• 适用范围：主要用于作业调度
• 算法思想：选择响应比（周转时间比执行时间）最高的作业执行
• 调度方式：非抢占式
• 特点：
  • 等待时间相同时，执行时间越短，响应比越高
  • 执行时间相同时，等待时间越长，响应比越高
  • FCFS和SJF的折中，兼顾了等待时间和执行时间，克服了饥饿现象

多级队列调度

• 简称：MLQ
• 适用范围：进程调度
• 算法思想
  • 多个就绪队列，队列间设置优先级
  • 每个队列内有各自的调度算法，
  • 进程执行完后，回到原队列
• 调度方式：根据具体的调度算法考虑

多级反馈队列调度

• 简称：MLFQ
• 适用范围：进程调度
• 算法思想
  • 多个就绪队列，从第1级到第n级的优先级递增，优先级较高队列为空才考虑调度优先级较低的队列
  • 每个队列设置一个时间片，优先级高的队列时间片短，是相邻的低优先级队列的时间片的一半
  • 最后一级队列，按RR方式，进程时间片用完后，回到最后一级队列（通常因为时间片较大，相当于FCFS）
  • 其他级队列，按FCFS的顺序，进程时间片用完后，进入下一级队列
• 调度方式：抢占式（注意当第i级队列处理时，高优先级的队列出现进程，会立刻抢占CPU）
• 特点
  • 短交互作业（终端型作业）：一般在第1级队列可完成
  • 短批处理作业：一般可在前几个队列完成，周转时间短
  • 长批处理作业：在前几个队列部分处理，响应时间短，但是可能有饥饿现象

甘特图

又叫横道图，绘制方法如下 + 横坐标绘制合适的时间间隔 + 纵坐标是程序的名称 + 在各时间位置，画平行于纵坐标的虚线 + 用不同的线表示各资源（CPU、打印机等），在各个程序位置，画平行于横坐标的线 + 各资源对应线的上方标注资源的名称

上下文和切换机制

• 详见前面进程的控制小节中，进程切换部分

同步与互斥

基本概念

• 临界资源：一次只允许一个进程访问的资源，如打印机
• 临界资源访问步骤
  • 进入区
    • 检查进程是否可以进入临界区
    • 可进入的进程设置正访问临界区标识，阻止其他进程进入临界区
  • 临界区（临界段）：进程使用临界资源的代码
  • 退出区：清除正访问临界区标识
  • 剩余区：代码剩余部分
• 同步：多个进程为了同一个任务，协调工作次序、等待传递信息的直接制约关系
• 互斥：当一个进程进入临界区，其他进程需要等其退出临界区才能访问临界资源的间接制约关系
• 同步机制准则
  • 空闲让进（必须实现）：临界区空闲允许进程进入
  • 忙则等待（必须实现）：临界区占用则其他进程等待
  • 有限等待（必须实现）：进程等有限时间后可以进临界区
  • 让权等待（建议实现）：进程不能进入临界区时，释放处理器资源

临界区访问方法

软件方法

以两个进程访问临界区为例

• 单标志法
  • 算法思想
    • 一个标志表示哪个进程可用临界区
    • 进程用完后把标志取反
  • 缺点
    • 一定只能交替进入临界区
    • 违背“空闲让进”
• 双标志法（先检查）
  • 算法思想
    • 两个标志分别表示两个进程是否可以使用临界区
    • 先检查另一方的标志是否为0，为0则设置自己标志为1
    • 使用结束后把自己的标志设置为0
  • 缺点
    • 双方可能先检查，都认为对方为0，然后都设置自己为1
    • 违背“忙则等待”
• 双标志法（后检查）
  • 算法思想
    • 两个标志分别表示两个进程是否想使用临界区
    • 先设置自己的标志为1，后检查另一方的标志是否为0，为0则使用临界区
    • 使用结束后把自己的标志设置为0
  • 缺点
    • 双方可能先设置自己的标志为1，都认为对方不为0，都无法使用临界区
    • 违背“有限等待”
• 彼得森算法
  • 算法思想
    • 两个标志分别表示两个进程是否想使用临界区
    • 再设置一个标志turn表示双方的谦让态度
    • 先设置自己的标志为1（提出想法），再设置turn为另一方（表达谦让）
    • 如果对方标志为1且turn为另一方则等待（即对方有想法就谦让给对方）
    • 最后一次的被谦让方可以访问临界区
    • 使用结束后设置自己的标志为0
  • 缺点
    • 进程等待时未让出CPU资源
    • 违背“让权等待”

硬件方法

硬件方法又叫低级方法、元方法，包括

• 中断屏蔽法
  • 步骤
    • 关中断
    • 访问临界区
    • 开中断
  • 特点：简单但只适用于内核进程、单处理器（中断是针对一个处理器而言）
• 原子硬件指令TestAndSet
  • TS指令功能
    • 设置锁变量为1
    • 返回原先的锁变量
  • 临界区访问步骤
    • 当TS为1则等待
    • 访问完临界区把锁变量设置为0
  • 特点
    • 实现简单、多进程
    • 原子操作（一般都是硬件实现），屏蔽中断，只适合多处理器
    • 违背“让权等待”
• 原子硬件指令Swap
  • Swap功能：交换两个变量的值（Ts指令的本质其实就是把1和锁变量旧值进行交换）
  • 临界区访问步骤
    • 新建变量old为1
    • old和锁变量交换
    • 如果old为1则等待
    • 访问完临界区把锁设置为0
  • 特点
    • 实现简单、多进程
    • 原子操作（一般都是硬件实现），屏蔽中断，只适合多处理器
    • 违背“让权等待”

锁

• 实现思路
  • 临界区可访问标志为available
  • acquire函数
    • 循环检查available，为0则循环检查
    • 当available为1时，则available设置为0
  • release函数
    • available设置为1
• 访问临界区步骤
  • 初始化available=1
  • 进程调用acquire()获得权限
  • 进程使用临界区
  • 进程调用release()释放权限
• 特点
  • 违背“让权等待”，有忙等待现象
  • acquire和release都是原语，硬件实现，屏蔽中断，因此只适合多处理器系统
  • 资源数为1

信号量

整型信号量

• 是锁方法的多资源的修改版本
• 用整型信号量S表示资源数
• wait(S)函数对应acquire函数，简称P操作
  • 循环检查整型资源S>0是否满足，不满足则循环检测
  • 当S>0时，S=S-1
• signal(S)函数对应release函数，简称V操作
  • S=S+1
• 违背“让权等待”，进程等待时一直占用处理器，不被阻塞
• P和V都是原子操作，屏蔽中断，只适合多处理器系统

记录型信号量

• 对整型信号量的忙等待现象的改进，一般默认信号量为记录型信号量
• 信号量S为记录型结构体，包括资源数value和等待的进程队列list
• wait(S)函数（简称P操作）
  • value=value-1
  • 如果value<0，则进程加入list并阻塞
• signal(S)函数（简称V操作）
  • value=value+1
  • 如果value<=0，则list中取出一个进程并唤醒
• 满足“让权等待”，进程在等待时主动被阻塞（不是外部中断），单处理器系统也可以使用

信号量实现同步

• 问题：希望进程A的a操作在进程B的b操作前执行
• 实现：
  • 初始化信号量，资源数设为0
  • a后面插入V操作：表示a执行完后出现一个资源，可以释放进程队列的B进程
  • b前面插入P操作：因为资源初始化为0，所以直接把B进程加入队列并阻塞

信号量实现互斥

• 问题：希望进程A和进程B互斥的访问一个临界区
• 实现
  • 初始化信号量，资源数为1
  • A和B在访问前加入P操作，访问后加入V操作
  • 注意
    • 互斥的操作前后需要用PV夹紧，不能有冗余操作，比如其他同步信号量的PV
    • 具体问题具体分析，但一般互斥的P需要夹紧，否则容易死锁；互斥的V不一定夹紧

信号量实现前驱关系

• 问题：希望多个进程的操作之间满足一定的执行顺序（有向图表示），是同步问题的多进程版本
• 实现：
  • 因为每个有向边为一个同步关系，即对应一个信号量，所以需要初始化多个信号量，资源数都设为0（一开始没有边，即没资源）
  • 每个进程在执行前，对所有入边信号量进行P操作（申请入边资源）
  • 每个进程执行后，对所有出边信号量进行V操作（释放出边资源）

信号量解决问题的思路

• 关系分析
  • 分析进程之间的同步、互斥关系
  • 每对关系需要一个信号量，想清楚该信号量对应什么资源
• PV操作位置
  • 每个进程都确定PV操作的顺序安排
  • 想清楚要申请什么资源，能释放什么资源
• 信号量设置和初始化
  • 设置需要的信号量
  • 根据开始时资源数目情况进行初始化

管程

• 管程也是一种进程同步互斥的工具
• 管程的特性保证进程互斥
• 管程提供的条件变量可灵活实现同步

定义

• 组成
  • 管程名称
  • 管程内的共享数据结构，对应系统某共享资源
  • 管程内共享数据结构的初始化函数
  • 管程内共享数据结构的函数过程
• 特点
  • 管程像一个类，把共享资源数据结构和在该数据结构上的操作封装起来
  • 一次只能一个进程进入管程，使用管程的调用接口，从而一定保证互斥
• 举例
  • monitor Name { //管程名称
  • 共享数据结构S; //管程内的共享数据结构
  • init_S(){S=5;} //初始化函数
  • take_away(){S=S-1;} //函数过程
  • give_back(){S=S+1;} //函数过程
  • }

条件变量

• 定义：条件变量是，进程进入管程后不满足某些条件而被阻塞的原因
• 功能
  • 一个条件变量x包含一个阻塞队列
  • x对应条件不满足时，可调用x.wait，进程加入x的阻塞队列、阻塞进程、释放管程
  • x对应的条件满足时，可调用x.signal，从x的阻塞队列中移出一个进程唤醒
• 举例
  • monitor Name { // 管程名称
  • 共享数据结构S; // 管程内的共享数据结构
  • condition x; // 条件变量
  • init_S(){S=5;} // 初始化函数
  • take_away(){if(S<=0) x.wait(); S=S-1;} // 函数过程
  • give_back(){S=S+1;if(有进程在阻塞队列) x.signal();} // 函数过程
  • }

管程和信号量对比

• 资源数
  • 管程：共享数据结构
  • 信号量：记录型信号量数据结构的一个成员
• 资源有关操作
  • 管程：在take_away和give_back过程实现
  • 信号量：PV操作内实现
• 阻塞队列
  • 管程：包含在条件变量中
  • 信号量：记录型信号量数据结构的一个成员
• 阻塞队列的进出操作（进程阻塞和唤醒）
  • 管程：条件变量的wait和signal
  • 信号量：PV操作内实现

经典同步问题

注： + 注意大部分同步问题的操作序列都是while(1)循环中 + 信号量类型是semaphore + 函数前缀可以是Procedure或process，也可以忽略 + 多个函数并行可以使用cobegin、coend框起来

生产者-消费者

• 问题：一个初始为空，大小为n的缓冲区，生产者放产品进入，消费者拿产品出
• 思路（可参考的前面信号量解决问题的思路小节）
  • 关系分析
    • 缓冲区访问是互斥的，需要先获取锁资源，信号量mutex，
    • 生产者放入产品的同步条件是，有空盘资源，信号量empty
    • 消费者拿出产品的同步条件是，有非空盘资源，信号量full
  • PV操作的位置
    • 生产者操作序列：申请空盘、申请锁、放入产品、释放锁、提供非空盘
    • 消费者操作序列：申请非空盘、申请锁、拿走产品、释放锁、提供空盘
  • 信号量设置和初始化
    • mutex=1，表示锁资源空闲
    • empty=n，表示n个空盘
    • full=0，表示0个非空盘

读者-写者问题

• 问题：一个文件，多个读者，多个写者。多个读者可以同时读；某写者写时不允许其他读者写者访问
• 思路
  • 关系分析
    • 写者访问文件需要互斥，先获得锁资源；读者访问文件需要和写者互斥，如果是第一个读者则需要获得锁资源，信号量mutex
    • 需要引入一个记录读者数量的变量count
    • 对count变量的访问需要互斥，锁count_mutex
  • PV操作的位置
    • 写者操作序列：申请mutex、写文件、释放mutex
    • 读者操作序列：申请count_mutex、若count为0则申请mutex、count+=1、释放count_mutex、读文件、申请count_mutex、count-=1、如果count为0则释放mutex、释放count_mutex
  • 信号量的设置和初始化
    • mutex=1
    • count=0
    • count_mutex=1
• 上面的思路优先处理读，随着读者不断进入，写者可能饥饿。下面改成读写公平算法
  • 关系分析
    • 在原本的关系基础上，要求所有的读者写者有同步关系，即读者和写者公平的按申请文件的顺序进入文件
    • 这可以理解成读者、写者一个个登记后才处理申请，需要信号量t表示目前有登记表资源
      
  • PV操作的位置
    • 写者修改思路：进入前申请登记表t，走之后才释放t，让其他人登记
    • 写者操作序列：申请t、申请mutex、写文件、释放mutex、释放t
    • 读者修改思路：进入前申请登记表t，再修改count（理解成登记过程），然后释放登记表。
    • 读者操作序列：申请t、申请count_mutex、若count为0则申请mutex、count+=1、释放count_mutex、释放t、读文件、申请count_mutex、count-=1、如果count为0则释放mutex、释放count_mutex
  • 信号量的设置和初始化
    • mutex=1
    • count=0
    • count_mutex=1
    • t=1

哲学家进餐问题

• 问题：n个哲学家，哲学家之间有一根筷子，共n根筷子，哲学家要拿起左右边两个筷子才能吃饭。哲学家毕生都在思考和吃饭
• 初步思路
  • 关系分析：n个筷子是互斥资源，n个信号量
  • PV操作的位置
    • 申请左边筷子、申请右边筷子、用餐、释放右边筷子、释放左边筷子、思考
  • 信号量的设置和初始化
    • n个chopstick[n]都设置为1
• 该初步思路可能存在死锁，即每个哲学家拿起一侧的筷子，相互等待出现死锁
• 三种改进方法
  • 最多允许n-1个哲学家一起用餐
    • 关系分析：考虑座椅资源，互斥关系，引入额外信号量seat
    • PV操作位置：申请座椅、申请左边筷子、申请右边筷子、用餐、释放右边筷子、释放左边筷子、释放座椅、思考
    • 信号量设置和初始化：seat=n-1，n个chopstick[n]都设置为1
  • 同时只允许1个哲学家拿筷子
    • 关系分析：考虑拿筷子锁，引入额外信号量mutex
    • PV操作位置：申请mutex、申请左边筷子、申请右边筷子、释放mutex、用餐、释放右边筷子、释放左边筷子、思考
    • 信号量设置和初始化：mutex=1，n个chopstick[n]都设置为1
  • 奇数号哲学家先拿左筷子，偶数号哲学家先拿右筷子
    • 关系分析：不用引入额外信号量
    • PV操作位置：申请左（右）边筷子、申请右（左）边筷子、用餐、释放右边筷子、释放左边筷子、思考
    • 信号设置和初始化：n个chopstick[n]都设置为1

吸烟者问题

• 问题：三个吸烟者，一个供应者，每次吸烟需要三种材料，吸烟者各自有一种材料，供应者可以提供三种材料。供应者提供两种材料，相应吸烟者拿材料吸烟，完成后供应者再提供其他两种材料，循环下去的过程。
• 思路
  • 关系分析
    • 三种材料的两两组合，共三种组合，对应三种同步资源，信号量为offer1、offer2、offer3
    • 完成信号finish也是一个同步资源，由吸烟者提供给供应者
    • 需要一个变量num来记录当前需要给哪个吸烟者提供材料，因为只有一个供应者可访问num，因此不需要加锁
  • PV操作
    • 吸烟者：申请offeri、吸烟、释放finish
    • 供应者：num++、根据num的值释放对应offeri、申请finish
  • 初始化
    • offeri=0
    • finish=0
    • num=0

死锁

基本概念

• 定义：死锁是多个进程竞争资源而造成的互相等待的僵局
• 产生原因
  • 对不可剥夺资源的竞争
  • 进程推进顺序非法
  • 死锁四个必要条件
    • 互斥：资源同段时间只能被一个进程使用
    • 不可剥夺：资源只能被主动释放，不能被剥夺
    • 请求并保持：请求资源的进程进入阻塞队列等待，但保持现有资源不释放
    • 循环等待：存在一条进程对资源的循环等待链（如果每类资源都只有一个，则本条变为充要条件）
• 处理策略
  • 死锁预防
    • 定义：设置限制条件，破坏4个必要条件中的一个或几个
    • 特点：限制严格，资源容易闲置，实现简单
  • 死锁避免
    • 定义：在资源动态分配过程中，设置限制条件，让系统保持安全状态（详见后面死锁避免小节）
    • 特点：限制相对较弱，不一定破坏4个必要条件，在运行时判断是否会死锁，实现复杂
  • 死锁检测和解除
    • 定义：允许死锁发生，但能检测出并解除
    • 特点：需要进行资源剥夺

死锁预防

• 破坏互斥条件
  • 适用于只读的文件、磁盘、时钟
  • 大部分情况不可行，因为有些资源必须互斥
• 破坏不剥夺条件
  • 适用于内存和处理器资源
  • 方法一：进程申请等待新资源，主动释放已占有资源，之后需要时向系统申请
  • 方法二：资源分配管理程序为进程分配资源，若资源不充足则剥夺其所有资源并阻塞，等资源充足再唤醒分配
• 破坏请求并保持条件
  • 静态分配法，进程执行前申请所有需要的资源，全部满足后再执行
  • 资源利用率低
• 破坏循环等待条件
  • 层次分配法：给资源分层次
    • 进程获得某资源后，只能申请高层次资源
    • 进程释放某资源前，先释放高层次资源
    • 进程获得某资源后，需要释放该资源才能申请同层次其他资源
  • 编号法：每个层次一个资源，即给资源编号

死锁避免

进程在动态分配资源前，先计算系统安全性，达到死锁避免的目的 #### 系统安全状态 + 安全序列：进程的完成推进顺序，按该顺序分配资源能满足每个进程的资源需求 + 系统安全状态：存在安全序列 + 系统安全状态和死锁的关系 * “破坏必要条件”是“安全状态”的真子集，保证系统安全状态不一定破坏必要条件 * “死锁”是“不安全状态”的真子集，系统不安全状态也不一定死锁（后面补充思考会进一步分析） * 系统安全可以保证避免死锁

银行家算法

• 数据结构
  • Available向量：当前的可用资源数
  • Max矩阵：各行进程对各列资源总需求（预估上界），等于Allocation+Need
  • Allocation矩阵：各行进程对各列资源已分配量
  • Need矩阵：各行进程对各列资源的剩余需求（预估上界）
  • Work向量：系统安全判断时使用，作为Available向量的副本，这样不用修改Available
  • Request向量：银行家算法的输入，是某进程发出的资源请求
• 安全判断算法（当系统安全时，求出一个安全序列）
  • 已知当前的Need、Allocation、Available
  • 备份Available，记为Work，此后对Work操作（Work=Available）
  • 选择比Work小的Need行，设对应进程k，完成该进程、加入安全序列、释放资源（Work+=Allocation[k]）
  • 重复上一步，直至找不到比Work小的Need行
  • 如果安全序列有所有进程，则系统安全；否则系统不安全
• 银行家算法（当进程k发出一个资源请求时，用银行家算法进行处理）
  • 已知当前的Request、Need、Allocation、Available
  • 检测请求合法性：Request<Need[k]，不合法则报错
  • 检测资源充足性：Request<Available，不充足则让进程等待
  • 计算资源分配后的数据：Available-=Request，Need[k]-=Request，Allocation[k]+=Request
  • 检查此时系统安全性
  • 如果安全则分配，不安全则让进程等待

死锁检测和解除

资源分配有向图

• 进程点：圆点表示一个进程
• 资源点：方形表示一类资源，如果该类资源的总数目为n，则方形内画n个小圆
• 分配边：从资源点到进程点的边，表示分配一个资源
• 请求边：进程点到资源点的边表示请求一个资源
• 分配边合法性
  • 资源点：分配边数资源总数n
  • 进程点：分配边数请求边数

死锁定理

利用资源分配图可用检测死锁

• 选择非孤立进程点（孤立进程不需要资源就能执行，不用考虑），且该点的每个申请边都满足
  • 要么已有对应资源的分配边
  • 要么对应资源可以合法的新添的分配边
• 简化：上一步所选的非孤立点进程，执行、完成、释放资源、去掉边，该进程点简化为孤立点
• 返回第二步重复执行
  • 如果全是孤立点，则不存在死锁
  • 如果存在非孤立点，但这些点无法简化，则存在死锁

补充思考

• 问题：系统安全性判断、死锁定理十分相似，但为什么找不到安全序列，不一定死锁；找不到简化序列，一定死锁
• 回答
  • 找不到安全序列
    • 指的是所有进程的Need都不比Work小的情况
    • Need是剩余资源需求，是对接下来资源请求上界的估计
    • 找不到安全序列不一定死锁，因为实际资源请求不一定到上界
  • 找不到简化序列
    • 指的是所有进程的Request都不比Work小的情况
    • Request是实际已发出的资源申请
    • 实际的资源请求得不到满足，必然死锁，所有进程都处于阻塞态

死锁解除

• 资源剥夺
  • 挂起进程、剥夺资源
• 撤销进程
  • 撤销进程、剥夺资源
• 进程回退法
  • 回退进程、非剥夺的主动释放资源
  • 要求进程保存历史信息设置还原点