201 进程与线程

进程与线程

进程的概念与特征

进程的定义

• 进程是程序的一次执行过程
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是具有独立功能的程序在一个数据集合上运行的过程
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• 为什么引入进程：
  • 为了使多道程序并发执行，提高资源利用率和系统吞吐量
  • 为了可以对并发执行的程序加以描述和控制，实现操作系统的并发性和共享性

进程的特征

• 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的【最基本的特征】
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能独立运行、获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进【操作系统要提供“进程同步机制”来解决异步问题】

进程与程序的区别

• 进程：是动态的，是程序的一次执行过程【如：可同时启动多次 QQ】
• 程序：是静态的，就是存放在磁盘里的可执行文件【如：QQ.exe】
• 同一个程序多次执行会对应多个进程

进程的组成

• 一个进程实体（进程映像）由 PCB、程序段、数据段组成
• 进程是动态的，进程实体是静态的
• 进程实体反映了进程在某一时刻的状态

进程控制块（PCB）

• 定义：
  • PCB 是进程实体的一部分，是进程存在的唯一标志
  • 进程创建时，操作系统为它新建一个 PCB，该结构常驻内存
• 包含：
  1. 进程描述信息：
     • 进程标识符 PID：标识各个进程，每个进程都有一个并且唯一的标识号
     • 用户标识符 UID：进程归属的用户，用户标识符主要为共享和保护服务
  2. 进程控制和管理信息：
     • 进程当前状态：描述进程状态信息，作为 CPU 调度的依据
     • 进程优先级：描述进程抢占 CPU 的优先级
     • 代码运行入口地址
     • 程序的外存地址
     • 进入内存时间
     • CPU 占用时间
     • 信号量使用
  3. 资源分配清单：
     • 有关内存地址空间和虚拟地址空间的状况
     • 所打开文件的列表和所使用的输入/输出设备信息
  4. 处理机相关信息【CPU 的上下文】：
     • CPU 中各寄存器的值
     • 当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中以便进程重新执行时，能从断点处继续执行
• 组织方式：
  • 链接方式：
    • 把同一状态的 PCB 链成一个队列，不同状态对应不同的队列
    • 也可把处于阻塞态的进程的 PCB，根据阻塞原因，排成多个阻塞队列
  • 索引方式：
    • 将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB
    • 如就绪索引表，阻塞索引表

程序段

• 能被进程调度程序调度到 CPU 执行的程序代码段
• 程序可以被多个进程共享，即多个进程可以运行同一个程序

数据段

• 可以是进程对应的程序加工处理的原始数据
• 可以是程序执行时产生的中间或最终结果

进程的状态与转换

五种状态

• 运行态 Running：该时刻进程占用 CPU
• 就绪态 Ready：进程获得了除处理机外的一切所需资源，一旦得到处理机，就可以立即运行
• 阻塞态 Blocked：该进程正在等待某一事件发生而暂停运行，如等待某个资源可用（不包括 CPU）或等待 I/O 完成
• 创建态 New：进程正在被创建时的状态
• 结束态 Exit：进程正在从系统中消失时的状态

状态转换

• 就绪态 -⇒ 运行态：
  • 进程被调度，获得处理机资源（分派处理机时间片）
• 运行态 -⇒ 就绪态：
  • 时间片用完后，不得不让出处理机
  • 可剥夺的 OS 中，当有更高优先级的进程就绪时，调度程序将正在执行的进程转换为就绪态
• 运行态 -⇒ 阻塞态：
  • 该过程是主动行为
  • 进程请求某一资源（如外设） 的使用和分配时
  • 等待某一事件的发送时（如 I/O 操作的完成）
  • 进程以系统调用的方式请求 OS 提供服务，这个过程系统从用户态转换为核心态
• 阻塞态 -⇒ 就绪态：
  • 该过程是被动行为，需要其他相关进程的协助
  • I/O 操作结束或中断结束时
  • 发送了阻塞队列等待的事件，如发送了 V 操作，信号量 +1，然后阻塞队列被唤醒到就绪队列中

进程控制

• 进程控制：主要功能是对系统中的所有进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能
• 原语：进程控制用的程序段【执行期间不允许中断，是一个不可分割的基本单位】
  • 可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性

进程的创建

定义及过程

• 允许一个进程创建另一个进程
• 允许子进程继承父进程所拥有的资源
• 创建原语：
  • 为新进程分配一个进程标识号，申请一个空白的 PCB【PCB 是有限的】
  • 为该进程分配运行时所必需的资源，如内存、文件、I/O 和 CPU 时间等
  • 初始化 PCB，如标志、状态、控制、优先级信息
  • 将 PCB 插入就绪队列

