第四章 进程与并发程序设计

4.1 进程与线程

进程概念的引入

并发与并行

  • 并发：只要某一时刻，活动1与活动2都处在运行状态，就称两者是并发执行的。

  • 并行：两个程序在同一时刻运行在不同的处理机上，则称这两个程序是并行执行的

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

    • 间断性：并发程序具有“执行 - 暂停 - 执行”的间断性规律
    • 非封闭性：存在共享资源，使得程序之间会相互影响
    • 不可再现性：在初始条件相同时，程序结果依赖于执行顺序

对于并发而言，偏重于开始 - 结束时间的区间上有重叠，两个程序不必在同一时刻都处于活跃状态；而并行则要求两个程序需要同时工作/活跃在 CPU 上，这需要多个处理机才能实现。并发的要求更加严格。

进程的定义与特征

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

  • 进程具有动态性、并发性、独立性、异步性

    • 动态性：进程是程序的一次调度过程，而程序是静态的实体
    • 并发性：多个进程同时存在于内存中，能同时运行
    • 独立性：进程是独立运行的基本单位
    • 异步性：进程之间相互制约，存在相关联的关系

  • 进程的结构：程序段、数据段、进程控制块 PCB

  • 进程与程序之间的联系：

    • 进程是动态的，程序是静态的：进程是程序的执行过程
    • 一个进程可以包括多个程序，一个程序也可以启动多个进程

进程状态与控制

进程控制的主要任务是创建和撤销进程，实现进程的状态转换。

大多由内核实现进程控制。

进程是系统进行资源分配的基本单位

线程是处理机调度和分派的基本单位

原语

  • 原语：由若干条指令组成的指令序列，用于实现某个特定功能。

原语是不可分割的，并且必须在内核态执行，常驻于内存。

进程状态及其演变

  • 进程的三种基本状态：就绪态、执行态、阻塞态
    • 就绪态：尚未运行，但只要提供 CPU 就能直接开始执行
    • 执行态：占用处理机资源，当没有进程可执行时，会自动执行系统的 idle 进程（开摆）
    • 阻塞态：等待某种信号的进程，不占用处理机资源

image-20230419133656524

  • 状态转换方式

    • 就绪态 → 运行态：调度程序选择就绪进程，开始运行
    • 运行态 → 就绪态：分配的时间片耗尽；当前存在高优先级进程可被调度（抢占式）
    • 运行态 → 阻塞态：需要等待资源、系统信号、IO 结果等外部信号
    • 阻塞态 → 就绪态：上述等待的信号处理完毕

进程控制块

  • 进程控制块：创建、撤销进程，进程的唯一标志，限制总进程数目

  • 进程控制块的主要内容：

    • 进程标识符：env_id
    • 现场保护区：env_tf
    • 当前状态与程序数据地址等

进程上下文切换 & 陷入内核

  • 进程上下文切换，通常由调度器执行，会切换内存映射
  • 陷入内核：CPU 状态会进入内核态，由中断异常等引起，发生时需要保存执行时现场

相较而言，陷入内核开销较小

线程概念的引入

  • 线程是系统调度和分派的单位，它不基本拥有资源、数据，但有线程栈，同时可以访问所在进程的数据，同进程的所有线程也可以共享所有资源
  • 引入线程可减少切换进程带来的开销、提升进程的并发速度（划分尺度更小），但线程必须依赖进程才能被执行

线程的实现方式

  • 用户级线程 ULT：用户在进程空间中模拟出新的进程
    • ULT 对于系统来说是不可见的，程序外观测不到额外线程
    • ULT 上下文切换快，本质上是用户对虚存空间与时间片的再分配
    • ULT 会因为内核阻塞而导致所有线程都被阻塞（内核看不到其他线程）；即使有多个处理器，ULT 进程也最多占用一个（内核看不到其他线程），无法实现多线程并行执行
  • 内核级线程 KLT：在内核中创建线程，支持线程的分发
    • 内核可以做到调度同进程的多个线程并行执行
    • 线程切换必须使用内核，切换的效率低
  • 混合实现方式：用户空间中可以创建管理线程，内核中存在多个内核线程，需要实现两类线程的映射
