第二章进程管理

操作系统详细思维导图，进程是为了控制好程序的并发执行而引入，线程是为了跟好地使多道程序并发执行，提高资源利用率和系统吞吐量。本图适合计算机相关专业期末复习，考研学习等。

第二章-进程管理

• 1. 进程
  • I. 程序的顺序执行
    • 1. 顺序性
    • 2. 封闭性
      • 独占全部资源
    • 3. 可再现性
      • 初始条件一致，执行结果也一致
  • II. 程序并发执行
    • 1. 间断性
      • 因为资源共享与相互合作
    • 2. 失去封闭性
      • 并发程序共享系统资源
    • 3. 不可再现性
  • III. 进程
    • i. 为了控制好程序的并发执行而引入
    • ii. 概念
      • 可理解程序的一次执行
    • iii. 进程实体（映像）
      • 进程控制块(PCB)
        • 进程存在的唯一标识
        • 包括
          • 1. 进程标识符（端口号）
          • 2. 处理机状态信息（寄存器的内容）
          • 3. 调度信息（进程优先级，运行时间等）
          • 4. 进程控制信息（如程序和数据地址）
      • 程序段
        • 多进程共享
      • 数据段
        • 包括原始数据，中间数据和最终结果
        • 数据区
          • 动态数据区
            • 堆区
              • 动态分配内存的区域
            • 栈区
              • 函数调用的参数
              • 局部变量
    • iv. 地位
      • 系统资源分配和CPU调度的基本单位
    • v. 特征
      • 1. 动态性
        • 由创建而产生
        • 调度而执行
        • 撤销而消亡
      • 2. 并发性
        • 多个进程实体同处内存，并在一段时间内同时执行
      • 3. 独立性
        • 每个进程实体独立分配资源，独立接收调度的
      • 4. 异步性
        • 进程独立地，不可预知地向前推进
          • 不可再现性
    • vi. 进程的基本状态
      • 1.就绪态
        • 进程已获得除CPU外的所有资源
      • 2.运行态
        • 在CPU上运行
      • 3.阻塞态
        • 又称等待态，进程等待某一件事情发生
        • 如等待某个资源可用，等待I/O完成
      • 其它状态
        • 4.创建态
          • 5.终止态
        • 进程的挂起状态
          • 活动状态下被挂起就变成了静止转态
          • 静止状态必须被激活成相应活动状态后才能参与调度
      • 状态装换过程
        • i. 就绪态->运行态
          • 进程获得调度
        • ii. 运行态->就绪态
          • 时间片用完
        • iii. 运行态->阻塞态
          • 申请资源失败，I/O操作等
        • iv. 阻塞态->就绪态
          • 等待的事情发生
      • 进程的基本状态保存在自己的PCB中
    • vii. 进程控制
      • 1. 进程创建
        • 过程
          • i. 分配唯一标识符，并申请空白PCB（有限）
            • 若PCB申请失败，则创建失败
          • ii. 分配资源（如为程序段和数据段以及用户栈分配内存空间）
            • 失败则阻塞
          • iii. 初始化PCB（如处理机状态信息，处理机控制信息等）
          • iv. 若就绪队列接纳，则入就绪队列
        • 举例
          • 用户登录
            • 作业调度
              • 系统提供服务
                • 应用程序请求
      • 2. 进程终止
        • 正常结束
          • 任务完成
        • 异常结束
          • 存储区越界
            • 特权指令
              • 超时
                • 算术错
        • 外界干预
          • 父进程终止
      • 3. 进程阻塞
        • 等待的事件未发生
          • 主动行为
      • 4. 进程唤醒
        • 等待的事件发生
          • 被动行为
      • 5. 进程切换
        • 时间片用完
        • 高优先级抢占
        • 主动放弃
    • viii. 进程通信
      • 1. 共享存储
        • 低级方式
          • 共享数据结构
        • 高级方式
          • 共享存储区
        • 互斥访问共享空间
      • 2. 消息传递
        • 传递的是格式化的信息（报文）
        • 分类
          • 直接通信方式
            • 直接将消息挂在接收方的消息缓冲队列
          • 间接通信方式
            • 放到某个中间实体，接收方从中间实体获得消息（邮件系统）
      • 3. 管道通信
        • 管道就是一个共享文件，固定大小的缓冲区（LINUX为4kb）
          • 半双工
        • 读写进程
          • 写进程
            • 互斥写（以字符流形式写入）
          • 读进程
            • 互斥读
            • （一旦数据被读就被抛弃了）
        • 原则
          • “非空不能写”
          • “非满不能读”
  • IV. 线程
    • 为了跟好地使多道程序并发执行，提高资源利用率和系统吞吐量
    • 概念
      • 轻量级“进程”
        • 由线程ID，线程控制块，程序计数器，寄存器，堆栈组成
          • 也具有三种基本状态
    • 地位
      • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
    • 特点
      • 共享进程的地址空间（没有独立的地址空间）
        • 共享进程的资源
          • 可被其他线程调用
            • 同一进程下直接通信
    • 实现方式
      • 用户级线程（ULT）
        • （多个用户级线程映射到一个内核级线程）
        • 内核意识不到用户级线程的存在
        • 管理工作全由用户程序完成
        • 由线程库完成切换
      • 内核级线程（KLT）
        • （每个用户级线程映射到一个内核级线程）
        • 管理工作全由内核程序完成
        • OS只能感知到内核级线程，因此只有内核级线程才是CPU调度的单位
      • 组合方式
        • （多个用户级线程映射到多个内核级线程上）
    • 多线程模型
      • 多对一模型
        • （多个用户级线程映射到一个内核级线程）
        • 优点
          • 线程管理在用户空间完成，用户级线程对OS不可见，高效高
        • 缺点
          • 一个线程阻塞，整个进程阻塞
            • 不能在多处理机上并行执行
      • 一对一模型
        • （每个用户级线程映射到一个内核级线程）
        • 优点
          • 一个线程阻塞了，其它还能继续运行
            • 并发能力强
        • 缺点
          • 一一对应的开销大
      • 多对多模型
        • n个用户级线程映射到m个内核级线程中
          • 要求m<=n
        • 使用频率高的单独组织到一个一个内核级线程下
        • 使用频率低的可以让多个ULT组织到一个内核级线程下
