操作系统-Part2

操作系统-Part2——进程管理

[TOC]

进程与线程

进程的概念、组成、特征

• 概念

  • 程序：是静态的，是存放在磁盘的可执行文件。
  • 进程：是动态的，是进程实体的运行过程，是能独立运行、独立获得资源、独立接受调度的基本单位。
    • 进程实体（进程映像）：是静态的，一个进程实体由 PCB、程序段、数据段组成。
    • 进程实体（进程映像）反应了进程某一时刻的状态
  • 同一个程序多次执行会对应多个进程

• 组成（严格地来说是进程实体的组成）

  • 进程控制块（Process Control Block，PCB）
    • 
      • 进程描述信息：用于区分各个进程
      • 进程控制和管理信息：用于实现操作系统对进程的控制、调度
      • 资源分配清单：用于实现对资源的管理
      • 处理机相关信息：用于实现进程切换
    • 其中，进程标识符 PID 是唯一的、不重复的，即使进程已经被杀死
    • 操作系统对进程进行管理工作所需的所有信息，都存在 PCB 中
    • PCB 是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其 PCB。
  • 程序段与数据段
    • PCB 是给操作系统用的。程序段、数据段是给进程自己用的。
    • 程序段：程序的代码（指令序列）
      • 一个应用的多个进程拥有相同的程序段
    • 数据段：运行过程中的各种数据（变量）
      • 一个应用的多个进程拥有不同的数据段

• 特征

  • 
  • 动态性是进程最基本的特征
  • 引入线程之后，进程不再是独立接受调度的基本单位，但仍是独立获得资源的基本单位

进程的状态与转换、进程的组织

进程的状态与转换

• 状态转换过程
  • 
  • 创建态（New，新建态）：进程正在被创建。在这个阶段，操作系统会为进程分配资源、初始化 PCB
  • 就绪态（Ready）：仅缺少 CPU，具备其他所有运行条件，随时可以被处理运行
  • 运行态（Running）：进程正在 CPU 上运行
    • 多核 CPU 可能有多个进程处于运行态
  • 阻塞态（Waiting/Blocked，等待态）：进程主动请求等待某个事件的发生（资源分配或其他进程响应）
    • 即除 CPU 之外还缺少必要的条件，只有被动获得其余条件，才能转化成就绪态
  • 终止态（Terminated，结束态）：执行 exit 系统调用，或出现终止异常。进程下 CPU、回收内存空间等资源、回收该进程的 PCB，彻底消失。
• 三种基本状态：运行态、就绪态、阻塞态
• 不能由阻塞态直接转为运行态，也不能由就绪态直接转为阻塞态。
• 进程 PCB 中，会有一个变量 state 来表示进程的当前状态

进程的组织

• 链接方式
  • 按照进程状态将 PCB 分为多个队列
  • 操作系统持有各个队列的指针
• 索引方式
  • 根据进程状态的不同，建立索引表
  • 操作系统持有各个索引表的指针

进程控制

• 基本概念

  • 进程控制：实现进程状态转换
  • 进程控制的实现方式：原语
    • 原语的执行具有原子性，运行必须一气呵成，不可中断
    • 进程控制/状态转换，不可中断
    • 通过关/中断指令这两个特权指令实现原子性
    • 进程控制必定是内核程序，需要运行在核心态

• 进程控制相关原语

  • 进程的创建
    • 
    • 作业调度：将位于外存后备队列中的作业调入内存
  • 进程的终止
    • 
  • 进程的阻塞、进程的唤醒
    • 
    • 阻塞和切换必定成对出现
  • 进程的切换
    • 
    • 通过 PCB 恢复运行环境

• 无论哪个进程控制原语，要做的无非三类事情：

  • 更新 PCB 中的信息（修改进程状态，保存/恢复运行环境）
    • 所有的进程控制原语一定都会修改进程状态标志
    • 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
    • 某进程开始运行前必然要恢复期运行环境
  • 将 PCB 插入合适的队列
  • 分配/回收资源

进程通信

