计算机操作系统(2):进程管理-考研笔记

2.0 综述

引入问题

• 为什么要引入进程？
• 什么是进程？进程由什么组成？
• 进程如何变换状态？

易错点

• 可能所有进程都阻塞（由于 I/O 或者死锁等情况）
• 进程的映像指进程的组成，具体为 PCB + 程序段 + 数据段
• 系统动态 DLL 库被不同进程调用后也是同一个线程

2.1 进程与线程

进程的概念和特征

• 组成
  • PCB (Process Control Block):进程控制块
  • 程序段
  • 数据段
• 特征
  • 并发、独立、异步、结构性（PCB+数据+程序）、动态

进程的状态与转换

• 基本状态
  • 运行态
  • 就绪态
  • 阻塞态
• 非基本状态
  • 创建态
  • 结束态
  • 就绪挂起态
  • 阻塞挂起态
• 转换关系
  • 创建 -> 就绪
  • 就绪 -> 运行
  • 运行 -> 就绪
  • 运行 -> 阻塞
  • 运行 -> 结束
  • 阻塞 -> 就绪

进程控制

• 进程创建
  • 分配唯一表示 PID ，申请空白 PCB，申请失败则创建失败
  • 分配内存等资源，分配失败会处于阻塞
  • 初始化 PCB
  • 尝试插入就绪队列
• 进程终止
  • 读其 PCB 状态
  • 若进程正在执行，则终止，并将 CPU 重新分配
  • 如果还有子孙进程，则一起终止
  • 将其所有资源归还给父进程或操作系统
  • 删除其 PCB
• 进程阻塞
  • 找到其 PCB
  • 如果正在运行则保存现场，改变状态为阻塞，停止运行
  • 将 PCB 插入相应事件的等待队列，将 CPU 重新分配
• 进程唤醒
  • 找到其 PCB
  • 修改状态为就绪，且移至就绪队列
• 进程切换
  • 保存现场或上下文，包括 PC 与其他通用寄存器
  • 更新 PCB 信息
  • 将 PCB 移入相应队列（如就绪或阻塞）
  • 选择另一个 PCB 修改为运行
  • 将环境置为对应进程环境

进程的组织

• PCB
  • 包含信息
    • 进程描述信息：如 PID，UID
    • 进程控制和管理信息：如 进程状态、优先级、代码入口地址、进入内存事件、CPU 占用时间等等
    • 资源分配清单：如 代码段指针、数据段指针、堆栈段指针、文件描述符、鼠标键盘
    • CPU 相关信息：如 通用寄存器值、地址寄存器值、标志寄存器值
• 程序段
  • 代码段，可以多个进程运行同一个程序
• 数据段
  • 一个进程的数据段

进程的通信

• 共享数据区
• 消息传递
  • 挂在接受进程的消息缓冲队列上
• 管道通信
  • 半双工
  • 互斥访问
  • 写满后才能读，读空后才能写
  • 通常管道大小和内存页大小一致
  • 读一次就抛弃
• 共享文件

线程概念和多线程模型

• 基本
  • 线程可以理解为轻量级进程
  • 是 CPU 调度的基本单位（进程是资源调度的基本单位）
  • 同一进程下的线程共享进程资源
  • 线程不带自己的数据
• 线程和进程对比维度
  • 调度
  • 资源
  • 并发
  • 系统开销
  • 地址空间和其他资源
  • 通信
• 线程的属性
  • 轻型实体
  • 不同线程可以执行相同程序
  • 统一进程中的各个线程共享进程的资源
  • 线程是处理机的独立调度单位
  • 线程生命周期内也可能会经历阻塞、就绪、运行等各种状态变化
• 多线程的实现方式
  • 线程类型
    • 用户级线程（ULT:User-Level Thread）
    • 内核级线程（KLT:Kernel-Level Thread）
  • 多线程方式
    • 多对一
    • 一对一
    • 多对多
      • 但一个用户级线程至多对应一个内核级线程

2.2 处理机调度

调度的层次

• 作业调度：高级调度，次数最少
• 内存调度：中级调度，次数中等
• 进程调度：低级调度，最频繁

调度的时机

• 不能进行调度的情况
  • 在处理中断的过程中
  • 进程在操作系统内核临界区时
  • 其他需要屏蔽中断的原子操作过程
• 应该进行调度的情况
  • 非剥夺式调度
    • 达到调度的条件且当前进程无法继续时，才调度
    • 通常针对于批处理系统
  • 剥夺式调度
    • 中断处理结束，如果发现有请求调度标志，则立刻调度
    • 通常针对于分时系统和实时系统

调度的基本指标

• CPU 利用率
• 系统吞吐量
• 周转时间
  • 周转时间 = 作业完成时间 – 作业提交时间
  • 平均周转时间 = 各任务周转时间总和 / 作业数量
  • 带权周转时间 = 作业周转时间 / 作业运行时间
  • 平均带权周转时间 = 个任务带权周转时间 / 作业数量
• 等待时间：进程处于等待的时间之和
• 响应时间：进程第一次被响应的时间

典型的调度算法

• 非优先级调度算法
  • FCFS（First Come First Serve）先来先服务算法
    • 对长作业有利，不利于短作业
  • SJF(Short Job First)短作业优先算法
    • 总等待时间最短
    • 长作业可能饥饿