• 2. 处理机的调度
  • i. 基本概念
    • 按照某种调度算法，从就绪队列中选择一个进程并分配给其处理机
  • ii. 调度的层次
    • 作业调度
      • 又称高级调度
        • 从外存中选取至少一个后备状态的作业为其分配内存，I/O设备等
      • 频率低，几分钟一次
    • 内存调度
      • 又称中级调度
        • 旨在提高内存利用率和吞吐量
          • 进程的挂起与激活
    • 进程调度
      • 又称低级调度
      • 频率高
        • 几十毫秒一次
  • iii. 调度的时机，切换与过程
    • 进程调度和切换程序是操作系统内核程序
    • 不能调度和切换的情况
      • 1. 处理中断的过程中
      • 2. 在OS内核临界区中
        • 普通用户程序的临界区是可以调度的
      • 3. 原子操作中
        • 如加锁，解锁，现场保护/恢复等
    • 可以调度和切换的情况
      • 1. 发生引起调度的条件和进程无法向下推进
        • 非剥夺
      • 2. 中断处理结束和自陷处理（系统调用处理）结束后，返回源现场
        • 剥夺
  • iv. 进程调度的方式
    • 抢占式
      • 适用
        • 时间片轮转调度
          • 优先权
            • 短进程优先
    • 非抢占式
      • 适用
        • 批处理
  • v. 调度的基本准则
    • CPU利用率
      • CPU工作时间/总时间
    • 系统吞吐量
      • 完成作业时间/所花的总时间
    • 周转时间
      • 完成时间-到达时间
      • 平均周转时间
        • 所有进程周转时间的均值
      • 带权周转
        • 周转时间/实际执行时间
        • 平均带权周转时间
          • 所有带权周转时间的期望
    • 等待时间
      • 开始执行时间-到达时间
    • 响应时间
      • 用户提交请求到系统首次产生响应的时间
  • vi. 典型调度算法
    • 1. 先来先服务（FCFS）
      • 每次选择最先到达的进程进行调度
        • （就绪队列中等待时间最久的）
      • 适合
        • CPU繁忙型作业
      • 不适合
        • I/O繁忙型作业
    • 2. 短作业优先（SJF）
      • 每次从就绪队列选择执行时间最短的进程进行调度
        • （静态优先级调度）默认非抢占
      • 缺点
        • i. 可能有“饥饿”现象
          • 对长作业不利
        • ii. 不能保证紧急作业及时处理
      • 最有利于提高系统吞吐量
    • 3. 优先级调度
      • 是否可抢占
        • 抢占式
        • 非抢占式
      • 优先级是否可变
        • 静态优先级
          • 一直不变
        • 动态优先级
          • 运行过程中改变
      • 设置优先级原则
        • i. 系统进程＞用户进程
        • ii. 交互型＞非交互性（前台进程＞后台进程）
        • iii. I/O型>计算型
      • 缺点
        • 可能“饥饿“
          • 对低优先级不利
    • 4. 高响应比优先调度（HRRN）
      • 响应比=1+等待时间/要求服务时间
      • 优点
        • 兼顾了长短作业，克服了饥饿
    • 5. 时间片轮转调度
      • 指分配CPU的时间片
        • 仅适合进程调度
          • 抢占式
      • 由时钟装置发出时钟中断来通知CPU进程运行的时间片已到
      • 发现
        • 当时间片≥max｛进程pi运行时间时｝，就变成先来先服务了
      • 应用
        • 分时OS
    • 6. 多级反馈队列调度
      • i. 设置多个就绪队列，每个队列赋予不同的优先级
      • ii. 优先级越高，时间片越短
        • 第n级是第n-1级队列中时间片的2倍
      • iii. 每级队列内采用先来先服务
      • iv. 若因高优先级进程加入而被抢占，则放入当前队列队尾，否则放入下级队列或撤离CPU
      • v. 应用
        • UNIX系统
