导图社区 进程管理
- 106
- 0
- 0
- 举报
进程管理
本导图整理了进程管理的知识点，包括进程与线程、处理机调度、进程同步、死锁等板块，希望梳理的内容对你有所帮助！
编辑于2021-12-20 12:00:03- 进程管理
- 相似推荐
- 大纲
2.进程管理
进程与线程
进程
进程的概念
进程被引入的背景条件
在多道程序环境下，多个并发执行的程序会失去封闭性并且具有间断性以及不可再现的特征
进程被引入的原因（进程的功能作用）
使多道程序正确并发执行、实现操作系统的并发性和共享性
进程运行的必要条件
为了进程能独立的运行，必须为之配置进程控制块（PCB——数据结构）
PCB的作用
PCB是用来描述进程的基本情况和运行状态，进而便于系统利用它来控制和管理进程
进程实体的组成
由程序段、相关数据段和PCB三部分构成
创建进程和撤销进程的实质
所谓创建进程，实质上就是创建进程实体中的PCB，而撤销进程，实质上是撤销进程的PCB
进程的定义
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程的组成
进程控制块
进程创建时，操作系统在创建进程时会为它创建一个PCB，该PCB会常驻内存（任意时刻都可以存取），进程结束时PCB会被删除；进程运行中，系统通过PCB获取其状态信息，以便对其进行控制和管理；进程结束时，系统会收回其PCB，该进程随之消亡
PCB是进程存在的唯一标志
内容
进程描述信息
进程标识符：标志各个进程，每个进程都有一个唯一的标识号
用户标识符：进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息
进程当前状态：描述进程的状态信息，作为处理机分配调度的依据
进程优先级：描述进程抢占处理机的优先级，优先级越高的进程可优先获得处理机
资源分配清单
用于说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息
处理及相关信息
主要指处理机中各寄存器的值，当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时，能被断点继续执行
程序段
能被进程调度程序调度到CPU执行的程序代码段。注：程序可被多个进程共享，即多个进程可以运行同一个程序
数据段
可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果
进程的特征
动态性
本质特征，即进程存在生命周期
并发性
独立性
各各进程地址空间相互独立
异步性
各进程按各自独立的，不可预知的速度向前推进
结构性
引入进程后需要考虑
1.空间开销：为进程建立数据结构PCB 2.时间开销：维护数据结构，切换进程，保护现场 3.进程调度算法，预防死锁
进程的状态
运行态
就绪态
进程获得了除处理机外的一切资源，一旦得到了处理机便可以立即运行
阻塞态
进程正在等待某一事件而暂停运行，如等待某资源为可用或等待输入/输出完成
单、多阻塞队列
创建态
已构建进程标识符，创建管理进程所需表格（相关信息保存在主存进程表中，进程本身未进入主存）
结束态
表格和其他信息暂时保留
挂起态
Swapping对换技术：内存中没有就绪进程或内存空间紧张，进程程序和数据段换出到磁盘
进程挂起原因
进程全部阻塞，处理机空闲 内存空间紧张 操作系统的需要 终端用户或者父进程请求
特征
不能立即执行 挂起条件独立于阻塞条件 使之挂起的进程：自身、OS、父进程 只有实施挂起操作的进程能将它激活
进程的转换
进程控制
基本概念
进程控制就是实现进程状态的转换
进程控制用原语实现
原语用关/开中断来实现
原语是一种特殊的程序
原语的执行必须一气呵成，不可中断
主要功能：对系统中的所有进程进行管理
进程的创建
引起进程创建的事件
用户登录
作业调度
提供服务
如要打印时建立打印进程
应用请求
由应用程序建立多个进程
进程创建原语的过程
1.为进程分配一个唯一的进程标识号，并申请一个空白的PCB
2.为新进程的程序和数据以及用户栈分配必要的内存空间
3.初始化PCB
初始化标识信息、处理机状态信息、进程调度信息
4.建立链接，将新进程插入就绪/挂起队列，建立或扩充其他数据结构
进程的终止
引起终止的原因
正常结束：进程已顺利完成并准备退出运行，如exit,halt,logoff
异常结束：进程运行过程中发生了某种异常事件使得程序无法继续运行---进程本身的原因出现终止
越界错误，保护错，非法指令，特权指令错，运行、等待超时，算术运算错，被0除，I/O故障
外界干预：指进程因外界的请求而终止运行，如操作员或系统的干预、父进程请求和父进程终止---外界的原因引起进程终止
进程被终止的过程
1.根据标志符检索PCB，从中读出该进程的状态
2.若处于执行状态则立即终止进程，将处理机资源分配给其他进程
3.若该进程还有子孙进程，则应将其所有子孙进程终止
4.将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统
5.将该PCB从所在队列（链表）中删除
进程的阻塞和唤醒
阻塞
正在执行的进程由于需要等待某一事件的发生，这时会自动执行阻塞原语，使自己由运行态转变为阻塞态，进程阻塞是一种主动的行为，只有处于运行态的进程才可能转变为阻塞态
阻塞原语block()的执行
1.找到将要被阻塞进程的标识号对应的PCB
2.若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行
3.把该PCB插入相关事件的等待队列，将处理机资源调度给其他就绪进程
唤醒
当被阻塞进程所期待的事情发生后，如它所启动的I/O操作已完成或所期待的数据已到达。由有关进程（释放该I/O设备的进程，或提供数据的进程）调用唤醒原语，将等待该事件的进程唤醒
唤醒原语wakeup()的执行
1.在等待发生的事件的等待队列中找到相应进程的PCB
2.将其从等待队列中移出，并置其状态为就绪态
3.把该PCB插入就绪队列，等待调度程序调度
进程的挂起和激活
挂起suspend()
首先检查被挂起进程的状态，若处于就绪，则改为就绪/挂起，若处于阻塞，则改为阻塞挂起
激活active()
将进程从外存调入内存，检查现行状态 就绪/挂起改为就绪，阻塞/挂起改为阻塞
进程的切换
调度和切换的区别：调度是决定资源分配给那个进程，是决策行为；切换是指实际分配的行为，是执行行为。一般来说，现有进程的调度，然后才有进程的切换
进程的切换是指调度另一个就绪进程占用处理器执行
进程切换的过程
1.保存处理机上下文，包括程序计数器和其他寄存器
2.更新PCB信息
3.把进程的PCB移入相应的序列，如就绪、阻塞等队列
4.选择另一个进程执行，并更新其PCB
5.更新内存管理的数据结构
6.恢复被选择进程的上下文
UNIX进程控制
fork()创建一个新进程
pid = fork(),父进程和子进程均在下一条语句运行 fork（）返回值：父进程为所创建子进程的标识，子进程为0。fork()创建子进程后,执行返回父进程或调度切换，子进程是父进程的精准复制。父子进程运行无关，若要求顺序一定：进程通信
exec()使子进程拥有自己的可执行代码，即用一个新进程覆盖调用进程
进程块的组织方式
两种常见的索引方式
链接索引
将同一状态或者同一阻塞原因的PCB链接成一个队列，操作系统持有指向各个队列的指针
单一队列：所有PCB连接成一个队列
索引方式
将同一状态的进程组织在一个索引表里，索引表的表项指向其对应的PCB，如就绪索引表和阻塞索引表，操作系统持有指向各个索引表的指针
进程的通信
概念：进程通信是指进程之间的信息交换，PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式
高级通信方式
共享存储
定义：在通信进程之间存在一块可直接访问的共享空间，通过对这块共享空间进行写/读操作实现进程之间的信息交换；工具：对共享空间进行写/读操作时，需要使用同步互斥工具；背景：操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成
共享方式分类
低级方式的共享，是基于数据结构的共享
高级方式的共享，是基于存储区的共享
消息传递
定义：通过系统提供的发送消息和接收消息两个原语进行数据交换，数据交换的基本单位是格式化的消息(Message)；
通信方式分类
直接通信方式
发送进程和接受进程直接通过接受进程的消息缓冲队列发送和接收消息
间接通信方式
发送进程和接受进程通过某个中间实体发送和接收消息，这种中间实体一般称为信箱，这种通信方式又称信箱通信方式
管道通信
定义：所谓“管道”，是指用于连接一个读进程和写进程的一个共享文件，和管道连接的读/写进程通过字符流形式分别从管道的输入和输出端进行发送和接受数据
功能：管道机制必须提供三方面的协调能力：互斥、同步和确定对方的存在
特性：而且管道只能采用半双工通信，即某一时刻只能单向传输数据；而且写进程会先把缓冲区写满然后才让读进程读，当缓冲区还有数据时，写进程不会往缓冲区写数据（写满才读，不读光不写）；数据一旦被读进程读出后，就会从管道程序中被抛弃
线程
线程的基本概念
线程和进程的内涵：进程（资源所有权）是除CPU之外的系统资源的分配单元，线程（调度并分配）是处理机的分配单元
线程（轻量级进程）的定义：是进程中的一个实体，是被系统独立调度和分派的基本单位，线程只拥有很少的私立资源，可与同属于同一个进程的其他线程共享进程所拥有的全部资源
引入线程的目的：减少并发执行时的时空开销，因此提高了操作系统的并发性能和吞吐量
线程的组成：线程ID、程序计数器、寄存器集合和堆栈组成
线程（轻型实体）的属性
基本操作 派生Spawn:创建进程时会为其派生一个线程，线程可派生其他线程 阻塞Block、接触阻塞Unblock、结束Finish(释放其私有资源)
线程的实现方式
用户级线程（User-Level Thread，ULT）
应用程序从单线程开始，通过使用线程库设计成多线程程序，有关线程管理的所有工作都由应用程序完成 操作系统不知道线程存在，以进程为调度单位eg:Infomix
优点：切换开销小，调度灵活，线程库独立于内核 缺点：系统调用会引起线程及整个进程阻塞，削弱并发，且不能利用多处理技术
内核级线程（Kernel-Level Thread，KLT）
内核级线程才是处理机分配的单位，所有用户级线程的实现都需要与内核级线程连接
线程管理的所有工作都由内核完成，操作系统以线程为调度单位应用程序只有一个到内核级线程的编程接口，因此内核级线程的切换必须在核心态下完成
优点：可把同一进程的多个线程调度到多个处理器 一个线程阻塞（包括页面故障），可调度同一进程的其他线程，内核例程也可以是多线程的
用户级和内核级的组合实现方式
在同时支持用户级线程和内核级线程的系统中，可采用将 n 个用户级线程映射到 m 个内核级线程上（n>=m）
多线程模型
定义：实现用户级线程和内核级线程的连接方式
分类
多对一模型
多个用户级线程映射到一个内核级线程，线程管理在用户空间完成
优点：线程管理是在用户空间，不需要切换到核心态，因此效率比较高；缺点：当一个用户级进程被阻塞后，整个进程都会被阻塞，并发度不高，且多个线程无法在多核处理机上并行运行
一对一模型
一个用户级线程映射到一个内核级线程
优点：并发能力强，多线程可在多核处理机上运行；缺点：一个用户进程会占用多个内核级线程，线程切换工作由内核完成，需要切换到核心态，因此线程管理成本高
多对多模型
n个用户级线程映射到m个内核级线程（n>=m）,每个用户级线程对应m个内核级线程
优点：克服了多对一模型中并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程而开销太大的缺点
处理机调度
调度的概念
基本概念
处理机调度是按照一定的调度算法在就绪队列中选择一个进程并将处理机分配给它
目标：防止进程长期不能获得调度饥饿 尽量提高处理剂利用率，系统吞吐量 减少进程响应时间
原则：满足用户、系统需求
调度的层次
三级调度
作业调度（高级/长度 调度）
由于内存空间有限，用户无法将所有作业都调入内存，按一定原则从外存上处于后备状态的作业中挑选一个（或多个）作业调入内存，并且为它们建立进程、分配系统资源，排在就绪（就绪/挂起）队列上。作业调度就是内存与辅存之间的调度
内存调度（中级/中程调度）
将那些暂时不能运行的进程调至外存，这种状态称为挂起态；当它们已经具备运行条件且内存有空闲时，内存调度又会将其调入内存，修改其状态为就绪态并挂在就绪队列上等待
进程调度（低级调度）
决定就绪队列中的哪个进程获得处理器
三级调度的联系
作业调度从外存中选择一批作业进入内存，为它们分配内存、建立进程、分配资源，把它们挂在就绪队列上，进程调度从就绪队列中选出一个进程，把CPU分配给它让其运行。中级调度是为了提高内存的利用率，中级调度会把那些暂时不能运行的进程挂起到外存上，当内存有空间了，就通过中级调度将其掉入内存，将其唤醒；简言之，中级调度是给 作业调度和进程调度 打下手的
七状态模型
调度的时机、切换与过程
进程调度的时机
能进行调度与切换的情况
不能进行进程调度与切换的情况
调度的切换与过程
进程的调度、切换是有代价的，并不是调度的越频繁，并发度就越高
保存原来运行进程的数据和信息
恢复新进程的数据和信息
进程调度方式
定义：所谓进程调度方式，有优先权更高的进程进入就绪队列，此时应该如何分配处理机
两种调度方式
非剥夺调度方式（非抢占式方式）
执行进程只有在执行完毕，或因申请I/O阻塞自己，才中断释放处理机（主要批处理）
剥夺调度方式（抢占方式）
若有某个更为重要或紧迫的进程进入就绪队列，或时间片用完的情况下，中断当前进程执行，调度新的进程执行（会产生较多中断）
调度算法的评价指标（调度的基本准则）
CPU利用率
应尽可能使CPU保持“忙”状态
系统吞吐量
单位时间内CPU完成作业的数量
周转时间
周转时间
从作业到达（包含驻内存等待调用时间）到作业完成所经历的时间
平均周转时间
指多个作业周转时间的平均值
带权周转时间
指作业周转时间与作业实际运行时间的比值
平均带权周转时间
指多个作业带权周转时间的平均值
等待时间
指进程处于等处理机状态的时间之和
响应时间
指从用户提交请求到系统首次产生响应所用的时间
典型的调度算法
先来先服务（FCFS）调度算法
短作业优先（SJF）调度算法
抢占式和非抢占式
抢占式
820木有
非抢占式
总结
优先级调度算法
例子
补充
总结
优先级
静态优先级——问题：低优先级无穷阻塞 解决：进程优先级随时间或执行历史而变化（老化策略）
动态优先级——调整时机：时钟中断，进程切换，进程终止
高响应比优先（HRRN）调度算法
例子
总结
时间片轮转调度算法
例子
总结
多级反馈队列调度算法
例子
总结
实时调度算法
基于时间片的轮转调度
响应：秒级 分时系统，一般实时处理系统
基于优先级的非剥夺
响应：数百毫秒～数秒 多道批处理、不太严格的实时处理系统
基于优先级的剥夺点剥夺
响应：几毫秒～几十毫秒 一般实时系统
立即剥夺
响应：微秒～毫秒 苛刻的实时系统
最早截止时间优先调度EDF
根据任务的截止时间确定优先级
最低松弛度优先调度算法LLF
完成截止时间-剩余执行时间-当前时间
进程同步
实现进程同步的基本概念
背景条件：在多道程序中，不同进程并发执行并且存在着不同的相互制约关系
引入进程同步的原因：为了协调进程之间的相互制约关系
临界资源
定义：一次仅允许一个进程使用的资源称为临界资源，且必须互斥的对临界资源进行访问；在每个进程中，访问临界资源的那段代码称为临界区
互斥访问临界资源过程的四个部分
进入区
负责检查是否可以进入临界区，若能进入，则应设置正在访问临界区的标识，以阻止其他进程同时进入临界区
临界区
进程中访问临界资源的那段代码，又称临界段
退出区
将正在访问临界区的标识清除，与进入区的代码共同作用实现互斥
剩余区
代码中的其余部分
同步
亦称直接制约关系，是指多个进程之间需要相互协调而产生的制约关系，进程之间的直接制约关系源于它们之间的相互合作
互斥
亦称间接制约关系，当多个进程需要使用同一临界资源时，一个进程使用，其他进程必须等待正在使用临界资源的进程使用完后才能去争夺临界资源的访问权限
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区，其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证能在有限的时间内进入临界区
让权等待
当进程不能进入临界区时，应立即释放处理器，防止进程忙等待
实现临界区互斥的基本方法
软件实现方法
单标志法
双标志法先检查
双标志法后检查
Peterson's Algorithm
硬件实现方法
中断屏蔽方法
避免进程切换，实现互斥访问
缺点：系统无法响应外部请求 无法接受异常，处理故障 无法切换进程，性能下降 不支持多处理机，对用户程序来说很危险
While(1){ disable interrupt; critical section; enable interrupt; remainder; }
硬件指令方法
TestAndSet指令
Swap指令
信号量
概念
信号量机制可用来解决互斥和同步问题，它只能被两个标准的原语Wait(S)和Signal(S)访问，也可记为“P操作”和“V操作”
两种信号量
整型信号量
一个用来表示资源数目的整形量S
记录型信号量
除了需要一个用来表示资源数目的整型变量value外，还要增加了一个用于链接所有等待该资源的进程的进程链表L
利用记录型信号量实现同步
1.分析什么地方需要实现同步关系，即必须保证“一前一后”执行的两个操作
2.设置同步信号量S，初始为0
3.在“前操作”之后执行V(S)
4.在“后操作”之前执行P(S)
利用信号量实现进程互斥
1.分析并发过程的关键活动，划定临界区
2.设置互斥信号量mutex，初值为1
3.在临界区之前执行P(mutex)
4.在临界区之后执行V(mutex)
在每个需要访问临界区资源的进程中是成对出现的
利用记录型信号量实现前驱关系
每一对前驱关系都是一个进程同步问题，需要保证一前一后的操作
实现过程
1.要为每一个前驱关系各设置一个同步变量
2.在“前操作”之后对相应的同步变量执行V操作
3.在“后操作”之前对相应的同步变量执行P操作
管程
引入管程的原因（管程的作用）
每个需要访问临界资源的进程都必须自备同步的PV操作，同步操作数量多又分散，操作系统管理起来就比较麻烦且容易产生死锁，所以为了解决这些问题引入了管程
管程的定义
系统中各种共享资源可以用共享数据结构抽象的描述其资源特性，而对数据结构实施的一系列操作（对共享资源的申请、释放等操作）定义为一组过程，实现就成互斥就是通过这组过程；管程就是代表共享资源的数据结构和对该共享数据结构实施操作的一组过程两者组成的资源管理程序
管程的组成
1.管程的名称
2.局部于管程内部共享数据结构的说明
3.对该数据结构进行操作的一组过程（或函数）
4.对局部于管程内部的共享数据（共享资源的数目）设置初始值的语句
管程的基本特征
局部于管程的数据只能被局部于管程的进程访问
一个进程只有通过调用管程中的过程才能进入管程并访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
条件变量
定义
进程被阻塞的原因定义为条件变量，每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程
对条件变量只能进行的两种操作
wait
x.wait：当条件变量x对应的条件不满足时，进程会调用 x.wait 将自己插入 x 的等待队列，并释放管程，让其他进程使用管程
signal
x.signal：x 对应的条件满足了，则调用 x.signal，唤醒一个因 x 条件而阻塞的进程
拓展1：用管程解决生产者消费者问题
拓展2：Java 中类似于管程的机制
经典同步问题
看书，题目从上面出
生产者-消费者问题
读者-写者问题
哲学家进餐问题
5个哲学家围坐一张餐桌，5只餐叉间隔摆放 哲学家行为：思考（将餐叉放回原处），进餐（同时拿到两边的餐叉）
若右边的叉子占用，则放下左边的叉子，等一段时间再拿
优先取用编号较低的刀叉，先放下编号较高的餐叉
奇数号拿左，偶数号拿右
引入服务生
吸烟者问题
死锁
死锁的概念
死锁的定义
多个进程因为竞争资源或执行时推进的顺序不当，或相互通信出现永久阻塞现象
死锁、饥饿、死循环的区别
死锁：各进程都在等待对方手里的资源，导致各进程都阻塞
饥饿：由于长期得不到资源，进程无法向前推进
死循环：程序执行过程中一直跳不出某个循环语句的现象
死锁产生的必要条件
互斥条件
在一短时间内临界资源只能被一个进程使用
不剥夺条件
获得临界资源的进程只能由自己释放资源，不会被其他进程强行夺走
请求并保持条件
进程请求新的临界资源的同时会保持已拥有的临界资源不释放
循环等待条件
存在一种循环等待链，链中的有关的临界资源被一个进程获得同时又被另外一个进程所请求
发生死锁时一定有循环等待链，但有循环等待链不一定发生死锁
820中的循环等待（不是指循环等待链）发生即发生死锁，这四个构成充分必要条件
什么时候会产生死锁
系统资源的竞争
对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会产生死锁的
并发执行顺序不当
请求和释放资源的顺序不当
信号量使用不当
如生产者-消费者问题中，如果实现互斥的 P 操作在实现同步的 P 操作之前，就有可能导致死锁
死锁的处理策略
不允许死锁发生
静态限制：死锁预防
破坏死锁产生的四个必要条件
限制条件比较严格，实现起来相对而言比较简单，但往往导致系统的效率低，资源利用率低
动态调整：避免死锁
在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁，比如银行家算法
限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态
允许死锁发生
死锁的检测及解除
允许发生死锁，死锁发生后，系统通过检测及时地检测出死锁的发生，然后采取某种措施解除死锁
忽略死锁
鸵鸟策略
死锁的预防
破坏互斥条件
将临界资源改造为可共享使用的资源（如SPOOLing技术：共享打印机）
缺点：由资源的固有特性决定，大部分时间无法破坏互斥条件
破坏不剥夺条件
资源的状态可保存和恢复
方案一：当进程申请的临界资源得不到满足时，立即释放所拥有的所有资源；方案二：进程申请的资源被占用时，操作系统考虑剥夺的可能
缺点：实现复杂，剥夺资源可能导致进程失效，而且，反复的申请和释放导致系统开销大，周转时间长，系统吞吐量低，可能导致饥饿
破坏请求并保持条件
进程运行前一次性申请全部资源
缺点：资源利用率低，可能导致饥饿，且无法预知所需资源的全集
破坏循环等待条件
给资源按类型线性排队，必须按编号从小到大的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦，只能请求某类型之后的资源
死锁的避免
什么是安全状态和安全序列
安全状态：系统能按照一种资源分配顺序将资源动态地分配给每个进程，使每个进程最终都能顺利完成，就说此时系统处于安全状态
如有安全序列{p1,p2,…,pn}，对每个进程pi，它以后需要点资源量不超过当前剩余资源量与其他进程当前占有资源量之和，则称系统处于安全状态，否则称系统处于不安全状态
不安全状态和安全序列和死锁的关系
不安全状态和死锁的关系
找不到任何一个安全序列，则系统处于不安全状态 避免死锁的实质：避免系统进入不安全状态
不安全状态和安全序列的关系
如果系统处于不安全状态，则系统可能是发生了死锁；如果系统发生了死锁，则一定处于不安全状态
按非安全序列分配资源，也会变成不安全状态
银行家算法
思想：分配资源前进行比较权衡，看此次分配之后会不会使得系统进入不安全状态，若不会则可进行分配
银行家算法优缺点
死锁检测和解除
死锁的检测
为了能对系统是否已经发生了死锁进行检测，必须有两个条件：
1.用某种数据结构来保存资源的请求和分配信息
2.提供一种算法，利用上述信息来检测系统是否已经进入死锁状态
死锁检测的数据结构 -- 资源分配图
两种结点
进程结点：对应一个进程
资源结点：对应一类资源，一类资源可能有很多个
两种边
进程结点--->资源结点（请求边）：表示进程想要申请该类资源，有几条边就代表想申请几个该类资源
资源结点--->进程结点（分配边）：表示已经为进程分配了该类资源，有几条边就代表分配了几个该类资源
化简：找出全部请求都能满足的结点，消去请求边和分配边，使其成为孤立结点
检测时机
每个资源请求时都进行，但是系统开销大 定时检测 系统资源利用率下降时检测
死锁检测的算法 -- 死锁定理
算法思想：首先在资源分配图中找到一个既不阻塞也不孤立的进程（申请的资源数量小于等于系统空闲的没有被分配给其他进程的资源数量），消去该进程所有的请求边和分配边，重复上述过程，若最终能消去所有的边，则称该图是完全简化的，此时一定没有发生死锁，如果不可完全简化，那么依据死锁定理，此时系统发生了死锁
死锁定理：如果某时刻系统的资源分配图是不可完全简化，那么此时系统发生死锁
死锁解除
死锁进程：死锁检测算法化简完的资源分配图中还连着边的进程就是死锁进程
资源剥夺法
挂起某些死锁进程，并抢占它的资源，将资源分配给其他死锁进程
注意：应防止被挂起的死锁进程因长时间得不到资源而饥饿的情况
撤销进程法（终止进程法）
强制撤销部分甚至全部死锁进程，并剥夺它们的全部资源
优点：实现简单；缺点：付出的代价可能很大，因为可能进程已经运行很长时间接近结束，而因为某种原因在这一时刻发生了死锁而被迫撤销，功亏一篑，从头再来又会造成不必要的资源浪费——因此撤销时基于某种最小代价原则
进程回退法
让一个或多个进程回退到足以避免死锁的地步，这就要求系统要记录进程的历史信息、设置还原点