进程、线程、死锁

2020-02-12

技术探索

操作系统

🗨️字数统计=8.9k字 ⏳阅读时长≈30分钟

🎉 进程、线程、死锁

一、进程的概念、组成、特征

1. 概念

进程（Process）：是动态的，是程序的一次执行过程。进程是资源分配的基本单位。

2. 进程的组成

PCB是给操作系统用的。

程序段、数据段是给进程自己用的

① 进程控制块 PCB

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”——PID（ProcessID，进程ID）
操作系统要记录PID、进程所属用户ID（UID）（基本的进程描述信息，可以让操作系统区分各个进程）
还要记录给进程分配了哪些资源（如：分配了多少内存、正在使用哪些I/O设备、正在使用哪些文件）
还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等）

这些信息都被保存在一个数据结构PCB（ProcessControlBlock）中，即 进程控制块

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中

PCB 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其PCB

② 程序段

程序的代码（指令序列）

比如：

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

③ 数据段

运行过程中产生的各种数据（如：程序中定义的变量）

3. 进程的特征

程序是静态的，进程是动态的，相比于程序，进程拥有以下特征：

动态性 ：进程是程序的一次执行过程，是动态的产生，变化和消亡的
动态性是进程最基本的特征
并发性：内存中有多个进程实体，各进程可以并发执行
独立性：进程是能独立运行，独立获得资源，独立接收调度的基本单位
异步性：各进程按照各自独立的，不可预知的速度向前推进。
异步性会导致并发程序执行结果的不确定性。操作系统要提供进程同步机制来解决异步问题
结构性：每个进程配置一个唯一PCB

二、进程的状态

1. 三态模型

运行(running)态：进程占有处理器正在运行。
就绪(ready)态：进程具备运行条件，等待系统分配处理器以便运行。
阻塞态/等待(wait)态：指进程不具备运行条件，正在等待某个事件的完成。

2. 五态模型

进程的五种状态：

创建状态(new) ：进程正在被创建，尚未到就绪状态。
就绪状态(ready) ：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
运行状态(running) ：进程正在处理器上上运行(单核CPU下任意时刻只有一个进程处于运行状态)。
阻塞状态(waiting)：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
结束状态(terminated)：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

应该注意以下内容：

只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

三、进程控制（实现进程状态转换）

1. 概念

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

简化理解：进程控制就是要实现进程状态转换

2. 如何实现进程控制

用 “原语”实现。原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断

思考：为何进程控制（状态转换）的过程要“一气呵成”？

答：如果不能“一气呵成”，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作

3. 进程控制相关的原语

① 进程的创建

② 进程的终止

③ 进程的阻塞和唤醒

④ 进程的切换

四、进程通信 IPC

1. 概念

顾名思义，进程通信（ IPC——InterProcess Communication）就是指进程之间的信息交换

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些进程之间通信的方法。

共享存储
消息传递
管道通信

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；

进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

2. 进程通信的方法

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种通信方式

两个进程对共享空间的访问必须是互斥的（这种方式需要依靠某种同步操作，如互斥锁和信号量等）。

② 管道 / 匿名管道 (Pipes)

“管道”是指用于连接读写进程的一个共享文件，又名 pipe 文件。其实就是在内存中开辟一个大小固定的缓冲区

管道是通过调用 pipe 函数 创建的，fd[0] 用于读，fd[1] 用于写。

1	int pipe(int fd[2]);

管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道。
数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
如果没写满，就不允许读。如果没读空，就不允许写。
数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。
只能在父子进程或者兄弟进程中使用。

③ 有名管道 / FIFO (Names Pipes)

匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。

有名管道严格遵循 先进先出(first in first out)。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信，去除了管道只能在父子进程中使用的限制。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

④ 消息队列 (Message Queuing)

消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。
消息队列允许一个或多个进程向它写入与读取消息.
管道和消息队列的通信数据都是先进先出的原则。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。比FIFO更有优势。
消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

⑤ 信号量 semaphore

信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。