• 基本概念
  • 进程通信（Inter-Process Communication， IPC）是指两个进程之间产生数据交互。
  • 进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
    • 为了保证安全，一个进程不能直接访问另一个进程的地址空间。
• 共享存储
  • 为避免出错，各个进程对共享空间的访问应该是互斥的。
  • 基于数据结构的共享：
    • 比如共享空间里只能放一个长度为 10 的数组。
    • 速度慢、限制多，是一种低级通信方式
  • 基于存储区的共享：
    • 操作系统在内存中划出一块共享存储区。数据的形式、存放位置都由通信进程控制，而不是操作系统。
    • 速度很快，是一种高级通信方式。
    • 
• 消息传递
  • 进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。
  • 直接通信方式
    • 消息发送进程要指明接收进程的ID
    • 
  • 间接通信方式
    • 通过“信箱”间接地通信。因此又称“信箱通信方式”
    • 
• 管信通信
  • “管道”是一个特殊的共享文件，又名 pipe 文件。其实就是在内存中开辟一个大小固定的内存缓冲区（循环队列）
  • 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现全双工通信，则需要设置两个管道。
  • 各进程要互斥地访问管道（由操作系统实现）
  • 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
  • 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
  • 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：
    • 一个管道允许多个写进程，一个读进程（2014年408真题高教社官方答案）；
    • 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。
  • 只要管道没空，读进程就可以从管道读数据；只要管道没满，写进程就可以往管道写数据。

线程的概念与特点

• 线程是一个基本的 CPU 执行单元，是程序执行流的最小单位。
• 带来的变化：
  • 资源分配、调度
    • 传统进程机制中，进程是资源分配、调度的基本单位
    • 引入线程之后，进程是资源分配的基本单位，线程是调度的基本单位
  • 并发性
    • 传统进程机制中，只能进程间并发
    • 引入线程之后，各线程之间也能并发，提升了并发度
  • 系统开销
    • 传统的进程间并发，需要切换进程的运行环境，系统开销大
    • 线程间并发，如果是同一线程内的线程切换，则不需要切换进程环境，系统开销小
    • 引入线程后，并发带来的系统开销减小
• 线程属性：
  • 线程是处理机调度单位
  • 多 CPU 计算机中，各个线程可以占用不同的 CPU
    • （一般是一个进程占一个核。因为不同逻辑核心用的缓存是不同的，若一个进程同时用多个核，则数据调用会变得困难。但是考纲表明，一个进程可以占用多个核心，核心级线程是处理机分配的最小单位）
  • 每一个线程都有线程 ID、线程控制块（TCB）
  • 线程也有就绪、堵塞、运行三种基本状态
  • 线程几乎不拥有系统资源
  • 同一进程的不同线程共享进程的资源
  • 由于共享内存地址空间，同一线程中的线程间通信无需系统干预
  • 同一进程中的线程切换，不会引起进程切换；不同进程中的线程切换，会引起进程切换。
  • 切换同进程内的线程，系统开销很小；切换进程，系统的开销较大。

线程的实现方式和多线程模型

• 线程的实现方式

  • 用户级线程（User-Level Thread, ULT）
    • 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
    • 用户级线程中，线程切换可以在用户态下完成，无需操作系统干预。
    • 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。
    • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的开销小，效率高
    • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
    • 
  • 内核级线程（Kernel-Level Thread, KLT，又称“内核支持的线程”）
    • 内核级线程的管理工作由操作系统内核完成。
    • 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
    • 操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块），通过 TCB 对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
    • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
    • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
    • 

• 多线程模型

  • 一对一模型：（内核级线程）
    • 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
    • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
    • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
  • 多对一模型：（用户级线程）
    • 多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
    • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
    • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行，因为只有这一个进程只有一个内核级线程。
  • 多对多模型：
    • n 用户及线程映射到 m 个内核级线程（n>=m）。每个用户进程对应 m 个内核级线程。
    • 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
    • 

  • 用户级线程是“代码逻辑”的载体
  • 内核级线程是“运行机会”的载体
  • 注意：内核级线程才是处理机分配的单位。

