大工13春《操作系统概论》辅导资料十三
大工13春《操作系统概论》辅导资料十三主 题：第七章死锁（第1—2节）
学习时间：2013年6月24日－6月30日
内 容：
第七章死锁
这周我们将学习第七章中的第1—2节，下面整理出的理念框架供同学们学习。
第一节 死锁问题的提出
一、死锁现象：
例1、话说狼GG和狼MM面对面走上一根独木桥。
狼GG说：呵呵，小MM，我已经占领了这座桥的一半，你不如退出去让我先过去吧。
狼MM说，哼哼，老兄，我也占了这座桥的一半，你咋不让给我？
狼GG和狼MM互不相让，都在等对方先让步。结果两个都过不了河。等着猎人来处理后事了。
例2、实验室来了一批新的科研资料，王老师想找个学生把这些资料扫描到电脑当中，然后把它们刻成一张光盘，以便于收藏。他先是给小张打电话，小张不在，同宿舍的同学答应转告。后来王老师又碰上小李，就吩咐他去做这件事。
小李来到设备科借扫描仪和光盘刻录机，扫描仪已被人借走，只好先借来刻录机。后来小张听同学转述了任务，他不知小李已在做此事，因此也去设备科借设备，恰好此时扫描仪已还，因此把它借走了。
再后来，小张一直在等着小李还刻录机，小李一直在等着小张还扫描仪，王老师布置的任务一直没有办法完成……
在以上的例子当中，都出现了事情无法进展下去的情形，这种情形称为“死锁”（deadlock）。
二、什么叫死锁
若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待其中另一个进程所占用的资源，这种等待永远不能结束，则说系统出现了“死锁”。或说这组进程处于“死锁”状态。
第二节死锁的必要条件
一、资源的概念
死锁现象既可以出现在现实生活当中，也可以出现在计算机科学的不同领域。例如，在操作系统当中，多个进程对各种I/O设备的争夺所引起的死锁；在一个数据库系统当中，多个进程对不同数据记录的互斥访问所引起的死锁等等。因此，为了对死锁问题进行更抽象、更具有普遍性地讨论，使之适用于各式各样不同的领域背景，我们把引发死锁的各种I/O设备、数据记录和共享文件等对象
统称为资源（resource）。
二、资源的分类
资源可以分为两大类：可抢占的（preemptable）和不可抢占的（nonpreemptable）。
可抢占的资源：当一个进程正在使用这种类型的资源时可以把它拿走而不会对该进程造成，任何不良的影响。例如：内存、CPU。
不可抢占的资源：当一个进程正在使用这种类型的资源时，如果强行把它拿走，将会导致该进程运行失败。例如：光盘刻录机。
死锁主要由不可抢占资源引起，对于可抢占资源而言，可以通过重新分配资源的方法来避免死锁。因此，这里只考察不可抢占资源。
进程在使用一个资源时，一般有三个步骤：申请资源、使用资源、释放资源。若申请不成功，则进程被阻塞。
死锁是指系统中多个进程无限期地等待永远不会发生的条件。
死锁是指系统中多个进程无限期地等待永远不会发生的条件。
三、死锁发生的原因
a)、对互斥资源的共享
b）、并发执行的顺序不当
永久性/可重用资源(reusable resource)：
每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如CPU、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。
有可能剥夺资源：由高优先进程剥夺低优先进程，或OS核心剥夺进程。
临时性/非可剥夺性资源(consumable resource)：可消耗，一般不限制数量。如硬件中断、信号、消息、缓冲区内的数据。
四、死锁发生的四个必要条件
只有4个条件都满足时，才会出现死锁。
互斥条件：任一时刻只允许一个进程使用资源
请求和保持：进程在请求其余资源时，不主动释放已经占用的资源
非剥夺：进程已经占用的资源，不会被强制剥夺环路等待（循环等待）：环路中的每一条边是进程在请求另一进程已经占有的资源。
解决死锁问题的几个策略：为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。
条件1(互斥条件)：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；允许多个进程同时使用一个资源。例如，采用假脱机打印方式，可以使多个进程同时生成输出数据，然后由一个后台打印进程来真正使用打印机。由于该打印进程不占用任何其他的资源，因此可以消除因争夺打印机资源而引发的死锁问题。但这种方法不具有普遍性。
条件2(请求和保持)：容易不定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。
条件3(非剥夺)：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。
条件4(循环等待)：实际上系统不采用部分分配，也就破坏了环路条件。
在应对死锁问题时，有四种策略可供选择：
“无为而治”：故意忽略这个问题，假装在系统中不会出现死锁现象。原因：进一步则代价高昂，退一步则影响不大。大多数操作系统均采用此种策略，如UNIX，Windows；
死锁的检测和解除：允许死锁发生，通过不断的检测及时发现，然后采取措施解除死锁；
动态避免：通过精心设计的资源分配方案来避免;
死锁预防：破坏死锁产生的四个必要条件之一。
处理死锁的基本方法：可归结为以下3种：
填空题
1、采用按序分配资源的策略可以预防死锁，这是利用了哪个条件不成立？（）。
A、互斥
B、循环等待
C、不可抢占
D、占有并等待
2、产生死锁的4个必要条件是：互斥、（）、循环等待和非抢占。
A、请求与阻塞 B、请求与保持 C、请求与释放 D、释放与阻塞
3、系统出现死锁的原因是（）。
A、计算机系统发生了重大故障
B、有多个封锁的进程同时存在
C、若干进程因竞争资源而无休止地等待着他方释放已占有的资源
D、资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数
4、系统死锁可利用（）来描述。
A、进程 B、程序 C、系统流程图 D、资源分配图
5、操作系统中，“死锁”的概念是指（）。
A、程序死循环
B、硬件发生故障
C、两个或多个并发进程各自占有某种资源而又都等待别的进程释放它们所占有的资源
D、系统停止运行
参考答案
1-5BBCDC
页:
[1]