JackCin's blog
JackCin
2023-09-13
目录

进程管理

# 操作系统之进程管理

操作系统之进程管理(上)，研究再多高并发，都不如啃一下操作系统进程！！！ - 知乎 (zhihu.com) (opens new window)

# 一、进程管理

  • 程序是如何运行的？
  • 我们首先了解一下程序与进程区别：
    • 程序:是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
    • 进程(Process):是动态的，是程序的一次执行过程，同一个程序多次执行会对应多个进程。

# 1、进程运行过程

img

  • 由图可知程序会先由：

    1. 编译器编译成机器指令，
    2. 运行之前先把程序放入内存，
    3. 在内存中创建一个进程实体。一个进程实体(进程映像)由PCB、程序段、数据段组成。
    4. 然后CPU从内存中取出指令，
    5. 来运行程序。

  • 进程实体 :

    • PCB：一个程序开始运行前，需要创建对应的进程，也就是创建相应的PCB；
    • 程序段： 包含程序指令；
    • 数据段：包含运行过程中产生的各种数据。

img

# 2、进程实体的组成

img

  • 同时挂三个QQ号，会对应三个QQ 进程，它们的PCB、数据段各不相同，但程序段的内容都是相同的 (都是运行着相同的QQ程序)

  • PCB 是给操作系统用的; 程序段、数据段是给进程自己用的。

  • 引入进程实体的概念后，可把进程定义为: 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

# 3、进程的组织

Linux进程使用 struct task_struct 来定义管理进程，源码字段如下:

struct task_struct {
 /*
  * offsets of these are hardcoded elsewhere - touch with care
  */
 volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
 unsigned long flags; /* per process flags, defined below */
 int sigpending;
 mm_segment_t addr_limit; /* thread address space:
       0-0xBFFFFFFF for user-thead
      0-0xFFFFFFFF for kernel-thread
      */
 struct exec_domain *exec_domain;
 volatile long need_resched;
 unsigned long ptrace;

 int lock_depth;  /* Lock depth */

/*
 * offset 32 begins here on 32-bit platforms. We keep
 * all fields in a single cacheline that are needed for
 * the goodness() loop in schedule().
 */
 long counter;
 long nice;
 unsigned long policy;
 struct mm_struct *mm;
 int processor;
 ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

img

  • Linux 把所有的进程使用双向链表连接起来。

# 4、进程的状态与转换

img

  • 创建态：进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB；
  • 就绪态：当进程创建完成后，便进入“就绪态”， 处于就绪态的进程已经具备运行条件， 但由于没有空闲CPU，就暂时不能运行；(学完了，没人给机会表现😭)
  • 运行态：如果一个进程此时在CPU上运行，那么这个进程 处于“运行态”。 CPU会执行该进程对应的程序(执行指令序列)；
  • 阻塞态：在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)。 在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”。当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行；
  • 终止态：一个进程可以执行 exit 系统调用，请求操作系统终止该进程。 此时该进程会进入“终止态”，操作系统会让该进程下CPU， 并回收内存空间等资源，最后还要回收该进程的PCB。 当终止进程的工作完成之后，这个进程就彻底消失了。

img

进程之间的转换， 就绪运行和阻塞三种状态之间的转换，大部分人总是记不住，其实很简答，死背硬记肯定是不行的，只需要记住下面几条，这个转换关系自己就能在脑海中画出来。

注意点：

  1. 阻塞态->就绪态 不是进程自身能控制的，是一种被动行为;（程序一直阻塞着等待获取某种资源或者信号，一旦获取了资源或者有信号通知阻塞态进程，那么他就可以变成就绪态等待CPU来执行它）
  2. 运行态->阻塞态是一种进程自身做出的主动行为；(程序运行到一半需要等待资源（临界资源、临界区等）; 或者需要进行 I/O输入输出、读写内存，都是程序主动的行为)
  3. 不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态(因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求)

  • 就绪态、阻塞态、运行态本质区别：

    • 阻塞态：进程停止，缺必要的资源，给CPU调度机会也不能运行

    • 就绪态：进程停止，资源都不缺，就缺CPU调度，给CPU调度就能运行

    • 运行态：什么都不缺，正在运行的进程

