管程与死锁

管程

这部分仅是了解内容，当做拓展就好

为什么引入管程

在提出信号量后我们确实可以借用信号量+PV操作实现进程互斥关系但是我们发现这对编程人员极其不友好，编写程序困难，易出错。如下图：

我们知道这种P操作顺序错误会造成死锁，但是在编程中我们确实需要时刻注意P,V操作的顺序，这非常困难，所以能不能设计一个机制，让程序猿写程序时不需要关心复杂的PV操作，让写代码更轻松呢？可以，1973年，Brinch Hanson首次在程序设计语言（Pascal)中引入了"管程"的概念–一种高级同步机制，自此我们不需要在关心复杂P,V操作了，而是由编译器负责实现各进程的互斥进入管程操作。

管程的定义和基本特征

管程实际上就是一种特殊地软件模块，由这些部分组成：

1. 局部于管程的共享数据结构说明
2. 对该数据结构进行操作的一组过程(实际上就是函数)
3. 对局部于管程的共享数据设置初始值的语句
4. 管程有一个名字

管程的基本特征：

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

所以我们知道管程有自己的内部局部变量和函数以及一个管程名字，管程一次性只允许一个进程执行管程内函数并且管程内的数据只能被局部于管程的函数访问这样就实现了进程之间的互斥，即管程的函数封装了具体的操作，并且凭借每次只有一个进程能够调用管程函数来修改管程内的数据(实际就是信号量)。这样我们就不需要经常关注PV操作了。

如下是一个应用：

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

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48

//定义管程数据结构为ProducerConsumer
monitor ProducerConsumer
    //管程内数据实际上就是信号量
    //解决同步问题
    condition full,empty;
	int count=0;//缓冲区内产品数
	//第一个管程内部函数
	//把产品放入到缓冲区
	void insert(Item item){
        if(count==N)//缓冲区已满
            wait(full)//阻塞等待
        count++;//否则产品数加一
        insert_item(item);//缓冲区放进一个产品
        if(count==1)
            //此时缓冲区不空了唤醒wait(empty)
            signal(empty)
    }
	//第二个管程内函数
	//从缓冲区取产品
	Item remove(){
        //缓冲区是空的
        if(count==0)
            wait(empty)//阻塞等待
        count--;//否则产品数减一
        if(count==N-1)
            //此时缓冲区不满了唤醒wait(full)
            signal(full);
        return remove_item();//取出产品
    }
end monitor;//结束管程定义

//生产者进程
producer(){
    while(1){
        item=生产一个产品;
        //调用管程函数进行放入产品操作
        ProducerConsumer.insert(item);
    }
}

//消费者进程
consumer(){
    while(1){
        //调用管程函数进行取出产品操作
        ProducerConsumer.remove();
        //消费产品item
    }
}

我们发现管程只是保证每次都只有一个进程进行操作的互斥关系，具体的同步关系还是需要我们在管程内自己实现代码逻辑，并且这种封装管程内函数然后暴露给其他进程调用来操作内部数据的方式就是典型的“封装”思想。

引入管程的目的无非就是要更方便的实现进程互斥和同步。所以原理如下：

1. 需要在管程中定义共享数据(如生产者-消费者问题中的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的"入口"–其实就是一些封装函数(如生产者-消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的"入口"才能访问共享数据
4. 管程中有很多"入口"，但是每次只能开放一个"入口"，并且只能让一个进程或线程进入(如生产者-消费者问题中，各进程需要互斥的访问共享缓冲区，管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序猿不用关心，但是互斥关系还是需要程序猿自己实现)
5. 可在管程中设置条件变量(实际上就是信号量)+等待/唤醒操作以解决同步问题，可以让一个进程或者线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出"入口")，可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

程序猿可以用某种特殊的语法定义一个管程（比如：monitor ProducerConsumer…end monitor)之后其他程序猿就可以使用这个管程提供的特定"入口"很方便的使用实现进程同步/互斥了。

JAVA中类似于管程的机制

JAVA中，如果使用synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

如下：

1
2
3
4
5
6
7
8

static class monitor{
    private Item buffer[]=new Item[N];
    private int count=0;
    
    public synchronized void insert(Item item){
        ....
    }
}

如上每次都只允许一个线程进入insert函数，如果多个线程同时调用insert函数则后来者需要排队等待。

总结

死锁

什么是死锁

