操作系统 第11次课.pptVIP

第11次课 算法-4 优先权(Priority)调度算法 算法5-多级队列调度算法 问题1：若采用短作业优先，如何确定执行时间？ 问题2：以上各算法均具有各自的局限性，应如何选取调度算法？ 图：多级反馈队列 4.6 死锁 问题1：什么是死锁？  1.死锁例子 一个由于申请不同类型资源而产生死锁的例子 设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。 用信号量S1表示R1是否可用，用信号量S2表示R2是否可用， S1、 S2初值为1。 2.死锁的概念 英文：Deadlock 多个进程 在运行过程中争夺资源 形成僵局(Deadly-Embrace) 若无外力，僵局无法解开 问题2：产生死锁的原因？  例：生产者－消费者问题 当缓冲区满时，生产者仍可顺利执行p(mutex)操作，于是它对缓冲区有控制权，然后，当它执行p(empty)时，由于没有空缓冲区被挂起。能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品，并执行v(empty)操作，但由于缓冲区已被生产者占用，出现了死锁。 死锁的原因 进程P和Q并发执行，进程P和Q程序如下： Process P Process Q .. .. Get A Get B .. .. Get B Get A .. .. Release A Release B .. .. Release B Release A .. .. 进程P和Q按路径1、2、5、6推进顺序合法，按3、4推进顺序非法，见下图： 进程推进顺序不当引起死锁例： 问题3：产生死锁的必要调件？ 死锁的必要条件 1.个资源一次只能被一个进程所使用 2.个资源仅能被占有它的进程所释放，而不能被别的进程强占。 3.进程已经保持了至少一个资源，但又提出了新的资源要求 4.当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。 问题4：如何处理死锁 处理死锁的基本方法 死锁的预防 在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一或几个，防止发生死锁 死锁的避免 在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。银行家算法。 死锁的检测和解除 这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。 问题5：使用银行家算法避免死锁 1. 安全状态与不安全状态 系统在某一时刻，所有进程如果按照某种次序执行，如：P1，P2，……，Pn的次序执行，所有进程都能顺利运行完成，那么就称系统此时所处的状态为安全状态，进程序列P1，P2，……，Pn相应的称为安全序列。否则就称系统此时所处的状态为不安全状态。 4.不安全状态 不存在一个安全序列，不安全状态一定导致死锁？？ 5.利用银行家算法避免死锁 当一个进程提出资源请求时，银行家算法要做的工作其要点是： ①判断有无实施资源分配的可能。如果系统有能力，则实施预分配。 ②判断分配后系统是否安全，若安全，则真正实施分配。 * Priority 静态 动态 根据 类型 资源 需求 用户 要求 1.对系统进程赋予高优先级 2.估计运行时间较短，赋予高优先级 3.用户在创建时设定了优先级 4.优先级随着等待时间增长而增长 5.运行的进程优先级随执行时间增 长而下降 策略 抢占式 非抢占式 设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。 赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。 算法5-多级队列调度算法 图 3-5 多级反馈队列调度算法 (2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。 当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次