image-20230419141435676

  • 线程映射方式：

    • 多用户 → 单内核：用户级线程不可见，用户进行调度，阻塞会全部阻塞
    • 单用户 → 单内核：并发能力强，创建、切换线程开销大
    • 多用户 → 多内核：折中

线程安全

  • 可重入不一定线程安全，但不可重入一定线程安全

4.2 同步与互斥

同步互斥

访问与竞争

程序的并发执行，不可避免地使得共享数据会被多个进程访问，这就造成了资源的竞争

  • 竞争条件：多个进程并发访问、变更同一数据，且执行后结果与访问的顺序相关
  • 临界资源：仅允许一个进程访问的资源；访问临界资源的代码称为临界区

同步与互斥

  • 进程互斥：间接制约关系

    • 两个或以上进程不能同时访问临界资源，否则会发生错误，是程序间的间接作用
    • 互斥是无序访问

  • 进程同步：直接制约关系

    • 各进程间相互合作从而满足程序正常执行需求的过程；当需要前后进程交换信息时，通常使其进入等待，这种制约关系便是进程同步
    • 同步是有序访问，通常同步已经实现了互斥（写入过程必然互斥）

临界区设计：空闲让进，忙则等待，有限等待，让权等待

忙等待解决互斥

  • 忙等待方法的解决方法都是正确的，原理在于使用循环持续检查程序是否能进入临界区（不能进入会原地等待并继续查询）；但是因为使用 while(); 会产生忙等待，而导致性能的浪费

软件互斥算法

repeat:
    entry section
    critical section
    exit section
    remainder section
Until false

面包店算法

  • 顾客进入面包店按照号码从小到大的次序购买面包，并且假定：

    • 面包店按照递增顺序发放号码，并且多个顾客可能拿到相同号码（即不严格递增）
    • 当号码相同时，按照顾客名字排序

  • 当多个进程同时进行号码计算时可能拿到相同号码，此时则按照进程 id 决定进入临界区的顺序

  • 使用 while(); 来循环测试进入互斥区的条件，形成忙等待，消耗 CPU 资源

硬件互斥方法

中断屏蔽

  • 实现简单
  • 单 CPU 系统中可以使用，多 CPU 会出现大幅性能损失
  • 内核进程会少量使用来保证互斥

TS 原语

  • TS(test-and-set)是一种原语，写入新的值后会将旧值传回
  • 在多进程中，如果一个程序处于 TS 原语中，则其他进程不可以使用 TS 原语
  • 相当于原子读写锁的内容，来保证临界区的互斥，但仍然需要忙等待 while

swap 指令

  • swap 是一种交换地址内容的原语，互斥描述如下：
bool k = true;
bool use = false;

while (k != false) {    // check use == 0 ?
    Swap(&use, &k); // use cannot be changed by others now
}                   // use has been changed by the program now
criticalRegionCode();
use = false;
otherRegionCode();
  • swap 也会因为循环 swap 而导致忙等待

信号量解决同步互斥

信号量方法改变了忙等待的特质，使用了阻塞方式休眠进程，避免了不必要的性能损失

信号量机制

  • 使用新的变量类型：semaphore
  • 信号量只能通过初始化和 P(semaphore) V(semaphore) 两个原语访问，不受进程调度的影响
  • S 的值为正时表示可用资源的个数、负表示等待资源的进程个数
semapgore S = ableNumber;
P(S) {
    while (S <= 0) { blockProgram(S); }  
    S--;
}

V(S) {
    S++;
    wakeProgram(S);
}

  • 使用信号量，能解决同步与互斥两类问题：

    • 互斥：S = 1，同时只有一个进程能申请资源（进入临界区）
    • 有限并发：S = const，分配 n 个资源，允许 n 个进程同时使用
    • 同步：S = 0，可以描述进程执行的先后关系，只有在前驱 V 后，自身的 P 才能解除 wait
// 互斥使用：每个进程都先 P 后 V
P(S);
// CODE HERE
V(S);

// 同步使用：后继进程先 P，等待前驱进程 V，传递了可以执行的信号
P(S);
// S != 0
// CODE

