进程管理

进程和线程

• 进程概念

  • 进程是指一个具有一定独立功能的程序在一个数据集合上的一次动态执行的过程
  • 进程包含了一个正在运行的程序的所有状态信息：代码、数据、状态寄存器、通用寄存器和进程占用系统资源 => 进程控制块
  • 进程是操作系统处于执行状态程序的抽象
  • 程序 => 文件
  • 进程 => 执行中的文件 => 程序 + 执行状态

• 进程的状态与转换
  • 进程创建：系统初始化时，用户请求创建一个新的进程 或 正在运行的进程申请创建新的进程。
  • 进程执行：内核通过调度算法选择一个就绪的进程开始执行。
  • 进程等待：请求并等待系统服务 或 启动过某种操作，导致无法马上完成进程的等待；比如需要的数据没有到达的等待。
  • 进程抢占：高优先级的进程就绪 或 当前执行的进程执行时间用完，被其他进程抢占。
  • 进程唤醒：被阻塞的进程需要的资源被满足；被阻塞的进程等待的事件到达（进程只能被其他进程或者操作唤醒，不能自身唤醒）
  • 进程结束：将进程占用的资源释放给操作系统（包括正常退出、错误退出、致命错误和被其它进程所杀等）
• 进程的控制与组织
  • 进程控制块：操作系统管理和控制进程运行所用的信息的集合

    • 进程控制块包括进程的基本信息（ID、程序） 和进程的变化过程（进程状态）
    • PCB是进程存在的唯一标示，每个进程在操作系统中都有唯一的PCB，PCB存放了 标识信息、处理机现场保存、进程控制信息等。
    • 进程地址空间包括：段表、共享库、栈、堆、初始化数据和代码

  • 调度队列和调度器TODO
  • 进程的创建和终止
    • 进程切换
      • 暂停当前运行的程序，从运行状态变为其他状态，调度另一个进程从就绪状态变为运行状态
      • 要求：切换前需要保证进程的上下文，切换后要恢复进程的上下文。切换速度要尽可能的快。
      • 要保存的信息：寄存器信息、CPU状态信息、内存地址空间
    • 进程创建
      • idleproc -> 分配idleproc需要的资源 -> 初始化PCB -> 完成初始化过程
      • fork()复制进程 -> exec()修改进程
      • pid -> 子进程的ppid
    • 进程等待和退出
      • 进程结束的时候调用exit(),完成对进程资源的回收

        • 资源回收的内容包括：将调用参数作为进程的结果结束、关闭所有打开的文件等占用资源、释放内存、释放大部分进程相关的内核数据结构、检查父进程是否存活（如果存活则保留返回值直到父进程需要，子进程进入僵尸状态；如果不存活，释放所有数据结构，进程结束）、清理所有处理等待状态的僵尸进程

      • 父进程在wait()的收检查子进程是否存活
• 进程概念与多线程模型
  • 作用：进程内部进一步提高并发性，线程间能直接通信和共享数据
  • 多线程的解决思路：实体间可以并发执行，实体间可以共享相同的地址，这种实体就是线程
  • 概念：线程是进程的一部分，描述指令流的执行状态。它是进程中指令流的最小单位，是CPU调度的基本单位。
  • 优点：一个线程中可以存在多个线程；各个线程之间可以并发执行；各个线程之间可以共享地址空间和文件等资源。
  • 缺点：一个线程的崩溃会导致该进程下面的所有线程的崩溃。

CPU调度

• 调度的基本概念

  • 基本概念：管理处理机执行能力资源的功能（对应进程切换，CPU资源当前占用者的切换）
  • 主要功能：从就绪队列中挑选下一个占用CPU资源运行的程序 + 从多个可用CPU中挑选出就绪进程可用使用的CPU资源
  • 调度程序：挑选就绪进程的内核函数

    • 调度程序需要考虑的方面有：1.调度策略，依据何种原则来挑选进程/线程；2.调度时机，什么时候进行调度