详见下文 八、信号量机制 Semaphore

⑥ 信号 signal

Attention: 信号和信号量是完全不同的两个概念！

信号：是一种处理异步事件的方式。是由用户、系统或者进程发送给目标进程的信息，以通知目标进程某个状态的改变或系统异常。
信号量：信号量是一个特殊的变量，它的本质是计数器，信号量里面记录了临界资源的数目，有多少数目，信号量的值就为多少，进程对其访问都是原子操作（pv操作，p：占用资源，v：释放资源）。它的作用就是，调协进程对共享资源的访问，让一个临界区同一时间只有一个进程在访问它。

⑦ 套接字(Sockets)

此方法主要用于在客户端和服务器之间通过网络进行通信。

套接字是支持TCP/IP的网络通信的基本操作单元，是应用层和传输层之间的桥梁，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以它可用于不同机器间的进程通信。

五、线程的概念和特征

1. 什么是线程

线程是独立调度的基本单位。

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

一个进程中可以有多个线程，它们共享进程资源。

QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。

2. 为什么要引入线程

进程是资源分配的基本单位，由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。

类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

3. 线程的特征和优点

进程间并发，开销很大。线程间并发，开销更小
引入线程机制后，并发带来的系统开销降低，系统并发性提升
注意：从属于不同进程的线程间切换，也会导致进程的切换！开销也大！
从属同一进程的各个线程共享进程拥有的资源。
进程间通信必须请求操作系统服务（CPU要切换到核心态），开销大。
同进程下的线程间通信，无需操作系统干预，开销更小
注意：从属于不同进程的线程间通信，也必须请求操作系统服务！
引入线程前，进程既是资源分配的基本单位，也是调度的基本单位。
引入线程后，进程是资源分配的基本单位，线程是资源调度的基本单位。线程也有运行态、就绪态、阻塞态
在多CPU环境下，各个线程也可以分派到不同的CPU上并行地执行。

4. 进程和线程的区别

Ⅰ 拥有资源
进程是资源分配的基本单位，线程不拥有资源(只拥有很少的资源)，但是线程可以访问隶属进程的资源。
Ⅱ 调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
Ⅲ 系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
Ⅳ 通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

六、处理机调度

1. 调度的概念

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

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

2. 调度的三个层次

高级调度（作业调度）

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
中级调度（内存调度）

就是要决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）

低级调度（进程调度）

其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次

七、进程调度算法

1. 先到先服务 FCFS 非抢占式

First Come First Serve

先来先服务调度算法：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。

优点：公平、算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即， FCFS算法对长作业有利，对短作业不利

2. 短作业优先 SJF 非抢占式

Shortest Job First

短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

3. 最短剩余时间优先 SRTN 抢占式

shortest remaining time next

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。

当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

4. 高响应比优先 HRRN 非抢占式

Highest Response Ratio Next

高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。

响应比 = (等待时间+要求服务时间) / 要求服务时间

八、信号量机制 Semaphore

1. 概念

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

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

一对原语：

P操作 wait(Semaphore)：等待一个信号量：该操作会测试这个信号量的值，如果小于等于0，就阻塞。如果大于0，就占用一个资源，信号量 - 1。
V操作 signal(Semaphore)：挂出一个信号量：该操作将信号量的值加1，即使用完资源后归还资源。

int S = 1; // 初始化信号量，表示当前系统中可用打印机的数量

// 请求占用资源
void wait(int S){
    while(S<=0); //如果可用资源不够，则一直等待
    S = S - 1; //如果有可用资源，则占用一个资源
}

// 归还资源
void signal(ing S){
    S =S + 1 ; //使用完资源后，归还资源
}

2. 信号量实现进程互斥

首先我们需要了解一个概念：临界资源

多道程序系统中存在许多进程，它们共享各种资源，然而有很多资源一次只能供一个进程使用。一次仅允许一个进程使用的资源称为临界资源。

许多物理设备都属于临界资源，如输入机、打印机、磁带机等。