// CODE
V(S);
// S == 0
image-20230420005920486
  • 只有前驱任务发出信号后（“释放”资源），后继任务才能从阻塞中脱离（“占用”资源），开始执行任务

一般信号量集

  • SP(S,a,d)：每次申请d个资源，少于a个便不再分配
  • SP(S,1,1)：互斥信号量
  • SP(S,1,0)：每次申请0个资源，s=0时禁止进入临界区

PV 操作优缺点

  • 表达能力强，使用简单
  • 使用不当易发生死锁

管程解决同步互斥

  • 管程把分散地临界区集中起来，可以以函数库的形式实现，是一种高级同步原语
  • 管程由变量、过程、数据结构等组成
  • 互斥：只能同时有一个活跃进程

管程的实现

  • Hoare 管程：执行 signal 的进程等待，直至其他 signal 唤醒

    • 入口等待队列：由于互斥而等待的一般队列
    • 紧急等待队列：由于唤醒操作而自身进入等待的进程队列，优先级高

  • Hansen 管程：signal 放在最后执行，执行后立即退出管程

进程通信的方式

  • 低级通信：只能传递控制信号
  • 高级通信：共享内存、消息系统、管道

管道

  • 管道是半双工的，即单向流动信息，对于管道双方，管道是一个文件系统
  • 无名管道只能用于有亲缘关系的进程，有名管道支持不相关进程
  • 数据传递先进先出，保持队列顺序

消息传递

  • 依靠通信原语实现：send(dst, &message), receive(src, &message)，类似于我们实现的ipc_send
image-20230420105758743

共享内存

  • 避免缓冲复制，最快的 ipc 形式
  • 实质是一块物理内存被同时映射到多个进程的虚拟内存空间，写机制需要同步约束

经典同步互斥问题

生产者-消费者问题

  • 生产者通过有限缓冲区向消费者发送数据，同时只有一个进程可对缓冲区操作

生产者、消费者自身互斥，两者之间同步（先放后取）

信号量设置

semaphore mutex = 1; // 互斥访问量
semaphore empty = N; // 同步使用，缓冲区空闲数量
semaphore full = 0;

实现过程

生产者：

P(empty); // 全满(empty = 0) 则无法放置
P(mutex); // 最后再申请互斥信号量，避免等待死锁
putOne();
V(mutex);
V(full);

消费者：

P(full);
P(mutex);
getOne();
V(mutex);
V(empty);

读者-写者问题

  • 对共享资源的访问操作，写者只允许一个，读者可以不限制数量 ，但是读写也存在互斥

  • 读写者有利：

    • 读者有利：只要有读者开始读，写者就必须一直等待到所有读者结束；写者需要确保没有读进程才能写，写完后允许读者进入
    • 写者有利：输入写后不再允许后续读者进入（reader++操作）
// 写有利

int read_count = 0, write_count = 0;
semaphore read_mutex = 1, write_mutex = 1;
semaphore data_mutex = 1;  // 互斥访问共享数据
semaphore read = 1;

void writer() {
    while (true) {
        P(write_count);
        if (write_count++ == 0) P(read);  //只要有写者，就占着read
        V(write_count);

        P(data_mutex);
        // writing
        V(data_mutex);

        P(write_count);
        if (--write_count == 0) V(read);  //没有写者才释放read
        V(write_count);
    }
}

void reader() {
    while (true) {
        P(read);  // 没有写者才能进入临界区

        P(read_mutex);
        if (read_mutex++ == 0) P(data_mutex);
        V(read_mutex);

        V(read);

        // reading

        P(read_mutex);
        if (--read_mutex == 0) V(data_mutex);
        V(read_mutex);
    }
}

读有利：

写者：

P(wmutex);
doWrite();
V(wmutex);

读者：

P(mutex);
if (reader == 0) {
    P(wmutex);
}
reader++;
V(mutex);
doRead();
P(mutex);
reader--;
if (reader == 0) {
    V(wmutex);
}
V(mutex);

image-20230420112817001

  • rwmutex 满足先到先得，谁先出现，谁先响应

