操作系统复习.陈向群（03-05）（进程线程）

Posted on Edited on In Views:
进程线程模型、进程线程调度、进程线程同步模型

操作系统复习（03-05）

Chapter 03：进程线程模型

关键词

  • 进程、进程状态及状态转换、进程控制、进程控制块、进程地址空间、进程上下文、线程、线程属性、Web 服务器、用户级线程、Pthreads、核心级线程 、原语、可再入程序

思考题

  • 怎样理解 “进程是对 CPU 的抽象” 这句话？
  • 一个程序要经过哪些准备工作才能运行(程序怎样变成进程) ？
  • 进程有哪些状态？状态之间转换的条件以及对应的操作？
  • 一个进程在生命周期内都由哪些要素组成？
  • 从静态和动态两个角度，怎样观察进程？
  • 进程与程序是一样的吗？你能用日常生活中的例子解释什么是进程、什么是程序吗？
  • 什么是可再入程序？为什么进程执行的程序要具备可再入特性？
  • 哪些应用场景需要多线程支持？
  • 线程的基本概念是什么？与进程是什么关系？
  • 线程有哪些属性？为什么线程要有自己的栈？
  • 线程实现机制有哪几种？
  • 典型的操作系统都是怎样支持线程的？
  • Linux 是怎样支持线程的？ Linux内核是否区分进程和线程？

内容

基本概念

  • 多道程序设计
  • 并发环境与并发程序
    • 如下都可以认为是并发

  • 进程
    • 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位

进程模型

  • 三状态
    • 运行态（Running）、就绪态（Ready）、等待态（Waiting/Blocked）

  • 5 状态
    • 创建（New）、终止（Terminated）、挂起（Suspended）
      • 挂起：把一个进程从内存转到磁盘

  • 7 状态

  • Linux 进程模型

  • 数据结构 PCB
    • PCB 是系统感知进程存在的唯一标志
  • PCB 内容
    • 进程描述信息、进程控制信息、所拥有的资源和使用情况、CPU 现场信息
  • 进程地址空间

  • 上下文切换
  • 进程表
    • 每类进程维护一个或者多个队列

进程控制

  • 原语
    • 原子操作
  • 进程的创建
  • 进程的撤销
  • 进程阻塞与进程唤醒
  • UNIX 系统设计的进程控制操作
    • fork、exec、wait、exit
  • copy-on-write 技术
  • 进程的分类
    • 系统进程、用户进程
    • 前台进程、后台进程
    • CPU 密集型进程、I/O 密集型进程
  • 进程的层次结构
    • UNIX进程家族树：init 为根
    • Windows：地位相同

线程模型

  • 为什么在进程中再派生线程？
    • 应用的需要
      • web 服务器
    • 开销的考虑
      • 创建、撤销、通信、切换
    • 性能的考虑
      • 并行
      • 多处理器
  • Web 服务器的 3 种实现方式
模型 特性
多线程 并行性、阻塞系统调用
单线程进程 无并行性、阻塞系统调用
有限状态机 并行性、非阻塞系统调用、中断
  • 线程：进程中一个运行实体，是 CPU 的调度单位
    • 轻量级进程
  • 单线程进程模型、多线程进程模型

  • 线程的实现
    • 用户级线程：Linux
      • 大多数系统调用是阻塞的，因此，由于内核阻塞进程，故进程中所有线程也被阻塞
        • 修改系统调用为非阻塞的
        • 重新实现对应系统调用的I/O库函数
    • 核心级线程：Windows
    • 混合：Solaris
      • 用户空间创建、核心态调度
      • 多个用户级线程多路复用多个内核级线程

  • Solaris
    • Solaris 的多线程模型中包括四种实体
      • 进程，内核线程，用户线程、轻量级进程（LWP）
      • LWP 把用户线程和内核线程绑定到一起

  • 可再入程序（可重入）
    • 可被多个进程同时调用的程序，具有下列性质
      • 它是纯代码的，即在执行过程中自身不改变
      • 调用它的进程应该提供数据区