• 调度时机、切换与过程

  • 内核运行调度程序的条件：
    • 进程从运行状态切换到等待状态
    • 进程被终结
  • 针对非抢占系统的过程
    • 当前进程主动放弃CPU资源
  • 针对抢占系统的过程
    • 中断请求被服务器例程响应完成时
    • 当前进程被抢占（进程时间片耗尽，进程从等待状态切换到就绪）

• 调度的基本准则

  • 调度策略和调度算法比较指标

    • 进程在CPU计算和IO操作间交替进行，每次调度 决定在下一个CPU计算时哪个工作交给CPU，在时间片机制下，进程可能在结束当前CPU计算结束前因时间片耗尽而放弃CPU资源

  • 衡量调度算法的指标
    • CPU使用率（CPU忙的时间百分比，一般而言越高越好）
    • 吞吐量（单位时间内进程完成的数量。用户希望有更快的服务，如传输文件时的高带宽、调度算法时的高吞吐量）、
    • 周转时间（进程从进入初始化到结束的总时间）
    • 等待时间（进程在就绪队列中消耗的时间）
    • 响应时间（从提交请求到产生响应所消耗的总时间）
  • 调度算法指标的期望值
    • 减少响应时间、减少平均响应时间波动、增加吞吐量（减少开销，系统资源的高利用率）、减少等待时间（减少每个进程的等待时间）

• 调度方式TODO

• 典型调度算法

  • 先来先服务算法[FCFS]
  • 短作业[SJF]（短进程，短线程）优先调度算法
    • 将最短的作业提前的调度算法。响应的变种有：最短进程优先，最短作业优先调度，剩余时间最短优先调度
    • 缺点：预知进程的运行时间一般是不容易的，对长进程不利会出现进程饥饿的情况，人机无法交互，没有考虑到进程的紧迫程度
  • 最高响应比算法（Wait/(Wait+Run)）
    • 将等待时间过长的进程优先执行，总体保证不会出现进程饥饿
  • 时间片轮调度算法[RR]配合FCFS
    • 确定进程执行的最大时间长度限制，片轮执行过程按照先来先服务进行调度，在合理的时间限制下，会兼顾到每个进程的运行
  • 优先级调度算法
    • 事先规定好的优先级算法
  • 多级反馈队列调度算法[MFQ]
    • 将就绪队列排成多个子队列，综合几种算法得出的结果

同步与互斥

• 进程间的三种关系

  • 互斥：一个进程占用了资源，其他进程不能使用
  • 死锁：多个进程占用了部分资源，形成循环等待
  • 饥饿：其他进程轮流占用资源，某一个进程一直得不到资源

• 进程同步和临界区的基本概念

  • 进程同步：协调多线程对共享数据的访问，任何时刻都只能有一个线程执行临界区代码

  # 临界区操作其实是一个原子操作
  # 进入临界区
  Lock.Acquire()
  if bread:
      buy
  # 离开临界区
  Lock.Release()

  • 进程的相互关系

  相互感知的程度	交互关系	进程间的影响	Sample
  相互不感知（完全不了解其他进程的存在）	独立	对其它进程没有任何影响	A和B独立运行
  间接感知（双方与第三方交互，如共享资源）	通过共享进行协作	一个进程的结果依赖共享资源的状态	A和B独立运行，但是A修改数据库结果会对B的显示产生影响
  直接感知（双方直接交互，如通信）	通过通信进行协作	一个进程的结果依赖于从其他进程获取的消息	A中代码有发起B中的接口请求代码

  • 临界区相关
    • 临界区：进程中访问临界资源的一段需要互斥执行的代码（如数据库中的事务上锁）
    • 进入区：检查是否可以进入临界区的一段代码；如果可以进入，设置相应标志（上锁）
    • 退出区：释放锁
    • 剩余区：释放锁后执行的代码
  • 临界区的实现方法：禁用中断、软件方法、抽象方法

• 信号量

  • 概念：信号量是操作系统中提供的一种协调共享资源的方法，用信号量表示系统资源的数量。

    • 信号量 = (一个整型变量 + 两个原子操作（P()+V()）) 类比车站应用