哲学家进餐问题

  • 五个哲学家坐成一圈，并且有五支筷子，哲学家动作包括思考和进餐，如何避免死锁，使得流程进行顺利？

显然不能直接 PV 筷子，这样每人一支肯定会死锁，应该最多允许四个人尝试进餐

4.3 进程调度

调度的概念与问题

  • CPU 调度就是按照一定的策略，从就绪的进程队列中选择一个进程并开始运行的过程
  • 进程调度主要需要考虑：进程调度的算法、进程调度的时机、进程切换的过程

调度的类型

  • 高级调度：又称宏观调度，通常上，高级调度的单位是分钟、小时或更大单位。它从用户工作流程的角度出发，关注宏观。
  • 中级调度：主要涉及内外存交换，从不同级别的存储器中进行内容交换
  • 低级调度：又称微观调度，通常单位是毫秒，特点是执行频率高，从 CPU 资源出发进行调度；
    • 抢占式调度：进程在运行过程中，处理机可能被其他进程抢走（被迫停止）
image-20230503145224087

调度时机与操作

实际上，只要操作系统能够获取到 CPU 的使用权（系统调用、时钟中断等进入内核态），就有可能发生进程的调度

在进行调度前，需要先给当前进程生成快照，保存信息；然后把进程控制块移动至队尾，最后选用其他的控制块并恢复其现场即可

调度性能准则

  • 周转时间：作业从提交到最后完成所经历的时间，包括所有等待、执行、输出等时间

  • 等待时间：用户输入请求到系统开始处理任务所需要的时间

  • 吞吐量、处理机利用率、资源利用率等

调度算法设计要点

进程优先级/数

优先数相当于把优先级用数字具体表示了出来，反映了某个优先级，可以采用静态/动态的方式组织优先级。按优先级排队方式就是按照不同进程优先级进行等待队列排序的一种调度方式。

占用 CPU 的方式

  • 不可抢占式方式：一旦 CPU 资源被分配，除非进程自身进入阻塞状态，或时间片耗尽外，不会让出 CPU
  • 抢占式方式：就绪队列中一旦存在更高优先级进程，就直接进行进程调度

时间片

时间片决定了 CPU 允许进程运行的时间长度：时间片短导致频繁切换进程，会产生大量开销；时间片长又会导致某些进程不能得到及时响应，调度能力退化；同时时间片的设置也与 CPU 硬件能力、进程执行的操作等相关

进程的分类

  • 第一种分类方式：
    • I/O 密集型：频繁进行 I/O，会花费很多时间进行阻塞等待
    • CPU 密集型：计算需求大，需要大量算力进行运算
  • 第二种分类方式：
    • 批处理进程：无需交互、响应，通常自行完成功能
    • 交互式进程：I/O 等交互频繁，同时响应速度要求高
    • 实时进程：实时性高，响应时间短，不能被低优先级进程阻塞，优先处理

批处理系统的调度算法

批处理系统有以下几种常见的调度算法：先来先服务-FCFS，最短时间优先-SJF，最短剩余时间有限-SRTF，最高响应比优先-HRRF

先来先服务 - FCFS

进程按照就绪的顺序进行调度，并采用非抢占式执行，进程阻塞结束后也不会立即抢回 CPU 继续执行，而是重新进入队列排队

  • FCFS 特点：
  • 利于长时间作业，不利于短时间作业
  • 利于 CPU 集中型作业，不利于 I/O、交互集中型作业

短作业优先 - SJF

在 FCFS 的基础上改进，同样采用非抢占式执行，但进程的排队顺序变为占用时间长短，短进程优先执行，用以减少 CPU 的等待时间

  • SJF特点：
  • 提高系统吞吐量，缩短作业总等待时间
  • 不能体现作业之间的优先级，同时对长作业很不利，可能长时间无法运行

最短剩余时间 - SRTF

一言蔽之，抢占式的短作业优先策略。

如果一个新就绪的进程如果时间比当前进程短，就会直接切换，即一直运行剩余时间最短的进程。

  • 持续的短任务可能会导致长任务一直无法运行/被抢占，导致长进程饥饿

最高响应比算法 - HRRF