• 3. 进程同步
  • i. 基本概念
    • 为协调并发进程间的相互制约关系
      • 保证结果的可再现性
    • 临界资源
      • 指每次仅允许一个进程使用的资源
      • 访问过程
        • I. 进入区
          • 一般包含了P操作
        • II. 临界区
          • 访问临界资源的那段代码
          • 每个进程有自己的临界区（引入管程前，临界区不共用）
        • III. 退出区
          • 一般包含了V操作
      • 举例
        • 1. 打印机
        • 2. 共享数据
        • 3. 共享变量
    • 同步
      • 源于相互合作
        • 直接制约
    • 互斥
      • 源于资源共享
        • 间接制约
      • 同步机制遵循的准则
        • I. 空闲让进
          • 临界区空闲时允许进入
        • II. 忙则等待
          • 临界区忙碌时必须等待
        • III. 有限等待
          • 不能一直等待
            • （防止饥饿）
        • IV. 让权等待
          • 进不了临界区就果断放弃CPU，防止其他进程忙等
          • 非必需实现
  • ii. 临界区互斥的方法
    • 1. 软件方法
      • 单标志法
        • 设置公用整型变量turn
          • turn=0
            • p0进入
          • turn=1
            • P1进入
        • 缺点
          • 违背“空闲让进”原则
          • 若p0/p1进入临界区退出后，p1/p0不进去了
          • 则p0/p1再也进不了临界区
      • 双标志先检验
        • 设置flag[0]和flag[1]分别表示自己是否进入临界区
          • 如p0进入时检查flag[1]
          • flag[1]=false则进入
          • 退出时将flag[0]置false
        • 缺点
          • 违背“忙则等待”原则
          • 初始状态下flag[0]=flag[1]=false，可能同时进入临界区
      • 双标志后检验
        • 进入临界区前，先设置自己的flag为true，再检查另外的flag是否为false
        • 是就进入
        • 缺点
          • “饥饿”
          • 若开始时p0和p1同时将自己的flag置true，则都进不了临界区
      • 皮特森算法
        • 再设置一个turn变量
          • 用turn变量表达“谦让”，flag变量表达意愿
          • 进入临界区前，先将自己的flag置true，但将turn置为对方值
          • 同时检查flag和true
        • 优点
          • turn解决了“饥饿”
          • flag解决了“互斥访问”
    • 2. 硬件方法
      • i. 中断屏蔽
        • 原理
          • CPU仅在发生中断时才进行进程切换
          • 这样就保证当前进程顺利执行完临界区的代码
        • 缺点
          • 不适用于多核
            • 只适用于OS内核进程
      • ii. 硬件指令
        • TestAndSet指令（TSL）
          • 该指令是原子操作
            • 由硬件逻辑直接实现
          • 功能是读出指定标志后再把该标志设置为真
        • swap指令
          • 交换两个变量值
      • iii. 优点
        • 1. 适用于多核多进程
        • 2. 支持进程内有多个临界区
      • iv. 缺点
        • 无法实现“让权等待”
          • 进程等待临界区时要耗费处理机的时间
        • “有饥饿”
          • 因为是随机选择进程进入临界区的
  • iii. 信号量
    • I. 整型信号量
      • 缺点
        • 未遵循“让权等待”
          • P操作没有阻塞原语
    • II. 记录型信号量
      • 优点
        • 遵循“让权等待”
          • P操作有阻塞原语
    • III. 应用
      • 1. 实现同步
      • 2. 实现互斥
      • 3. 实现前驱关系（拓扑序列）
  • iv. 管程
    • I. 思想
      • 面向对象程序设计
    • II. 组成
      • 1. 管程名
      • 2. （局部于管程内部的）共享数据结构
        • （局部于管程内部的）即私有
      • 3. 对共享数据结构的操作（函数）
      • 4. 对共享数据结构设置的初始化语句
    • III. 互斥原理
      • 每次仅允许一个进程进入管程，从而实现互斥
    • IV. 条件变量
      • 定义了进程因某类资源而阻塞的原因
      • 管程内设计多个条件变量
        • 每个条件变量保存一个等待队列
        • 记录因某类资源而阻塞的所有进程
        • 调用wait函数阻塞进程
      • 与信号量的区别
        • 条件变量是“无值”的，仅实现排队等待功能
        • 信号量是有值的，正数值表示剩余资源数，负数值的绝对值表示阻塞进程数