Chapter 04：进程线程调度

关键词

  • 调度层次、调度时机、进程切换、调度算法设计原则、抢占与非抢占、时间片、饥饿、调度算法、优先级反转、吞吐量、周转时间、响应时间、Linux调度算法、Windows 线程调度

思考题

  • 所谓调度仅仅是指的CPU(处理器)调度吗？
  • 怎样描述进程的优先级？
  • 就绪队列有哪些组织方式？
  • 有哪些引发调度的原因？
  • 衡量调度算法的指标有哪些？怎样选取？
  • 怎样区分抢占式和非抢占式调度思想？
  • 操作系统内核怎么实现抢占式调度策略的？
  • 时间片轮转算法是抢占式调度算法吗？
  • 操作系统的调度机制很好地体现了机制和策略分离 的原则，请举例说明这一点
  • 请同学们上网查一查, 1997年，美国发射的探测器‘探路者号”在火星上究竟发生了什么？请回答：
    • 这个故事涉及到进程调度的哪个知识点？
    • 故事中涉及到的是哪一个操作系统？
    • 运行过程中“ 探路者号” 遇到了什么问题？
    • 这个问题产生的原因是什么？
    • 工程师们是怎么解决这个问题的？
    • 这件事给我们什么启示？

内容

  • 调度的 3 个层次
    • 长程调度：作业调度或宏观调度
    • 中程调度：进程在内外存之间的交换
    • 短程调度：微观调度（毫秒级）
  • 处理器调度
    • 系统空闲进程、idle 进程
    • 调度程序
  • 三个问题：调度算法、调度时机、调度过程
  • 调度时机：事件发生
    • 内核对中断/异常/系统调用处理后返回到用户态前最后时刻
  • 调度过程：进程切换
    • 全局页目录
    • 内核栈、硬件上下文
    • 保存旧的，恢复新的
  • 上下文切换开销
    • 直接开销
    • 间接开销：高速缓存 Cache、Buffer Cache、TLB

调度算法

  • 目标
    • 交互式进程（interactive process）：响应时间、均衡性
    • 批处理进程（batch process）：吞吐量、周转时间、CPU利用率
    • 实时进程（real-time process）：最后期限、可预测性
  • 评价指标
    • 公平性 Fairness
    • 吞吐量 Throughput
    • 周转时间 TT (Turnaround Time)：提出请求到完成
    • 响应时间 RT (Response Time)
    • CPU 利用率 (CPU Utilization)
    • 等待时间 (Waiting time)
调度算法要点
  • 进程优先级
  • 进程就绪队列组织
    • 按优先级排队、多级队列

  • 抢占与非抢占
  • I/O 密集型与 CPU 密集型进程
  • 时间片
    • 长短、长短是否一致、是否可变
批处理系统中采用的调度算法
  • 先来先服务（FCFS-First Come First Serve）
  • 最短作业优先（SJF-Shortest Job First）
  • 最短剩余时间优先（SRTN-Shortest Remaining Time Next）
    • SJF 的抢占版本
  • 最高响应比优先（HRRN-Highest Response Ratio Next）
    • 响应比 R = 作业周转时间 / 作业处理时间 = 1 +（作业等待时间 / 作业处理时间）
    • 抢占版本、不可抢占版本
交互式系统中采用的调度算法
  • 轮转调度（RR-Round Robin）
    • 对于相同大小的进程不利（平均周转时间）
  • 优先级调度（HPF-Highest Priority First）
    • 通常而言
      • 系统进程优先级 高于 用户进程
      • 前台进程优先级 高于 后台进程操作
      • 系统更偏好 I/O 型进程
    • 优先级反转问题（抢占才会出现）
      • 设置优先级上限（优先级天花板协议 priority ceiling protocol）
      • 优先级继承
        • 阻挡了谁就继承谁
      • 使用中断禁止
  • 多级队列（Multiple queues）与多级反馈队列（Multiple feedback queue）
  • 最短进程优先（Shortest Process Next）
