第三章同步、通信与死锁2.ppt

第五章 调度与死锁 3.5 死锁 在多道程序系统中,多个进程并发执行可改善系统资源利用率,提高系统的吞吐量,但也有可能发生一种危险---死锁。 一、死锁的概念 例1： 两个小孩在一起玩耍，一个在玩皮球，另一个玩自动步枪，如果这两个小孩都要对方手中的玩具，而又不肯先放掉自己拿着的玩具，这时就发生了僵持局面。 例2：系统有一台打印机和一台扫描仪，进程P1、P2并发执行，在执行过程中均需使用打印机和扫描仪。 1.死锁的定义 在一组进程中，每个进程都等待被该组进程中其他进程所占有的资源，从而无限期陷入僵持的局面，这种现象称为死锁。 3.产生死锁的必要条件 1971年Coffman总结了系统产生死锁的四个必要条件： 互斥条件：系统中存在临界资源，进程应互斥地使用这些资源。 占有和等待条件：进程在请求资源得不到满足而等待时，不释放已占有的资源。 不剥夺条件：进程已占有的资源只能由属主释放，不能强行剥夺。 循环等待条件：存在循环等待链，链中的每一个进程都在等待下一进程所持有的资源。 4.处理死锁的基本方法 （1）死锁防止（deadlock prevention） 通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。 较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。 （2）死锁避免 不事先采取限制措施去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。 只需事先施加较弱的限制条件，可获得较高的资源利用率和系统吞吐量，但在实现上有一定难度。在较完善的系统中常用此方法。 （3）检测死锁 事先并不采取任何限制，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源。 二、死锁防止 设法破坏产生死锁的四个必要条件之一。 条件1（互斥条件）是由设备的固有特性所决定的，不仅不能改变，还应加以保证。 破坏条件2（占有和等待条件） 采用资源的静态分配策略。 静态分配是指进程必须在执行前一次性地申请在所需的全部资源，若系统有足够资源则完全分配。若分配时只要有一种资源不能满足，则不分配任何资源，而让进程等待。 破坏条件3（不剥夺条件） 采用剥夺式调度方法。 占有资源的进程，再提出新资源请求时，若有则分配，否则剥夺此进程已占有的所有的资源，并让进城进入等待状态，资源充足后再唤醒它重新申请所需资源。 实现复杂、要付出很大的代价。 破坏条件4（循环等待条件） 资源按序分配：把系统中的所有资源编号，所有分配请求必须以序号上升的次序进行。 例如：系统中有下列设备：输入机（1），打印机（2），穿孔机（3），磁带机（4），磁盘（5）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。 三、死锁避免 各种死锁防止方法能够防止死锁发生，但由于所加限制条件太严格，会导致系统资源利用率和系统吞吐量的降低。 另一种解决死锁问题的方法称为避免死锁。 避免死锁基本思想：把系统状态分为安全状态和不安全状态，只要系统一直处于安全状态即可避免死锁的发生。 1.系统状态 （1）安全状态 如果系统能按某种进程顺序（如P1，P2，…,Pn）为每个进程分配其所需的资源，直至所有进程都能运行完成，此时称系统处于安全状态。进程序列P1,P2,…..,Pn称为安全序列。 （2）不安全状态 若不存在这样一个安全序列称系统处于不安全状态。 系统进入不安全状态后，就有可能进而进入死锁状态，反之，只要系统处于安全状态，便可避免进入死锁状态。 例：有三个进程p1,p2,p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。 T0时刻：p1,p2,p3分别获得5、2、2台，尚有3台空闲。系统状态见下图： T1时刻：P3请求1台磁带机，若系统分给它一台，分配后系统状态如下图。 死锁避免实质： 允许进程动态地申请资源，但系统在资源分配前先检查此次分配后系统的安全性，若分配后系统仍处于安全状态，则将资源分配给进程，否则不分配，令进程等待。 2.银行家算法 最有代表性的避免死锁算法，由Dijkstra提出。 银行家算法 银行家拥有有限周转资金 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款 银行家应谨慎的贷款，防止出现坏帐 用银行家算法避免死锁 操作系统（银行家） 操作系统管理的资源(周转资金) 进程（要求贷款的客户） (1)银行家算法中的数据结构 考虑一个系统有n个进程（P1,P2,..,Pn）和m类资源(r1,r2,…,rm) a.每类资源总数向量Resource Resource=(R1,R2,…,Rm) b.每类资源可用数向量Avilab