# 二、进程控制

# 1、为什么需要原语

  • 进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
  • 如何实现进程的控制？
    • 答：用“原语实现”。

img

img

  • 原语的执行具有“原子性”，一气呵成。

  • 那么，为何进程控制(状态转换)的过程要“一气呵成”?

  • 举个栗子：假设PCB中的变量 state 表示进程当前所处状态，1表示就绪态，2表示阻塞态...

img

假设此时进程2等待的事件发生了，则操作系统中，负责进程控制的内核程序至少需要做这样两件事:

  1. 将PCB 2的 state 设为 1;
  2. 将PCB 2从阻塞队列放到就绪队列;

完成了第一步后收到中断信号，那么PCB 2 的 state=1，但是它却被放在阻塞队列里，主要原因就是第一，第二步操作不是一个原子操作。

那么，这个原语厉害呀，lua脚本也可以实现这种原子操作redis，那么这个原语的原子性是怎么实现的呢？

# 2、原语的实现

在了解原语实现之前，我们有必要先了解一下中断机制（）。

  • 可以用 “关中断指令”和“开中断指令”这两个特权指令实现原子性。
  • 正常情况:CPU每执行完一条指令都会例行检查是否有中断信号需要处理，如果有，则暂停运行当前这段程序，转而执行相应的中断处理程序。CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。

img

  • 以下四张图是进程创建，终止，阻塞和唤醒，切换时候的原语操作

img

img

img

img

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

    • 1、更新PCB中的信息

      • 所有的进程控制原语一定都会修改进程状态标志；

      • 剥夺当前运行进程的CPU使用权必然需要保存其运行环境；

      • 某进程开始运行前必然要恢复其运行环境；

    • 2、将PCB插入合适的队列

    • 3、分配/回收资源

# 3、中断机制

  • 关中断和开中断其实就是像我们生活中的开关一样。关中断是为了保护一些不能中途停止执行的程序而设计的，计算机的CPU进行的是时分复用，即每个时钟周期内，CPU只能执行一条指令。

  • 在多道程序设计的环境下（就是我们通常所说的多个程序同时运行时），CPU是不断地交替地将这些程序的指令一条一条的分别执行，这样从宏观上看我们就感觉多个程序是在同时执行，但从微观上看则是**CPU在不同的时间段（极短）内执行着不同程序的单条指令**。

  • 而CPU在这些指令之间的切换就是通过中断来实现的。关中断就是为了让CPU在一段时间内执行同一程序的多条指令而设计的，比如在出现了非常事件后又恢复正常时，CPU就会忙于恢复非常事件出现之前计算机的工作环境（通常叫做恢复现场），在恢复现场的时候，CPU是不允许被其他的程序打扰的，此时就要启动关中断，不再相应其他的请求。当现场恢复完毕后，CPU就启动开中断，其他等待着的程序的指令就开始被CPU执行，计算机恢复正常。

  • 中断的分类这里就不列举了，感兴趣的宝宝可以自己去搜索一下。

# 三、进程通信

img

  • 进程通信分为共享存储，消息传递，管道通信。

  • 顾名思义，进程通信就是指进程之间的信息交换。进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

# 1、共享内存

img

  • 为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的。那么该怎么共享呢？

img

  • 注意点：

    1. 两个进程对共享空间的访问必须是互斥的(互斥访问通过操作系统提供的工具实现)。

    2. 操作系统只负责提供共享空间和同步互斥工具(如P、V操作)

  • 共享存储分为两种方式：

    1. **基于数据结构的共享 **: 比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式；

    2. **基于存储区的共享 **: 在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