HRRF 实际上是短作业优先与先到先服务两个算法的结合，即综合考虑作业等待时间和作业运行时间后再进行调度，同时系统是非抢占的。

在每次选择作业投入运行时，先计算每个作业的响应比（RR），然后选择权重最大的投入运行。
$$
RR=1+\frac{已等待时间}{要求运行时间}
$$

  • HRRF特点：
  • 短作业容易获得高权重（同等的等待时间时，其要求运行时间更短）
  • 不会发生饥饿现象（由于等待时间能控制权重，所以长作业不会饥饿）
  • 计算响应比需要时间开销，算法本身的性能较差

交互式系统的调度算法

交互式系统常见调度算法如下：时间片轮转算法、优先级算法、多级队列算法、多级反馈队列算法

时间片轮转算法

各个进程通过轮换运行较短的时间片，使用进程切换来提高进程的并发性和响应时间等特性，从而提高资源利用率

时间片轮转的步骤

  • 按照插入时间形成调度队列
  • 将 CPU 分配给队列头部进程，并运行一个时间片
  • 时间片结束后使用时钟中断来暂停进程，并将该进程移动至队尾
  • 重新分配 CPU，直至所有进程结束

系统是非抢占式的，进程停止运行可以是时钟中断，或是自行让出（阻塞态）。时间片长度过长会导致算法退化为 FCFS，即每个进程都只在单个时间片内运行结束；过短则会导致进程频繁切换，切换上下文的过程中时间开销大。

优先级算法

优先级算法平衡了各进程对响应时间的要求，优先级可以是静态/动态生成的。

  • 静态优先级：在创建进程时就确定该进程的优先级：进程类型（用户/内核），资源需求量、用户等级
  • 动态优先级：在进程调度过程中可能发生动态更改；可以类似于一堆人等着吃饭，厨师看情况再决定给谁先做
    • 进程等待时间过长等可以导致优先级提高（等的时间长了就先做饭）
    • 进程每次执行一个时间片就降低优先级（吃了一点了就后做）

多级队列算法

引入多个就绪队列，并给各个队列不同的优先级，以此调度进程。

不同的队列有不同的优先级、时间片长度、调度策略。例如系统进程和用户进程、不同用户的进程就可以放在不同的就绪队列中用以优先调度

多级反馈队列算法

在多级队列算法和时间片轮转算法基础上发展而来，优先短进程以提高系统吞吐量、缩短平均周转时间；优先 IO 进程以获得更短的响应时间

实际操作：

  • 设置多个不同优先级的就绪队列，并保证优先级越低时间片越长
  • 新进入的进程从最高优先级队列开始插入，如果在该时间片结束后仍未结束，则对其“降级”，即插入下一级的队列中
  • 只有当高优先级队列为空时才能调度低优先级队列中的进程；当出现抢占时，被抢占进程重新插入至原队列末尾，不改变优先级

image-20230507155736703

在这种算法下， I/O 进程通常在最高优先级队列/阻塞队列中，计算进程通常在低优先级队列中

优先级倒置

优先级倒置是高优先级进程被低优先级进程阻塞，或在其之后运行的现象

常见于高、低优先级进程共享临界资源时：当低优先级进程先获取了临界资源，随后被高优先级进程抢占，高优先级进程又需要该临界资源。此时高优先级进程只能阻塞，等待低优先级进程完成临界资源使用后才能恢复。

下图的 Task A 就被 Task C 阻塞了，这里的 Task B 就先于 Task A 运行，产生了优先级的倒置

image-20230507160228040

解决优先级倒置的方式是优先级继承：当高优先级进程阻塞后，可以令等待的目标进程获取和高优先级进程相同的优先级，这样就会立即运行拥有临界资源的进程。

也就是给 Task C 一个和 A 相同的优先级，当 Task A 阻塞后，B 的优先级没有继承后的 C 高，所以不会发生优先级倒置

实时系统的调度算法

实时系统是一种时间起主导作用的系统，也就是说，计算机系统需要对某个外界产生的操作在合适的时间内做出响应，也就是说，操作响应的实时性在这类系统中十分重要。

实时系统的进程要求更详细的调度信息：资源要求、详细优先级、响应截止时间。采用抢占式调度，响应中断快速，采用较小的调度单位（更轻量的线程）