• 4. 死锁
  • i. 死锁的概念
    • 并发进程因资源竞争而形成的相互等待的局面
  • ii. 产生原因
    • 1. 资源竞争
      • 这里的资源指不可剥夺资源（独占资源）
      • 可剥夺资源，非共享资源是不会引起死锁的
      • 不是因为系统资源不足
    • 2. 进程的推进顺序非法
  • iii. 必要条件
    • 1. 互斥条件
      • 一段时间内资源仅由一个进程所占有
        • 最难破坏
    • 2. 不剥夺条件
      • 资源未使用完之前，不能由其他进程剥夺，只能自己释放
    • 3. 请求并保持
      • 已获得资源的进程，再次申请资源失败的时候，保持自己的资源不放
    • 4. 循环等待
      • 出现了循环等待链
  • iv. 死锁的处理策略
    • 1. 死锁预防
      • 破坏四个必要条件
    • 2. 死锁避免
      • 防止系统进入不安全态
    • 3. 死锁的检测与解除
  • v. 死锁预防
    • 1. 破坏互斥条件
      • 行不通
      • 可以通过spooling技术将独占设备虚拟为共享设备
    • 2. 破坏不剥夺条件
      • 允许剥夺进程拥有的资源
      • 适用于寄存器及内存资源，不适合打印机之类的资源
    • 3. 破坏请求保持条件
      • 一次性把进程执行所需的全部资源分配给它
      • 只要进程所需的资源未分配完成就不让运行
    • 4. 破坏循环等待条件
      • 资源有序分配
      • 将资源编号，进程申请资源时只能按编号递增的顺序进行
  • vi. 死锁避免
    • 安全态
      • 系统能够找到一种资源分配方式，使进程向下推进
    • 举例
      • 银行家算法
    • 推论
      • 1. 系统处于安全态，一定不会发生死锁
      • 2. 系统处于不安全态，不一定会发送死锁
        • 只有此时没有进程提出资源请求
  • vii. 死锁的检测与解除
    • 1. 资源分配图
    • 2. 死锁定理
      • 产生死锁的充要条件是资源分配图不能完全简化
    • 3. 死锁公式
      • 若n个进程共享系统m个资源，且每个进程所需资源数为ri
      • 产生死锁的条件
        • (r1-1)+(r2-1)+...+(rn-1)>=m
    • 4. 死锁解除
      • a. 资源剥夺
      • b. 撤销进程
      • c. 进程回退
        • 要求系统能保存进程的历史信息（断点）