其实我们在前面已经不止一次提到“死锁”的概念了，例如刚刚讲到的哲学家问题中同时都先拿左筷子再拿右筷子就会导致死锁现象出现。这里每个人都占有一个资源同时又在等待另一个人手里的资源的情况就是“死锁”这里我们给出严格的定义：在并发环境下，各种进程因争夺资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是"死锁"。发生死锁后若无外力干涉，这些进程都将无法向前推进。

思考：死锁，饥饿，死循环有什么区别？

• 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
• 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：SPF算法中，若有源源不断的短进程到来，则长进程一直得不到处理机，从而发生长进程“饥饿”。
• 死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序猿故意设计的（比如while(1)）。

死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任意一个条件不成立，死锁就不会发生。

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

所以我们完全可以参照哲学家问题的死锁情况推出这四个条件，并且还可以知道发生死锁时一定是有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）。当然如果同类资源数大于1，则即使有循环等待，也未必发生死锁，但如果系统中每类资源都只有一个，那循环等待就是死锁的充要条件了。

什么时候发生死锁

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

总之对不可剥夺的资源的不合理分配就可能会导致死锁。

死锁的处理策略

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或多个
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
3. 死锁的检测和接触、允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后才去某种措施解除死锁。

前面的两种方法都是不允许死锁发生，最后一种是允许死锁发生。

总结

死锁的处理策略

那么接下来我们就逐一讲解一下死锁处理的三条策略。

预防死锁

破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

如果我们把只能互斥使用的资源改造为允许共享使用，那么系统就不会再进入死锁状态了，比如：SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备，比如用SPOOLing技术将打印机改造成共享设备。

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

破坏不剥夺条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

我们可以采用以下两种方案破坏不剥夺条件

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

这种策略的缺点是：

1. 实现起来复杂无论是方案1还是方案2
2. 释放已获得的资源可能会造成前一阶段的工作的失效，因此这种方法一般适用于易保存和恢复状态的资源，如cpu。（有PCB记录信息的好处）
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 如果采用方案1，意味着只要暂时得不到某个资源，之前获得的那些资源都要放弃，以后再重新申请，如果一直放生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

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

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

破坏循环等待条件

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

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

思考：什么原理破坏了循环等待条件？

一个进程只有已经占有小编号的资源时，才有资格申请更大编号的资源，按照此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就破坏了循环等待链也就不会再出现循环等待的现象了。

我们假设现在有10个资源，编号1~10。

该策略的缺点：

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

总结

避免死锁

避免死锁就是利用银行家算法避免系统处于不安全状态，那么首先我们先了解一下一个定义

安全序列，不安全序列，安全状态，不安全状态

我们以一个投资的例子来分析介绍，假设你是一位成功的银行家，手里拥有100亿资金，有三个企业借贷，分别是B,A,T三个公司：

1. B表示最多会借70亿
2. A表示最多会借40亿
3. T表示最多会借50亿

然而有个不成文规定，如果你借给企业的钱总数达不到企业提出的最大要求那么值钱借给企业的钱就都拿不回来了。刚开始B,A,T三个企业分别借了20,10,30亿，如下：

此时我们手里还剩下40亿，此时A又提出要借款20亿，那么我们能否借给A呢？

思考：如果借给A会有三家公司的钱都要不回来的风险吗？

我们思考，此时借给A20亿，如下:

那么此时我们手中还剩下20亿，此时如果按照T->B->A或者A->T->B的顺序追债是可以把之前借的钱都要回来的，所以此时没有三家公司的钱都要不回来的风险，所以此时是安全的，我们可以借给A20亿。

思考：能否举出一个三家公司的钱都要不回来的情况吗？

很简单，假设此时我们手上还有40亿，此时B也要借钱借30亿，那么此时如果我们借出去，如下图：

那么此时我们手中还剩下10亿，我们发现此时就不安全了，因为三家公司的钱我们都要不回来了。所以此时就是不安全的，我们不能再借给B30亿了。

根据上面的例子我们知道所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全的，当然安全序列可能有多个。

如果分配了资源之后，系统找不出任何一个安全序列，系统就进入了不安全状态，这也就意味着之后可能所有进程都无法顺利的执行下去了，当然如果有进程提前归还了一些资源（比如A先归还了10亿，那么手里有20亿按照T->B->A），那么系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入了不安全状态也未必就一定发生死锁，只是有死锁的风险，但是如果死锁了那么一定是在不安全状态下发生的。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也是“银行家算法”的核心思想。

