操作系统·进程与处理机管理

进程与线程

进程的概念和特征

• 进程的概念
  • 进程的定义
  • 进程实体（进程映像）
    • 程序段
    • 数据段
    • PCB
• 进程的特征
  • 动态性
  • 并发性
  • 独立性
  • 异步性

进程的状态与状态的转换

• 基本状态(5)
  • 运行态
  • 就绪态
  • 阻塞态（等待态）
  • 创建态（新建态）
  • 终止态（结束态）
• 基本状态转换(3)

进程的组成

• PCB
  • 进程存在的唯一标志，进程存在时PCB常驻内存（中的系统区）
  • 通常包含的内容
    • 进程描述信息
      • PID
      • UID
    • 进程控制和管理信息
      • Status
      • Priority
      • 代码运行入口地址
      • 程序的外存地址
      • 进入内存时间
      • 处理机占用时间
      • 信号量使用
    • 资源分配清单
      • 代码段指针
      • 数据段指针
      • 堆栈段指针
      • 文件描述符（FD）
      • 键盘
      • 鼠标
    • 处理机相关信息
      • 通用寄存器值
      • 地址寄存器值
      • 控制寄存器值
      • 标志寄存器值
      • 状态字
  • PCB的组织方式
    • 链接
    • 索引
• 程序段
• 数据段

进程控制

• 📝进程控制使用原语
• 进程的创建
  • 创建原语
    • 申请空白PCB
    • 分配资源
      • 分配成功
      • 分配失败->阻塞态
    • 初始化PCB
    • 插入就绪队列
• 进程的终止
  • 引起终止的事件
    • 正常结束
    • 异常
    • 外界干预
  • 终止原语
    • 检索出PCB
    • 若处于运行态
    • 一并终止子孙进程
    • 归还资源
    • 从队列中移除
• 进程的阻塞和唤醒
  • 阻塞原语
    • 找到PCB
    • 保护现场，转态，停止运行
    • 插入相应队列
  • 唤醒原语
    • 找到PCB
    • 移出队列
    • 插入就绪队列
• 进程的切换
  • 引起切换的事件
    • 时间片到
    • 高优先级进程到达
    • 主动阻塞
    • 进程终止
  • 切换原语
    • 将运行环境存入PCB
    • 移入响应队列
    • 选择另一个进程执行，并更新PCB
    • 根据PCB恢复运行环境

进程的通信

• 低级通信方式：PV操作
• 高级通信方式
  • 共享存储
    • 低级方式：基于数据结构的共享
    • 高级方式：基于存储区的共享
    • 不同进程共享存储需通过syscall
    • 进程内的线程是自然共享进程空间的
  • 消息传递
    • 通过发送、接受两个原语进行（具体实现是透明的）
    • 分为
      • 直接通信方式：发送方->接收方（的消息缓冲队列）
      • 简介通信方式：发送方->信箱->接收方
  • 管道通信
    • 按生产者-消费者方式进行通信
    • 互斥、同步、确定对方存在
    • 仅允许单向通信

线程和多线程模型

• 线程的基本概念
• 线程与进程的比较
• 线程的属性
• 线程的状态与转换
• 线程的组织与控制
  • 线程控制块（TCB）
    • 线程标识符
    • 一组寄存器
    • 线程运行状态
    • 优先级
    • 线程专有存储区
    • 堆栈指针
  • 线程的创建
  • 线程的终止
• 线程实现方式
  • 用户级线程
    • 优点
      • 线程切换不需要转换到内核空间，节省了模式切换的开销
      • 调度算法可以是进程专用的，不同进程可根据自身需要，对自己的线程选择不同的调度算法
    • 缺点
      • 系统调用的阻塞问题：进程中的一个线程进行系统调用时，进程的所有线程都会被阻塞
      • 不能发挥多处理机的优势，内核每次分配给一个进程的仅有一个CPU，因此进程中仅有一个线程能运行
  • 内核级线程
    • 优点
      • …（对照上面的缺点）
      • …（…）
    • 缺点
      • 同一进程的线程切换需要转到核心态，开销较大
  • 组合方式
    • 三种主要的线程库
      • POSIX Pthreads
      • Windows API
      • Java
• 多线程模型
  • 多对一
  • 一对一
  • 多对多

不讲辅助码，什么是双拼

处理机调度

调度的概念

• 调度的基本概念
  • 对处理机进行分配
  • 是操作系统的核心问题
• 调度的层次
  • 高级调度（作业调度）
  • 中级调度（内存调度）：将暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态
  • 低级调度（进程调度/处理机调度）
• 三级调度的联系

调度的目标

• CPU利用率

• 系统吞吐量：单位时间内CPU完成作业的数量

