并发进程

顺序程序设计

顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。

顺序程序设计的特点：

• 程序执行的顺序性
• 程序环境的封闭性：运行程序独占全部资源，除初始状态外，其所处的环境由程序本身决定，只有程序本身的动作才能改变其环境
• 执行结果的确定性：程序执行过程中允许被中断，但这种中断对程序的最终结果无影响，也即程序的执行结果与它的执行速率无关
• 计算过程的可再现性：在同一个数据集合上重复执行一个程序会得到相同结果，因而错误也可以重现，便于分析

并发程序设计

程序并发机制

进程执行的并发性： 一组进程的执行在时间上是重叠的。（和并行区分开）

从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。

从微观上看，任一时刻仅有一个进程在处理器上运行。

并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。

并发进程的特性

并发进程之间的关系分为两类：无关的和交互的

无关的并发进程： 一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关，即一个并发，进程不会改变另一个并发进程的变量值。

交互的并发进程： 一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的执行结果。交互的并发进程之间具有制约关系，这种交互必须是有控制的,否则会出现不正确的结果。

对于一组交互的并发进程，若执行的相对速度无法相互控制，则各种与时间有关的错误就可能出现。与时间有关的错误有两种表现形式:
+ 结果不唯一
+ 永远等待

并发多道程序的优点：

• 对于单处理器系统，可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。
• 对于多处理器系统，可让各进程在不同处理器上物理地并行，加快计算速度。
• 简化程序设计任务。

并发程序设计的特征：

1. 并行性：进程的执行在时间上可以重叠，在单处理器系统中可以并发执行，在多处理器环境中可以并行执行
2. 共享性：并发进程通过引用共享变量交换信号，从而，程序运行的环境不再是封闭的
3. 制约性：进程并发执行或协同完成同一任务时，会产生相互制约关系，必须对它们并发执行的次序加以协调
4. 交互性：由于并发进程共享某些变量，所以，一个进程的执行可能影响其他进程的执行结果，程序运行结果可能不确定，计算过程具有不可再现性。因此，这种交互必须是有控制的，否则会出现不正确的结果

进程的交互

交互进程有两种关系：

• 竞争关系：系统中的多个进程之间彼此无关，相互并不知道其它进程的存在，相互之间并不交换信息。但是由于这些进程共用了一套计算机系统资源,因而必然产生竞争资源的问题，一个进程的执行可能影响到同其竞争资源的其它进程。操作系统必须协调好诸进程对资源的争用。一旦一个进程要使用已分配给另一个进程的资源，则该进程必须等待。资源竞争产生两个问题:
  • 一个是死锁(Deadlock)问题，就是一组进程如果都获得了部分资源，还想要得到其他进程所占用的资源，最终所有进程都将陷入死锁
  • 一个是饥饿(Starvation)问题，是指一个进程由于其它进程总是优先于它而被无限期拖延
  • 既要解决饥饿问题，又要解决死锁问题。解决饥饿问题的最简单策略是FCFS资源分配策略
  • 竞争关系的进程使用同一资源时，同一时刻最多只允许一个进程使用，其他进程必须等待，我们称这种现象为进程互斥。
• 协作关系：某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当协作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后才被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步
  • 进程间的协作可以是双方不知道对方名字的间接协作（如多个进程通过访问一个公共缓冲区进行松散式协作），也可以是双方知道对方名字的直接协作，进程间通过通信机制紧密协作。

临界区管理

互斥与临界区

并发进程中与共享变量有关的程序段叫“临界区”， 共享变量代表的资源叫“临界资源”。

与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。如果能保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误

临界区调度原则

• 一次至多一个进程能够进入临界区内执行
• 如果已有进程在临界区，其他试图进入的进程应等待
• 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

临界区调度原则可总结为：

互斥使用、有空让进，
忙则等待、有限等待，
择一而入、算法可行。

算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁。

软件管理临界区

软件方法是为在具有一个处理器或共享主存的多处理器上执行的并发进程实现的，这种方法假定对主存中同一个单元的同时访问必定由存储器进行仲裁，使其串行化。

临界区管理的尝试：（下面是一段伪代码，非C语言）

bool inside1=false;      /*P1不在其临界区内*/
bool inside2=false;      /*P2不在其临界区内*/
cobegin             /*cobegin和coend表示括号中的进程是一组并发进程*/
process P1() {                
    while(inside2);/*等待*/  
    inside1=true;                  
    /*临界区*/                      
    inside1=false;                 
}

process P2() {
    while(inside1);  /*等待*/
    inside2=true;
    /*临界区*/;
    inside2=false;
}
coend 

这种方法看似没有问题，实则是错误的，