# 2、管道通信

img

  • “管道”是指用于连接读写进程的一个共享文件，又名pipe 文件。其实就是在内存中开辟 一个大小固定的缓冲区。
    1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道；
    2. 各进程要互斥地访问管道；
    3. 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞；
    4. 如果没写满，就不允许读。如果没读空，就不允许写；
    5. 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

# 3、消息传递

  • 进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

  • 消息包括消息头和消息体，消息头包括:发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息(计算机网络中发送的“报文”其实就是一种格式化的消息)。

  • 消息直接挂到接收进程的消息缓冲队列上, 消息要先发送到中间实体(信箱)中，因此也称“信箱通信方式”。Eg:计网中的电子邮件系统。

img

# 4、小结

img

# 四、线程

img

  • 上图就是线程的基本属性。

img

# 1、三种线程模型

  • 每一种线程模型的实现我们都围绕四个话题展开：
    1. 线程的管理工作由谁来完成?
    2. 线程切换是否需要CPU变态?
    3. 操作系统是否能意识到用户级线程的存在?
    4. 这种线程的实现方式有什么优点和缺点?

# 2、多对一模型

  • 历史背景:早期的操作系统(如:早期Unix)只支持进程，不支持线程。当时的“线程”是由线程库实现的。

img

  • 多对一模型:多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

  • 线程模拟实现代码如下：

img

  • 从代码的角度看，线程其实就是一段代码逻辑。 上述三段代码逻辑上可以看作三个“线程”。 while 循环就是一个最弱智的“线程库”，线程库完成了对线程的管理工作(如调度)。

  • 很多编程语言提供了强大的线程库，可以实现应用线程的创建、销毁、调度等功能。

  • 多对一模型特点：

    1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责(包括线程切换)
    2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
    3. 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”
    4. 优缺点
      • 优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
      • 缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

注意：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

# 3、一对多模型

大多数现代操作系统都实现了内核级线程，如 应用 Windows、Linux。

img

一对一模型: 一个用户级线程映射到一个内核态核级线程。每个用户进程有与用户级线程同数量的内核级线程。

  • 一对一模型特点：

    1. 内核级线程的管理工作由操作系统内核完成；

    2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成；

    3. 操作系统会为每个内核级线程建立相应的 TCB (Thread Control Block，线程控制块)， 通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”；

    4. 优缺点

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

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

  • 值得注意的是，一对一模型由于每创建一个用户线程就要创建一个相应的内核线程，由于创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数实现限制了系统支持的线程数量。Linux，还有 Windows 操作系统的家族，都实现了一对一模型。

Java使用的就是一对一线程模型，它的一个线程对应于一个内核线程，调度完全交给操作系统来处理，所以切换线程的代价很大，线程数调参是Java工程里面重要的一个环节。
1

# 4、多对多模型

img

  • 多对多模型: n个用户级线程映射到m个内核级线程(n >= m)。每个用户进程对应 m 个内核级线程。
  • 内核级线程才是处理机分配的单位。例如:多核CPU环境下，左边这个进程最多能被分配两个核。

多对多模型特点：

  1. 克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点；
  2. 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞；
  3. 虽然多对多模型允许开发人员创建任意多的用户线程，但是由于内核只能一次调度一个线程，所以并未增加并发性。
  4. 当一个用户线程执行阻塞系统调用时，内核可以调度另一个用户线程来执行。
  5. 区别于一对一模型，它的进程里的所有用户线程并不与内核线程一一绑定，而是可以动态绑定内核线程， 当某个内核线程因为其绑定的用户线程的阻塞操作被内核调度让出CPU时，其关联的进程中其余用户线程可以重新与其他内核线程绑定运行。

这个是GO语言这些年这么火热的基础，Go语言中的协程goroutine调度器就是采用的这种实现方案，在Go语言中一个进程可以启动成千上万个goroutine，goroutine非常轻量，一个goroutine只占几KB，并且这几KB就足够goroutine运行完，这就能在有限的内存空间内支持大量goroutine，支持了更多的并发。

