OS-Chapter3-进程与并发程序设计

# 进程与线程

# 进程概念的引入

# 并发与并行

• 并发：设有两个活动 a1 和 a2，如果在某一指定的时间 t，无论 a1 和 a2 是在同一处理机上还是在不同的处理机上执行，只要 a1 和 a2 都处在各自的起点和终点之间的某一处，则称 a1 和 a2 是并发执行的。
• 并行：如果考虑两个程序，它们在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的。

并发可能是伪并行，也可能是真并行

并发的特征：间断性、非封闭性、不可再现性

# 进程的定义

进程是程序的一次执行（同一程序多次执行会对应多个进程）

进程是可以和别的计算并发执行的计算；

进程可定义为一个数据结构，及能在其上进行操作的一个程序；

进程是一个程序及其数据，在处理机上顺序执行时所发生的活动；

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

# 进程的特征

• 动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。而程序是静态实体。
• 并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
• 独立性：在传统 OS 中，进程是独立运行的基本单位
• 异步性：也叫制约性，进程之间相互制约，进程以各自独立的不可预知的速度向前推进。

# 进程的结构

# 进程状态与控制

# 进程的状态

为了方便进程管理，把进程分为了，运行态，就绪态，阻塞态、创建态、终止态五种状态。

• 创建态：系统创建进程，操作系统给进程分配系统资源、PCB 等等
• 就绪态：已经具备运行条件，等待空闲的 CPU，进行调用
• 运行态：当 cpu 处于空闲阶段就会在就绪态的进程里面选择一个进行执行，，也就是把 cpu 占据进入了运行态，一核的 cpu 就只可以一次运行一个进程，多少核的 cpu 可以有多少个进程处于运行态
• 阻塞态：因为某个事件而暂时不可用运行
• 终止态：运行进程从 cpu 撤销，操作系统就会回收资源、撤销 PCB

# 进程控制块 PCB

系统为每个进程定义了一个数据结构：进程控制块 PCB（Process Control Block）。

进程控制块是进程管理和控制的最重要的数据结构，每一个进程均有一个 PCB，在创建进程时，建立 PCB，伴随进程运行的全过程，直到进程撤消而撤消。

作用：

• 进程创建、撤消；
• 进程唯一标志；
• 限制系统进程数目。

内容：

• 进程标识符：每个进程都必须有一个唯一的标识符
• 程序和数据的地址
• 当前状态：为了管理的方便，系统设计时会将相同的状态的进程组成一个队列
• 现场保护区：当进程因某种原因不能继续占用 CPU 时（等待打印机），释放 CPU，这时就要将 CPU 的各种状态信息保护起来，为将来再次得到处理机恢复 CPU 的各种状态，继续运行。
• 同步与同步机制：用于实现进程间互斥、同步和通信所需的信号量等
• 优先级
• 资源清单：列出所拥有的除 CPU 外的资源记录，如拥有的 I/O 设备，打开的文件列表等
• 链接字：指出该进程所在队列中下一个进程 PCB 的首地址
• 其他信息

组织方式：

• 链式：

• 索引式：

# 进程的控制

进程控制的主要任务是创建和撤消进程，以及实现进程的状态转换，由内核来实现。

进程控制由 原语 实现。原语，一般是指由若干条指令组成的指令序列：

• 指令序列执行是连续的，不可分割
• 是操作系统核心组成部分
• 必须在管态 (内核态) 下执行，且常驻内存

# 线程概念的引入

进程包含了两个概念：资源拥有者 和 可执行单元。

现代操作系统将资源拥有者称为进程（process, task），可执行单元称为线程（thread）

线程：将资源与计算分离，提高并发效率

下图直观地展示了 多进程 (左) 和 多线程 (右) 的区别

目的：

• 减小进程切换的时空开销，使得并发粒度更细、并发性更好
• 提高进程内的并发程度
• 共享资源

进程与线程对比：

# 线程的实现方式

# 用户级线程

线程在用户空间，通过 library 模拟的 thread，不需要或仅需要极少的 kernel 支持

用户级线程由应用程序通过线程库实现。所有的线程管理工作都 由应用程序负责（包括线程切换)

用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。（用户级线程对用户不透明，对操作系统透明)

优点：

• 线程切换 与内核无关
• 线程的调度由应用决定，容易进行优化
• 可 运行在任何操作系统上，只需要线程库的支持

缺点：

• 很多系统调用会引起阻塞，内核会因此而 阻塞所有相关的线程。
• 内核只能将处理器分配给进程，即使有多个处理器，也 无法实现一个进程中的多个线程的并行执行。

# 内核级线程