处理机调度

调度的概念、层次

• 基本概念：确定某种规则来决定处理任务的顺序

• 三个层次

  • 高级调度（作业调度）
    • 作业：指一个具体的任务
    • 用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）
    • 按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。
    • 每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。
  • 中级调度（内存调度）
    • 内存不够时，将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。
    • 暂时调到外存等待的进程状态为挂起状态（suspend）。被挂起的进程 PCB 会被组织成挂起队列
    • 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
  • 低级调度（进程调度）
    • 从内存中的就绪队列中选取一个进程，将处理机分配给它。
    • 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
    • 进程调度的频率很高，一般几十毫秒一次。

• 补充

  • 进程的挂起态
    • 暂时调到外存等待的进程状态为挂起状态
    • 挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
  • 七状态模型
    • 注意：挂起和阻塞，两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。
    • 有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。
    • 

• 三个层次的联系、对比

  • 	内容	发生位置	发生频率	进程状态
    （高级）作业调度	从后备队列选择以创建进程	外存 -> 内存（面向作业）	最低	无 -> 创建态 -> 就绪态
    （中级）内存调度	从挂起队列选择以调回内存	外存 -> 内存（面向进程）	中等	挂起态 -> 就绪态
    （低级）进程调度	从就绪队列选择以分配 CPU	内存 -> CPU	最高	就绪态 -> 运行态

进程调度的时机、切换与过程、方式

• 进程调度的时机
  • 进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。
  • 
  • 需要进行进程调度与切换的情况
    • 当前进程主动放弃处理机
      • 进程正常终止
      • 发生异常而终止
      • 进程主动请求阻塞（如 等待I/O）
    • 当前进程被动放弃处理机
      • 分给进程的时间片用完
      • 有更紧急的事需要处理（如 I/O中断）
      • 有更高优先级的进程进入就绪队列
  • 不能进行进程调度与切换的情况
    • 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
    • 进程在操作系统内核程序临界区中。但是进程在普通临界区中是可以进行调度、切换的。
    • 在原子操作过程中（原语）。原子操作不可中断。（如修改 PCB 中进程状态标志，并把 PCB 放到相应队列）
  • 真题案例：
    • 进程在操作系统内核程序临界区中不能进行调度与切换。对
    • （2012年联考真题）进程处于临界区时不能进行处理机调度。错
    • 临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
    • 临界区：访问临界资源的那段代码。
    • 内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 PCB 组成）
      • 进程还未退出临界区时，临界资源（就绪队列）则一直处于上锁状态，则其他进程调度相关的程序就会被阻塞。
      • 内核程序临界区访问的临界资源如果不尽快释放，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度和切换。
    • 普通临界区
      • 在打印机打印完成之前，进程一直处于临界区内，临界资源（打印机）不会解锁。但打印机是慢速设备，如果不允许进程调度则会导致 CPU 一直空闲
      • 普通临界区资源（如打印机）不会影响到操作系统内核的管理工作。因此在访问普通临界区资源时可以进行调度与切换。
• 进程调度的方式
  • 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
    • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
  • 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
    • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统
• 进程的切换与过程
  • 进程调度与进程切换的区别：
    • 狭义的进程调度，指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
    • 进程切换，指一个进程让出处理机，由另一个进程占用处理机的过程。
    • 广义的进程调度，包含了选择一个进程和进程切换两个步骤
  • 进程切换的过程主要完成了：
    • 对原来运行进程各种数据的保存
    • 对新的进程各种数据的恢复
  • 进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

调度算法的评价指标

• CPU 利用率：指 CPU 忙碌的时间占总时间的比例。
• 系统吞吐量：单位时间内完成作业的数量
• 周转时间
  • 周转时间，指从作业被提交给系统开始，到作业完成为止的时间。
    • 包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待 I/O 操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
  • 带权周转时间必然 ≥ 1
  • 带权周转时间与周转时间都是越小越好
• 等待时间
  • 等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
  • 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
  • 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
• 响应时间：指从用户提交请求到首次产生响应所用的时间。