常见的实时调度算法有以下几种：静态表调度、单调速率调度，最早截止时间优先算法

静态表调度算法

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

  • 不需要计算，只按照固定的方案进行，调度的开销最小
  • 拓展性差，只适用于固定的场景，要求系统中只有已知的进程

单调速率调度算法

静态要求下最优的调度算法，开销小，灵活性相对好

  • 任务的周期越小，优先度越高，按照优先级高低进行调度，对于同优先级进程随机调度
  • 该调度是静态、抢占式的

最早截止时间优先算法

按照任务的截止时间设置优先级，优先级越高的任务最先被调度，也就是说优先级是实时变化的，对同优先级进程随机调度。

最低松弛度优先算法

$$
松弛度=截止时间-剩余运行时间-当前时间
$$

该算法按照各进程的松弛度进行进程的调度，当某个进程的松弛度为0时会发生抢占式调度（此刻全力运行该进程才能刚好运行完，换句话说不抢占就完不成了）

多处理机调度

多处理机调度更注重整体的运行效率，对于单个处理机不过分注重其利用率，同时多调度机需要考虑访问的互斥问题；调度单位多为线程

多处理机系统可分为非对称式和对称式两种。

  • 非对称式：各个处理器的地位不同，每个处理器有各自分工，存在一个主处理机向外分发任务
  • 对称式：处理器地位相同，调度算法分集中、分散两种。

对称式处理系统的调度算法

  • 静态分配（集中）：每个 CPU 设立一个就绪队列，进程分配给某个处理器后就不会变更处理器运行；调度算法的开销小，但是各处理器会忙闲不均
  • 动态分配（集中）：所有 CPU 共享一个就绪队列，队首进程分派到空闲 CPU 中运行，能解决忙闲不均问题
  • 自调度（分散）：系统采用一个公共就绪队列，处理机选取适当进程执行，易于移植，相对成熟
    • 不需要处理机进行任务分配，但是共享队列的同步、不同处理机的 cache 等缓存、线程协作等需要设计
  • 成组调度（分散）：分配和阻塞时的单位为一组线程，每次分配都为这组线程寻找一组合适的处理机
    • 成组调度提高了线程的并行度，有利于减少阻塞
    • 可以减少调度次数，从而减少调度算法自身的开销
    • 相当于面向进程分配任务，而不是面向线程

4.4 死锁

死锁的定义

一组进程中，每个进程都无限等待被其他进程所占用的资源，并且将永远获取不到对应资源而无法运行的现象。

四个必要条件

注意这里说的是必要条件，也就是说只要有一个条件被打破，死锁就不会存在

  • 互斥条件：存在互斥资源，并且只能由一个进程占用，只有该进程主动释放，其他进程才能再分配给其他进程
  • 请求并占有条件：当进程无法获得所有资源请求，而被迫阻塞时，不会释放自己已经获得的资源（类似于 sleep 不放锁
  • 不可剥夺条件：进程已获得的资源只能由进程在使用结束后释放
  • 环路等待条件：发生死锁时，必然存在一条环状链将所有发生死锁的进程有序连接
    • 需要注意如果环路中的某个点同时可以请求环路外的某进程所持有的资源，这个环路将不成立，也就是这个回路不一定能锁上

活锁和饥饿

  • 活锁：执行者未被阻塞，但某些条件不满足，导致进程持续尝试（也持续失败
    • 活锁可能会在某次尝试中自行解开，死锁由于陷入等待，无法自救
  • 饥饿：资源分配策略不公平导致某些进程长时间等待，产生饥饿。
    • 通常在短任务优先等抢占式调度方式时，长作业就很容易饥饿

处理死锁的方法

通常采用死锁预防、死锁避免、死锁检测三个方式对死锁进行处理。

死锁预防