对应事件

• 用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程
• 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
• 系统提供服务：用户向操作系统提出某些请求时，会建立一个进程处理该请求
• 用户程序的应用：由用户进程主动请求创建一个子进程
• 注意：设备分配不需要创建进程

进程的终止

定义及过程

• 当子进程被终止时，其在父进程处继承的资源应当还给父进程
• 当父进程被终止时，该父进程的子进程就变为孤儿进程
• 终止原语：
  • 查找需要终止的进程的 PCB
  • 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程
  • 如果其还有子进程，全部终止
  • 将该进程所拥有的全部资源都归还给操作系统
  • 将其从 PCB 所在队列中删除

对应事件

• 正常结束：进程任务完成并自己准备退出运行
• 异常结束：进程运行时发生了异常事件
• 外界干预：如操作系统干预、父进程请求或父进程终止

进程的阻塞

定义及过程

• 当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待
• 一旦被阻塞等待，只能由另一个进程唤醒
• 阻塞原语：
  • 找到将要被阻塞进程标识号对应的 PCB
  • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
  • 将该 PCB 插入到阻塞队列中去

对应事件

• 需要等待系统系统分配某种资源
• 需要等待相互合作的其他进程完成工作

进程的唤醒

定义及过程

• 进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成
• 处于阻塞状态的进程是绝对不可能叫醒自己
• 如果某进程正在等待 I/O 事件，需由别的进程发消息给它
• 只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它
• 唤醒原语：
  • 在该事件的阻塞队列中找到相应进程的 PCB
  • 将其从阻塞队列中移出，并置其状态为就绪状态
  • 把该 PCB 插入到就绪队列中，等待调度程序调度
• 注意：阻塞原语和唤醒原语必须成对使用

对应事件

• 等待的事件发生

进程通信

• 进程通信：指进程之间的信息交换
• 各进程拥有的内存地址空间相互独立
• 为了保证安全，一个进程不能直接访问另一个进程的地址空间

低级通信方式

• PV 操作

高级通信方式

共享存储

• 设置一个共享内存区域，并映射到进程的虚拟地址空间
• 要互斥地访问共享空间【通信进程自己负责实现】
• 基于数据结构的共享：
  • 比如共享空间里只能放一个长度为 10 的数组
  • 速度慢、限制多
  • 是一种低级通信方式
• 基于存储区的共享：
  • 操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统
  • 灵活性高、速度快
  • 是一种高级通信方式

信息传递

• 进程间的数据交换以格式化的消息（Message）为单位
• 进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换
• 隐藏了通信实现细节，对用户透明，简化了通信程序的设计
• 应用最广泛
• 直接通信方式：发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从队列取得消息
• 间接通信方式：发送进程将消息发送给某个中间实体【信箱】

管道通信

• 管道只能采用半双工通信，某一时间段内只能实现单向的传输【如果要实现双向同时通信，则需要设置两个管道】
• 各进程要互斥地访问管道【由操作系统实现】
• 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程
• 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程
• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱，解决方案：
  1. 一个管道允许多个写进程，一个读进程
  2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）
• 管道是一种特殊文件，可以克服使用文件通信的两个问题：
  1. 限制管道的大小：管道文件是一个固定文件大小的缓冲区
  2. 读进程也可能工作得比写进程快
• 管道只能由创建进程访问【子进程可继承父进程的管道，并可用它来与父进程通信】
• 从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据

线程和多线程模型

线程的基本概念

• 线程可理解为轻量级进程
• 线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位
• 引入线程后的变化：
  • 并发性：进程内的各线程之间也可以并发，从而进一步提升了系统的并发度
  • 资源分配、调度：进程是资源分配的基本单位，线程是处理机调度的基本单位
  • 系统开销：线程间并发，如果是同一进程内的切换，则不需要切换进程环境，系统开销小
• 多 CPU 计算机中，各个线程可占用不同的 CPU
• 每个线程都有一个唯一的标识符和一个线程控制块【记录线程执行的寄存器和栈等现场状态】
• 不同的线程可以执行相同的程序
• 线程也有就绪、阻塞、运行三种基本状态，和进程之间的转换是一样的
• 线程共享进程地址空间和资源，线程自己没有独立的地址空间

线程的组成和控制

线程控制块 TCB

• 功能：每个线程配置一个 TCB，用于记录控制和管理线程的信息
• 组成：
  • 线程标识符
  • 一组寄存器，包括程序计数器、状态寄存器和通用寄存器
  • 线程运行状态
  • 优先级
  • 线程专有存储区，线程切换时用于保存现场
  • 堆栈指针，用于过程调用时保存局部变量及返回地址