调度算法

• 各种调度算法的学习思路
  1. 算法思想
  2. 算法规则
  3. 作业调度 or 进程调度
  4. 抢占式 or 非抢占式
  5. 优点 and 缺点
  6. 是否会导致饥饿/饿死
• FCFS、SJF/SPF、HRRN 适合用于早期的批处理系统；时间片轮转、优先级调度、多级反馈队列适合用于交互式系统

先来先服务

• 先来先服务（FCFS, First Come First Serve）
  • 算法思想：主要从“公平”的角度考虑
  • 算法规则：按照到达的先后顺序进行服务
  • 调度对象：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
  • 是否抢占：非抢占式
  • 优点：公平、算法实现简单
  • 缺点：
    • 带权周转时间很大。
    • 公平
    • 对长作业有利，对短作业不利。
  • 是否会导致饥饿/饿死：不会

最短作业优先

• 短作业优先（SJF, Shortest Job First）

  • 算法思想：追求最少的平均等待时间、平均周转时间、平均带权周转时间
  • 算法规则：要求服务时间最短的作业/进程优先得到服务
  • 调度对象：作业/进程调度皆可。用于进程调度称为，短进程优先算法（SPF, Shortest Process First）
  • 是否抢占：SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
    • SJF：仅在每次调度时选择当前已到达且运行时间最短的作业/进程。
    • SRTN：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。
  • 优点：“最短的”平均等待时间、平均周转时间
  • 缺点：
    • 不公平。
    • 对短作业有利，对长作业不利。
    • 可能产生饥饿现象。
    • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
  • 是否会导致饥饿/饿死：会

• 注意：

  • 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
  • “SJF 调度算法的平均等待时间、平均周转时间最少”，严格来说，这个表述是错误的，不严谨的。
    • 在所有进程同时可运行时，采用 SJF 调度算法的平均等待时间、平均周转时间最少
    • 在所有进程都几乎同时到达时，采用 SJF 调度算法的平均等待时间、平均周转时间最少
    • 抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRNT算法）的平均等待时间、平均周转时间最少

最高响应比优先

• 高响应比优先（HRRN, Highest Response Ratio Next）
  • 算法思想：综合考虑作业/进程的等待时间和要求服务的时间
  • 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
    • 响应比 =（等待时间+要求服务时间）/ 要求服务时间
  • 调度对象：即可用于作业调度，也可用于进程调度
  • 是否抢占：非抢占式
  • 优缺点：
    • 综合考虑了等待时间和运行时间（要求服务时间）
    • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
    • 要求服务时间相同时，等待时间长的优先（FCFS 的优点）
    • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
  • 是否会导致饥饿/饿死：不会

时间片轮转

• 时间片轮转（RR，Round-Robin）
  • 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  • 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
  • 调度对象：进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
  • 是否抢占：抢占式。由时钟装置发出时钟中断来通知 CPU 时间片已到
  • 优点：公平；响应快，适用于分时操作系统；
  • 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
  • 是否会导致饥饿/饿死：不会
• 注意：
  • 当同时有进程 a 下处理机、有进程 b 到达，则默认新到达的进程先进入就绪队列
  • 进程主动放弃处理机，则立刻调度下一个进程上处理机，并且不影响下一个进程的时间片周期
  • 通常，设计时间片要让切换进程的开销占比不超过 1%
    • 时间片不能太大：否则，将使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。
    • 时间片不能太小：否则会导致进程切换过于频繁，而进程调度、切换都有时间代价（保存、恢复运行环境）。

优先级调度

• 优先级调度算法
  • 算法思想：根据任务的紧急程度来决定处理顺序
  • 算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的
  • 调度对象：作业、进程、I/O 调度
  • 是否抢占：抢占式、非抢占式都有。
    • 非抢占式只需在进程主动放弃处理机时进行调度即可
    • 抢占式另外还需在就绪队列变化时，检查是否会发生抢占
  • 优点：
    • 用优先级区分紧急程度、重要程度，适用于实时操作系统。
    • 可灵活地调整对各种作业/进程的偏好程度。
  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
  • 是否会导致饥饿/饿死：会
