OS2013_UNIT5 死锁.ppt

Unit 5 死　锁 内容 　　 ●什么是死锁 　　●产生死锁的条件 　　●死锁的应对　 　　 §1 什么是死锁 ◆产生死锁的原因 ◆ 死锁定义 　　　造成这种死锁的根本原因是什么？ 　　　　　　　　 　　　　　　　　竞争资源！ 　　　 　　　在计算机系统中同样会发生类似交通死锁的线程死锁现象。 　　　例如，设有两个线程A和B，它们都要使用资源R1和R2来完成各自的任务，且用以下方式使用这两个资源： 　　　　　　　线程A　　　　　 线程B 　　　　　　　．．．　　　　　 ．．． 　point1: 　 申请 R1 　　申请 R2 　　　　　　　．．． 　　 ．．． 　point2: 　 申请 R2 　　申请 R1 　　　　　　　．．． 　　 ．．． 　　　　　　　释放 R1 　 　 释放 R2 　　　　　　　．．． 　　 ．．． 　　　　　　　释放 R2 　　　释放 R1 　　　　　　　．．． 　　 ．．． 　　　如果一个线程在另一个线程到达执行点point1之前率先到达执行点point2，那么它就能获得它所需要的第二个资源，从而可继续运行下去。但是，由于各线程都是异步前进的，如果没有一个线程先于另一个线程到达point1之前到达point2，即它们都处于point1和point2之间，此时任一线程到达point2都将相继被阻塞，它们都在等待获取对方已经占用了又无法释放的资源，于是线程A和B陷入了死锁。 　　　再考虑下面的线程通信例子，每个线程都试图接收另一个线程发来的消息，然后再给对方发送一则消息： 　　　　线程A 　　　 线程B 　　　　．．． 　　　 ．．． 　　　　receive (B , mes); receive (A , mes); 　　　　．．． 　　 ．．． 　　　　send (B , mes); 　　 send (A , mes); 　　　　．．． 　　 ．．． 　　　这种设计错误导致任一线程执行receive操作时将被阻塞而无法去执行send操作，从而发生死锁。 　死锁（deadlock）定义： 　　　如果有一组线程，每个线程都在等待一个事件的发生，而这个事件只能由该组线程里面的另一个线程发出，则称这组线程发生了死锁。 　（这里的事件通常是指释放资源） 　　　在死锁状态下，没有线程可以执行或被唤醒，即该组线程陷入了相互永久阻塞的困局，其中的每个线程都必须在另一个线程向前推进之后才能继续推进，但每个线程又都无法推进，导致了系统的局部瘫痪，进而可能导致整个系统的瘫痪。 §2 产生死锁的条件 ◆必要条件 ◆充分必要条件 2.1 产生死锁的必要条件 　■条件1：资源互斥。即一组进程使用了必须互斥的临界资源。如果大家使用的是非临界资源，就不会发生相互等待现象，也就不会发生死锁。 　■条件2：请求和保持。即进程在请求使用新的资源的同时，保持对已获取资源的占有并不释放。 　■条件3：不可剥夺。即一进程所占有的资源是不可剥夺资源。如果占有的是可剥夺资源则不会发生死锁，例如，不会因为对CPU的争夺而产生死锁。 　■条件4：循环等待。即存在一个闭合的进程－资源环路，其中的每个进程已占有着某个（些）资源，同时又在等待获取被环路中另一个进程占有的资源。 2.2 充分必要条件 　　　假定在某个时刻一组线程使用一组资源的状态为S（S也称资源分配状态），一个RAG (Resources Allocation Graph)是该S所对应的有向图，如果： 　　　(1)该RAG中未出现任何环路，则S为非死锁状态，也称安全状态。 　　　(2)该RAG中出现了环路，但环路中的各资源不全为单单位资源，则S不一定是死锁状态。换言之，由若干不全为单单位资源构成的环路是S为死锁状态的必要条件但非充分条件。 　　　(3)该RAG中出现了环路，且环路中的各资源均为单单位资源，则S为死锁状态。换言之，由若干单单位资源构成的环路是S为死锁状态的充要条件。 图5-2 死锁定理(1) 　　　　　　　　　图5-3 死锁定理(2) 　死锁定理： 　　　在某个时刻的进程资源状态S为死锁状态的充分必要条件是当且仅当S的资源分配图（RAG）是不可完全化简的。 §3 死锁的应对 ◆忽略死锁策略 ◆检测并解除策略 ◆避免死锁策略 ◆预防死锁策略 ◆综合治理 　　　死锁