内核级线程就是 kernel 有好几个分身，一个分身可以处理一件事

这用来处理 非同步事件 很有用，kernel 可以对每个非同步事件产生一个分身来处理.

支持内核线程的操作系统内核称作多线程内核

内核级线程的管理工作 由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。只有内核级线程才是处理机分配的单位

优点：

• 内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
• 阻塞发生在线程级别
• 内核中的一些处理可以通过多线程实现

缺点：

• 一个进程中的线程切换需要内核参与，线程的切换涉及到两个模式的切换（进程 - 进程、线程 - 线程）
• 降低效率

# 混合的线程实现方式

使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来，形成混合的线程实现方式。

内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。

# 多线程模型

一对一模型：一个用户级线程映射到一个内核级线程。

• 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

• 缺点：每个用户进程会占用一个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

** 多对一模型：** 将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见

• 优点：线程管理是在用户空间进行的，因而效率比较高

• ** 缺点：** 当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。

** 多对多模型：**n 个用户级线程映射到 m 个内核级线程 (n>=m)。每个用户进程对应 m 个内核级线程。

克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

# 同步与互斥

# 同步与互斥问题

# 几个概念

• 竞争：两个或多个进程对同一共享数据同时进行访问，而最后的结果是不可预测的，它取决于各个进程对共享数据访问的相对次序。这种情形叫做竞争。
• 竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关。
• 临界资源：我们将一次仅允许一个进程访问的资源称为临界资源。
• 临界区：每个进程中访问临界资源的那段代码称为临界区。

# 进程互斥（间接制约）

某一资源同时只允许一个访问者对其进行访问，具有 唯一性 和 排它性。互斥无法限制访问者对资源的访问顺序，即访问是 无序访问

# 进程同步（直接制约）

指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的 有序访问。在大多数情况下，同步已经实现了互斥，特别是所有对资源的写入的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

# 互斥访问临界资源的原则

• 空闲让进：临界资源处于空闲状态，允许进程进入临界区。

• 忙则等待：临界区有正在执行的进程，所有其他进程则不可以进入临界区

• 有限等待：对要求访问临界区的进程，应在保证在有限时间内进入自己的临界区，避免死等。

• 让权等待：当进程（长时间）不能进入自己的临界区时，应立即释放处理机，尽量避免忙等。

# 基于忙等待的互斥方法（软件）

# 临界区空满标志法

# 单标志法

固然实现了互斥。但 要求两进程严格交替进入临界区，比如上图 P1 无法先进入临界区。违反了 空闲让进 原则

# 双标志先检查法

若 1 和 5 先执行，则无法实现互斥，违反 忙则等待 原则

# 双标志后检查法

若 1 和 5 先执行，则两个进程都无法进入，违反 忙则等待 原则

# Dekker 算法

1965 年第一个用软件方法解决了临界区问题

# Peterson 算法

# 基于忙等待的互斥算法（硬件）

# 中断屏蔽方法

使用 “开关中断” 指令（与 原语的实现思想相同）

• 执行 “关中断” 指令，进入临界区操作；
• 退出临界区之前，执行 “开中断” 指令。

优点：简单高效

缺点：

• 不适用于多 CPU 系统：往往会带来很大的性能损失；
• 不适用于多处理器
• 只适用于内核进程，不适用于用户进程

# Test And Set 指令

# swap 指令

# 几个算法的共性问题

• 忙等待，浪费 CPU 时间
• 优先级反转：低优先级进程先进入临界区，高优先级进程一直忙等

# 基于信号量的方法

其基本思路是使用一种新的变量类型（semaphore）

信号量 只能通过初始化和两个标准的原语（P、V）来访问，作为 OS 核心代码执行，不受进程调度的打断。原语是由关中断 / 开中断指令实现的。

优点：简单，而且表达能力强（用 P.V 操作可解决任何同步互斥问题）

缺点：不够安全；P.V 操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂

# 经典信号量机制（整型）

# 计数型信号量机制（记录型）

# 实现互斥、同步、前驱

互斥：

划定临界区，先 P 后 V

semaphore mutex = 1; // 初始化信号量

P1() {  

    ...  

    P(mutex); // 使用临界资源前需要加锁  

    临界区代码段...  

    V(mutex); // 使用临界资源后需要解锁  

    ...  

}  

P2() {  

    ...  

    P(mutex);  

    临界区代码段...  

    V(mutex);  

    ...  

}

对不同的临界资源（如摄像头，打印机）需要设置不同的互斥信号量。

同步：

分析什么地方需要实现 “同步关系”，即必须保证 “一前一后” 执行的两个操作（或两句代码)