线程的控制

• 创建线程：
  • 用户程序启动时，通常仅有一个称为初始化线程的线程正在执行，其主要功能是用于创建新线程
• 终止线程：
  • 通常，线程被终止后并不立即释放它所占有的资源，只有当进程中的其他线程执行了分离函数后，被终止线程才与资源分离，此时的资源才能被其他线程利用
  • 被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行

线程的实现方式

用户级线程（ULT）

• 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在【“用户级线程”就是“从用户视角看能看到的线程”】
• 优点：
  • 线程切换不需要转到内核空间，节省了模式切换的开销
  • 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法
  • 与操作系统平台无关，对线程管理的代码是属于用户程序的一部分
• 缺点：
  • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
  • 不能发挥多 CPU 的优势，内核每次分配给一个进程的仅有一个 CPU，因此进程中仅有一个线程执行
• 形成多对一模型

内核级线程（KLT）

• 内核级线程的管理工作由操作系统内核完成
• 内核级线程的切换必然需要在核心态下才能完成
• 操作系统会为每个内核级线程建立相应的 TCB，通过 TCB 对线程进行管理【“内核级线程”就是“从操作系统内核视角看能看到的线程”】
• 优点：
  • 能发挥多 CPU 的优势，内核能同时调度同一进程的多个线程并行执行
  • 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用 CPU，也可以运行其他进程中的线程
  • 内核支持线程具有很小的数据结构和栈，线程切换快、开销小
  • 内核本身也可采用多线程技术，可以提高系统的执行速度和效率
• 缺点：
  • 同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大【用户进程的线程在用户态执行，而线程调度和管理是在内核实现】
• 形成一对一模型

组合方式

• 内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
• 用户级线程通过时分多路复用内核线程实现
• 结合 KLT 和 ULT 的优点，又克服各自的不足
• 线程库：为程序员提供创建和管理线程的 API，实现方法：
  • 在用户空间中提供一个没有内核支持的库【调用库内的一个函数只导致用户空间中的一个本地函数的调用】
  • 实现由操作系统直接支持的内核级的一个库【调用库中的一个 API 函数通常会导致对内核的系统调用】
• 形成多对多模型

多线程模型

• 由于用户级线程和内核级线程的连接方式不同，从而形成了三种不同的多线程模型
• 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位

多对一模型

• 定义：多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程
• 优点：
  • 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
• 缺点：
  • 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高
  • 任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个 CPU 上运行

一对一模型

• 定义：一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程
• 优点：
  • 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强
  • 多线程可在多核处理机上并行执行
• 缺点：
  • 每创建一个用户线程，就要创建一个对应的内核线程，开销大
  • 线程切换由操作系统内核完成，需要切换到核心态，线程管理的成本高，开销大

多对多模型

• 定义：n 用户及线程映射到 m 个内核级线程（n >= m），每个用户进程对应 m 个内核级线程。
• 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点
• 用户级线程是“代码逻辑”的载体
• 内核级线程是“运行机会”的载体
• 一段“代码逻辑”只有获得了“运行机会”才能被 CPU 执行
• 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有所有内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

CPU 调度

调度的概念

基本概念

• 调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将 CPU 分配给它运行，以实现进程并发地执行
• CPU 调度是多道程序操作系统的基础，是 OS 设计的核心问题

调度的层次

高级调度（作业调度）

• 是内存与辅存的调度，从外存上处于后备队列的作业中调度
• 每个作业只调入调出一次
• 通常存在于多道批处理系统中
• 内存与磁盘之间交换数据的转态转换：就绪态到挂起态

中级调度（内存调度）

• 目的：提高内存利用率和系统吞吐量
• 将暂时不能运行的进程调到外存等待，设为挂起态
• 当具备运行条件且内存稍有空闲时，重新调入内存，修改状态为就绪态，挂在就绪队列上
• 是存储器管理中的对换功能

低级调度（进程调度）

• 从就绪队列中选取一个进程，调用频率很高
• 各种 OS 都必须配置这种调度

三种调度的联系

• 作业调度为进程活动做准备，进程调度使进程正常活动
• 中级调度将暂时不能运行的进程挂起，中级调度处于另外两个调度之间
• 调用频率：作业调度 < 内存调度 < 进程调度
• 进程调度是最基本的，不可或缺

调度的实现

调度程序（调度器）