• 周转时间

  • 周转时间：作业完成时间-作业提交时间
  • 平均周转时间
  • 带权周转时间：作业周转时间/作业实际在处理机上运行的时间
  • 平均带权周转时间

• 等待时间

• 响应时间

调度的实现

• 调度程序
  • 排队器
  • 分派器
  • 上下文切换器
• 调度的时机、切换与过程
  • 不能进行进程的调度与切换的情况有以下几种
    • 在处理中断的过程中
    • 进程在操作系统内核临界区内（普通临界区不影响）
    • 其他需要完全屏蔽中断的源自操作过程中
  • 应该进行进程调度与切换的情况如下
    • 发生引起调度条件且当前进程无法继续运行下去时
    • 返回被中断进程的用户态程序执行现场前
• 进程调度方式
  • 非抢占调度方式（非剥夺式）
    • 优点：实现简单、系统开销小
    • 缺点：不能用于分时系统和大多数实时系统
  • 抢占调度方式（剥夺式）
• 闲逛进程
  • 系统中没有就绪进程，就会调度闲逛进程（idle）运行
  • 优先级最低
  • 不需要CPU之外的资源
  • 不会被阻塞
• 两种线程的调度
  • 用户级线程调度
  • 内核级线程调度

典型的调度算法

• FCFS
  • 可用于作业调度，也可用于进程调度
  • 属于不可剥夺算法
  • 不能作为分时系统和实时系统的主要调度策略
  • 算法简单
  • 效率低
  • 对长作业有利，对短作业不利
  • 有利于CPU繁忙型作业，不利于I/O繁忙型作业
• 短作业优先调度算法（SJF）和段进程优先调度算法（SPF）
  • 选择的是估计运行时间最短的作业
  • 属于不可剥夺算法
  • 缺点
    • 对长作业不利，可能导致“饥饿现象”
    • 完全未考虑作业的紧迫度
  • SJF调度算法的平均等待时间、平均周转时间最少
• *最短剩余时间优先算法（SRTN, shortest remaining time next）
• 优先级调度算法（PS, priority scheduling）
  • 作业调度&进程调度
  • 非抢占&抢占式优先级调度算法
  • 静态优先级&动态优先级
  • 优先级设置的原则
    • 系统进程>用户进程
    • 交互型进程>计算型进程
    • I/O型进程>计算型进程
• 高响应比优先调度算法（HRRN, highest response ratio next）
  • 响应比=$(等待时间+要求服务时间)/要求服务时间$
  • 克服了“饥饿”现象
• 时间片轮转调度算法（RR, Round-Robin）
  • 主要适用于分时系统
  • 优点：公平、响应快
  • 缺点：进程切换的开销；无优先级
  • 时间片大小的选择
• 多级队列调度算法
• 多级反馈队列调度算法（融合了前几种算法的优点）（MFQS, multiple feedback queue scheduling）
  • 实现思想
    • 多个就绪队列，优先级递减，时间片递增
    • 对于单个队列采用FCFS
    • 高优先级进程到达将立即剥夺正在运行的进程的处理机资源
  • 兼顾了多方面的系统目标
  • 可能导致饥饿

进程切换

• 上下文切换
  • 上下文：某一时刻CPU寄存器和程序计数器的内容
  • 流程
• 上下文切换的消耗
• 上下文切换与模式切换

多种作业、进程调度算法比较表格

死锁

死锁的概念

• 定义
• 死锁产生的原因
  • 资源竞争
  • 进程推进顺序非法
• ❗死锁产生的必要条件
  • 互斥条件
  • 不剥夺条件
  • 请求并保持条件
  • 循环等待条件
    • 循环等待不等于死锁（当同类资源数大于1）
    • 当同类资源只有1个时，循环等待就是死锁产生的充分必要条件
• 死锁的处理策略
  • 死锁预防
  • 避免死锁
  • 死锁的检测与解除

死锁预防

• 破坏互斥条件
• 破坏不剥夺条件
  • 请求新的不行，则放弃旧的
  • 请求新的不行，则抢！
• 破坏请求并保持条件
  • 一次性申请所有需要资源，只有所有资源可用时才运行，在运行期间一直占有
  • 实现简单
  • 资源浪费，饥饿
• 破坏循环等待条件（资源顺序分配法）

死锁避免

• 系统安全状态
• ⭐银行家算法
  • 合理范围内吗
  • 尝试分配
  • 用安全算法检测
    • 如果存在安全序列则确认分配
    • 如果不存在…，则撤回分配

死锁检测和解除

• 资源分配图
  • 资源
  • 进程
  • 请求边
  • 分配边
• 死锁定理：当且仅当资源分配图是不可完全简化的，死锁
• 死锁解除
  • 资源剥夺法
  • 撤销进程法
  • 进程回退法