【操作系统】进程同步、进程互斥、死锁

@[toc]

2.3.1 进程同步、进程互斥

什么是进程同步？

我们都知道在多线程里，进程具有异步性，每个线程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个线程能密切合作，以实现一个共同的任务。

例子，线程 1 是负责读入数据的，而线程 2 是负责处理数据的，这两个线程是相互合作、相互依赖的。线程 2 在没有收到线程 1 的唤醒通知时，就会一直阻塞等待，当线程 1 读完数据需要把数据传给线程 2 时，线程 1 会唤醒线程 2，并把数据交给线程 2 处理。

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

什么是进程互斥？

进程的并发和共享的支持。各个并发执行的进程不可避免地需要共享一些系统资源（比如内存、打印机等）

我们把一个时间段内只允许一个进程使用地资源称为临界资源。许多资源都属于临界资源。

对临界区地访问，必须互斥地进行，亦称间接制约关系，进程胡策指当一个进程访问某临界资源时，另一个想要访问该临界资源地进程必须等待，当前访问临界资源地进程访问结束，释放该资源之后，另一个进程才可以访临界资源。

对临界资源地互斥访问，可以在逻辑上分为几个部分：

do{
    entry section; // 进入区
    critical section; // 临界区
    exit section; // 退出区
    remainder section; // 剩余区
}

• 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源地标志（上锁），以组织其他进程同时进入临界区
• 临界区：访问临界资源地那部分代码
• 退出区：解锁
• 剩余区：进行其他处理

为了实现对临界资源地互斥访问，同时保证系统整体性能，需要遵循以下原则：

• 空闲让进：临界区空闲时，可以允许一个请求进入林既然去地进程立即进入临界区
• 忙则等待：当已有进程进入临界区时，其他试图进入临界区地进程必须等待；
• 有限等待：对请求访问地进程，应保证能在有限时间内进入临界区（保证不会饥饿）
• 让权等待：当进程不等进入临界区时，应立即释放处理机，防止进程忙等待（一直占用CPU）

2.3.2 进程互斥地软件实现方法

单标志法

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

单标志会先指定一个进程允许，此时只有当指定地那个进程运行完后才会让另外一个进程运行。

但是这样很容易带来一个问题，假设让A先执行，但CPU此时在执行B，但是B进不来临界区，A也没有进临界区，所以就违反了闲则让进原则。

双标志先检查法

算法思想：如果发现其他人不想进临界区地话那就我来进。

但是这样会存在一个问题：假如A先发现没有人想进入临界区，那么A进去了，但是突然时钟中断导致A还没有表达自己想进入临界区的标志，此时CPU执行B，B发现也没有人想进入临界区，所以B就进了，那么此时两个进程都进入了临界区，这样就会出现大问题。违反了忙则等待的原则。

双标志后检查法

算法思想：双标志先检查法是检查后上锁，但是这两个动作无法一气呵成，导致了两个进程同时进入临界区的问题，因此，双标志后检查法是先上锁，后检查

但是这样又有问题，比如A上了锁之后时钟中断到了B执行，B也上了锁，那么此时无论是A还是B都会发现有人上了锁，那么都不能进入临界区。违反了空闲让进和有限等待原则。

Peterson算法

算法思想：结合双标志法、单标志法的思想，如果双方都想进入临界区，那么就让进程尝试“谦让”

每个进程都会先表达自己的意愿，然后自己不进入临界区，而是先让别人进临界区，当对方想要进入临界区并且也谦让的话那我就进入临界区。这里很有意思，双方先客套一下，第二次客套就变成了真的。

这个算法解决了互斥问题并且遵守了空闲让进、忙则等待，有限等待原则。

2.3.3 进程互斥的硬件实现方法

中断屏蔽方法

利用“开/关中断”指令实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问位置都不允许被中断，也就不能发生进程切换，因为也不可能发生两个同时访问临界区的情况）

优点：虽然简单、高效。

缺点：不适用于多处理机，虽然实现了中断，一个CPU执行临界区代码，但是其他CPU仍然可以进入临界区。（我觉得开中断和关中断只能对一个CPU有效果，对其他CPU没影响，其他CPU也可以执行开/关中断指令）而且开/关中断只能在内核态下执行，所以只适用于内核级进程。

