03处理机调度与死锁

《03处理机调度与死锁》由会员分享，可在线阅读，更多相关《03处理机调度与死锁（69页珍藏版）》请在金锄头文库上搜索。

1、处理机调度与死锁Processes Scheduling and DeadlockChapter 3,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除,第三章 处理机调度与死锁,高级调度(作业调度)作业作业=程序+数据+作业说明书作业步 编译、连结装配、运行作业控制块JCB 作业在系统中存在的标志，保存了系统最作业调度的全部信息作业流,3.1.1 高级、中级和低级调度,作业调度在每次执行作业调度时，都须做出以下两个决定。1) 接纳多少个作业 取决于多道程序度。太多太少？2) 接纳哪些作业 取决于

2、何种调度算法。,3.1.1 高级、中级和低级调度,3.1.1 高级、中级和低级调度,2. 低级调度(进程调度)调度对象：进程低级调度的功能 保存处理机的现场信息 按某种算法选择进程 把处理器分配给进程进程调度的三个基本机制 排队 分配程序 上下文切换,2. 低级调度的两种基本方式,非抢占方式 一旦CPU分给某进程后，它一直执行，直到完成或发生某时间被阻塞，才分给其他进程抢占式 允许根据某原则，停止正在执行的进程，将处理机分给其他进程 有时间片原则，优先权原则，短作业优先原则,3. 中级调度,主要目的：提高内存利用率和系统吞吐量。 涉及到内外存的交换，把暂时不执行的进程换出到外存，将当前进程所需

3、部分换入到内存，为当前进程的执行提供所需内存空间。,3.1.1 高级、中级和低级调度,1.调度队列模型之一：仅有进程调度,3.1.2 调度队列模型和调度准则,分时系统中,2.调度队列模型之二：高级和低级调度并存,批处理系统中,3. 调度队列模型之三：高、中、低并存,1. 对用户,(1) 周转时间短。,可把平均周转时间描述为：,作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:,3.1.3 选择调度方式和调度算法的若干准则,(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,2. 对系统,系统吞吐量高。(2) 处理

4、机利用率好。 (3) 各类资源的平衡利用。,3.1.3 选择调度方式和调度算法的若干准则,3.2.1 先来先服务和短作业(进程)优先调度算法,1. 先来先服务调度算法(FCFS),3.2 调 度 算 法,对作业调度 按照作业在后备队列中的先后次序调度对进程调度 按照进程就绪的先后次序调度优点 实现简单缺点 没有考虑优先级，有利于长作业，对短作业不好,先来先服务调度算法,FCFS和SJF调度算法的性能比较,2. 短作业(进程)优先调度算法,基于FCFS算法对短作业不利而提出，使占很大比例的短作业优先于长作业执行。缺点：该算法对长作业不利；该算法完全未考虑作业的紧迫程度；不公平。由于作业(进程)的

5、长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,优先权调度算法的类型 为了使得后进入系统的作业能优先获得处理，引入该算法,非抢占式优先权算法,系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。,3.2.2 高优先权优先调度算法,系统首先把处理机分配给优先权最高的进程，使之执行。在其执行期间，只要又出现了另一个其优先权更高的进程

6、，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。此算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。,2) 抢占式优先权调度算法,静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权 创建进程时所赋予的优先权，可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,2. 优先权的类型,优先权的变化规律可描述为：,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：,3. 高响应比优先调度算法,RP =,

7、(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。,1. 时间片轮转法系统将所有的就绪进程按FCFS的原则，排成一个队列每次调度时，把CPU分配给队首进程，并令其执行一个时间片当执行的时间片用完时，调度程序将它送往就绪队列的末尾；把处理机分配给就绪队列中新的队首进程执行一个时间片。这样就可以保证就绪队列中的所有

8、进程，在一给定的时间内，均能获得一时间片的处理机执行时间。,3.2.3 基于时间片的轮转调度算法,(1) 设置多个就绪队列，并为各个队列赋予不同的优先级。,2. 多级反馈队列调度算法,(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转

9、的方式运行。,(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。,3.3.1 实现实时调度的基本条件,1. 向调度程序提供必要的信息2. 系统处理能力强3. 采用抢占式调度机制4. 具有快速切换机制,3.3 实 时 调 度,1. 向调度程序提供必要的信息,就绪时间。开始截止时间和完成截止时间

10、。 处理时间。 资源要求。 优先级。,在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件： 系统才是可调度的。,2. 系统处理能力强,6个硬实时任务，周期时间都是 50 ms，处理时间为 10 ms,解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件

11、改为：,当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。,3. 采用抢占式调度机制,该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。 (2) 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。,4. 具有快速切换机制,1. 非抢占式调度算法,非抢占式轮转调

12、度算法。 (2) 非抢占式优先调度算法。,3.3.2 实时调度算法的分类,基于时钟中断的抢占式优先权调度算法。(2)立即抢占(Immediate Preemption)的优先权调度算法。,2. 抢占式调度算法,实时进程调度,1. 最早截止时间优先算法,EDF(Earliest Deadline First),图 EDF算法用于非抢占调度方式,3.3.3 常用的几种实时调度算法,按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。,2. 最低松弛度优先算法,LLF(Least Laxity First),该算法

13、是根据任务紧急(或松弛)的程度，来确定任务的优先级，松弛度越低，优先级越高。任务紧急(或松弛)的程度:完成截止时间运行时间,图 任务A和B每次必须完成的时间,假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。,在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出：

14、 A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms B1的松弛度为15ms，故调度程序应选择B2运行。,在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-4

15、5)，于是又应调度A3执行。在t6=55ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7=70 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。,图 利用LLF算法进行调度的情况,3.4.1 产生死锁的原因,竞争资源 资源不充分 (2) 进程间推进顺序非法 请求和释放资源的顺序不当,3.4 产生死锁的原因和必要条件,死锁：多个进程由于竞争资源而造成的一种僵局，若无外力作用，这些进程将无法向前推进。,资源:永久性资源，可再用资源，可以被多个进程多次使用可剥夺

16、资源，如CPU、内存，优先权高者可抢占优先权低者的资源非剥夺性资源，如打印机，分配后不能强行收回，只有等进程使用完毕临时性资源，只可使用一次的资源，如信号量,1. 竞争资源引起进程死锁,竞争资源而引起的死锁：,竞争非剥夺性资源而引起的死锁,竞争临时性资源引起的死锁,R1：打印机R2：扫描仪,1) 进程推进顺序合法,2. 进程推进顺序不当引起死锁,2) 进程推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1, P2保持了资源R2, 系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2: Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。,