• 注意：
  • 优先数要按照题意判断：优先数越大（或者越小），优先级越高
  • 根据优先级是否可以动态改变，有两种分类
    • 静态优先级：创建进程时确定，之后一直不变。
    • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
  • 通常：
    • 系统进程优先级高于用户进程
    • 前台进程优先级高于后台进程
    • 操作系统更偏好 I/O 型进程（I/O 繁忙型进程）
      • 相对的是计算型进程（CPU 繁忙型进程）
  • 动态优先级调整策略
    • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
    • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
    • 如果发现一个进程频繁地进行 I/O 操作，则可适当提升其优先级

多级反馈队列

• 多级反馈队列

  • 算法思想：对其他调度算法的折中权衡
  • 算法规则：
    • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    • 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片。若用完时间片进程还未结束，则进入下一级队列队尾。如果已经在最下级队列，则重新放回该级队列队尾
    • 被抢占处理机的进程重新放回原队列队尾
    • 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片。
  • 调度对象：进程调度
  • 是否抢占：抢占式
  • 优缺点：
    • 对各类型进程相对公平（FCFS的优点）
    • 每个新到达的进程都可以很快就得到响应（RR的优点）
    • 短进程只用较少的时间就可完成（SPF的优点）
    • 不必实现估计进程的运行时间（避免用户作假）；
    • 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
  • 是否会导致饥饿/饿死：会

进程同步

进程同步、进程互斥

• 进程同步
  • 针对问题：进程具有异步性的特征。各并发执行的进程以各自独立的、不可预知的速度向前推进。
  • 同步亦称直接制约关系。指为了完成某种任务而建立的多个进程，因为需要在某些位置上协调工作次序而产生的制约关系。
• 进程互斥
  • 针对问题：一个时间段内只允许一个进程使用的资源称为临界资源。
  • 互斥，亦称间接制约关系。指当一个进程访问临界资源时，另一个想要访问该临界资源的进程必须等待，直到临界资源被释放
  • 
  • 注意：
    • 临界区是进程中访问临界资源的代码段。
    • 进入区和退出区是负责实现互斥的代码段。
    • 临界区也可称为“临界段”。
  • 四个原则：（为了实现对临界资源的互斥访问，同时保证系统整体性能）
    1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
    2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
    3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
    4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法（高频）

• 单标志法
  • 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。即，每个进程进入临界区的权限只能被另一个进程赋予
  • 主要问题：违背“空闲让进”原则。
  • 
• 双标志先检查
  • 算法思想：设置一个布尔型数组，用来标记各进程想进入临界区的意愿
  • 主要问题：违反“忙则等待”原则。
  • 问题原因：检查与上锁之间可能发生进程切换。
  • 
• 双标志后检查
  • 算法思想：先“上锁”后“检查”
  • 主要问题：违背了“空闲让进”和“有限等待”原则，会产生“饥饿”现象。
  • 
• Peterson 算法
  • 算法思想：结合双标志法（争取）、单标志法（谦让）的思想。主动争取、主动谦让、检查。
  • 主要问题：未遵循“让权等待”原则
  • 

进程互斥的硬件实现方法

• 中断屏蔽方法
  • 利用“开/关中断指令”实现
  • 优点：简单、高效
  • 缺点：
    • 不适用于多处理机。A 核执行了关中断，不影响 B 核使用相同的临界区。
    • 只适用于操作系统内核进程，不适用于用户进程（开/关中断指令只能运行在内核态）
• TestAndSet 指令
  • TS 指令，也称 TestAndSetLock（TSL）指令
  • TSL 指令是用硬件实现的，执行的过程不允许被中断
  • 
  • 优点：
    • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
    • 适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用 CPU 并循环执行TSL指令。
• Swap 指令
  • 也称 Exchange（XCHG）指令
  • Swap 指令是用硬件实现的，执行的过程不允许被中断
  • 
  • 优缺点：同 TestAndSet 指令

信号量机制

