操作系统第二章--进程的描述与控制

前趋图和程序执行
- 前趋图
  - 前趋图是一个有向无循环图DAG，用来描述进程之间执行的前后关系
  - 初始结点：没有前趋的结点
  - 终止结点：没有后继的结点
  - 重量：表示该结点所含有的程序量或结点的执行时间
- 程序执行
  - 顺序执行
    - 顺序性
    - 封闭性：程序运行时独占全机资源
    - 可再现性
  - 并发执行
    - 间断性
    - 失去封闭性
    - 不可再现性
进程的描述
- 进程的定义和特征
  - 进程定义
    - 进程是程序的一次执行
    - 进程是一个程序及其数据在处理机上顺序执行时发生的活动
    - 进程是系统进行资源分配和调度的一个独立单位
  - 进程结构
    - 进程控制块PCB：使程序能独立运行
    - 程序段、相关的数据段、PCB
  - 进程特征
    - 动态性：它由创建而产生，由调度而执行，由撤销而消亡
    - 程序是指令集是静态的，进程是动态的
    - 并发性：多个进程实体在一段时间内同时进行
    - 独立性：进程实体是独立运行、独立分配资源和独立接受调度的基本单位
    - 异步性：各进程独立、异步（速度不一致）地运行
- 进程的基本状态和转换
  - 基本状态
    - 就绪状态：万事俱备，只差CPU资源
    - 执行状态：获得CPU资源，正在执行
    - 阻塞状态：由于突发事件，进程放弃处理机而处于暂停状态
  - 转换
    - 进程调度：就绪态-->运行态
    - 被高优先级任务抢占或超时：运行态-->就绪态
    - I/O请求：运行态-->阻塞态
    - I/O完成：阻塞态-->就绪态
- 挂起操作
  - 执行的进程暂停下来，处于静止状态
- 进程管理中的数据结构
  - 进程控制块的作用PCB
    - 独立运行基本单位的标志
    - 间断性运行：保护CPU现场
    - 进程管理：OS通过CPU对进程实施控制和管理
    - 进程调度：提供进程状态、优先级等信息
    - 进程同步与通信：消息队列指针，信号量
  - 进程控制块的内容
    - 进程标识符：唯一标识一个进程
      - 内部标识符：Pid
      - 外部标识符：进程的名字
    - 处理机状态：由各种寄存器内容构成
      - 通用寄存器
      - 指令计数器PC
      - 程序状态字PSW
      - 用户栈指针SP
    - 当进程切换时需要把当前进程的状态的内容保存在进程控制块中
    - 进程调度信息
      - 进程状态：sched.h定义了6个进程状态
        可运行状态
        可中断阻塞状态
        不可中断阻塞状态
        僵死状态
        暂停态
        交换态
      - 进程优先级
      - 其他信息：进程已执行时间
      - 事件：阻塞原因
    - 进程控制信息
      - 程序和数据地址：基地址
      - 进程同步和通信机制
      - 资源清单
      - 链接指针
  - 进程控制块的组织方式
    - 链接方式：指针指向PCB地址
    - 索引方式：通过不同状态的索引表指向PCB地址
    - 多级队列：按照不同状态组织PCB队列，同一状态按照优先级链接
进程控制
- 原语：由若干条指令组成，用于完成一定功能
  - 是原子操作，一个操作中的所有动作要么不做，要么全做
- 进程的创建
  - 进程图：描述一个进程的家族关系的有向图
    - 子进程可以继承父进程所拥有的资源
    - 当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程
    - 在撤销父进程时，也必须同时撤销其所有的子进程
  - 引导进程创建另一个进程的事件
    - 用户登录
    - 作业调度
    - 提供服务
    - 应用请求
  - 进程创建 fork（）函数
    - 申请空白PCB
    - 为新进程分配资源
    - 初始化进程控制块
    - 将进程插入就绪队列，启动调度
- 进程终止 exit（）函数
  - 根据被终止进程的PID，找到PCB，读取进程状态
  - 若处于执行状态，则终止执行，重新调度
  - 若有子孙进程，则终止所有子孙进程
  - 归还所有资源给父进程或系统
  - 从所在队列移除终止进程PCB
- 进程的阻塞与唤醒
  - 阻塞过程 block
    - 调用阻塞原语block把自己阻塞
    - 状态由执行改为阻塞，将PCB插入阻塞队列
    - 重新调度，将处理机分配给另一就绪进程
  - 唤醒过程 wakeup
    - 从阻塞队列中移除
    - 状态由阻塞改为就绪
    - PCB插入到就绪队列
- 进程的挂起与激活
  - 挂起原语 suspend
    - 检查被挂起进程的状态
      - 活动就绪：静止就绪
      - 活动阻塞：静止阻塞
    - PCB复制到指定区域
  - 激活原语 active
    - 检查激活进程的状态
      - 静止就绪：活动就绪
      - 静止阻塞：活动阻塞
进程的同步
- 进程同步的基本概念
  - 临界资源：互斥使用的资源
  - 临界区：访问临界资源的那段代码
- 信号量机制
  - 按照功能分为
    - 互斥信号量：0或1
    - 资源信号量：数字表示资源的可用个数
  - 按照机制分为
    - 整型信号量：定义一个整型量，wait、signal，P、V操作
    - 记录型信号量：不存在忙等现象
    - AND型信号量：同步机制，原子操作
    - 信号量集：分配多个资源
- 管程机制
经典进程的同步问题
- 生产者/消费者问题
  - 生产者和消费者进程共享一个大小固定的缓冲区n
  - 分别设置两个指针in和out
    - in指向生产者将存放数据的存储单元
    - out指向消费者将取出数据的存储单元
  - 创建信号量实现生产者和消费者进程的同步
    - 互斥信号量mutex：进程对缓冲池互斥使用
    - 资源信号量empty：空缓冲区的数量
    - 资源信号量full：满缓冲区的数量
- 读者/写者问题
  - 允许多个读者进程可以同时读数据
  - 写者进程互斥写数据
  - 若有写者进程正在写数据，则不允许读者进程读数据
  - 读者优先：只有当全部读者退出，才允许写者进入写数据
- 哲学家进餐问题
  - 记录型信号量：wait、signal考虑左筷子和右筷子（可能存在死锁）
  - AND信号量：Sswait、Ssignat
进程通信
- 进程通信的类型
  - 共享存储器系统
    - 基于共享数据结构的通信方式
    - 基于共享存储区的通信方式
  - 管道Pipe通信
    - 用于连接读写进程以实现通信的共享文件
  - 消息传递方式
    - 直接通信：利用OS提供的发送命令Send、Receive
    - 间接通信
      - 信箱：通过中间实体（如共享数据结构）
      - 消息队列：msgsnd、msgrcv、msgget
线程VS进程
- 调度：线程是调度分配的基本单位，进程是拥有资源的基本单位
- 并发性：线程并发执行效率更高
- 拥有资源：线程仅有少量资源来完成运行需求，不拥有系统资源
- 独立性：线程独立性更低
- 系统开销：切换线程系统开销低