img

# 5、小结

img

  • 了解这些线程模型，对每种语言的机制，以及对那些高并发机制，优缺点，其实就会有更加深刻的理解。

# 五、进程调度

  • 当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

img

  • 先关注三个问题， 进程调度的时机，进程的切换与过程，进程调度方式。

# 1、进程调度的时机

  • 进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

img

img

解释一下两个名词：

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区：访问临界资源的那段代码。

# 2、进程的切换与过程

  • 广义的进程调度包含了选择一个进程和进程切换两个步骤。 进程切换的过程主要完成了:
    1. 对原来运行进程各种数据的保存;
    2. 对新的进程各种数据的恢复 (如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)

# 3、进调度的方法

  • 非剥夺调度方式，又称非抢占方式。

    • 即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
    • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统.

  • 剥夺调度方式，又称抢占方式。

    • 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

    • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统.

img

# 4、调度算法的评价指标

img

  • 很多指标看名称就能知道，这个地方我重点说一下**CPU利用率和系统吞吐量**,这两个指标也是现在很多架构并发，或者 java 垃圾回收器主要考虑的两个指标。

  • ①「CPU利用率」

    • CPU利用率: 指CPU “忙碌”的时间占总时间的比例。
    • 利用率 = 忙碌的时间 / 总时间
    • Eg:某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒， 再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中， CPU利用率=（5+5）/（5+5+5）

  • ②「系统吞吐量」

    • 对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业。

      • 系统吞吐量:单位时间内完成作业的数量
      • 系统吞吐量= 总共完成了多少道作业 / 总共花了多少时间

    • Eg:某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为? 10/100 = 0.1 道/秒.

  • 没有最好的调度算法，只有最合适的算法，实际应用中取什么算法，主要根据自身场景是更加追求响应时间，还是系统吞吐量。

  • 例如：垃圾回收器中，CMS是响应时间有优先，以获取最小停顿时间为目的，为了减少STW，牺牲了一定的吞吐量。在一些对响应时间有很高要求的应用或网站中，用户程序不能有长时间的停顿，CMS 可以用于此场景；UseParalleGC+UseParalleoldGC 垃圾回收器是吞吐量优先，但是需要长时间的STW。

# 5、调度算法

  • Tips:各种调度算法的学习思路

    • 算法思想
    • 算法规则
    • 这种调度算法是用于作业调度还是进程调度?
    • 抢占式?非抢占式?
    • 优点和缺点
    • 是否会导致饥饿

  • ①「适合早起批处理系统」

img

  • 这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

  • ②「适合交互式系统」

img

  • 比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统(包括 分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)

  • 具体的算法这里不展开,可自行查阅。。。。

# 六、进程同步，进程互斥

# 1、进程同步

  • 进程具有异步性的特征。

    • 异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

  • 看一个例子:进程通信——管道通信。

img

  • 读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行的。 如何解决这种异步问题，就是 “进程同步”所讨论的内容。

  • 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

# 2、进程互斥

  • 进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/O设备)。

  • 有两种共享方式：

      1. 互斥共享方式： 系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源；
      1. 同时共享方式： 系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问.

  • 我们把一个时间段内只允许一个进程使用的资源称为"临界资源"。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

  • 对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。

    • 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

# 3、临界区的互斥访问

  • 对临界资源的互斥访问，可以在逻辑上分为如下四个部分:

img

  • 临界区是进程中访问临界资源的代码段。

  • 进入区和退出区是负责实现互斥的代码段。

  • 临界区也可称为“临界段”。

有个问题：如果一个进程暂时不能进入临界区，那么该进程是否应该一直占着处理机?该进程有没有可能一直进不了临界区?

//为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:
1
    1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
    2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
    3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿);
    4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

img

# 4、进程互斥的软件实现方法