TestAndSet指令

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成，

bool TestAndSet(bool *lock)
{
    bool old;
    old = *lock;  //存放lock原来的值
    *lock = true; //无论之前是否已加锁，都给他锁上
    // 1.如果之前是false，现在变成true，表示上锁
    // 2.如果之前是true，设置称true，还是已上锁
    return old; //返回之前lock的值
}
//使用TSL指令实现互斥的算法逻辑
while (TestAndSet(&lock)); //只有当lock之前为false时才会退出循环并且上锁，实现了原子操作
临界区代码...;
lock = false;
剩余区代码...;

Swap指令

Swap指令是用硬件实现，执行的过程不允许被中断，只能一气呵成。

// 交换两个变量的值
void Swap(bool *a, bool *b)
{
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
//使用Swap指令实现互斥的算法逻辑
// lock表示当前临界区是否被加锁
bool old = true;
while (old == true)
    Swap(&old, &lock); //当lock解锁了之后才会退出while循环
临界区代码...;
lock = false; //解锁
剩余区代码...;

2.3.4 信号量机制

信号量

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

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量。比如：系统中只有一台打印机，那就可以设置一个处置为1的信号量。

信号量是操作系统提供的一种协调共享资源访问的方法。

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

• P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
• V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

P 操作是用在进入临界区之前，V 操作是用在离开临界区之后，这两个操作是必须成对出现的。

原语是一种特殊的程序段，由开/关中断指令实现，其执行只能一气呵成，

整型信号量

避免了并发、异步问题，单无法解决忙等问题

记录型信号量

当一个进程发现没有资源可用时，会主动的让出处理机，并进入阻塞队列。由一个进程用完资源后，会唤醒阻塞队列中等待的进程。

S.value的初值表示某种资源的数量

对信号量S的一次P操作意味着进程请求一个单位的该类资源，如果资源数小于0，表示没有资源可用，那么该进程就调用block原语进行自我阻塞，主动放弃处理机，并插入到等待队列中，该机制遵循了让权等待原则。

对信号量S的一次V操作一位着释放一个单位的资源，资源数就加1，如果加1后发现S.value<=0表明由进程在等待该类资源，那么调用wakeup原语，唤醒等待队列中的第一个进程。

2.3.5 用信号量实现进程互斥、同步、前驱关系

信号量实现进程互斥

信号量实现进程同步

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

比如必须先做好饭之后才能吃，又是事务必须有一定顺序，让异步并发的进程相互配合，有序推进。

先执行的操作执行完后执行V操作，让资源数从0到1，后执行的进程发现有资源后（P操作）才能继续执行。

类比：先把饭做好之后，才能吃上饭。如果饭没做好那就只能干等着。

信号量实现前驱关系

拓扑排序：一个有向图，每个点的前序必须遍历完后才能允许。

2.3.6 管程

为什么要引入管程

解决信号量机制编程麻烦、易出错的问题

看下图中的内容：假如执行了1、2、3会发生什么

1. 生成者进程先拿到了互斥信号量
2. 检查当前是不是空的，如果不是就等待
3. 消费者进程检查互斥信号量发现已经被占用，所以也要等待

这样就导致两个进程都在等待，发生了死锁。这里主要的问题是信号量实现的互斥，导致消费者无法取出数据而陷入了死锁。

这里怎么改为正确的呢？

我们可以先检查后上锁，我们把1和2掉下顺序，3和4掉下顺序。

这样生产者会先检查是否空了，消费者会检查是否满了，它俩总会有一个满足条件从而进入临界区。从而不会导致死锁。

管程的定义和基本特征

管程是一种特殊的软件模块，由这些部分组成：

• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部于管程的共享数据设置初始值的语句
• 管程的变量名

管程的基本特征：

1. 局部于管程中的数据只能被局部于管程的过程所访问
2. 一个进程只有通过调用管程内的过程才能进入管程访问数据
3. 每次仅允许一个进程在管程内执行某个内部过程（实现了互斥）

用管程解决生产者消费者问题

每次仅允许一个进程进入管程，生产者发现如果缓冲区已满的话就进入full的等待队列中，如果生产了第一个产品，可能会有消费者在等待产品，所以需要唤醒empty中等待的消费者进程。消费者发现缓冲区中没有产品的话就进入empty等待队列中，如果发现消费的是最后一个产品，那么可能由生产者线程因为没有空闲位置而阻塞在full队列中，需要唤醒它。

Java中类似于管程的机制

2.3.7 生产者-消费者问题

问题描述

生产者-消费者问题描述：

• 生产者在生成数据后，放在一个缓冲区中；
• 消费者从缓冲区取出数据处理；
• 任何时刻，只能有一个生产者或消费者可以访问缓冲区；（如果不互斥的话会出现冲突，两个写进程同时写同一片区域）

问题分析

PV操作题目分析步骤：

1. 关系分析，找出题目中描述的各个进程，分析他们之间的同步、互斥关系
2. 分析各进程的操作流程缺点P、V操作的大致顺序
3. 设置信号量，并根据题目条件确定信号量初值（互斥信号量一般初始值为1，同步信号量初始值为0）

我们对问题分析可以得出：

• 任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥；
• 缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步。

生产者：先生产一个产品，后检查是否有空闲的缓冲区，如果没有就等待。有的话就上锁后把产品放入缓冲区，生产完了解锁并将产品的数量加1，唤醒消费者进程。

消费者：先检查是否有满的缓冲区，如果没有就等待，有的话就上锁后取出产品，后解锁并将空的缓冲区数量减1，唤醒生产者进程。

能否改变相邻P、V操作的顺序？

如上图所示，假设当前缓冲区已满，empty=0，full = n

若此时生产者执行①，在执行②，那么就会先上锁后检查没有缓冲区，那么就会等待。由于生产者阻塞，因此切换回消费者仅，消费者进程执行③，由于互斥信号量已经被上锁，所以消费者也被阻塞。

这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况。陷入了死锁。

2.3.8 多生产者-多消费者问题

问题描述

问题分析

父亲：P检查盘子是不是空，不是的话就等待，是的话就进入临界区放入一个苹果，放完后退出临界区执行V操作，让苹果数加1，并唤醒儿子进程

母亲：P检查盘子是不是空，不是的话就等待，是的话就进入临界区放入一个橘子，放完后退出临界区执行V操作，让橘子数加1，并唤醒儿子进程

儿子：P检查是不是有苹果，没有就等待，有就去临界区拿走苹果，后退出临界区执行V操作，唤醒父亲和母亲进程

女儿：P检查是不是有橘子，没有就等待，有就去如临界区拿走苹果，后退出临界区执行V操作，唤醒父亲和目前进程

如何实现

问题1：可不可以不用互斥信号量

只有当缓冲区大小最多为1时才可能不用互斥量。在任何时刻，只会有一个进程不会被阻塞，并顺利的进入临界区

问题2：如果缓冲区容量大于1的时候能不能不用互斥信号量

不行，会导致资源覆盖重写

总结回顾

2.3.9 吸烟者问题

问题描述

问题分析

各种信息：

1. 生产者每次生产的不是一个物品，而是几个物品的组合
2. 生产者生产完后对应的消费者才能抽烟
3. 抽烟者抽完之后会提醒生产者继续生产
4. 生产者轮流为三个抽烟者生产
5. 只有一个桌子

解决方案：

1. 生产者每次生产的都是多个物品的组合
2. 同步关系，先V后P，初始值为0
3. 同步关系，先V后P，初始值也为0
4. 用一个while循环和一个变量i，每次操作i=(i+1)%3
5. 互斥关系，需要添加一个互斥信号量，初始值为1，由于这里只有一个缓冲区，每次只能由一个不会被阻塞，所以不需要添加信号量

2.3.10 读者写者问题

问题描述

读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。

读者-写者的问题描述：

• 「读-读」允许：同一时刻，允许多个读者同时读
• 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
• 「写-写」互斥：没有其他写者时，写者才能写

问题分析

先解决读写互斥和写写互斥问题，只需要加一个信号量，初始值为1，写的时候需要加锁防止被其他读或者写，读的时候也需要加锁。防止被其他进程写。

但是这样没办法实现多个进程同时读文件的情况。我们可以用一个count来记录正在读的进程个数，只有当第一个进程在读，那就上锁，当所有进程都读完了之后才解锁。这样就是实现了多个读进程同时进行。

但是这样写又存在一个问题，比如当前count = 0，一个读进程上锁之后时钟中断切换到另一个读进程，它发现此时count=0，但是锁已经被占用，所以就一直陷入了等待，导致无法实现多个读进程同时执行的情况。

这个问题的主要原因就是没有实现加锁和修改count的原子化操作，我们可以使用信号量机制给这一部分上锁，实现互斥访问。

这里还有一个潜在的问题：只要有读进程在读，写进程就一直阻塞，可能会“饿死”，因此，在这种算法中，读进程是优先的。

这就好比在生活中，一家银行优先处理VIP客户，这样普通用户可能就一直在等待。

那如何优化呢？

多有一个读进程在读文件的时候，其他读进程就可以直接去读，不受约束。我们希望接下来不让后来的读进程继续读下去的话可以在加一个互斥信号量，让读进程和写进程公平竞争，先来的先执行。

2.3.11 哲学家进餐问题

问题描述

1. 问题1：每个筷子是互斥关系，只能被一个人获得
2. 问题2：每个人需要拿到两只筷子才能吃饭

方案一

我们用信号量的方式，也就是 PV 操作来尝试解决它，代码如下：

不过，这种解法存在一个极端的问题：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了， 这样就没有人能够拿到他们右边的叉子，也就说每一位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了，很明显这发生了死锁的现象。

方案二

既然「方案一」会发生同时竞争左边叉子导致死锁的现象，那么我们就在拿叉子前，加个互斥信号量，让拿左右筷子实现原子操作，代码如下：

上面程序中的互斥信号量的作用就在于，只要有一个哲学家进入了「临界区」，也就是准备要拿叉子时，其他哲学家都不能动，只有这位哲学家用完叉子了，才能轮到下一个哲学家进餐。

方案二虽然能让哲学家们按顺序吃饭，但是每次进餐只能有一位哲学家，而桌面上是有 5 把叉子，按道理是能可以有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案。

方案三

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

方案四

那既然方案二使用互斥信号量，会导致只能允许一个哲学家就餐，那么我们就不用它。

另外，方案一的问题在于，会出现所有哲学家同时拿左边刀叉的可能性，那我们就避免哲学家可以同时拿左边的刀叉，采用分支结构，根据哲学家的编号的不同，而采取不同的动作。

即让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。

奇数的哲学家会先拿左边的，如果此时进程切换到了他的右边的哲学家，那右边的哲学家会先拿他右边的，加入此时又发生进程切换，奇数的哲学家也会拿到右边的筷子，他右边的哲学家就拿不到左边的筷子只能等待。

2.4.1 死锁的概念

什么是死锁

在多线程编程中，我们为了防止多线程竞争共享资源而导致数据错乱，都会在操作共享资源之前加上互斥锁，只有成功获得到锁的线程，才能操作共享资源，获取不到锁的线程就只能等待，直到锁被释放。

那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

举个例子：A和B都想要吃饭，A只有碗没有筷子，B有筷子却没有碗，两个人都希望对方的东西给我，都不肯让步，这样就导致了死锁。

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

死锁产生的条件

死锁只有同时满足以下四个条件才会发生：

• 互斥条件；
• 持有并等待条件；
• 不可剥夺条件；
• 环路等待条件；

互斥条件

互斥条件是指多个线程不能同时使用同一个资源。

比如下图，如果线程 A 已经持有的资源，不能再同时被线程 B 持有，如果线程 B 请求获取线程 A 已经占用的资源，那线程 B 只能等待，直到线程 A 释放了资源。

持有并等待条件

持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。

不可剥夺条件

不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。

环路等待条件

环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。

比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。

注意

发生死锁时一定有循环等待，但是发生循环等待时未必死锁。

如果同类资源大于1，则即使有循环等待，也未必发生死锁。如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

什么时候会发生死锁

1. 对资源的竞争，个进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争时不会引起死锁的。
2. 进程推进顺序非法，请求和释放资源的顺序不当，也同样导致死锁。例如，并发执行的进程P1，P2分别申请并占有了资源R1，R2，之后进程P1有紧接着申请资源R2，二进程P2又申请资源R1，两者会因为申请的资源被对方占有二阻塞，从而发生死锁。（环路等待条件）
3. 信号量的使用不当，也会造成死锁，如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看成时一种抽象的系统资源）

死锁的处理策略

1. 预防死锁：破坏死锁产生的四个必要条件中的一个或几个
2. 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
3. 死锁的检测和接触：允许死锁的发生，不过操作系统会扶着检查除死锁的发生，然后采取某种措施交界处死锁。

2.4.2 预防死锁

破坏互斥条件

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

我们可以把要访问互斥的资源的进程通过一个中介来管理，那么进程就可以继续下面代码的执行，而不用管这部分代码逻辑。

但这里有一个缺点：并不是所有的资源都可以改造程可共享使用的资源，并且为了系统安全，很多地方还要保留互斥性，所以很多时候都无法破坏互斥条件。

破坏不剥夺条件

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

该策略的缺点：

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

破坏保持和请求条件（持有并等待条件）

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

缺点：有些资源可能只需要用很短地时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用里很低，也有可能导致某些进程饥饿（想用的某个资源一直被分配给其他资源用了，总是凑不齐全部资源）。（占着茅坑不用）

破坏循环等待条件

顺序资源分配法，每个进程获取的资源都是按顺序排列的。

一个进程只有占有小编号的资源时，才由资格申请更大编号的资源。所以不可能出现一个拥有大编号的进程去申请小编好的资源。

线程 A 和 线程 B 获取资源的顺序要一样，当线程 A 是先尝试获取资源 A，然后尝试获取资源 B 的时候，线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和 线程 B 总是以相同的顺序申请自己想要的资源。

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

2.4.3 避免死锁（银行家算法）

什么是安全序列

通过银行家借款这个问题我们可以发现，如果执行某一个操作之后，可能会引发死锁，那么就是这个操作就是不安全的。那就可以阻止这个操作的执行。

安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要找出一个安全序列，系统就是安全状态。安全序列有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。着就意味着之后可能所有进程都无法顺利的执行下去，当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全序列，不过我们再分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就有可能发生死锁。

银行家算法

银行家算法：再资源分配之前预先预测这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。

我们可以用矩阵的形式来表示一些进程所需要的多个资源

如何判断当前是否处于安全状态？

尝试找出一个安全序列，一个一个判断，看满不满足某些进程的需求，已加入安全序列的就不再看了。这样一直执行下去，检查是否所有的进程都能进入安全序列中，

安全序列的例子

不安全序列的例子

算法流程

银行家算法步骤

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

安全性算法步骤

检查当前的剩余可用资源是否满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。

不断重复上述过程，看最终是否能让所有进程都加入安全序列中。

2.4.4 死锁的检测和解除

死锁的检测

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

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

数据结构资源分配图

死锁的检测方法

先找到能够满足所有需求的进程，把这个进程和与它相关联的边都去除。然后再继续往下找，一直找到不能找到为止。如果此时分配图中还有其他边，说明发生了死锁，否则表示没有发生死锁。

对于上图中，P1已经得到了所有需求，那就可以顺利的执行下去，等P1执行完后归还了所需的资源，P2就能够获得足够的资源而执行，这样就等到了一个安全序列。

对于下图中，就发生了死锁。由于R2资源不足，导致P1等待R2的资源，但P2拥有R2的资源不放，这样就发生了死锁。

检测死锁的算法

死锁的解除

1. 资源剥夺法：挂起某些死锁进程，并抢占他们的资源，将这些资源分配给其他的死锁进程，但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源，这种方式的优点时实现简单，但付出的代价可能会很大。因为有些进程可能已经运行了很长时间，一旦被终止可谓功亏一篑，从头再来。效率很低。
3. 进程回想法：让一个或多个进程回退到足以避免死锁的地步，这就要求系统要记录进程的历史信息，设置还原点。

死锁的解除无非就是谁放弃资源给别人。可以放弃一部分，也可以放弃全部。