• 调度程序：用于调度和分配 CPU 的组件
• 组成：
  • 排队器：按策略将就绪进程排成一个或多个队列
  • 分派器：从就绪队列中取出进程，并分配 CPU
  • 上下文切换器：在对处理机进行切换时，会发生两对上下文的切换：
    • 第一对：将当前进程的上下文保存到 PCB 中，再装入分派程序的上下文，以便分派程序运行
    • 第二对：移出分派程序的上下文，将选新进程的 CPU 现场信息装入 CPU 的各个相应寄存器

调度的时机

1. 需要进行进程调度与切换的情况：
   • 当前运行的进程主动放弃处理机：
     • 进程正常终止
     • 运行过程中发生异常而终止
     • 进程主动请求阻塞（如等待 I/O）
   • 当前运行的进程被动放弃处理机：
     • 分给进程的时间片用完
     • 有更紧急的事需要处理（如 I/O 中断）
     • 有更高优先级的进程进入就绪队列
2. 不能进行进程调度与切换的情况：
   • 在处理中断的过程中【中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换】
   • 进程在操作系统内核程序临界区中【内核程序临界区一般是用来访问某种内核数据结构的，若不尽快释放访问的临界资源，可能会影响到 OS 内核的其他管理工作】
   • 在原子操作过程中（原语）

进程调度的方式

1. 非抢占调度方式【非剥夺方式】：只允许进程主动放弃处理机
   • 优点：实现简单，系统开销小，适用于早期的批处理系统
   • 缺点：不适合分时和大多数的实时系统
2. 抢占调度方式【剥夺方式】：当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程
   • 优点：提高系统吞吐率和响应率
   • 缺点：必须遵循一定的原则（优先权、短进程优先、时间片原则等）

进程的切换与过程

• 狭义的进程调度：从就绪队列中选中一个要运行的进程【这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换】
• 广义的进程调度：包含了选择一个进程和进程切换两个步骤，进程切换的过程主要完成了：
  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）
• 闲逛进程：
  • 在进程切换时，如果系统中没有就绪进程，就会调用闲逛进程一直运行【PID 为 0】，并在指令周期后测试中断
  • 优先级最低，只要有进程就绪，就会立即让出 CPU
  • 不需要 CPU 之外的资源，不会被阻塞

两种线程的调度

• 用户级线程调度：
  • 内核不知道线程的存在，选择一个进程，并给予时间控制
  • 由进程中的调度程序决定哪个线程运行
  • 线程切换在同一进程中进行，仅需少量的机器指令
• 内核级线程调度：
  • 内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程
  • 超过时间片，强制挂起该线程
  • 需要完整的上下文切换、修改内存映像、使高速缓存失效，导致若干数量级的延迟

进程的上下文切换

基本概念

• 进程上下文切换：
  • 完成 CPU 切换到另一个进程时，保存当前进程状态并恢复另一个进程的状态的任务
  • 采用进程 PCB 表示，包括寄存器的值、进程状态和内存管理信息等
  • 内核将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文
  • 进程的运行环境发生实质性变化
• 上下文切换通常是计算密集型的，需要消耗大量的 CPU 时间
• 有些处理器提供多个寄存器组，上下文切换只需要简单改变当前寄存器组的指针，不需要用到磁盘和主存

上下文切换的场景

• 某个进程时间片耗尽时
• 进程在系统资源不足时，要等到资源满足后才可以运行
• 进程通过 sleep 将自己主动挂起
• 有优先级更高的基础运行时
• 发送硬件中断时

上下文切换的流程

1. 挂起一个进程，保存 CPU 上下文，包括 PC 和其他寄存器
2. 更新 PCB 信息
3. 把进程的 PCB 移到相应的队列（如就绪队列，阻塞队列）
4. 加载另一个进程执行，更新其 PCB
5. 跳转到新进程 PCB 中的 PC 所指向的位置执行
6. 恢复处理机上下文

上下文切换和模式切换

• 模式切换时，CPU 逻辑上可能还在执行同一进程
• 上下文切换只能发生在内核态【多任务 OS 的一个必需特性】
• 用户态与内核态之间的切换为模式切换【没有改变当前的进程】

调度和切换的区别

• 先有资源的调度，才有进程的切换
• 调度：决定资源分配给哪个进程的行为；是一种决策行为
• 切换：实际分配的行为；是一种执行行为

调度的目标

CPU 利用率

• $CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$
• $利用率=\frac{忙碌的时间}{总时间}$ 注意：计算作业完成时间时，要注意 CPU 与设备、设备与设备之间时可以并行的

系统吞吐量

• 表示单位时间内 CPU 完成作业的数量
• $系统吞吐量=\frac{总共完成了多少作业}{总共花了多少时间}$

周转时间