• 优先级调度算法
  • 根据是否剥夺分类
    • 非剥夺式优先级算法
    • 剥夺式优先级算法
  • 根据优先级是否静态分类
    • 静态优先级算法
    • 动态优先级算法
  • 优先级原则
    • 系统进程 > 用户进程
    • 交互型进程 > 非交互性进程
    • I/O 型进程 > 非 I/O 型进程
  • 高响应比优先调度算法
    • 响应比 = （等待时间 + 要求服务时间） / 要求服务时间
    • 不会饥饿
  • 时间片轮转算法(RR:Round-Robin)
    • 需要选择合适的时间片大小
  • 多级反馈队列调度算法

2.3 进程同步

基本概念

• 临界资源：一次仅允许一个进程使用的资源
• 临界资源的访问过程
  • 进入区
  • 临界区
  • 退出区
  • 剩余区
• 同步：多进程内部有先后顺序要求
• 互斥：多进程对临界资源的访问
  • 准则
    • 空闲让进：临界区空闲时允许一个请求的进程立刻进入
    • 忙则等待：当已有进程在临界区时，其他进程须等待
    • 有限等待：请求的进程在有限时间内能够访问到临界区
    • 让权等待：当进程不能进入临界区时，应立即释放处理器，不要忙等待

实现临界区互斥的基本方法

• 软件实现的方式
  • 单标志法
    • 用一个公共变量 turn 轮转指示被允许的进程编号，turn 不为自己时则 while 一直循环，为自己后则访问并在访问完成时将 turn 置为对方编号
      • 问题
        • 不满足空闲让进、有限等待、让权等待
        • 必须轮流进，否则会卡住
  • 双标志先检查法
    • 用一个标志数组 flag[] 记录每个进程当前是否在访问，每个进程想访问时需先检查标志数组是否都处于未访问状态，是则置自己的标志并访问并在访问结束时反置自己标志，否则等待。
      • 问题
        • 不满足忙则等待、让权等待
        • 可能出现多进程一起访问的情况使互斥失效
  • 双标志后检查法
    • 用一个标志数组 flag[] 记录每个进程当前是否在访问，每个进程想访问时先置自己的标志，再去检查其他进程的标志，如果其他进程已置标志则 while 循环等待，其他进程都未置标志则访问并在访问结束后反置自己的标志
      • 问题
        • 不满足空闲让进、有限等待、让权等待
        • 可能出现死锁互等
  • Peterson’s Algorithom
    • 用一个标志数组 flag[] 记录想进入的意愿，同时用 turn 记录可进入的进程。当一个进程想进入时，先置自己的标志，同时将 turn 置为对方进程编号，之后用 while(flag[other] && turn == other)进行检查等待
      • 最多谦让两次后即可顺利访问临界区
• 硬件实现的方式
  • 中断屏蔽方法
    • 在访问临界区前关中断，访问后再开中断
      • 问题
        • 系统效率降低
        • 用户可以控制中断开关这样的高级权限
  • 硬件指令方法
    • 硬件完成 TestAndSet(ResLock) 原子操作，并在执行完成后再将对应资源锁 ResLock 置 false
    • 或用 Swap 指令替代 TestAndSet 指令
    • 分析
      • 优点
        • 适用于任意数目的进程
        • 简单
        • 支持多个临界区，每个临界区一个 Lock 变量
      • 缺点
        • 等待进入时处于 while 状态，不能让权等待
        • 可能出现饥饿

信号量

• 用不可被打断的原语进行判断
• 分类
  • 整形信号量
    • 依旧有忙等的现象
  • 记录型信号量
    • 不再忙等
• 应用
  • 利用信号量实现同步
  • 利用信号量实现互斥
  • 利用信号量实现前驱关系

管程

• 特征
  • 每次只有一个进程访问管程
  • 用类似于“类”的手段，把对共享资源的操作给封装起来
  • 由编程语言支持的进程同步机制
  • 管程中定义的变量只能被管程内的过程访问
  • 管程是被进程调用的，限于语法范围，无法创建和撤销
• 组成
  • 管程名称
  • 局部于管程内部的共享结构和数据说明
  • 对该数据结构进行操作的一组过程
  • 初始化语句

经典同步问题

• 生产者消费者问题
• 读者-写者问题
• 哲学家进餐问题
• 吸烟者问题

2.4 死锁

死锁产生的原因

• 四个必要条件
  1. 资源互斥
  2. 持有请求
  3. 不剥夺
  4. 循环等待

死锁的预防

• 破坏必要条件
  1. 破坏护持条件：通常不可行
  2. 破坏持有请求：一次性申请所有需要的资源
  3. 破坏不剥夺条件：当新申请的资源得不到满足时，需释放已拥有的资源
  4. 破环循环等待条件：比如要求程序仅能按序号递增的次序申请资源，且同类资源需要一次性申请完

死锁的避免（和预防不同，在正常分配中增加一些考虑以避免死锁）

• 用银行家算法避免系统进入不安全状态
  • 系统的安全状态
    • 以最大需求即最坏的情况作为考虑，所以安全的一定不死锁，不安全的不一定死锁
  • 银行家算法
    • 需已知每个进程对每个资源的最大需求量
    • 不断想象完成可完成的进程，测试是否能完成所有任务

死锁的检测

• 资源分配图
• 死锁定理
  • 类似银行家算法的思路，不断剔除满足条件的进程，观察是否能剔除完所有进程

死锁的解除

1. 资源剥夺法：挂起某些死锁进程并抢占其资源
2. 撤销进程法：强制撤销部分死锁进程
3. 进程回退法：回退部分进程至可避免死锁的状态，需记录进程的历史操作