• 基本概念：
  • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
  • 信号量其实就是一个变量，用来表示系统中某种资源的数量。
  • 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。
  • 一对原语：wait(S) 原语和 signal(S) 原语，S 为信号量
  • wait、signal 原语常简称为 P、V 操作（来自荷兰语 proberen 和 verhogen），即 P(S)、V(S)
• 整型信号量
  • 用一个整数型的变量作为信号量。
    • 与普通整数变量的区别：对信号量的操作只有三种，初始化、P 操作、V 操作
  • 其实和 TS 指令差不多
  • 
  • 问题：不满足“让权等待”
• 记录型信号量
  • 用记录型数据结构表示的信号量。
    • 如果剩余资源数不足，使用 block 原语使进程从运行态进入阻塞态，并把挂到信号量 S 的等待队列（阻塞队列）中
    • 释放资源后，若还有别的进程在等待这种资源，则使用 wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
  • 
  • P(S)、V(S) 实现系统资源的“申请”和“释放”。
  • S.value 的初值表示系统中某种资源的数目。
  • P 操作：
    • 对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value–，表示资源数减 1。
    • 当 S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（**当前运行的进程从运行态 -> 阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中**。
    • 可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
  • V 操作：
    • 对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加 1。
    • 若加 1 后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应**调用 wakeup 原语**唤醒等待队列中的第一个进程（**被唤醒进程从阻塞态 -> 就绪态**）。

信号量的值 = 这种资源的剩余数量

P( S ) —— 申请一个资源 S，如果资源不够就阻塞等待

V( S ) —— 释放一个资源 S，如果有进程在等待该资源，则唤醒一个进程

信号量实现进程互斥、同步、前驱关系

• 实现进程互斥
  • 过程：
    • 分析并发进程的关键活动，划定临界区
    • 设置互斥信号量 mutex，初值为 1
    • 在进入区 P(mutex)——申请资源
    • 在退出区 V(mutex)——释放资源
    • 
  • 注意：
    • 对不同的临界资源需要设置不同的互斥信号量。
    • P、V 操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
• 实现进程同步
  • 过程：
    • 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作
    • 设置同步信号量 S，初始为 0
    • 在“前操作”之后执行 V(S)
    • 在“后操作”之前执行 P(S)
      • 信号量 S 代表“某种资源”，刚开始是没有这种资源的。P2 需要使用这种资源，而又只能由 P1 产生这种资源
      • 前 V 后 P
    • 
• 实现前驱关系
  • 过程
    • 为每一对前驱关系各设置一个同步信号量
    • 在“前操作”之后对相应的同步信号量执行 V 操作
    • 在“后操作”之前对相应的同步信号量执行 P 操作
    • 
  • 前驱关系问题，本质上就是多级同步问题。

生产者-消费者问题

• 问题描述：系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。生产者、消费者共享一个初始为空、大小为 n 的缓冲区。
• 问题分析：
  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。——同步
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。——同步
  • 缓冲区是临界资源，各进程必须互斥地访问。——互斥
• 算法实现：
  • 
• 注意：
  • 实现互斥的 P 操作一定要在实现同步的 P 操作之后。
  • V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。
  • 生产产品与使用产品可以放在 P、V 中间，但是这样会使得临界区代码变长
  • 有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的“一前一后问题”。因此，题目隐含两对同步关系，也需要设置两个同步信号量。

多生产者-多消费者

• 问题描述：桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
• 问题分析：
  • 对缓冲区（盘子）的访问要互斥地进行。——互斥
  • 父亲将苹果放入盘子后，女儿才能取苹果。——同步
  • 母亲将橘子放入盘子后，儿子才能取橘子。——同步
  • 只有盘子为空时，父亲或母亲才能放入水果。——同步
    • “盘子为空”这个事件可以由儿子或女儿触发。
• 算法实现
  • 
• 注意：
  • 当缓冲区容量为 1 时，则可能不设置专门的互斥变量 mutex，也不会出现多个进程同时访问盘子的现象。具体情况具体分析
  • 如果来不及仔细分析，完全可以加上互斥信号量，以保证各进程一定会互斥地访问缓冲区。互斥的 P 一定要在同步 P 之后。