• 周转时间包括四个部分：
  • 作业在外存后备队列上等待作业调度（高级调度）的时间
  • 进程在就绪队列上等待进程调度（低级调度）的时间
  • 进程在 CPU 上执行的时间
  • 进程等待 I/O 操作完成的时间
• 后三项在一个作业的整个处理过程中，可能发生多次
• $周转时间=作业完成时间-作业提交时间$
• $平均周转时间=\frac{作业1的周转时间+...+作业n的周转时间}{n}$
• $带权周转时间=\frac{作业周转时间}{作业实际运行时间}$
• $平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$

等待时间

• 指进程/作业处于等待处理机状态时间之和
• 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间
• 对于作业来说，等于建立进程后的等待时间 + 作业在外存后备队列中等待的时间

响应时间

• 指从用户提交请求到首次产生响应所用的时间
• 在交互式系统中，一般采用响应时间作为衡量调度算法的准则之一

调度算法

先来先服务 FCFS

算法思想

• 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）

算法规则

• 按照作业/进程到达的先后顺序进行服务

用于作业/进程调度

• 用于作业调度时，考虑的是哪个作业先到达后备队列
• 用于进程调度时，考虑的是哪个进程先到达就绪队列

是否可抢占

• 非抢占式

优缺点

• 优点：
  • 公平、算法实现简单
  • 有利于 CPU 繁忙型作业
  • 一般适用于早期批处理系统
• 缺点：
  • 对长作业有利，对短作业不利【排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好】
  • 不利于 I/O 繁忙型作业

是否会导致饥饿

• 不会
• 饥饿：某进程/作业长期得不到服务

短作业优先 SJF

算法思想

• 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

算法规则

• 最短的作业/进程优先得到服务【要求服务时间最短】

用于作业/进程调度

• 即可用于作业调度，也可用于进程调度
• 用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法

是否可抢占

• SJF 和 SPF 是非抢占式算法
• 短剩余时间优先算法（SRTN）是抢占式的

优缺点

• 优点：
  • 在所有进程都几乎同时到达时，采用 SIF/SPF 调度算法的平均等待时间、平均周转时间最少
  • 抢占式的 SJF/SPF 调度算法【最短剩余时间优先算法】的平均等待时间、平均周转时间最少
  • 一般适用于早期批处理系统
• 缺点：
  • 对短作业有利，对长作业不利
  • 可能产生饥饿现象
  • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

是否会导致饥饿

• 会
• 如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象
• 如果一直得不到服务，则称为“饿死”

高响应比优先

算法思想

• 综合考虑作业/进程的等待时间和要求服务的时间

算法规则

• 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
• $响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}$

用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

是否可抢占

• 非抢占式的算法
• 因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

优缺点

• 等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，类似于 SJF
• 要求服务时间相同时，等待时间越长，响应比越高，类似于 FCFS
• 响应比可以随等待时间的增加而提高，克服了饥饿现象
• 适用于分时操作系统

是否会导致饥饿

• 不会

优先级

算法思想

• 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

算法规则

• 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

用于作业/进程调度

• 既可用于作业调度，也可用于进程调度

是否可抢占

• 非抢占式：直到由于自身原因而让出 CPU 时，更高优先级的进程才可运行
• 抢占式：有更高优先级的进程进入就绪队列时，立即停止正在运行的进程
  • 静态优先级：
    • 优先级是在创建时确立的
    • 优点：简单易行，系统开销小
    • 缺点：不够精确，可能出现优先级低的进程长时间得不到调用
  • 动态优先级：
    • 优先级随进程的推进或等待时间的增加而改变，以获得更好的性能
    • 系统进程 > 用户进程
    • 交互型进程 > 非交互型进程
    • I/O 型进程 > 计算型进程

优缺点

• 优点：
  • 用优先级区分紧急程度、重要程度，适用于实时操作系统
  • 可灵活地调整对各种作业/进程的偏好程度
• 缺点：
  • 若源源不断地有高优先级进程到来，则可能导致饥饿

是否会导致饥饿

• 会

时间片轮转 RR

算法思想

• 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则

• 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100 ms）
• 若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

用于作业/进程调度

• 用于进程调度
• 只有作业放入内存建立了相应的进程后，才能被分配处理机时间片

是否可抢占

• 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法
• 由时钟装置发出时钟中断来通知 CPU 时间片已到

优缺点

• 优点：
  • 公平，响应快
  • 适用于分时操作系统
• 缺点：
  • 由于高频率的进程切换，因此有一定开销
  • 不区分任务的紧急程度