如上图所示，由于P1执行的时候将inside1设为true存在一定的时间延迟（和上一个操作不是原子的），在这段延迟的时间内，P2发现inside1仍为false，于是也进入临界区执行。出现了两个进程同时进入临界区的情况。

此外还有可能P1在临界区内失败（异常），导致无法将inside1置为false，使得其他进程再也无法进入临界区。

除此之外还出现了许多尝试，但仍存在一些无法解决的问题。

后来出现了两个真正实现了临界区管理的软件方法：Dekker算法和Peterson算法。由于软件实现临界区管理也不是主流，这里不重点研究了。

Dekker算法的实现：（下面两段代码来自 https://blog.csdn.net/JustJavaC2016/article/details/78660768）

#include<stdio.h>  
#include<stdlib.h>  
#include<pthread.h>  
#define true 1  
#define false 0  
typedef int bool;  
bool flag[2];  
int turn;  
void visit(int num)  
{  
    sleep(1);  
    printf("P%d is visting\n",num);  
}  
void P0()  
{  
    while(true)  
    {  
        flag[0] = true;//P0想使用关键区。  
        while(flag[1])//检查P1是不是也想用？  
        {  
            if(turn == 1)//如果P1想用，则查看P1是否具有访问权限？  
            {  
                flag[0] = false;//如果有，则P0放弃。  
                while(turn == 1);//检查turn是否属于P1。  
                flag[0] = true;//P0想使用。  
            }  
        }  
        visit(0); //访问Critical Partition。  
        turn = 1; //访问完成，将权限给P1。  
        flag[0] = false;//P0结束使用。  
    }  
}  
void P1()  
{  
    while(true)  
    {  
        flag[1] = true; //P1想使用关键区。  
        while(flag[0]) //检查P0是不是也想用？  
        {  
            if(turn == 0) //如果P0想用，则查看P0是否具有访问权限？  
            {  
                flag[1] = false; //如果有，则P1放弃。  
                while(turn == 0); //检查turn是否属于P1。  
                flag[1] = true; // P1想使用。  
            }  

        }  
            visit(1); //访问Critical Partition。  
        turn = 0; //访问完成，将权限给P0。  
        flag[1] = false; //P1结束使用。  
    }  
}  

void main()  
{  
    pthread_t t1,t2;  
    flag[0] = flag[1] = false;  
    turn = 0;  
    int err;  
    err =  pthread_create(&t1,NULL,(void*)P0,NULL);  
    if(err != 0) exit(-1);  
    err = pthread_create(&t2,NULL,(void*)P1,NULL);  
    if(err != 0 ) exit(-1);  
    pthread_join(t1,NULL);  
    pthread_join(t2,NULL);  
    exit(0);  
}  

Peterson算法的实现：

#include<stdio.h>  
#include<stdlib.h>  
#include<pthread.h>  
#define true 1  
#define false 0  
typedef int bool;  
bool flag[2];  
int turn;  
void procedure0()  
{  
    while(true)  
    {  
        flag[0] = true;  
        turn = 1;  
        while(flag[1] && turn == 1)
        //退出while循环的条件就是，要么另一个线程  
        //不想要使用关键区，要么此线程拥有访问权限。  
        {  
                sleep(1);  
                printf("procedure0 is waiting!\n");  
        }  
        //critical section  
        flag[0] = false;  
    }  
}  
void procedure1()  
{  
    while(true)  
    {  
            flag[1] = true;  
            turn = 0;  
            while(flag[0] && turn == 0)  
            {  
                    sleep(1);  
                    printf("procedure1 is waiting!\n");  
            }  
            //critical section  
            flag[1] = false;  
    }  
}  
void main()  
{  
    pthread_t t1,t2;  
    flag[0] = flag[1] = false;  
    int err;  
    turn = 0;  
    err =  pthread_create(&t1,NULL,(void*)procedure0,NULL);  
    if(err != 0) exit(-1);  
    err = pthread_create(&t2,NULL,(void*)procedure1,NULL);  
    if(err != 0 ) exit(-1);  
    pthread_join(t1,NULL);  
    pthread_join(t2,NULL);  
    exit(0);  
}  

硬件管理临界区

使用软件方法实现进程互斥使用临界资源是很困难的，他们通常能实现两个进程之间的互斥，很难控制多个进程的互斥。

关中断

关中断是实现互斥的最简单方法之一。

进程在测试标志之前，首先关中断，直到测试完并设置标志之后才开中断。进程在临界区执行期间，计算机系统不响应中断。因此不会转向调度，也就不会引起进程或线程切换，正在执行标志测试和设置的进程或线程不会被打断，从而保证了互斥。