对临界资源进行访问的那段代码称为临界区。

信号量实现进程互斥的步骤：

分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
设置互斥信号量 mutex，初值为1 （即代表进入临界区的名额，可用资源数）
在进入区P(mutex)——申请资源
在退出区V(mutex)——释放资源

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

// 进程P1
P1(){
    ...
    P(mutex); //申请资源
    临界区代码...
    V(mutex); //用完后释放资源
}

// 进程P2
P2(){
    ...
    P(mutex); //申请资源
    临界区代码...
    V(mutex); //用完后释放资源
}

P、V操作必须成对出现。缺少 P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

3. 信号量实现进程同步（一前一后）

进程同步：要让各并发进程按要求有序地推进。

比如，P1、P2并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

P1(){
    代码1;
    代码2;
    代码3;
}

P2(){
    代码4;
    代码5;
    代码6;
}

若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。

这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

信号量实现进程同步的步骤：

分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量S,初始为0
在“优先级较高操作”之后执行V(S) 释放资源
在“优先级较低操作”之前执行P(S）申请资源

semaphore S = 0; //表示当前可用资源为0，需要等待P1释放资源

P1(){
    代码1;
    代码2;
    V(S); //代码2运行完后，释放资源
    代码3;
}

P2(){
    V(S); //代码4运行前先请求资源，保证代码4一定是在代码2之后执行
    代码4;
    代码5;
    代码6;
}

九、经典同步互斥问题

1. 生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，
生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。 (同步关系)
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。 (同步关系)
缓冲区是临界资源，各进程必须互斥地访问。（互斥关系）

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示生产者还能生产多少，即还能放入多少产品，该数量小于等于0，则生产者不能进行生产
semaphore full = 0; //同步信号量，表示消费者还能取出多少，即当前缓冲区已有产品的数量，该数量小于等于0，则消费者不能进行读取

producer(){
    while(1){
        p(empty); //申请一个生产者可用数量，若该信号量小于等于0，则阻塞，不进行生产
        p(mutex); //互斥使用缓冲区
        把产品放入缓冲区
        v(mutex); //释放缓冲区占用
        v(full); // 增加一个消费者可用数量
    }
}

consumer(){
    while(1){
        p(full); //申请一个消费者可用数量，若该信号量小于等于0，则阻塞，不进行消费
        p(mutex); //互斥使用缓冲区
        从缓冲区中取出一个产品
        v(mutex); //释放缓冲区占用
        v(empty); // 增加一个缓冲区/生产者可用数量
    }
}

2. 多生产者-多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。

只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。

仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果

互斥关系：对缓冲区（盘子）的访问要互斥地进行
同步关系（一前一后）：
- 父亲将苹果放入盘子后，女儿才能取苹果
- 母亲将橘子放入盘子后，儿子才能取橘子
- 只有盘子为空时，父亲或母亲才能放入水果

semaphore mutex = 1; //实现互斥访问盘子（缓冲区） 
semaphore apple = 0; //盘子中有几个苹果 
semaphore orange = 0; //盘子中有几个橘子 
semaphore plate = 1; //盘子中还可以放多少个水果

dad (){ 
    while(1){ 
        准备一个苹果; 
        P(plate); 
        P(mutex); 
        把苹果放入盘子; 
        V(mutex); 
        V(apple); 
    } 
}

mom (){ 
    while(1){ 
        准备一个橘子; 
        P(plate); 
        P(mutex); 
        把橘子放入盘子; 
        V(mutex); 
        V(orange); 
    }
}

daughter (){ 
    while(1){ 
        P(apple); 
        P(mutex); 
        从盘中取出苹果; 
        V(mutex); 
        V(plate); 
        吃掉苹果; 
    } 
}

son (){ 
    while(1){ 
        P(orange); 
        P(mutex); 
        从盘中取出橘子; 
        V(mutex); 
        V(plate); 
        吃掉橘子; 
    } 
}

3. 哲学家进餐问题

4. 读者-写者问题

十、管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

Java中类似于管程的机制 synchronized

十一、进程同步的方法

总结一下进程同步的方法：

临界区
信号量
管程

进程的同步离不开死锁问题，下面来详细解释一下死锁的相关概念

十二、死锁

1. 什么是死锁

死锁是指两个或两个以上的线程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

2. 死锁产生的必要条件

互斥
只有对必须互斥使用的资源的争抢才会导致死锁。
请求和保持
进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
不可抢占/不剥夺
进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
循环等待
存在一种进程资源的循环等待环路，该环路中的每个进程都在等待下一个进程所占有的资源。

3. 死锁的处理策略

死锁的产生必须满足四个必要条件，只要其中一个或者几个条件不满足，死锁就不会发生。

3.1 鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

3.2 死锁预防

破坏互斥条件

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

比如: SPOOLing 技术。操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件

破坏不可抢占条件

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。
这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

该策略的缺点：

实现起来比较复杂。
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
反复地申请和释放资源会增加系统开销，降低系统吞吐量。
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿

破坏请求和保持条件

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

该策略实现起来简单，但也有明显的缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件

可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点：

不方便增加新的设备，因为可能需要重新分配所有的编号；
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
必须按规定次序申请资源，用户编程麻烦。

3.3 死锁避免

安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能够完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

💭 举例如下：

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

银行家算法

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

💭 举例：

系统中有5个进程P0-P4，3种资源R0-R2，初始数量为（10，5，7），某一时刻的情况如下所示：

此时总共已分配 (7,2,5)，还剩余 (3,3,2)

3.4 死锁检测和解除

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

① 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
② 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

死锁检测

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

①用某种数据结构来保存资源的请求和分配信息；
②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

🚩 检测死锁的算法：
1）在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。
如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中， P1是满足这一条件的进程结点，于是将P1的所有边消去。
2）进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在上图中，P2就满足这样的条件。根据1）中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁解除

一旦检测出死锁的发生，就应该立即解除死锁。

并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有：

资源剥夺法

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

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

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

🎉 进程、线程、死锁

一、进程的概念、组成、特征

1. 概念

2. 进程的组成

① 进程控制块 PCB

② 程序段

③ 数据段

3. 进程的特征

二、进程的状态

1. 三态模型

2. 五态模型

三、进程控制（实现进程状态转换）

1. 概念

2. 如何实现进程控制

3. 进程控制相关的原语

① 进程的创建

② 进程的终止

③ 进程的阻塞和唤醒

④ 进程的切换

四、进程通信 IPC

1. 概念

2. 进程通信的方法

① 共享存储 (share memory)

② 管道 / 匿名管道 (Pipes)

③ 有名管道 / FIFO (Names Pipes)

④ 消息队列 (Message Queuing)

⑤ 信号量 semaphore

⑥ 信号 signal

⑦ 套接字(Sockets)

五、线程的概念和特征

1. 什么是线程

2. 为什么要引入线程

3. 线程的特征和优点

4. 进程和线程的区别

六、处理机调度

1. 调度的概念

2. 调度的三个层次

七、进程调度算法

1. 先到先服务 FCFS 非抢占式

2. 短作业优先 SJF 非抢占式

3. 最短剩余时间优先 SRTN 抢占式

4. 高响应比优先 HRRN 非抢占式

八、信号量机制 Semaphore

1. 概念

2. 信号量实现进程互斥

3. 信号量实现进程同步（一前一后）

九、经典同步互斥问题

1. 生产者-消费者问题

2. 多生产者-多消费者问题

3. 哲学家进餐问题

4. 读者-写者问题

十、管程

十一、进程同步的方法

十二、死锁

1. 什么是死锁

2. 死锁产生的必要条件

3. 死锁的处理策略

3.1 鸵鸟策略

3.2 死锁预防

破坏互斥条件

破坏不可抢占条件

破坏请求和保持条件

破坏循环等待条件

3.3 死锁避免

安全序列

银行家算法

3.4 死锁检测和解除

死锁检测

死锁解除