大工20春《操作系统概论》辅导资料九
《操作系统概论》辅导资料九主 题：第3章处理器调度与死锁（第3—5节）学习时间：2020年5月25日--5月31日“不忘初心、牢记使命”主题理论学习：
“我们既要绿水青山，也要金山银山。宁要绿水青山，不要金山银山，而且绿水青山就是金山银山。”要按照绿色发展理念，树立大局观、长远观、整体观，坚持保护优先，坚持节约资源和保护环境的基本国策，把生态文明建设融入经济建设、政治建设、文化建设、社会建设各方面和全过程，建设美丽中国，努力开创社会主义生态文明新时代。
摘选自《习近平总书记系列重要讲话读本》内 容：
第3章处理器调度与死锁
这周我们将学习课件第3章中的第3—5节，下面整理出的理念框架供同学们学习。
本篇的基本要求：
1．掌握死锁的定义
2. 掌握死锁的四个必要条件
3．了解预防死锁的基本方法
重点掌握内容：
1. 死锁的概念，死锁的必要条件，预防死锁3.3 实时调度与进程切换
一、实现实时调度的基本条件
1. 提供必要的信息
2. 系统处理能力强
3. 采用抢占式调度机制
4. 具有快速切换机制二、实时调度算法的分类
根据实时任务性质：
硬实时调度算法
软实时调度算法
根据调度方式：
抢占式实时调度算法
不可抢占式实时调度算法
根据调度的时间：
静态调度算法
动态调度算法三、进程切换
进程调度和切换程序是操作系统内核程序。获得内核服务的唯一方法是通过中断或异常。处理机在执行每一条指令时，系统都会检查是否有中断或异常发生；如果没有中断和异常，处理机继续执行原来的流程；如果有中断或异常发生，系统将暂停正在执行的进程，将处理机的状态由用户态切换到核心态，执行操作系统内核程序。这个过程称为处理机模式切换。进行处理机模式切换后，被中断进程仍处于自己的执行环境中，内核在被中断进程的环境中进行处理。
进程切换与处理机模式切换区别：
处理机模式切换，只是处理机通过中断或异常由用户态转换成了核心态（或进行相反的转换），并没有进行进程切换，被中断进程仍然处于自己的执行环境中，处理机逻辑上还在被中断进程中运行，进程空间等环境信息并没有改变，中断或异常处理结束后，操作系统只需要恢复进程进入内核时保存的处理机现场，不需要恢复进程空间等环境信息。
进程切换指处理机从执行一个进程转到执行另一个进程，进程切换过程中，由于当前运行的进程改变了，因而当前进程空间等环境信息也需要改变。3.4 死锁的必要条件
一、死锁现象：
例1、话说狼GG和狼MM面对面走上一根独木桥。
狼GG说：呵呵，小MM，我已经占领了这座桥的一半，你不如退出去让我先过去吧。
狼MM说，哼哼，老兄，我也占了这座桥的一半，你咋不让给我？
狼GG和狼MM互不相让，都在等对方先让步。结果两个都过不了河。等着猎人来处理后事了。例2、实验室来了一批新的科研资料，王老师想找个学生把这些资料扫描到电脑当中，然后把它们刻成一张光盘，以便于收藏。他先是给小张打电话，小张不在，同宿舍的同学答应转告。后来王老师又碰上小李，就吩咐他去做这件事。
小李来到设备科借扫描仪和光盘刻录机，扫描仪已被人借走，只好先借来刻录机。后来小张听同学转述了任务，他不知小李已在做此事，因此也去设备科借设备，恰好此时扫描仪已还，因此把它借走了。
再后来，小张一直在等着小李还刻录机，小李一直在等着小张还扫描仪，王老师布置的任务一直没有办法完成……
在以上的例子当中，都出现了事情无法进展下去的情形，这种情形称为“死锁”（deadlock）。
二、什么叫死锁
若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待其中另一个进程所占用的资源，这种等待永远不能结束，则说系统出现了“死锁”。或说这组进程处于“死锁”状态。
三、资源的概念
死锁现象既可以出现在现实生活当中，也可以出现在计算机科学的不同领域。例如，在操作系统当中，多个进程对各种I/O设备的争夺所引起的死锁；在一个数据库系统当中，多个进程对不同数据记录的互斥访问所引起的死锁等等。因此，为了对死锁问题进行更抽象、更具有普遍性地讨论，使之适用于各式各样不同的领域背景，我们把引发死锁的各种I/O设备、数据记录和共享文件等对象
统称为资源（resource）。
四、资源的分类
资源可以分为两大类：可抢占的（preemptable）和不可抢占的（nonpreemptable）。
可抢占的资源：当一个进程正在使用这种类型的资源时可以把它拿走而不会对该进程造成，任何不良的影响。例如：内存、CPU。
不可抢占的资源：当一个进程正在使用这种类型的资源时，如果强行把它拿走，将会导致该进程运行失败。例如：光盘刻录机。
死锁主要由不可抢占资源引起，对于可抢占资源而言，可以通过重新分配资源的方法来避免死锁。因此，这里只考察不可抢占资源。
进程在使用一个资源时，一般有三个步骤：申请资源、使用资源、释放资源。若申请不成功，则进程被阻塞。
死锁是指系统中多个进程无限期地等待永远不会发生的条件。
五、死锁发生的四个必要条件
只有4个条件都满足时，才会出现死锁。
互斥条件：任一时刻只允许一个进程使用资源
请求和保持：进程在请求其余资源时，不主动释放已经占用的资源
不剥夺：进程已经占用的资源，不会被强制剥夺环路等待
循环等待：环路中的每一条边是进程在请求另一进程已经占有的资源。
解决死锁问题的几个策略：为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。
条件1(互斥条件)：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；允许多个进程同时使用一个资源。例如，采用假脱机打印方式，可以使多个进程同时生成输出数据，然后由一个后台打印进程来真正使用打印机。由于该打印进程不占用任何其他的资源，因此可以消除因争夺打印机资源而引发的死锁问题。但这种方法不具有普遍性。
条件2(请求和保持)：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。
条件3(非剥夺)：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。
条件4(循环等待)：实际上系统不采用部分分配，也就破坏了环路条件。3.5预防死锁
1.破坏“请求和保持”条件
采用资源预分配策略，每个进程在执行之前必须一次性申请它运行所需要的全部资源；只要系统具有足够的资源，就进行分配，这种就使得进程在执行过程中不会再提出新的资源请求，从而使请求条件不成立；但在分配时，只要系统有一种资源不能满足进程要求，即使其他资源空闲，也不进行分配，而让进程等待；由于进程等待时没有占用任何资源，所以保持条件也不成立。
优点：简单、容易实现、安全、 。
缺点：（1）系统资源浪费严重 （2）导致一些进程延迟运行
2．破坏“不剥夺”条件
进程执行过程中，根据需要提出资源请求，当一个已经占有了某些资源的进程，又提出新的资源请求而暂时得不到满足时，它必须释放原来已获得的全部资源，进入等待状态，以后需要时再重新申请。由于进程在等待时已释放了它占有的全部资源，于是可以认为该进程占有的资源被剥夺了，从而破坏了不剥夺条件。
存在问题：
（1）实现起来较复杂、代价太大。因为一个资源在使用一段时间后又强行剥夺，有可能造成前段时间的工作失效，即使采取一些补救措施，也有可能前后两次的执行结果不连续。
（2）进程反复申请和释放资源，致使进程执行被无限期推迟，延长了系统的周转时间，增加了系统开销，降低了系统性能。
3．破坏“循环等待”条件
将系统中的资源按照大多数进程使用资源的顺序进行编号，每个进程只能严格按照编号递增的顺序申请资源。在这种分配策略下，进程在获得某个资源后，只能申请较高编号的资源，不能再申请低编号资源，于是，任何时候，在申请资源的诸进程中，总有一个进程占据了具有较高编号的资源，它继续申请的资源必然是空闲的，以至于在对应的资源分配图上，不可能形成进程—资源循环等待环路，从而破坏了循环等待条件。
与前两种策略相比，系统的资源利用率和吞吐量得到了明显改善。但也存在以下不足：
（1）进程实际使用资源的顺序不一定与编号的顺序一致，本分配策略会造成资源浪费；
（2）资源的编号必须相对稳定，当系统新增设备后，处理起来比较麻烦，限制了新设备的增加；
（3）这种严格的资源分配顺序使用户编程的自主性受到限制。
例如：进程PA，使用资源的顺序是R1，R2；
进程PB，使用资源的顺序是R2，R1；
若采用动态分配有可能形成环路条件，造成死锁。
采用有序资源分配法：R1的编号为1，R2的编号为2；
PA：申请次序应是：R1，R2
PB：申请次序应是：R1，R2
这样就破坏了环路条件，避免了死锁的发生。重要考点
一、单选题
1、采用按序分配资源的策略可以预防死锁，这是利用了哪个条件不成立？（）。
A、互斥
B、循环等待
C、不可抢占
D、占有并等待
答案：B
解析：有序资源分配法
这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。系统要求申请进程：
1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
2、在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。
采用有序资源分配法：R1的编号为1，R2的编号为2；
PA：申请次序应是：R1，R2
PB：申请次序应是：R1，R2
这样就破坏了环路条件，避免了死锁的发生2、产生死锁的4个必要条件是：互斥、（）、循环等待和非抢占。
A、请求与阻塞
B、请求与保持
C、请求与释放
D、释放与阻塞
答案：B
解析：互斥条件：任一时刻只允许一个进程使用资源
请求和保持：进程在请求其余资源时，不主动释放已经占用的资源
非剥夺：进程已经占用的资源，不会被强制剥夺环路等待
循环等待：环路中的每一条边是进程在请求另一进程已经占有的资源。3、系统出现死锁的原因是（）。
A、计算机系统发生了重大故障
B、有多个封锁的进程同时存在
C、若干进程因竞争资源而无休止地等待着他方释放已占有的资源
D、资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数
答案：C
解析：死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。4、操作系统中，“死锁”的概念是指（）。
A、程序死循环
B、硬件发生故障
C、两个或多个并发进程各自占有某种资源而又都等待别的进程释放它们所占有的资源
D、系统停止运行
答案：C
解析：死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。
转载注明 奥鹏无忧答案网
页:
[1]