解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。

在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。

• 如果从单个进程行为的角度来考虑的话，我们会有以下结论：
  • 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
  • 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
  • 意味着要设置四个同步信号量分别实现这四个“一前一后”的关系？
• 正确的分析方法应该从“事件”（面向过程）的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”
  • 盘子变空事件 -> 放入水果事件。
  • “盘子变空事件”既可由儿子（进程）引发，也可由女儿（进程）引发；“放水果事件”既可能是父亲（进程）执行，也可能是母亲（进程）执行。
  • 这样的话，就可以用一个同步信号量解决问题了

吸烟者问题

• 问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
• 问题分析：
  • 也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”。
  • 缓冲区大小为 1，每个吸烟者其实需要的是一个“组合”，且可以不设置互斥信号量
  • 
• 算法实现：
  • 

读者-写者问题

• 问题描述：
  • 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
  • 因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
• 问题分析：
  • 两类进程：写进程、读进程
  • 互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。
• 算法实现：
  • 读进程优先：
    • 
    • 问题：若两个读进程并发执行，则 count=0 时两个进程也许都能满足 if 条件，都会执行 P(rw)**，从而使第二个读进程阻塞**的情况。
    • 原因：在于对 count 变量的检查和赋值无法一气呵成
    • 解决：设置 mutex 互斥信号量来保证各读进程对 count 变量的互斥访问
    • 特点：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，该算法为读进程优先
  • 读写公平：
    • 
    • 精髓：在读者写者中 P(w)、V(w) 分别包住了写文件和没有包住读文件，因此可以保证写者与其他互斥，读文件可以并发

总结：

• 互斥 -> 读者写者；同步 -> 生产者消费者
• 对于读者共享，要设置计数器 count 来记录当前正在访问共享文件的读进程数。只有第一个/最后一个读进程需要进行 P、V 操作。
• 对于需要一气呵成的“检查和赋值” ，自然应该想到用互斥信号量实现。
• 解决“写进程饥饿”问题，需要通过写者来限制读者访问 count。

哲学家进餐问题

• 问题描述：一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
• 问题分析：因为需要同时持有两个临界资源，所以如果多个哲学家并发则可能出现循环等待，发生死锁。
• 算法实现：
  • 保证了“各哲学家拿筷子这件事必须互斥的执行”。
    • 即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家继续尝试拿筷子。
  • 并不能保证“仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子”。
  • 

管程

• 针对问题：编写程序困难、易出错
• 改进方向：将复杂部分封装为管程，对外仅暴露接口
• 组成：
  • 局部于管程的共享数据结构
  • 对该数据结构进行操作的过程
  • 对共享数据设置的初始值
  • 管程的名字
• 基本特征：
  • 共享数据只能由内部的过程操作
  • 一个进程只有通过调用管程的过程才能访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程
  • 其互斥特性是由编译器负责实现
  • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。
• 实现：（伪代码，不考）
  • 
  • JAVA 中的 synchronized 关键字

死锁

死锁的概念

• 死锁、饥饿、死循环
  • 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
  • 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。
  • 死循环：某进程执行过程中一直跳不出某个循环的现象。
• 共同点：都是进程无法顺利向前推进的现象
• 死锁、饥饿、死循环的区别
  • 数量：
    • 死锁：如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。
    • 饥饿：可能只有一个或多个进程发生饥饿。
    • 死循环：可能只有一个或多个进程发生死循环。
  • 原因：
    • 死锁：一定是“循环等待对方手里的资源”导致的
    • 饥饿：长期得不到需要的 I/O 设备或处理机
    • 死循环：代码逻辑的错误或者人为因素
  • 进程状态：
    • 死锁：一定处于阻塞态。
    • 饥饿：既可能是阻塞态，也可能是就绪态。
    • 死循环：可以是运行态
  • 死锁和饥饿，是由于操作系统分配资源的策略不合理导致的，是管理者（操作系统）的问题；死循环是被管理者的问题。