关中断方法的缺点:
+ 关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力
+ 关中断方法也不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同临界区代码

测试并设置指令

其实就是TestAndSet，Java CAS的原理，操作系统层面提供的原子操作指令。

因为该指令是原子的，就可以使用该指令管理一个互斥量，从而实现临界区管理。

TS指令实现临界区管理的算法如下：（自旋锁）

bool s=true;
cobegin
process Pi()  { //i=1,2,...,n
    while(!TS(s));        /*上锁*/
    /*临界区*/;
    s=true;               /*开锁*/
}
coend

对换指令

对换指令（swap）交换两个字的内容，在Intel 80x86中，对换指令称为XCHG指令

swap指令也可以看作是同时设置两个值的原子指令实现，所以也可以用于临界区管理，思想类似。

软件方法和硬件方法都存在忙等问题（当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环测试一个变量直到某个值出现为止），浪费了处理器的时间，不会成为一种通用的方法。

信号量与PV操作

信号量机制

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

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

一对原语：wait(S)原语和signal(S)原语，常简称为P、V操作。

wait(S)相当于占用一个S资源，signal(S)相当于释放一个S资源。

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。下面是P、V原语的实现思想：

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

void wait(int S){
    while(S<=0);    //如果资源数不够，就一直循环等待
    S = S-1;        //如果资源数够，则占用一个资源
}

void signal(int S){
    S = S+1;
}

进程Pn：

wait(S);
//使用打印机资源...
signal(S);

记录型信号量

（思维导图中的二值信号量和一般信号量都是属于这里的记录型信号量）

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

/*记录型信号量的定义*/
typedef struct {
    int value;//剩余资源数
    struct process *L;//等待队列
} semaphore;

void wait(semaphore S){
    S.value--;
    if(S.value<0){
        //如果剩余资源数不够
        //使用block原语使进程从运行态进入阻塞
        //并把进程挂到信号量S的等待队列(即阻塞队列)中
        block(S.L);
    }
}

void signal(semaphore S){
    S.value++;
    if(S.value<=0){
        //释放资源后，若还有别的进程在等待这种资源
        //则使用wakeup原语唤醒等待队列中的个进程
        //该进程从阻塞态变为就绪态
        wakeup(S.L);
    }
}

这里信号量的语义就是资源的个数，并且实现了让权等待，不会形成忙等。

信号量机制实现进程互斥

我们可以把临界区看作一种特殊的资源，为临界区抽象出一个互斥信号量mutex，它是二值的，初值为1，代表同一个时间只能有一个进程进入临界区。

• 在进入临界区之前执行P(mutex)
• 在退出临界区之后执行V(mutex)

信号量机制实现进程同步

进程同步问题要求多个进程按一定次序先后执行一段代码。这个前驱关系可能是较复杂的，如下图所示，可以为每一对前驱关系各设置一个同步信号量，初值为0，要执行某操作前需要对前驱操作对应的信号量进行P操作，当完成了前驱操作时对对应的信号量执行V操作。

semaphore a = 0,b = 0,c = 0,d = 0,e = 0,f = 0,g = 0;

P1(){
    ...
    S1;
    V(a);
    V(b);
    ...
}

P2(){
    ...
    P(a);
    S2;
    V(c);
    V(d);
    ...
}

P3(){
    ...
    P(b);
    S3;
    V(g);
    ...
}

P4(){
    ...
    P(c);
    S4;
    V(e);
    ...
}

P5(){
    ...
    P(d);
    S5;
    V(f);
    ...
}

P6(){
    ...
    P(e);
    P(f);
    P(g);
    S6;
    ...
}

管程

管程和条件变量

为什么要引入管程

信号量机制存在的问题：编写程序困难、易出错。

管程：
+ 把分散在各进程中的临界区集中起来进行管理
+ 防止进程有意或无意的违法同步操作
+ 便于用高级语言来书写程序，也便于程序正确性验证

管程的定义

管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块。

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

管程的属性:

• 共享性
• 安全性
• 互斥性

管程的结构

管程是一种特殊的软件模块，有这些部分组成:
1. 局部于管程的共享数据结构说明
2. 对该数据结构进行操作的一组过程
3. 对局部于管程的共享数据设置初始值的语句
4. 管程有一个名字

例如：(使用类C语言语法模拟管程结构)

type ProducerConsumer = monitor{
    condition full, empty;//条件变量用来实现同步排队
    int count=0;//缓冲区中的产品数
    void insert(Item item){//把产品item放入缓冲区
        if (count ==N)
            wait(full);
        count++;
        insert_item(item);
        if (count = 1)
            signal(empty);
    }
    Item remove(){//从缓冲区中取出一个产品
        if (count ==0)
            wait(empty);
        count--;
        if(count==N-1)
            signal(full);
        return remove_item()
    }
}