• 使用信号量描述和解决经典同步问题

  • 互斥访问：每类资源设置一个信号量，初始值为1，必须要同时使用P（保证互斥访问临界资源）V（使用后释放资源）操作。
  • 条件同步：设置一个信号量，初始值为0。在要插入的地方加入P，插入结束的地方加入 V。以此完成条件等待以完成条件同步（数据库update操作参考）
  • 生产者消费者问题：
    • 要求：

      • 任何时刻只能有一个线程控制缓存区（互斥访问）
      • 缓冲区为空，消费者必须等待生产者（条件同步）
      • 缓冲区为满，生产者必须等待消费者（条件同步）

    • C++代码示例
  • 哲学家就餐问题：
    • 要求：略
    • 代码：略
  • 读者写者问题：
    • 要求：
      • 读者：读但不修改
      • 写者：读且修改
    • 需定义变量：
      • 信号量WriteMutex： 控制读写操作的互斥 初始化为1
      • 读者计数：RCount 正在进行读操作的读者个数
      • 信号量CountMutex：控制对读者计数的互斥 初始化为1
    • 代码：Go代码示例

死锁

• 死锁的概念
  • 概念：由于竞争资源或者通信关系，两个或者更多线程在执行中出现永远的互相等待只能由其他进程引发的事件。
  • 可重用资源：处理器，IO，存储器，文件，数据库，信号量等数据结构。每个进程占用部分资源而请求其它资源
  • 消费资源：IO缓冲区的中断，信号，消息等。进程间相互等待对方的消息
  • 出现死锁的必要条件：互斥、持有并等待、非抢占、循环等待
• 死锁的处理策略
  • 死锁预防（确保系统不会进入死锁状态）
  • 死锁避免（在使用前进行判断，只允许不会出现死锁的进程请求资源）
  • 死锁的检测和恢复（在检测到系统进入到死锁状态后，进行恢复）

    • 需要由应用程序检测死锁，因为系统通常会忽略死锁

• 死锁预防（限制申请的方式）
  • 概念：采用某种策略，限制并发进程对资源的请求，使系统在任何时候都不满足死锁的必要条件
  • 互斥预防：将互斥的共享资源改封装成可同时访问
  • 持有并等待预防：进程请求资源时，要求它不持有任何资源，仅允许进程开始执行时一次性请求所有需要的资源
  • 非抢占预防：如进程请求不能立即分配资源，则释放已占用资源，只有能同事获得所有资源时，才分配操作
  • 循环等待预防：对资源排序，要求进程按照顺序请求资源
• 死锁避免（利用额外的先验信息，在分配资源前判断是否会出现死锁，只在不会死锁时分配资源）
  • 死锁避免方法：要求声明需要资源的最大量，限定提供与分配的资源数量确保满足进程的最大需求，动态检查资源分配状态确保不会出现环形等待
  • 系统安全状态：当进程请求资源时，系统判断分配后是否处于安全状态；系统处于安全状态后，针对所有已占用进程，存在安全序列
  • 银行家算法：
    • 数据结构：
      • 记录系统状态（Max=线程数量*资源类型数量）
      • 剩余空闲量
      • 已分配量
      • 未来需要量
    • 安全状态判断
      • 判断剩余空闲量能否和某一个线程的需要量匹配
      • 如果有：分配给该线程并执行，执行完毕后回收资源
      • 如果无：系统状态不安全，无法执行，死锁避免
• 死锁的检测和解除
  • 步骤：
    • 1. 允许系统进入死锁状态
    • 2. 维护系统的资源分配图

         周期性调用死锁检测算法搜索是否有死锁

    • 3. 出现死锁时进行恢复
      • 数据结构：资源分配图应当为一个向量列表，最终构成一个矩阵
      • 死锁恢复：终止所有的死锁进程，一次只终止一个进程直到死锁结束
      • 终止进程的顺序：优先级、已运行时间、已占用资源、完成需要资源、终止进程数量等
      • 可能会导致的问题：
        • 选择被抢占的资源（最小成本目标）
        • 进程回退（返回到安全状态）
        • 可能饥饿（某一进程长时间被选为抢占者）