img

# ①「单标志法」

​ 算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

img

  • 解释：turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。 若 P1 先上处理机运行，则会一直卡在 5。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。 代码 1 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间即时切换回 P1，P1依然会卡在 5。 只有 P0 在退出区将 turn 改为 1 后，P1才能进入临界区。

  • 缺点：只能按 P0 -〉 P1 -〉 P0 -〉 P1 -〉......这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。

  • 因此，单标志法存在的主要问题是:违背“空闲让进”原则。

# ②「双标志检查法」

​ 算法思想:设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

img

  • 缺点：若按照 152637....的顺序执行，P0 和 P1 将会同时访问临界区。 因此，双标志先检查法的主要问题是:违反“忙则等待”原则。 原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

# ③「双标志后检查法」

​ 算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

img

  • 若按照 1526....的顺序执行，P0 和 P1 将都无法进入临界区 因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待” 原则，会因各进程都长期无法访问临界资源而产生**“饥饿”现象**。 两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

# ④「Peterson 算法」

​ 算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。

img

❝ 谁最后说了“客气话”，谁就失去了行动的优先权。 Eg: 过年了，某阿姨给你发压岁钱。 阿姨: 乖，收下阿姨的心意~ 你: 不用了阿姨，您的心意我领 阿姨:对阿姨来说你还是个孩子，你就收下吧 结局... ❞

Peterson 算法用软件方法解决了进 程互斥问题，遵循了空闲让进、忙 则等待、有限等待 三个原则，但是 依然未遵循让权等待的原则。

Peterson 算法相较于之前三种软件 解决方案来说，是最好的，但依然 不够好。

img

# 5、进程互斥的硬件实现

img

# 5.1 中断屏蔽方法

「中断屏蔽方法」

img

  • 优点：简单、高效；

  • 缺点：

    • 不适用于多处理机;
    • 只适用于操作系统内核进程;
    • 不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

# 5.2 TestAndSet指令

「TestAndSet指令」

  • 简称 TS 指令，也有地方称为 TestAndSetLock（检测和设置🔒） 指令，或 TSL 指令 TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

img

  • 解释：
    • 若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。
    • 若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
  • 相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
  • 优点：
    • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;
    • 适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

# 5.3 Swap指令

「Swap指令」

  • 有的地方也叫 Exchange 指令，或简称 XCHG 指令。 Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言 述的逻辑：

img

  • 逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在 old 变量上)，再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

  • 优点：

    • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;
    • 适用于多处理机环境

  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从 而导致“忙等”。

img

# 8、JAVA 并发包 CAS 实现

「JAVA 并发包CAS实现，对Swap指令的利用」

  • （这块没看懂，跳过了。。。。😥😥😥）

  • java.util.concurrent.atomic 包下有个原子类 AtomicInteger，其中的 compareAndSet 方法即 CAS。CAS 全称是 compare and swap，是一种用于在多线程环境下实现同步功能的机制。代码如下：