• 若时间片足够大：所有进程都能在一个时间片内执行完毕，退化为 FCFS
• 若时间片足够小：CPU 将在进程间过于频繁的切换，使 CPU 的开销增大

是否会导致饥饿

• 不会

多级队列

算法思想

• 在系统中设置多个就绪队列
• 按不同类型或性质的进程固定分配到不同的就绪队列
• 每个队列可实施不同的调度算法
• 在多 CPU 系统中，可以很方便为每个 CPU 设置一个单独的就绪队列

多级反馈队列

算法思想

• 对其他调度算法的折中权衡

算法规则

1. 设置多级就绪队列，赋予每个队列不同的优先级【第 1 级队列最高，依次降低】
2. 赋予各个队列的进程运行时间片的大小各不相同【优先级越高的队列，每个进程的时间片越小】
3. 每个队列采用 FCFS 算法：
   • 新进程进入内存后，首先放入第 1 级队列的队尾，等待调度
   • 在第一个时间片结束时尚未完成，将其转入第 2 级队列的末尾，依次类推
   • 当进程被降到第 n 级队列后，采用时间片轮转方式运行
4. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片

用于作业/进程调度

• 即可用于作业调度，也可用于进程调度

是否可抢占

• 抢占式的算法
• 在 k 级队列的进程运行过程中，若更上级的队列（1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾

优缺点

• 对各类型进程相对公平（FCFS 的优点）
• 每个新到达的进程都可以很快就得到响应（RR 的优点）
• 短进程只用较少的时间就可完成（SPF 的优点）
• 不必实现估计进程的运行时间（避免用户作假）
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程
• 拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级

是否会导致饥饿

• 会

常见算法的对比

同步与互斥

基本概念

• 因为并发进程是异步的，为了协调进程之间的相互制约关系，所以引入同步互斥
• 同步【直接制约关系】：
  • 指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系
• 互斥【间接制约关系】：
  • 当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许访问临界资源
• 临界资源：一次仅允许一个进程使用的资源，对其访问过程分为：
  • 进入区：负责实现互斥，设置标志
  • 临界区：进程中访问临界资源的那段代码
  • 退出区：负责实现互斥，清楚标志
  • 剩余区：代码中的其余部分
• 同步机制应遵循的准则：
  • 空闲让进：临界区空闲，允许一个进程进入【运行进程访问空闲的临界资源】
  • 忙则等待：有进程进入临界区时，其他进程需等待【两个进程不能同时进入临界资源】
  • 有限等待：请求访问的进程应保证在有限时间内进入临界区，防止无限等待【进程等待进入临界区的时间是有限的】
  • 让权等待【原则上遵循，非必须】：进程不能进入临界区时，应该立即释放处理器，防止进程忙等待【不能进入临界区的执行态进程立即放弃 CPU】

实现临界区互斥的方法

软件实现方法

单标志法

• 设置一个公用整型变量 turn，指示允许进入临界区的进程编号
• 每次只允许一个进程进入临界区
• 违背“空闲让进”

双标志先检查法

• 设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿
• 违背“忙则等待”【进入区“检查”后，“上锁”前可能发生进程切换】

双标志后检查法

• 先“上锁”，后“检查”，避免上诉问题
• 解决“忙则等待”
• 违反“空闲让进”和“有限等待”，会导致饥饿现象

Peterson 算法

• 利用 flag 解决互斥访问问题，利用 turn 解决饥饿问题
• 违反“让权等待”

硬件实现方法

中断屏蔽法

• 关中断：防止其他进程进入临界区
• 优点：简单、高效
• 缺点：
  • 限制了 CPU 交替执行程序的能力，因此系统效率会明显降低
  • 不适用于多处理机
  • 只适用于操作系统内核进程，不适用于用户进程【因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险】

硬件指令——TestAndSet 指令（TS 指令）

• 为每个临界资源设置一个共享布尔变量 lock，表示该资源的两种状态【true 表示被占用】
• 若刚开始 lock 是 false，则 TS 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区
• 若刚开始 lock 是 true，则执行 TS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”
• 优点：
  • 实现简单，TS 指令将“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作
  • 适用于多处理系统
• 缺点：不满足“让权等待”原则

硬件指令——Swap 指令（XCHG 指令）

• 为每个临界资源设置一个共享布尔变量 lock，初值 false
• 在每个进程中设置一个局部变量 key，初值 true，用于与 lock 交换信息
• 优点：
  • 简单，容易验证其正确性
  • 适用于多处理机系统
  • 支持系统中有多个临界区，只需为每个临界区设立一个布尔变量
• 缺点：
  • 不满足“让权等待”原则
  • 从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，导致饥饿

互斥锁