设置同步信号量 S，初始为 0。在 “前操作” 之后执行 V (S)，在 “后操作” 之前执行 P (S)

如下图示例，要求 P2 的代码 4 必须晚于 P1 的代码 2

前驱关系：

要为每一对前驱关系各设置一个同步变量

在 “前操作” 之后对相应的同步变量执行 V 操作，在 “后操作” 之前对相应的同步变量执行 Р 操作

# 信号量集

利用信号量机制解决了单个资源的互斥访问，而信号量集是指 同时需要多个资源时 的信号量操作。

AND 型信号量集机制：

• 将进程需要的所有共享资源 一次全部分配 给它；待该进程使用完后再 一起释放

一般 “信号量集” 机制：

• 在 AND 型信号量集的基础上进行扩充：进程对信号量 Si 的测试值为 ti（用于信号量的判断，即 Si >= ti，表示资源数量低于 ti 时，便不予分配），占用值为 di（用于信号量的增减，即 Si = Si - di 和 Si = Si +di ）
• 几个例子：
  • SP (S, d, d)：表示每次申请 d 个资源，当资源数量少于 d 个时，便不予分配。、
  • SP (S, 1, 1)：表示互斥信号量。
  • SP (S, 1, 0)：可作为一个可控开关 (当 S≥1 时，允许多个进程进入临界区；当 S=0 时禁止任何进程进入临界区)。

# 基于管程的同步与互斥

# 管程的引入

信号量机制的缺陷：

• 加重编程负担
• P、V 操作分散在各个进程中，操作不当易导致死锁

** 管程：** 把分散的临界区集中起来，** 为每个可共享资源设计一个专门机构 ** 来统一管理各进程对该资源的访问，这个专门机构称为管程，任一时刻，管程中只能有一个活跃进程。

管程是一种高级的同步原语，是一种语言概念，由编译器负责实现互斥

# 管程的实现

• 局部控制变量（临界资源）：一组局部于管程的控制变量
• 初始化代码：对控制变量进行初始化的代码
• 操作原语（互斥）：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。
• 条件变量（同步）：每个独立的条件变量是和进程需要等待的某种原因相联系的，当定义一个条件变量 x 时，系统就建立一个相应的等待队列

条件变量与信号量的区别：

如何避免 signal() 后管程中有两个活跃进程？

• Hoare 管程（阻塞式条件变量）：执行 signal 的进程等待，直到被释放进程退出管程或等待另一个条件
• Mesa 管程（非阻塞式条件变量）：被释放进程等待，直到执行 signal 的进程退出管程或者等待另一个条件
• Hansen 管程：执行 signal 的进程立即退出管程，即 signal 操作必须是管程中的过程体的最后一个操作

# 进程通信的主要方法

低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的 信号量和管程机制 。

• 缺点：传送信息量小，效率低；编程复杂；

高级通信：适用于分布式系统，基于共享内存的多处理机系统，单处理机系统，能够传送任意数量的数据，可以解决进程的同步问题和通信问题，主要包括三类：共享内存、消息传递、管道

# 共享内存

# 消息传递

# 管道

• 管道是 半双工 的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；

• ** 无名管道 ** 只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程），** 有名管道（FIFO）** 突破了这一限制

• 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在在内存中。

• 数据的读出和写入：先进先出。一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据

# 经典的进程同步与互斥问题

# 生产者 — 消费者问题

• 若两个 P 操作互换位置，则会产生死锁
• 若两个 V 操作互换位置，则没有影响

# 读者 — 写者问题

① 允许多个读者可以同时对文件执行读操作；

② 只允许一个写者往文件中写信息；

③ 任一写者在完成写操作之前不允许其他读者或写者工作；

④ 写者执行写操作前，应让已有的读者和写者全部退出。

读者优先：

读写公平（先到先得）：

读者 - 写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个 / 最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现 “一气呵成”，自然应该想到用互斥信号量。

# 哲学家进餐问题

①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。伪代码如下

# 理发师问题

# 吸烟者问题

# 进程调度

# 基本概念

# 调度类型

# 调度时机

# 调度性能准则

面向用户：

• 周转时间 = 完成时刻 - 提交时刻

  带权周转时间 = 周转时间 / 执行时间

  平均周转时间（ T ） = 周转时间之和 / 作业数

  平均带权周转时间（ T/Ts ） = 带权周转时间之和 / 作业数

• 响应时间：用户输入请求到系统给出首次响应的时间

• 截止时间：开始截止（最早开始）时间和完成截止（最晚完成）时间

• 优先级

• 公平性

面向系统：

• 吞吐量：单位时间内所完成的作业数

