计算机操作系统: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 型进程
    • 高响应比优先调度算法
      • 响应比 = (等待时间 + 要求服务时间) / 要求服务时间
      • 不会饥饿
    • 时间片轮转算法
      • 需要选择合适的时间片大小
    • 多级反馈队列调度算法

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. 进程回退法:回退部分进程至可避免死锁的状态,需记录进程的历史操作

Leave a Comment