• 是解决临界区最简单的工具
• 通常采用硬件机制实现
• 获得锁：acquire，释放锁：release，都是原子操作
• 使用互斥锁解决经典同步问题
• 优点：
  • 进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高
  • 适用于多处理系统
• 缺点：忙等待

信号量

PV 操作定义

• 信号量：表示系统中某种资源的数量
• P 操作【wait() 原语】：将信号量值 S 减 1，表示申请占用一个资源
• V 操作【signal() 原语】：将信号量值 S 加 1，表示释放一个资源，即使用完资源后归还资源

信号量分类

整型信号量

• 该信号量被定义为一个用于表示资源数目的整型量 S
• 该机制不遵循“让权等待” 的准则【只要 s≤0，就会不断循环测试】

记录型信号量

• 需要一个用于代表资源数目的变量 value
• 需要一个进程链表 L，用于链接所有等待该资源的进程
• S.value 的初值表示系统中某种资源的数目
• P 操作【wait () 原语】：
  • 如果 S.value<0，表示已经没有可用资源，则进程调用 block 原语进行自我阻塞【运行态 -⇒ 阻塞态】，主动放弃处理机，并插入该类资源的 S.L
  • 遵循“让权等待”
• value: 仍然表示资源的数量。但它的含义有了扩展：
  • value > 0: 表示当前可用资源的数量。
  • value = 0: 表示没有可用资源，也没有进程在等待。
  • value < 0: 表示没有可用资源，且其绝对值 |value| 是正在等待队列中阻塞的进程数量。
• V 操作【signal () 原语】：
  • 如果加 1 后 S.value≤0，表示仍有进程正在等待该资源，调用 wakeup 原语唤醒 S.L 中的第一个进程【阻塞态 -⇒ 就绪态】

特征	单信号量 (资源计数)	双信号量 (生产者-消费者)
问题模型	多个进程竞争有限的同类资源。	两类进程围绕缓冲区协作。
等待条件	只有一种：等待资源变得可用。	有两种：等待缓冲区有空位 (生产者) / 等待缓冲区有产品 (消费者)。
信号量语义	S = 可用资源数。	empty = 空位数，full = 产品数。 empty + full = 容量 (恒成立)。
生活类比	图书馆借书处有10本相同的书。你只需要关心“有没有书可借”。信号量 S=10。	一个快递柜有10个格子。快递员（生产者）关心“有没有空格子”，收件人（消费者）关心“有没有快件”。empty=10, full=0。

信号量的应用

利用信号量实现互斥

• 互斥信号量 S 初始值=1，表示临界区只允许一个进程进入，从而实现互斥
• 把对临界资源的访问操作置于 P (S) 和 V（S）之间
• P 操作和 V 操作必须成对出现
• 缺少 P 操作：不能保证对临界资源的互斥访问
• 缺少 V 操作：导致临界资源永远得不到释放，使因等待该资源而阻塞的进程永远得不到唤醒

利用信号量实现同步

• 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
• 设置同步信号量 S 的初始值 = 0
• 在“前操作”之后执行 V (S)
• 在“后操作”之前执行 P (S)

利用信号量实现前驱关系

• 信号量用来描述程序或语句之间的前驱关系
• 要为每一对前驱关系各设置一个同步信号量
• 在“前操作”之后对相应的同步信号量执行 V 操作
• 在“后操作”之前对相应的同步信号量执行 P 操作

经典同步问题【王道 25 版 p103】

生产者——消费者问题

问题描述

• 一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区
• 进程每次从缓冲区中取出一个产品并使用
• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待
• 缓冲区是临界资源，各进程必须互斥地访问

问题分析

• 关系分析：
  • 生产者和消费者对缓冲区的互斥访问是互斥关系
  • 生产者和消费者之间相互协作，是同步关系
• 整理思路：确定 P、V 操作的大致顺序
• 信号量设置：
  • 互斥信号量：mutex 初始值 1，用于控制互斥访问缓冲池
  • 同步信号量：full 初始值 0，表示非空缓冲区（产品）的数量
  • 同步信号量：empty 初始值 n，表示空闲缓冲区的数量
• 注意：
  • 实现互斥的 P 操作一定要在实现同步的 P 操作之后
  • V 操作不会导致进程阻塞，因此两个 V 操作顺序可以互换

管程

基本概念

• 引入管程的原因：
  • 信号量机制存在的问题：编写程序困难、易出错
  • 管程的特性保证了互斥，程序员无须自己实现，并提供条件变量，更灵活地实现进程同步
