计算机操作系统CPU调度与死锁.ppt

第三章处理机调度与死锁 3．1处理机调度的基本概念 分配处理机的任务是由处理机调度程序完成的。 由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏， 3．1．1高级、中级和低级调度 3.1.2 调度队列模型 1．仅有进程调度的调度队列模型 2．具有高级和低级调度的调度队列模型 3．同时具有三级调度的调度队列模型 3．1．3选择调度方式和调度算法的若干准则 1.面向用户的准则 :这是为了满足用户的需求所应遵循的一些准则。其中，比较重要的有以下几点。 （1）周转时间短。 所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。 平均周转时间描述为： 3．2 调度算法 调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。 3.2.1 先来先服务和短作业优先调度算法 FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 举例：下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。 FCFS算法 2．短作业优先调度算法 3.2.2 高优先权优先调度算法 该算法是把处理机分配给就绪队列中优先权最高的进程。 该算法分两种类型： （1）非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。 3．高响应比优先调度算法 该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。 利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销。 3.2.3 基于时间片的轮转调度算法 1.时间片轮转法 在时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程。并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间，换言之，系统能在给定的时间内，响应所有用户的请求。 2.多级反馈队列调度算法 多级反馈队列调度算法实施过程如下： （1）应设置多个就绪队列，并为各个队列赋予不同的优先级。 （2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……。 （3）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 图3-5 多级反馈队列调度算法 3.3 实时调度 由于在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个外部事件，往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求，前面所介绍的多种调度算法，并不能很好地满足实时系统对调度的要求，为此，需要引入一种新的调度，即实时调度。 3.3.1实现实时调度的基本条件 1．提供必要的信息 （1）就绪时间。这是该任务成为就绪状态的起始时间。 （2）开始截止时间和完成截止时间。 （3）处理时间。这是指一个任务从开始执行直至完成所需的时间。 （4）资源要求。 （5）优先级。 3.3.2 实时调度算法的分类 1．非抢占式调度算法 （1）非抢占式轮转调度算法: 调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行。 （2）非抢占式优先调度算法: 如果在系统中存在着实时要求较为严格的任务，则可采用非抢占式优先调度算法，为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，才能被调度执行。 实时进程调度 3.3.3 常用的几种实时调度算法 1．最早截止时间优先算法 该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。调度程序总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。 A和B任务每次必须完成的时间