public class AtomicInteger extends Number implements java.io.Serializable {

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            // 计算变量 value 在类对象中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    
    public final boolean compareAndSet(int expect, int update) {
        /*
         * compareAndSet 实际上只是一个壳子，主要的逻辑封装在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    // ......
}

public final class Unsafe {
    // compareAndSwapInt 是 native 类型的方法，继续往下看
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);
    // ......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

  • 在 Java 中，Java 并没有直接实现 CAS，CAS 相关的实现是通过 C++ 内联汇编的形式实现的。Java 代码需通过 JNI 才能调用，compareAndSwapInt 是 native 类型的方法。

  • CAS 底层的实现离不开处理器的支持。C++底层代码，其实核心代码就是一条带 lock 前缀的 cmpxchg 指令，即lock cmpxchg dword ptr [edx], ecx.

交换指令：CMPXCHG、XCHG
1
  1. CPMXCHG

用于比较并交换操作数，CPU对CAS的原语支持 非原子性，最早用于单核CPU

  1. XCHG

用于交换两个操作数 具备原子性，CPU会自动加LOCK前缀

LOCK前缀:
1
  1. 作用 CPU保证被其修饰的指令的原子性。
  2. 实现方式
  • 依赖内存有序模型，来保证读取指令有序；
  • 通过总线锁或缓存一致性，保证被修饰指令操作的数据一致性：
当访问的数据在系统内存时，通过在总线锁实现原子性； 当访问的数据在处理器的缓存时，通过缓存一致性协议实现原子性；
举个栗子:
1
2

  • volatile 关键字有两个作用，一个是保证线程可见性，一个是禁止指令重排。Java的DCL中若返回的变量不加volatile修饰，则可能会由于指令重排导致另一个线程获取到一个非完全初始化的对象。

  • 当volatile修饰的变量所在的代码段成为热点，被JIT编译为汇编代码后，会增加LOCK前缀来禁止指令重排和来保证数据一致；具体的详细的，可以移步一篇博客文“https://www.cnblogs.com/ITPower/p/13580691.html (opens new window)”

# 9、信号量机制

  • 这个信号量，非常的抽象，他到底是什么？

# 9.1 什么是信号量

​ ❝ 信号量就是在一个叫做互斥区的门口放一个盒子，盒子里面装着固定数量的小球，每个线程过来的时候，都从盒子里面摸走一个小球，然后去互斥区里面浪，浪开心了出来的时候，再把小球放回盒子里。如果一个线程走过来一摸盒子，得，一个球都没了，不拿球不让进啊，那就只能站在门口等一个线程出来放回来一个球，再进去。这样由于小球的数量是固定的，那么互斥区里面的最大线程数量就是固定的，不会出现一下进去太多线程把互斥区给挤爆了的情况。这是用信号量做并发量限制。

另外一些情况下，小球是一次性的，线程拿走一个进了门，就把小球扔掉了，这样用着用着小球就没了，不过有另外一些线程（一般叫做生产者）会时不时过来往盒子里再放几个球，这样就可以有新的线程（一般叫做消费者）进去了，放一个球进一个线程，这是信号量做同步功能。这种就是生产者消费者模型。 ❞

  • 信号量其实就是一个变量 (可以是一个整数，也可以是一个结构体)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为 1 的信号量。

# 9.2 信号量实现

  • 我们前面说到进程控制的时候，花了大篇的篇幅来讲原语，信号量机制就是利用了原语操作。前面看进程互斥的软件实现方式的时候，各种的编码方式，各种的名称，其实主要是因为读和写操作不是一个原子操作，即然原语可以保证原子操作，利用在这里再好不过了。

  • 一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

  • wait、signal 原语常简称为 P、V操作(来自荷兰语 proberen 和 verhogen)。信号量（Semaphore）也称为信号灯，典故来源于荷兰：火车根据旗标来决定是否通行。其实就是红绿灯的作用。

# 9.3 信号量作用

  • 信号量可以实现进行互斥，进程同步，进程的前驱关系
一个信号量对应一种资源
1
  • 信号量的值 = 这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源);
  • P( S ) —— 申请一个资源S，如果资源不够就阻塞等待;
  • V( S ) —— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程;

信号量可以实现进行互斥，进程同步，进程的前驱关系。以实现前驱关系举例：

  • 进程 P1 中有句代码 S1，P2 中有句代码 S2 ，P3中有句代码S3 ...... P6 中有句代码 S6。这些代码要求按如下前驱图所示的顺序来执行:

img

代码实现如下图：

img

  • 每个进程都需要申请和释放自己对应的资源。
      1. 信号量解决 生产者-消费者 问题
      1. 信号量解决 多生产者-多消费者 问题
      1. 信号量解决 哲学家进餐 问题
      1. 信号量解决 读者-写这 问题

# 10、管程

# 10.1 为什么要引入管程

  • 信号量机制存在的问题: 编写程序困难、易出错；进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。.

  • 能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?

  • 1973年，Brinch Hansen 首次在程序设计语言 (Pascal) 中引入了“管程”成分：一种高级同步机制。

# 10.2 管程定义和基本特征

❝ 引用一段专业书里对管程的介绍: 在利用管程实现进程同步时，当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上。仅当另一个进程访问完成并释放该资源后，管程才又调用signal原语，唤醒等待队列中的队首进程。但是，考虑这样一种情况：当一个进程调用了管程后，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除；在此期间，如果该进程不释放管程，则其它进程就无法进入管程，被迫长时间等待。 为了解决这个问题，引入条件变量condition。通常，一个进程被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问智能在管程中进行。 ❞ ❝ wiki百科的简单定义: 管程 (英语：Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。 这些共享资源一般是硬件或一群变量。管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。 与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。 ❞

  • 管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。

  • 管程(monitor)只是保证了同一时刻只有一个进程在管程内活动,即管程内定义的操作在同一时刻只被一个进程调用(由编译器实现).但是这样并不能保证进程以设计的顺序执行,因此需要设置condition变量,让进入管程而无法继续执行的进程阻塞自己.

  • 管程是一种特殊的软件模块，有这些部分组成:

      1. 局部于管程的共享数据结构说明;
      2. 对该数据结构进行操作的一组过程;
      3. 对局部于管程的共享数据设置初始值的语句;
      4. 管程有一个名字。

  • 管程的基本特征:

      1. 局部于管程的数据只能被局部于管程的过程所访问;
      2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
      3. 每次仅允许一个进程在管程内执行某个内部过程。

# 10.3 管程解决互斥和同步问题

  • 管程如何解决互斥和同步问题：

互斥问题：

    1. 管程是互斥进入，管程提供了入口等待队列：存储等待进入同步代码块的线程;
    2. 管程的互斥性是由编译器负责保证的。

同步问题: 管程中设置条件变量，等待/唤醒操作，以解决同步问题。

  1. 条件变量（java里理解为锁对象自身）
  2. 等待操作：可以让进程、线程在条件变量上等待（此时，应先释放管程的使用权，不然其它线程、进程拿不到使用权）；将线程存储到条件变量的等待队列中。
  3. 发信号操作：也可以通过发送信号将等待在条件变量上的进程、线程唤醒（将等待队列中的线程唤醒）

# 11、synchronized 底层原理-管程

  • synchronized（同步）是语法糖，会被编译器编译成：1个monitorenter 和 2个monitorexit（一个用于正常退出，一个用于异常退出）。monitorenter 和 正常退出的monitorexit中间是synchronized包裹的代码.
  • monitor（管程）

img

img

  • synchronized是重量级锁，存储了是指向monitor的指针。monitor(又称管程)，在Java中是ObjectMonitor(JVM源码中C++实现)来实现管程。

img

  • synchronized 内部实现流程：
    • 想要获取monitor的线程先进入monitor的_EntryList（entry 进入）队列阻塞等待。即遇到 synchronized（同步的）关键字时。
    • 如果monitor的_owner(所有者)为空，则从队列中移出并赋值与_owner。
    • 如果在程序里调用了wait()方法，则该线程进入 _WaitSet 队列。注意 wait方法我们之前讲过，它会释放monitor锁，即将 owner赋值为null并进入 _WaitSet 队列阻塞等待。这时其他在_EntryList中的线程就可以获取锁了。
    • 当程序里其他线程调用了notify/notifyAll方法时，就会唤醒_WaitSet中的某个线程，这个线程就会再次尝试获取monitor锁。如果成功，则就会成为monitor的owner。
    • 当程序里遇到synchronized关键字的作用范围结束时，就会将monitor的owner设为null，退出。

调用的方法自然也是管程提供的方法，如下图：

img

# 七、死锁

# 1、什么是死锁

  • 在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

# 2、死锁、饥饿、死循环的区别

img

# 3、死锁产生的必要条件

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

# 八、 死锁的处理策略

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

# 1、预防死锁

img

  • 用SPOOLing技术将打印机改造为共享设备...

img

  • 核心就是破坏死锁产生的四个必要条件中的一个或几个。

# 2、避免死锁 - 银行家算法

  • 先看一个借钱的例子：

❝ 你是一位成功的银行家，手里掌握着100个亿的资金... 有三个企业想找你贷款，分别是 企业B、企业A、企业T，为 述方便，简称BAT。 B 表示:“大哥，我最多会跟你借70亿...” A 表示:“大哥，我最多会跟你借40亿...” T 表示:“大哥，我最多会跟你借50亿...” 然而...江湖中有个不成文的规矩:如果你借给企业的钱总数达不到企业提出的最大要求，那么不管你之前给企业借了多少钱，那些钱都拿不回来了... 刚开始，BAT三个企业分别从你这儿借了 20、10、30 亿 ... ❞

img

  • 第二步，假如，再给B借30亿，这样是不安全的...之后手里只剩10亿，如果BAT都提出再借20亿的请求，那么任何一个企业的需求都得不到满足...如下：

img

  • 这样肯定不行，这不是银行家，这是马大哈。

# 2.1 安全序列

  • 这种场景，涉及到一个安全序列。
  • 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。如下图，借钱就达到了一个安全序列：

img

第二步，给A借 20 亿是安全的，因为存在 T-〉B-〉A 这 样的安全序列。

# 2.2 银行家算法

  • 银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。

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

  • BAT 的例子中，只有一种类型的资源——钱，但是在计算机系统中会有多种多样的资源，应该怎么把算法拓展为多种资源的情况呢?

  • 举例：可以把单维的数字拓展为多维的向量。比如:系统中有5个进程 P0~P4，3 种资源 R0~R2，初始数量为 (10, 5, 7)，则某一时刻的情况可表示如下:

img

  • 此时总共已分配 (7, 2, 5)，还剩余 (3, 3, 2) 可把最大需求、已分配的数据看作矩阵， 两矩阵相减，就可算出各进程最多还需要多少资源了。

  • 经对比发现，(3, 3, 2)可满足 P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因此P1、P3 一定可以顺利的执行完，并归还资源。 可把 P1、P3 先加入安全序列。

img

  • (2, 0, 0) + (2, 1, 1) + (3, 3, 2) = (7, 4, 3)， 剩下的 P0、P2、P4 都可被满足。同理，这些进程都可以加入安全序列。 于是，5个进程全部加入安全序列，说明此时系统处于安全状态，暂不可能发生死锁。

  • 银行家算法步骤:

    1. 检查此次申请是否超过了之前声明的最大需求数
    2. 检查此时系统剩余的可用资源是否还能满足这次请求
    3. 试探着分配，更改各数据结构
    4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

  • 安全性算法步骤:

    1. 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
    2. 不断重复上述过程，看最终是否能让所有进程都加入安全序列。

# 3、死锁的检测和恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

# 3.1检测

  • 为了能对系统是否已发生了死锁进行检测，必须:

    • 用某种数据结构来保存资源的请求和分配信息;

    • 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

img

  • 上图为资源分配图，其中方框表示资源结点，圆圈表示进程结点，进程结点向资源结点请求资源；资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

  • 图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

  • 每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

  • 使用类似于这种的算法来进行检测，当然实际实现还会有比这个更加牛的算法来进行检测。

# 3.2 解除

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

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

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

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

编辑 (opens new window)
上次更新: 2023/09/13, 12:29:52
内存管理
文件管理

← 文件管理→

最近更新
01
51单片机及补充知识
09-13
02
独立按键
09-13
03
LCD1602液晶显示器
09-13
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Evan Xu | MIT License