• 管程：定义了共享数据结构和能为并发进程执行（在该数据结构上）的一组操作
• 管程的组成：
  • 管程的名称
  • 局部于管程内部的共享数据结构或者共享变量说明
  • 对管程内的数据结构进行操作的一组过程（函数）
  • 对局部于管程内部的共享数据设置初始值的语句
• 管程的基本特征：
  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程，从而实现互斥【编译器实现该特性】

管程中设置的条件变量

• 定义：将一个进程进入管程后被阻塞的原因定义为条件变量 condition
• 管程中设置了多个条件变量，每个条件变量保存了一个等待队列【记录因该条件变量而阻塞的所用进程】
• 两种操作：
  • x.wait：x 对应的条件不满足，将正在调用管程的进程插入到 x 条件的等待队列，并释放管程
  • x.signal：唤醒一个因 x 条件而阻塞的进程
• 与信号量的相似点：
  • wait/signal 类似于信号量的 P/V 操作，实现进程的阻塞/唤醒，但不能说和 PV 操作相同
• 与信号量的不同点：
  • 条件变量没有值，仅实现“排队等待”功能
  • 信号量有值，这个值反映了剩余资源数
  • 在管程中，剩余资源数用共享数据结构记录

死锁

死锁的概念

基本概念

• 死锁：指多个进程因为竞争资源而造成的一种僵局【互相等待对方手里的资源】
• 死锁的充分条件：资源分配图中每种资源只有 1 个，出现了环路
• 死锁和饥饿的共同点：都是进程无法顺利向前推进的现象
• 死锁和饥饿的不同点：
  • 发生饥饿的进程可以只有 1 个；发生死锁的进程必然大于等于 2 个
  • 发生饥饿的进程能处于就绪态【长期得不到 CPU】，也可能处于阻塞态【长期得不到 I/O 设备】；发生死锁的进程必然处于阻塞态

死锁产生的原因

1. 系统资源的竞争【空间上】：
   • 系统中不可剥夺资源（磁带机、打印机等）不足以满足多个进程
   • 只有对不可剥夺资源的竞争才可能产生死锁
2. 进程推进顺序非法【时间上】：
   • 请求和释放资源的不当，会导致死锁
   • 信号量使用不当，会导致死锁

死锁产生的必要条件

产生死锁必须同时满足以下四个条件：

• 互斥条件：
  • 只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）
  • 像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）
• 不可剥夺条件：
  • 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
• 请求并保持条件：
  • 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
• 循环等待条件：
  • 存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

死锁的处理策略

• 死锁预防：破坏死锁产生的四个必要条件中的一个或几个
• 死锁避免：用某种方法防止系统进入不安全状态，从而避免死锁
• 死锁检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

死锁预防

1. 破坏互斥条件：

   • 不可行
   • 有些资源（打印机等临界资源）根本不能同时访问
   • 为了系统安全，很多时候必须保护这种互斥性

2. 破坏不可剥夺条件：

   • 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请
   • 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺
   • 缺点：
     • 实现起来比较复杂
     • 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU
     • 反复地申请和释放资源会增加系统开销，降低系统吞吐量
     • 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

3. 破坏请求并保持条件：

   • 采用预先静态分配法：
     • 进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行
     • 一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了
   • 缺点：资源利用率低，可能导致饥饿
   • 改进：允许进程只获得运行初期所需的资源后，便可开始运行

4. 破坏循环等待条件：

   • 采用顺序资源分配法：
     • 首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源
     • 同类资源（编号相同）一次申请完
   • 原理分析：
     • 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源
     • 已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象
   • 缺点：
     • 不方便增加新的设备，因为可能需要重新分配所有的编号
     • 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
     • 必须按规定次序申请资源，用户编程麻烦

死锁避免

系统安全状态

• 安全序列：
  • 指如果系统按照这种序列分配资源，则每个进程都能顺利完成
  • 只要能找出一个安全序列，系统就是安全状态
  • 安全序列可能有多个
• 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利的执行下去【如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态】
• 处于不安全状态未必发生死锁
• 发生死锁时一定是处于不安全状态

银行家算法

• 详见王道书 25 版 p152

• 例题

死锁检测和解除

死锁的检测

• 资源分配图：
  • 圆圈代表进程，框表示一类资源
  • 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源
  • 从资源到进程的有向边称为分配边，表示该类资源已有一个资源分配给该进程
• 简化资源分配图可检测系统状态是否为死锁：
  • 在资源分配图中，找出既不阻塞又不是孤点的进程 Pi【即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量】
  • 然后消去该进程所有请求边和分配边
  • 若能消去图中所有的边，则该图可完全简化
• 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源
2. 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
3. 进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非剥夺