死锁预防通过打破死锁的四个必要条件，阻止死锁的形成。是排除死锁的静态策略。

  1. 互斥条件：允许多个进程占用同一个互斥资源（通常不可实现）
  2. 申请且占有条件：实现资源的预分配，当系统能够满足进程的全部资源请求时一次性把所有资源全部分配，否则不分配任何资源
    • 资源的利用率低；同时计算一个动态进程需要的全部资源也很困难
  3. 不可剥夺条件：当请求不能被满足时，进程立刻释放已有的全部资源并等待之后重新申请，相当于这部分已分配的资源被“剥夺”了
  4. 循环等待条件：实施资源有序分配的策略，将所有资源按号分配，并且所有资源请求都必须先申请小号资源，从而避免产生环路。
    • 编号带来的系统开销大；同时会预先占用可能不常用的资源，导致资源利用率低

死锁避免

死锁避免不限制死锁的必要条件，而是动态地检测每一个申请资源的请求，然后再决定是否进行资源分配，是一种排除死锁的动态策略。

安全序列：一个进程的序列，对于其中每一个进程而言，其占用的资源可以被系统可用资源 + 已被序列靠前的进程占用的资源所满足

如果不存在这样一个序列，则系统是不安全的。但是系统不安全不一定会发生死锁，反之，死锁时系统一定处于不安全状态。

银行家算法

银行家把固定资金贷款给若干顾客，在过程中只要不出现超过最大值的请求，应能保证资金安全。

  • 单次请求的最大需求量不超过现有现金时即可处理请求
  • 一次请求中的金额可以分期支付，但总和不会超过请求的最大需求量
  • 当现有现金不能满足请求的请求剩余的金额时，请求会被搁置，但总能处理
  • 当满足了请求的所有需求后，会在一定时间内归还所有资金

这里处理的资源就只有一种：“现金”，而在操作系统中，我们会对可能用到的所有种类的资源都进行如上的限制。

在银行家算法中，我们假定有 $n$ 个进程，同时有 $m$ 种类型的资源

数据定义

  • 可利用资源向量 Available：一个具有 $m$ 个元素的向量，向量的每一个值都代表对应类资源的可用资源数量。即 Available[j] = k 说明第 $j$ 类资源目前可用 $k$ 个。
  • 最大需求矩阵 Max：一个大小为 $n × m$ 的矩阵，定义了所有进程对于所有资源的最大需求数量。即 Max(i, j) = k 说明第 $i$ 个进程最多需要 $k$ 个 $j$ 类资源
  • 分配矩阵 Allocation：一个大小为 $n × m$ 的矩阵，定义已经分配给进程的资源数目，规则类似于 Max 矩阵
  • 需求矩阵 Need ：一个大小为 $n × m$ 的矩阵，定义进程仍需的资源数目。

根据三者关系，易得
$$
Need(i,j)=Max(i,j)-Allocation(i,j)
$$

算法过程

当一个进程发出资源请求后，操作系统会按序进行检查：

  • 如果数量超过了 $Need(i,j)$，说明前提/请求出错
  • 当数量超过了$Available(i,j)$，说明当前资源无法满足请求，进程等待
  • 尝试修改资源矩阵，并进行安全性算法检查；未通过则复原矩阵，拒绝请求

安全性算法

  1. 设置两个向量：
    • Work：一个 m 个元素的向量，表示系统可提供的资源数，初始值与$Available$相同
    • Finish：表示系统是否有足够资源进行分配，初始时为 false
  2. 从进程集合中找到一个进程 $i$，满足：
    • $Finish[i] = false\ \ &&\ \ Work \gt Need(i)$，说明进程 $i$ 可以正常结束，并释放 $Max(i)$ 所占用的全部资源
    • 令 $Finish[i] = true\ \ &&\ \ Work\ += Allocation(i)$，并重复本过程，直至找不到满足条件的进程
  3. 循环结束，检查此刻的 $Finish$ 向量，如果满足所有进程均为 true，则说明系统出于安全状态（能找到一个序列进行资源的分配）；否则系统将处于不安全状态

特点

  • 允许互斥、资源部分分配、满足不可抢占、资源利用率高
  • 要求进程预先计算最大资源请求，难以实现

死锁检测

保存资源的请求、分配信息，判断是否会在分配的过程中发生死锁

资源分配图

