3操作系统 - 处理机调度与死锁

第三章处理机调度与死锁Page2第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除Page33.1处理机调度的层次引述多道程序系统中，作业提交后，要想获得处理机而执行，必须要经过处理机调度。一个批处理作业，可能经历三级调度：3.1.1高级调度3.1.2低级调度3.1.3中级调度Page43.1处理机调度的层次3.1.1高级调度高级调度又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的哪些作业调入内存。根据JCB的信息决定：（1）接纳多少个作业（2）接纳哪些作业Page53.1处理机调度的层次3.1.2低级调度低级调度又称为进程调度或短程调度，它所调度的对象是进程。低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。进程调度方式：（1）非抢占方式：进程占用处理机直至自愿放弃或发生某事件被阻塞时，在把处理机分配给其他进程。（2）抢占方式：允许暂停某个正在执行的进程，将处理机重新分配给另一个进程。Page63.1处理机调度的层次3.1.3中级调度中级调度又称为中程调度。将那些暂时不能运行的进程调至外存上等待（此时进程状态称为挂起状态），当这些进程重又具备运行条件、且内存又稍有空闲时由中级调度来决定把外存的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。属于对换功能的一部分Page73.1处理机调度的层次终端型作业：低级批量性作业：高级---低级现代较完善的os具有三级调度。Page8第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除Page93.2调度队列模型和调度准则引述三级调度都涉及进程的队列。可以形成以下三种调度队列模型1、仅有进程调度2、具有高级和低级调度3、具有三级调度Page103.2调度队列模型和调度准则3.2.1调度队列模型1、仅有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完Page113.2调度队列模型和调度准则3.2.1调度队列模型2、具有高级调度和低级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……Page123.2.1调度队列模型3、同时具有三级调度的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2调度队列模型和调度准则Page133.2调度队列模型和调度准则3.2.2选择调度方式和调度算法的若干准则在不同的系统中通常采用不同的调度方式和算法。系统选择调度方式和算法的准则分为两种面向用户的准则面向系统的准则Page143.2调度队列模型和调度准则3.2.2选择调度方式和调度算法的若干准则面向用户的准则（1）周转时间/带权周转时间评价批处理系统性能（2）响应时间评价分时系统性能（3）截止时间可评价实时系统性能（4）优先权原则Page153.2调度队列模型和调度准则3.2.2选择调度方式和调度算法的若干准则面向系统的准则（1）系统吞吐量评价批处理系统性能（2）处理机利用率（3）各类资源的平衡利用Page16第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除Page173.3调度算法引述调度算法：根据系统的资源分配策略所规定的资源分配算法。不同类型的系统和系统目标，采用不同的调度算法。常用的调度算法先来先服务（掌握）短作业（进程）优先（掌握）优先权—高响应比优先（掌握）时间片轮转法（掌握）多级反馈队列（理解）调度算法有的适用于高级调度，有的适用于低级调度，有的既可用于高级调度，也可用于低级调度。Page183.3调度算法引述需要了解几个时间的参数（1）服务时间Ts：进程预期需要的执行时间。（2）周转时间T：进程从进入系统到运行结束所经历的全部时间。（3）带权周转时间T/Ts：周转时间/服务时间。进程到达时间服务时间A03B26C44D65E82Page193.3调度算法3.3.1先来先服务调度算法（FCFS）调度策略：非抢占每一个进入系统的进程都放入就绪队列(ReadyQueue)当前运行的进程结束，选择就绪队列中等待最久的进程ABCDE05101520Page203.3调度算法3.3.1先来先服务调度算法（FCFS）完成时间周转时间带权周转时间进程到达时间服务时间平均有利于长作业（进程），不利于短作业（进程）。Page213.3调度算法3.3.2短作业/进程优先调度算法(SJF/SPF)调度策略：非抢占当前进程运行结束后选择就绪队列中服务时间最短的进程ABCDE05101520Page223.3调度算法3.3.2短作业/进程优先调度算法(SJF/SPF)有效降低作业的平均等待时间，提高系统吞吐率缺点：对长作业不利，如D，甚至长作业无法被调度没考虑作业紧迫性根据用户估计的执行时间而定，会有人的因素干扰算法。进程到达时间服务时间平均完成时间周转时间带权周转时间SPFPage233.3调度算法3.3.3高优先权优先调度算法(HRRN)优先权调度算法的类型（1）非抢占式优先权算法进程运行直到完成或因某事件放弃处理机（2）抢占式优先权调度算法进程执行期间，有出现另一个优先权更高的进程，则调度程序立即停止当前进程，将处理机分配给新到的进程。Page243.3调度算法3.3.3高优先权优先调度算法(HRRN)优先权的类型（1）静态优先权创建进程时确定，在进程的整个运行期间保持不变。（2）动态优先权创建进程时所赋予的优先权，可以随进程的推进或随其等待时间的增加而改变。Page253.3调度算法3.3.3高优先权优先调度算法(HRRN)调度策略：非抢占策略选择就绪队列中响应比(优先权)最高的进程要求服务时间要求服务时间等待时间优先权ABCDE05101520Page263.3调度算法3.3.3高优先权优先调度算法(HRRN)等待时间相同时，有利于短作业要求服务时间相同时，先来先服务长作业随着等待时间优先级增加，从而可以获得处理机。折中算法，但每次调度前要计算响应比，增加系统开销。完成时间周转时间带权周转时间进程到达时间服务时间平均Page273.3调度算法3.3.4基于时间片的轮转调度算法（RR）调度策略：抢占策略就绪队列进程每次只能执行一个时间片，时间片用完由调度程序停止该进程，并送往队尾，再将CPU分给队首进程。时间片的选择最好略大于一次典型的交互所需要的时间Page283.3调度算法3.3.4基于时间片的轮转调度算法（RR）ABCDE05101520ABCDE05101520一个单位四个单位Page293.3调度算法3.3.5多级反馈队列调度算法基于时间片的调度就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1＜S2＜S3)Page303.3调度算法3.3.5多级反馈队列调度算法过程(1)按优先级由高到低设置多个队列RQ0，RQ1…RQn，高优先级队列时间片小。(2)刚进入系统的进程按FCFS放入最高的RQ0中(3)进程一次时间片没执行完，就降至下一级队列，以此类推，降至最低优先级队列后，一直在此队列中不再下降。(4)系统优先调度高优先级队列中的进程，仅当RQ0空闲时才调度RQ1队列进程，以此类推。缺点：处罚长进程，长进程可能被饿死优点：不需要知道进程执行所需时间Page313.3调度算法练习题请按照FCFS、SPF、HRRN、RR(1)算法对上面的进程进行调度，要求画出调度过程。进程名达到时间服务时间A03B16C32D55E74Page323.3调度算法练习题01234567891011121314151617181920ABCDEPage33第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除Page343.4实时调度引述实时任务任务的结束时间有严格约束(Deadline)，即任务执行必须在Deadline之前完成。具有紧迫性。前述算法不能很好地满足实时系统对调度的特殊要求，所以引入实时调度。Page353.4实时调度3.4.1实时调度的基本条件1、提供必要的信息就绪时间、开始/完成截止时间、处理时间、资源要求、优先级。2、系统处理能力强提高系统处理能力途径单处理机，增强处理能力多处理机3、采用抢占式调度机制高优先权任务可以抢占低优先权，使用处理机。4、具有快速切换机制对外部中断的快速响应能力快速的任务分派能力Page363.4实时调度3.4.2实时操作系统RTOSReal-TimeOperatingSystem对外部输入的信息，实时操作系统能够在规定的时间内处理完毕并做出反应正确性：不仅依靠计算逻辑的正确，而且要求在规定的时间内得到该结果通常给定一个开始时间或者结束时间的最后期限多用于工业、军事等控制领域或实时信息处理方面Page373.4实时调度3.4.2实时操作系统RTOS嵌入式操作系统的实时性都比较强，可归为RTOSVxWorks操作系统美国WindRiver公司于1983年设计开发，实时性强，内核可极微（据说最小可8K），可靠性较高等，主要在通信设备等实时性要求较高的系统中。uCOSuC/OS是一种免费公开源代码、结构小巧、具有可剥夺实时内核的实时操作系统。嵌入式Linux操作系统Linux本身嵌入式操作系统，嵌入式领域使用的是专为嵌入式设计的已被裁减过的Linux系统，如uClinuxWindowsCE主要用于PDA、手机、显示仪表等界面要求较高或者要求快速开发的场合其他RTOS：Symbian、PalmOS等Page38第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除Page393.5产生死锁的原因和必要条件3.5.1死锁的定义所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法向前推进。Page403.5产生死锁的原因和必要条件3.5.2产生死锁的原因1、竞争资源2、进程间推进顺序非法Page413.5产生死锁的原因和必要条件3.5.2产生死锁的原因1、竞争资源资源分为可剥夺资源和非剥夺资源。竞争非剥夺资源，且数量不能满足进程运行需要，就会陷入僵局。如：200K的可用内存，P1，P2都进行到第二步时，死锁发生。P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;Page423.5产生死锁的原因和必要条件3.5.2产生死锁的原因2、进程间推进顺序非法进程P进程QGetAGetB…………GetBGetA…………ReleaseAReleaseB…………ReleaseBReleaseAPage433.5产生死锁的原因和必要条件3.5.3产生死锁的必要条件（1）互斥条件一段时间内，某