• 处理及利用率：忙碌时间 / 总时间

• 各种资源均衡利用

# 批处理系统

• 无需与用户交互，通常在后台运行
• 不需很快的响应

# 先来先服务算法（FCFS）

最简单的调度算法，按先后顺序调度

• 按照作业提交或进程变为就绪状态的先后次序，分派 CPU
• 当前作业或进程占用 CPU ，直到执行完或阻塞，才出让 CPU （非抢占式）

特点

• 比较有利于长作业，而不利于短作业
• 有利于 CPU 繁忙的作业，不利于 I/O 繁忙的作业

# 短作业优先算法（SJF，SPN）

这是对 FCFS 算法的改进，其目标是减少平均周转时间

• 对预计执行时间短的作业（进程）优先分派处理机
• 通常后来的短作业不抢先正在执行的作业（非抢占式）

优点：

• 比 FCFS 改善平均周转时间和平均带权周转时间，缩短作业的等待时间
• 提高系统的吞吐量

缺点：

• 对长作业非常不利，可能长时间得不到执行
• 未能依据作业的紧迫程度来划分执行的优先级
• 难以准确估计作业（进程）的执行时间，从而影响调度性能

# 最短剩余时间优先算法（SRTF）

将短作业优先进行改进，改进为 抢占式

即一个 新就绪的进程 如果比当前运行进程具有更短的完成时间，则系统抢占当前进程，选择新就绪的进程执行。

缺点：

• 源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生 “饥饿” 现象。

# 最高响应比优先算法（HRRF）

在每次选择作业投入运行时，先计算后备作业队列中每个作业的响应比 RR (响应优先级)，然后选择其值最大的作业投入运行

RR = 1 + 已等待时间/要求运行时间

响应比的计算时机：

• 每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响应比最高者投入运行。(非抢占式)

优点：

• 饥饿现象不会发生

缺点：

• 每次计算各道作业的响应比会有一定的时间开销，性能比 SJF 略差

# 交互式系统

• 与用户交互频繁，因此要花很多时间等待用户输入
• 响应时间要快，平均延迟要低于 50~150ms

# 时间片轮转算法（RR）

• 【排队】将系统中所有的就绪进程按照 FCFS 原则，排成一个队列
• 【轮转】每次调度时将 CPU 分派给队首进程，让其执行一个时间片。时间片的长度从几个 ms 到几百 ms
• 【中断】在一个时间片结束时，发生时钟中断
• 【抢占】调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程
• 【出让】进程可以未使用完一个时间片，就出让 CPU （如阻塞）。

# 优先级算法

平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢占式和非抢占式

静态优先级：

• 创建进程时就确定，直到进程终止前都不改变。通常是一个整数

动态优先级：

• 在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能

  我们的 Lab3 实验采用的就是基于动态优先级的时间片轮转算法：

  进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让 CPU

# 多级队列算法

引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标

• 根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列
• 每个作业固定归入一个队列
• 不同队列可有不同的优先级、时间片长度、调度策略等；在运行过程中还可改变进程所在队列

# 多级反馈队列算法

• 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列 1 的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍
• 新进程进入内存后，先投入队列 1 的末尾，按 “时间片轮转” 算法调度；若按队列 1 一个时间片未能执行完，则降低投入到队列 2 的末尾，同样按 “时间片轮转” 算法调度；如此下去，降低到最后的队列，则按 “FCFS” 算法调度直到完成。
• 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾

# 优先级倒置现象

高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞

解决方法：

• 优先级置顶
• 优先级继承

# 实时系统

实时系统是一种 时间 起着主导作用的系统。

实时系统被分为硬实时系统和软实时系统。硬实时要求绝对满足截止时间要求（如：汽车和飞机的控制系统），而软实时可以偶尔不满足（如：视频 / 音频程序）

实时系统通常将对不同刺激的响应指派给不同的进程（任务），并且每个进程的行为是 可提前预测 的。

# 静态表调度算法

通过对所有周期性任务的分析预测，事先确定一个固定的调度方案。

• 无任何计算，按固定方案进行，开销最小
• 无灵活性，只适用于完全固定的任务场景

# 单调速率调度算法（RMS）

• 静态优先级固定分配：

  优先级与周期成反比，周期越短优先级越高。如果两个任务的优先级一样，当调度它们时， RM 算法将随机选择一个调度

• 任务在周期起点释放，高优先级任务可抢占低优先级任务的执行

# 最早截止时间优先算法（EDF）

• 任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度（动态优先级）
• 如果两个任务的优先级一样，当调度它们时， EDF 算法将随机选择一个调度

# 多处理机系统