//生产者进程
producer(){
    while(1){
        item = 生产一个产品;
        ProducerConsumer.insert(item);
    }
}

//消费者进程
producer(){
    while(1){
        item = ProducerConsumer.remove(item);
        消费产品item   
    }
}

管程的条件变量

条件变量是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它。

• wait()：挂起调用进程并释放管程，直到另一个进程在该条件变量上执行signal()。
• signal( )：如果存在其他进程由于对条件变量执行wait()而被挂起，便释放之；如果没有进程在等待，那么，信号不被保存。

死锁

死锁的产生

操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。

死锁产生的例子：

设系统有打印机、读卡机各一台，被进程Ｐ和Ｑ共享。两个进程并发执行，按下列次序请求和释放资源：

进程Ｐ|进程Ｑ
:-:|:-:
请求读卡机|请求打印机
请求打印机|请求读卡机
释放读卡机|释放读卡机
释放打印机|释放打印机
 
在PV操作中对应

在第一步中，双方都拿到了请求的资源，但是第二步中请求的资源都被对方所持有，于是都在等待对方释放资源，从而陷入死锁。

若系统中有m个资源被n个进程共享，每个进程都要求Ｋ个资源，而m < n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。

在著名的哲学家就餐问题中，若五个哲学家同时拿起右手边的餐具，此时左手边的的餐具就被另外一个哲学家占用，所有哲学家都陷入了无止境的等待资源释放状态，即死锁。

死锁产生的必要条件

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

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

归根结底，循环等待条件是前三种条件导致的结果。

解决方法

死锁防止

死锁防止就是要破坏死锁产生的必要条件。

破坏互斥条件： 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如: 操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。例如使用SPOOLing技术将打印机改造为共享设备。

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

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

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

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

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

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

死锁避免

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

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

死锁避免就是避免系统进入不安全状态。

银行家算法的数据结构：

一个系统有n个进程和m种不同类型的资源,定义包含以下向量和矩阵的数据结构：
+ 系统每类资源总数：该m个元素的向量为系统中每类资源数量Resource=(R1,R2,…,Rm)
+ 每类资源未分配数量：该m个元素的向量为系统中每类资源尚可供分配数量Avilable=(V1,V2,…,Vm)
+ 最大需求矩阵：每个进程对每类资源的最大需求量，Claim[I,j]表示进程Pi需Rj类资源最大数
+ 分配矩阵：表示进程当前已分得的资源数，Allocation[i,j]表示进程Pi已分到Rj类资源个数
+ 尚需矩阵：表示进程当前尚需资源数，Need[i,j]表示进程Pi尚需Rj类资源个数

银行家算法中下列关系式确保成立：
+ Ri=Vi+∑Allocation[k,i]（对i=1,..,m,k=1,..,n）：表示所有资源要么已被分配、要么尚可分配
+ Claim[k,i]≤Rj（对i=1,..,m,k=1,..,n）：表示进程申请资源数不能超过系统拥有的资源总数
+ Allocation[k,i] ≤ Claim[k,i]（对i=1,..,m,k=1,..,n）：表示进程申请任何类资源数不能超过声明的最大资源需求数

系统中若要启动一个新进程工作,其对资源Ri的需求仅当满足下列不等式：

Ri ≥ C[(n+1),i]+ ∑C[k,i] 对i=1,..,m,k=1,..,n;

即应满足当前系统中所有进程对资源Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数。

系统安全性定义：在时刻T0系统是安全的,仅当存在一个进程序列P1,..,Pn,对进程Pk满足公式：

Need[k,i] ≤Available [i]+ ∑Allocation[j,i] 对于k=1,…,n;i=1,…,m;

即对任何一个进程都能满足其所需要的资源。

银行家算法的基本思想：

• 系统中的所有进程进入进程集合,
• 在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。
• 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。
• 把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。
• 最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。

死锁的检测和解除

该部分参考自：死锁的检测和解除

解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发性了死锁，再采取措施解除它。

进程-资源分配图：

如图所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。

1. 如果进程-资源分配图中无环路，则此时系统没有发生死锁。
2. 如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。
3. 如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。可以使用将资源分配图简化的方法来检测系统是否处于死锁状态：

在资源分配图中，找出既不阻塞又不是孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如上图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之称为孤立的结点。在上图中，P1 是满足这一条件的进程结点，于是将P1的所有边消去。

进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在上图中，P2 就满足这样的条件。根据上面的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。

一旦检测出死锁，就应立即釆取相应的措施。死锁解除算法有：

1. 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
2. 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3. 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。