• 死锁产生的必要条件
  • 产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。
  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
  • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
• 注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）
  • 存在循环等待的同时，还存在其他可以获得资源的分支
  • 
• 发生死锁的情况（对不可剥夺资源的不合理分配）
  • 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
  • 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程 P1、P2 分别申请并占有了资源 R1、R2，之后进程 P1 又紧接着申请资源 R2，而进程 P2 又申请资源 R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
  • 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的 P 操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

死锁的处理策略

预防死锁（静态策略）

• 破坏互斥条件
  • 把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
  • 如：SPOOLing 技术把独占设备在逻辑上改造成共享设备。
    • 
  • 缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
• 破坏不剥夺条件
  • 方案一：当某个进程请求新的资源得不到满足时，必须立即主动释放保持的所有资源，以后需要时重新申请。
  • 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。
    • 这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
  • 缺点：
    • 实现起来比较复杂。
    • 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU。
    • 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
    • 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生放弃资源，就会导致进程饥饿。
• 破坏请求和保持条件
  • 采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
  • 缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
• 破坏循环等待条件
  • 采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源（持有 n 号资源时，不允许请求 <n 号的资源），同类资源（即编号相同的资源）一次申请完。
  • 缺点：
    • 不方便增加新的设备，因为可能需要重新分配所有的编号；
    • 进程实际使用资源的顺序可能和编号递增顺序不一致（必须先占有资源，但不使用），会导致资源浪费；
    • 必须按规定次序申请资源，编程麻烦。

避免死锁（动态策略）

• 安全序列，指如果系统按照这种序列分配资源，则每个进程都能顺利完成。

  • 只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个。
  • 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
    • 如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

• 注意：

  • 如果系统处于安全状态，就一定不会发生死锁；如果系统进入不安全状态，就可能发生死锁。
  • 处于不安全状态未必会发生死锁，但发生死锁时一定是在不安全状态

• 核心思想：

  • 在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

• 算法实现：

  • 假设系统中有 n 个进程，m 种资源

  • 数据结构：

    • n*m 矩阵 Max 表示各进程对资源的最大需求数

    • n*m 矩阵 Allocation 表示已经给各进程分配了多少资源

    • Max – Allocation = Need 矩阵表示各进程最多还需要多少资源

    • 长度为 m 的一维数组 Available 表示还有多少可用资源

    • 用长度为 m 的一位数组 Request 表示进程此次申请的各种资源数

  • 银行家算法步骤：

    • Request ≤ Need[i]：检查此次申请是否超过了之前声明的最大需求数
    • Request ≤ Available：检查此时系统剩余的可用资源是否还能满足这次请求
    • Available -= Request；Allocation[i] += Request；Need[i] -= Request：试探着分配，更改各数据结构
    • 用安全性算法检查此次分配是否会导致系统进入不安全状态（是否能找到安全序列）。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。

  • 

  • 

死锁的检测与解除

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：

• 死锁检测算法：

  • 用于检测系统状态，以确定系统中是否发生了死锁。
  • 算法实现：
    • 用某种数据结构来保存资源的请求和分配信息
    • 提供一种算法，利用上述信息来检测系统是否已进入死锁状态
    • 
    • 删去所有可以请求到足够资源（不阻塞）的进程节点的边
      • 最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（能找到一个安全序列）
      • 如果最终不能消除所有边，那么此时就是发生了死锁。
      • 化简资源分配图后，还连着边的那些进程就是死锁进程。
  • 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

• 死锁解除算法：

  • 当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

  • 解除死锁的主要方法有：

    1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。

    2. 撤销进程法（终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。

    3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

  • 确定解除对象进程：

    1. 进程优先级（优先级更高的进程先获得资源）

    2. 已执行时间（回退已执行时间越长的进程，代价越大）

    3. 预计完成花费时间（优先让快结束的进程获得资源）

    4. 进程已使用资源量（优先牺牲持有多资源的进程）

    5. 进程是交互式的还是批处理式的（优先牺牲批处理式进程）