资源分配图算法：一个有向图 $G$ 的顶点为资源或进程，这个图的边有两种属性：

  • 进程 → 资源：进程发起资源的请求，也叫请求边
  • 资源 → 进程：资源已经分配给进程，也叫分配边

对于它的进程顶点，也有两种属性：

  • 封锁进程：请求了超过系统中未分配的总数的资源
  • 未封锁进程：与封锁进程相对应

在这样的资源分配图中，若要发生死锁，则图中必须有环，反之则不然。

有环无死锁案例

图中 $R$ 为进程节点， $P$ 为资源节点

资源分配图的化简

对于一个非封锁进程，有如下的化简流程：

  • 对于所有请求边，都转化为分配边
  • 当进程只含有分配边时，说明程序所需的所有资源请求都已满足，这时等待程序结束释放资源
  • 释放资源时将所有的分配边也去掉，只保留进程和资源的节点

死锁定理

系统处于死锁状态，当且仅当资源分配图不可完全化简；换言之，若能消去所有边，即说明资源请求关系已被处理，则系统不处于死锁状态。

死锁解除

死锁解除要求释放资源的进程恢复到原来的状态，保证程序的正常运行。

  • 资源剥夺法：先挂起一些进程，暂时释放它们拥有的资源，供其他进程调度
    • 保证不总是剥夺一个进程的资源，均匀处理
  • 撤销进程法：使全部进程按照某种顺序回退，直至死锁状态消除
    • 经济合算的算法使得进程回退带来的开销最小

小结

死锁小结

章节总结

进程与线程

  • 进程由程序段、数据、进程控制块三部分构成
  • 管道机制允许两个进程按生产者 - 消费者方式进行通信
  • 内核级线程需要进入内核切换，用户级线程不需要；内核级线程可以按线程阻塞，用户级只能按进程
  • 并发进程失去封闭性，指并发进程共享变量，其执行结果与速度有关（可受到外界影响）
  • 关于数据结构的存放：
    • 正文段：全局变量（赋值 → .data、未赋值 → .bss），常量
    • 进程控制块：进程优先级
    • 堆区：malloc 等动态申请的存储区域
    • 栈区：函数调用传递的参数、未赋值的局部变量
  • 进程唤醒指的是重新进入就绪态，并不能直接进入运行态，唤醒类似于 notifyAll，同时要区分唤醒（阻塞 → 就绪）与调度（就绪 → 运行）的区别
  • 用户级线程可以在任意操作系统中执行，因为其实现基于用户程序

处理机调度

  • 对短作业不利的是先进先出算法，所有因抢占式处理不当可能出现饥饿的调度算法都对长作业不利
  • 考虑紧急作业时使用剥夺式优先级算法，提前运行特定任务；考虑人机交互时使用时间片轮转算法，均衡运行各个任务
  • 优先级算法是绝对可抢占的
  • $响应比=\frac{等待时间+运行时间}{运行时间}$
  • $周转时间=处理结束时间-任务进入系统的时间$ ，计算平均周转时间时要记得减去任务进入的时间点

同步与互斥

  • 临界区是指并发进程访问临界资源（共享变量）的代码程序
  • 对并发进程同步的原因是并发进程是异步的
  • 临界区的执行可以被中断，例如申请 I/O，但内核态的临界区不会中断
  • 管程定义了共享数据结构和各种进程在该数据结构上的全部操作
  • 用信号量实现互斥，初值为 1；实现同步，由用户决定
  • 当采用“读/写者优先”的策略时，有可能会使得另一种角色发生饥饿
  • 管程中的 signal 与 V 操作不同，V一定释放信号量，signal 可能没有待唤醒的进程
  • 并发进程是时间上重合的，可能有交互也可能没关系
  • 信箱通信是一种间接通信方式

死锁

  • 破坏四个必要条件的方式：
    • 循环等待：资源有序分配策略
    • 不剥夺：暂时释放已有资源
    • 请求并保持：预先静态分配，运行前一次性申请所有资源
    • 无法破坏互斥条件
  • 资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的关系
  • 当每种资源都只有一个，且出现环路时，必然死锁；若没有前提限制，则不一定死锁
  • 产生死锁的根本原因是系统资源分配不足和进程推进顺序非法