文档
计算机科学
操作系统
进程

进程

  • 进程
    • 定义
      • 进程是程序的一次执行过程，是程序在一个数据集合上顺序执行时发生的活动。
      • OS 用进程描述系统的并发活动。
    • 特性
      • 动态性：进程是一次执行过程，是临时的，具有生命周期。
      • 独立性：进程是系统进行资源分配和调度的独立单元（没有线程时），进程之间相对隔离。
      • 并发性：多个进程可以交替执行。
      • 结构性：OS 为每个进程建立进程控制块（PCB），结构化地描述进程信息。
    • 与程序的区别
      • 程序是静态、永久的，进程是动态、暂时的。
      • 程序一般可以在计算机之间迁移，进程只有在一个 OS 的范围内。
      • 进程包括程序、数据、PCB。
      • 一个程序多次执行可以对应多个进程，一个进程可以通过调用包括多个程序。
      • 进程可以创建进程，程序自身不能产生新程序。
  • PCB
    • 定义
      • PCB 是进程的唯一标识，也包括进程的各种信息。
    • 内容
      • 进程标识数/PID：区分不同进程的 ID。
        • 可以有外部标识符，提供用户使用。
      • 状态、调度、存储器管理信息：调度所需的必要信息
        • 状态：描述进程所处的生命周期阶段。
        • 调度：优先级等。
        • 存储器：程序在主存、外存的地址等。
      • 资源：使用的设备、打开的文件等资源。
      • CPU 现场保护区：执行时的 CPU 上下文
        • PC
        • 程序状态字（PSW）
        • SP
        • 各种通用寄存器
        • …
      • 记账信息：使用 CPU 时间量、运行的用户等。
      • 家族关系：记录父子进程信息。Windows 无。
      • 进程链接指针：记录相同状态的进程（如兄弟进程）。
    • 实现
      • PCB 可能拆分，如 Windows 使用 EPROCESS 表示 PCB，其中包含 KPROCESS，仅内核使用。
    • 状态
      • 分类
        • 创建态：进程刚被创建，还进入就绪态，没有被调度。
        • 运行态：正在 CPU 上运行。
        • 阻塞态：正在等待某些资源，无法继续运行。
        • 就绪态：不在 CPU 上运行，但是没有等待的资源，可以随时被 CPU 继续执行。
        • 终止态：进程已经正常或异常结束，但是相关数据没有被清理，仍然驻留在系统中。
      • 转移
        • process-state-transition
        • 运行态 to 阻塞态：启动 IO 设备，导致进程需要等待。
        • 阻塞态 to 就绪态：IO 完成，设备发生中断，中断处理程序把阻塞进程改为就绪。
        • 运行态 to 就绪态：调度被抢占或进程主动让出。
        • 就绪态 to 运行态：进程被分配到 CPU。
    • 组织方式
      • 线性表：PCB 都放在一个数组中。
      • 链表：PCB 之间用指针相连。
        • 可以拆分为多个链表，每个链表表示不同状态。
        • 对于阻塞态进程，可以按照阻塞原因继续拆分链表。
  • 控制
    • 定义
      • 系统使用特定代码完成进程的创建、撤销、状态切换的过程。
      • 进程控制由内核实现。
      • 进程控制操作是原语，不能中断。
    • 分类
      • 创建原语
        • 调用时机
          • 批处理系统：每次提交作业时。
          • 分时系统：每个用户登录时，创建终端进程。
          • 交互式系统：运行命令、点击图标时。
          • DE：打开新窗口时，每个窗口对应一个进程。
          • *nix：fork()、execve() 等。
          • Windows：CreateProcess()。
        • 步骤和功能
          • 找到并分配一个未初始化的 PCB。
          • 为新进程的分配内存，包括程序代码、数据、栈等。
          • 初始化 PCB，填入 PCB 包含的所有信息。
          • 把新进程加入就绪队列。
      • 撤销原语
        • 调用时机
          • *nix 调用 exit()，Windows 调用 ExitProcess()。
        • 步骤和功能
          • 在 PCB 集合中找到对应进程的 PCB。
          • 终止此进程的子进程。
          • 释放资源。
          • 撤销 PCB。
      • 阻塞原语
        • 调用时机
          • 进程等待事件或资源时，自动执行。
        • 步骤和功能
          • 中断 CPU 执行。
          • 保持 CPU 现场信息至 PCB。
          • 切换进程状态为阻塞态。
          • 加入进程到相应事件的阻塞队列。
          • 转入到调度其他进程的过程。
        • *nix 的相关函数
          • sleep()：使进程休眠指定时间，进入阻塞态。
          • pause()：使进程挂起，直到收到信号才恢复。
          • wait()：等待子进程结束，当前进程阻塞。
      • 唤醒原语
        • 调用时机
          • IO 完成后发出中断，CPU 处理中断，唤醒阻塞进程，设置为就绪态。
          • 其他进程发送消息给等待进程。
        • 步骤和功能
          • 类似阻塞。
        • *nix 的相关函数
          • wakeup()：唤醒等待某事件的进程，使其进入就绪态。
      • 挂起原语
        • 步骤和功能
          • 实时系统：根据实时现场需要，把正在执行或没有执行的进程暂停一段时间，切换为静止状态。
          • 分时系统：把进程从内存换到外存，不能被调度。
      • 解挂原语
        • 步骤和功能
          • 与挂起相反。
          • 进程恢复为就绪态后，通常立即转入进程调度。（不一定立刻执行）
  • 调度
    • 定义
      • 为进程分配处理器资源。
    • 级别
      • 作业调度：高级调度。
      • 进程调度：低级调度。
      • 交换调度：中级调度。
        • 把暂不具备运行条件的进程换出到外存交换区。主存就绪和主存阻塞的进程都可能被换。
        • 把外存交换区中具备运行条件的进程换进主存。
        • 可以控制进程对主存的使用。
    • 功能
      • 记录进程执行情况：及时记录进程的状态、资源需求情况到 PCB。
      • 选择就绪进程占有 CPU。
      • 进行进程的上下文切换。
    • 上下文
      • 用户级：进程的程序、数据、用户栈。
      • 寄存器级：CPU 现场信息。
      • 系统级：PCB、内核栈等。
    • 分类
      • 非抢占式：进程一直占用 CPU，直到完成或必须阻塞。
        • 用于批处理系统。
      • 抢占式：调度程序可以剥夺进程的 CPU 给其他进程。
        • 用于分时系统、实时系统。
    • 时机
      • 当前进程完成或错误终止。
      • 等待 IO 资源。
      • 时间片用尽。
      • 更高优先级进程就绪。
      • 调用相关原语，包括阻塞和唤醒。
    • 算法
      • 先来先服务/FCFS
        • 遇到大作业，增加平均周转时间。
      • 最短作业优先/SJF
        • 遇到大量短作业，导致长作业饥饿。
      • 相应比高者优先/HRN
        • 相应比 Rp=TrTe=Tw+TeTe=1+TwTe\text{Rp} = \dfrac{T_r}{T_e} = \dfrac{T_w + T_e}{T_e} = 1 + \dfrac{T_w}{T_e}。
          • 其中 TrT_r 为估计周转时间，TeT_e 为估计运行时间，TwT_w 为等待时间。
        • 结合了 FCFS 和 SJF。
        • 实现比较复杂。
      • 优先级调度
        • 分配 CPU 给最高优先级的就绪进程。
        • 静态优先级：在进程创建时就确定的固定优先级。系统进程优先级更高。
        • 动态优先级：根据占用 CPU 时间和等待 CPU 时间调整。
      • 轮转法/RR
        • 划分时间片，每个时间片调度一个就绪进程，轮流执行。
        • 需要使用定时时钟中断，时间片结束后发出中断，中断处理程序转入调度。
        • 时间片过短导致调度开销大，时间片过长导致响应慢。
      • 多级反馈队列轮转法
        • 将就绪进程分为多个队列，每个队列分配不同的时间片长度和优先级，队列分前后台。
        • 前台队列使用 RR，后台使用 FCFS。
        • 新进程、等待 IO 的进程先进入高优先级队列，2~3 个时间片用完未完成则降到下一队列。
        • 优先调度高优先级队列中的进程。
        • 高优先级进程分配短时间片，低优先级分配长时间片。
      • 时间驱动法
        • 用于实时系统。
        • 任务调度按照预先确定的方式进行，调度程序按顺序执行任务。
      • 加权轮转法
        • 每个时间片的长短由进程的权重确定。
OS 概论线程