Windows 调度算法
  • 动态优先级、抢占式
  • 具体算法
  • 线程优先级提升与时间配额调整
Linux 调度算法

多处理器调度
  • 负载均衡、迁移开销（直接、间接）
  • 静态进程分配、动态进程分配

Chapter 05：进程线程同步模型

关键词

  • 临界区、进程互斥、进程同步、信号量、PV 操作、管程、生产者消费者问题、读者写者问题、 条件变量、wait/signal、锁、Pthreads、Hoare 管程

思考题

  • 课件第 17 页，如果把判断标志然后谖置标志实现为 lock()，则lock() 应该满足 什么性质？
  • 当有进程在临界区时，有两种处理方式: (1) 一直占用 CPU 等待进入临界区; (2) 阻塞等待。试问前者的效率一定比后者的效率低吗？
  • 课件 25-26 页， “睡眠” 与“唤醒”操作都是原语操作，为什么用它们解决生产者消费者问题时依然可能出错？在什么场景下会出错？简单思考一下如何解决？
  • 课件32页上给出的 PV 操作的定义与参考书《现代操作系统》或 ICS 课上的定义不同，但效果是否一样？请解释一下
  • 请简单总结一下JAVA语言对管程的支持
    • 如何解决互斥问题？
    • 如何解决同步问题？
  • 课件第 80 页上锁的实现代码是否正确？为什么？第 81 页的解决方案是不是对的？第 82 页的呢？请解释一下 83 页的方案
  • 阅读一下课件第 91 页上的例子，总结一下在用消息传递实现生产者消费者问题时，send 和 receive 的作用
  • 请举一个简单的例子，说明 Linux 的共享内存机制的应用

内容

  • 进程：并发、共享、不确定性
  • 顺序环境：程序执行的顺序性
  • 并发环境
  • 进程前趋图
  • 竞争条件（race）
  • 进程互斥
    • 临界资源（critical resource）
    • 临界区（critical section/region）
  • 临界区使用规则
    • 有空让进、无空等待、有限等待
    • 多中择一、让权等待
  • 进程的同步
    • 某种时序关系
  • 实现进程互斥的方案
    • 软件解法：Dekker、Peterson
    • 硬件解法：中断屏蔽方法、测试并加锁（TSL）
  • 生产者消费者问题（有界缓冲区）

信号量及 PV 操作

  • PV 操作是原语操作
  • 信号量
    • 初始化（非负数），P 操作、V 操作
  • 生产者消费者问题（有界缓冲区）
  • 读者写者问题
    • 读者优先

管程

  • 由关于共享资源的数据结构及在其上操作的一组过程组成
  • 进程只能通过调用管程中的过程来间接访问管程中的数据结构
  • 两个问题：同步、互斥
Hoare 管程
  • 管程中的两个进程，P 唤醒 Q：P 等待，Q 运行

  • 条件变量：在管程内部说明和使用的一种特殊类型的变量
    • var c:condition;
    • 对于条件变量，可以执行 wait 和 signal 操作
  • wait(c)
    • 如果紧急等待队列非空，则唤醒第一个等待者，否则释放管程的互斥权
    • 执行此操作的进程进入c 链尾部
  • signal(c)
    • 如果 c 链为空，则相当于空操作，执行此操作的进程继续执行
    • 否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的尾部
Mesa 管程
  • signal \(\to\) notify
    • notify：当一个正在管程中的进程执行 notify(x) 时，它使得 x 条件队列得到通知，发信号的进程继续执行
  • notify 的结果：位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行
    • 得用 while 再次判断条件
  • 超时则改为就绪（优化），但是还是得判断条件
    • 避免 notify 的程序炸掉导致无法被唤醒
  • broadcast 原语：全唤醒成就绪