银行家算法

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

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

思考：对于多种资源的情况，如何实现银行家算法？

我们思考在BAT借贷的例子中只有一种类型的资源–钱，但是在实际的计算机系统中会有多种多样的资源，应该怎么把算法拓展为多种资源的情况呢？这里我们可以把单维的数字拓展为多维的向量，比如：系统中有5个进程P0~P4，3中资源R0~R2，初始数量为(10,5,7)，则某一时刻的情况可用下表方式表示：

对于上面的例子我们分析一下能否安全。首先第一次分配后剩余的资源数如下表：

此时我们还剩下（3,3,2）的资源在手里，那么此时系统是否处于安全状态？

我们先检查（3,3,2）此时可以满足那些进程的需求，很明显现在满足P1,P3：

假设我们先把P1收回，此时应该是按照下面的公式更新已有资源

$$if(已有的资源>最多还会需求)\\ then\{ 已有资源=已有资源+已分配资源 \}$$

所以我们收回P1后，已有资源更新为(3,3,2)+(2,0,0)=(5,3,2),剩余的进程资源表变为

此时满足收回条件的有P3,P1，我们假设先收回P3，那么现有资源为(5,3,2)+(2,1,1)=(7,4,3)，表更新为

此时全部进程都满足收回条件了，那肯定是先收回那个都可以了，所以只要是P1->P3开头的序列就一定是安全序列，所以操作系统处于安全状态，当然也不是只有P1->P3开头的是安全序列，同理P3->P1同样是安全序列，总之只要找到一条安全序列就是安全状态所以此时不会发生死锁。

以此类推，共5次循环检查即可将5个进程都加入安全序列，最终得到一个安全序列。这种算法成为安全性算法，可以很方便的使用代码实现以上流程，每一轮都从编号较小的进程开始检查。这里主要是要牢记已有资源的更新公式！

思考:银行家算法的定义？

假设系统有n个进程，m中资源，每个进程在运行前先声明对各种资源的最大需求数，则可以用一个n*m的矩阵（可以用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max,Max[i,j]=K表示进程Pi最多需要K个资源Rj,同理，系统可以使用一个n*m的分配矩阵Allocation表示对所有进程的资源分配情况，Max-Allocation=Need矩阵，表示各进程最多还需要多少各类资源。另外还要用一个长度为m的一维数组Available表示当前系统还有多少可用资源。某进程Pi向系统申请资源，可用一个长度为m的一维数组Requesti表示本次申请的各种资源量。

可用银行家算法预判本次分配是否会导致系统进入不安全状态：

1. 如果

   $$Request_i[j]<=Need[i,j](0<=j<=m)$$

   便转向2，否则认为出错

2. 如果

   $$Request_i[j]<=Available[j](0<=j<=m)$$

   便转向3，否则表示尚无足够资源，Pi必须等待

3. 系统试探着把资源分配给Pi,并修改相应的数据（并非真的分配，修改数值只是为了做预判）：

   $$Available=Available-Request_i$$

   $$Allocation[i,j]=Allocation[i,j]+Request_i[j]$$

   $$Need[i,j]=Need[i,j]-Request_i[j]$$

4. 操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配，否则，恢复相应数据，让进程阻塞等待。

总结

死锁的检测和解除

死锁的检测和解除一大特点就是他允许死锁的发生然后检测到死锁后用一些方法解除死锁。所以首先我们需要能够检测出死锁。

死锁的检测

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

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

我们一般可以用资源分配图来保存资源的请求和分配信息，有以下两点两边的定义：

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不用阻塞的，可以顺利执行，如果这个进程执行结束了把资源归还给系统，就可能使某些正在等待资源的进程被激活，并顺利的执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程。

按照上面的过程叙述，我们知道对于资源分配图，每一个边对应一个圆的资源节点，如果最终能够消除所有边（优先消除绿边然后再消除蓝边），就称这个图是可完全简化的，此时一定没有发生死锁（相当于能找到一个安全序列）。如果最终不能消除所有变，那么此时就是发生了死锁，最终还连着的边的那些进程就是处于死锁状态的进程。

检测算法：

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

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁，注意并不是系统中的所有进程都是死锁状态，而是用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。解除死锁的方法有：

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

总结