操作系统-处理机调度和死锁OS3 (4)

第三章处理机调度和死锁2本章主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除33.4实时调度3.4.1实现实时调度的基本条件3.4.2实时调度算法的分类3.4.3常用的几种实时调度算法4实时调度定义实时系统中存在着若干个实时进程或任务，它们用来反应或控制某个外部事件，往往带有某种程度的紧迫性，因而对实时系统中的调度也提出了某些特殊要求。实现实时调度的基本条件1实时调度算法的分类2常用的几种实时调度算法35实现实时调度的基本条件1提供必要的信息就绪时间任务称为就绪状态的起始时间。开始截止时间和完成截止时间处理时间指一个任务从开始执行直至完成所需的时间。资源要求任务执行时所需的一组资源。优先级可以设为绝对优先级或相对优先级。6解决方法•增强单处理机的处理能力，以减少单一任务的处理时间•采用多处理机系统实现实时调度的基本条件1系统处理能力强若处理机处理能力不够强，则会出现处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。7实现实时调度的基本条件1采用抢占式调度机制为了让分派延迟保持很小，需要允许系统调用是可被抢占的•在长时间系统调用内插入抢占点：该点用来检查高优先权进程是否需要允许，如要则进行任务切换；当高优先权进程终止时，它所中断的进程继续完成系统调用–抢占点只能放在内核的“安全”位置，但是此处空间有限，不能增加过多抢占点，因此也有可能产生较大的分派延迟•整个内核可抢占：所有正在被修改的内核数据结构必须通过各种同步机制加以保护，使其不受高优先权进程修改8实现实时调度的基本条件1采用抢占式调度机制可预知任务开始截止时间的小型实时系统采用非抢占调度机制，以减少系统开销这种OS中，实时任务小，完成关键任务和临界区后，阻塞自身释放处理机，使得调度程序可以选择开始截止时间即将到达的任务9实现实时调度的条件具有快速切换机制为保证硬实时的及时响应，OS需要具有快速切换机制对外部中断的快速响应能力系统应具有快速硬件中断机构保证对紧迫外部中断请求的及时响应，同时也要保证本次中断的时间间隔尽量的小快速的任务分派能力完成任务调度后，需要进行任务切换，此时应使系统中每个运行功能单位适当小，以减少切换的时间开销实现实时调度的基本条件110实时调度算法的分类按实时任务性质分硬实时与软实时按调度方式分非抢占式与抢占式按调度时间分静态调度：进程执行前已经决定各进程执行顺序动态调度：根据当前运行情况选择可投入运行的进程多处理机环境下集中式与分布式11非抢占式调度算法优点算法思想简单，易于实现常用于小型实时系统或实时要求不严格的实时控制系统中可分为：非抢占式轮转调度算法非抢占式优先调度算法非抢占式轮转调度算法算法思想：在一台计算机中为生产现场的多个相同或类似对象建立一一对应的实时任务，并将其排成轮转队列等待调度，每次可获得数秒或数十秒的时间片响应常用于工业生产的群控系统12非抢占式调度算法非抢占式轮转调度算法算法思想：在一台计算机中为生产现场的多个相同或类似对象建立一一对应的实时任务，并将其排成轮转队列等待调度，每次可获得数秒或数十秒的时间片响应常用于要求不太严格的实时控制系统进程1进程2进程n实时进程实时进程要求调度调度实时进程运行调度时间非抢占式轮转调度13非抢占式调度算法非抢占式优先调度算法算法思想：非抢占式优先调度算法可以为要求较为严格的任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。常用于有一定要求的实时控制系统中当前进程实时进程实时进程请求调度当前进程运行完成调度时间非抢占式优先权调度14抢占式调度算法基于时钟中断的抢占式优先权调度算法在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。立即抢占的优先权调度算法这种调度算法要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。抢占式调度算法可分为：基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法15当前进程实时进程实时进程请求调度时钟中断到来时调度时间基于时钟中断抢占的优先权调度当前进程实时进程实时进程请求调度实时进程抢占当前进程，并立即执行调度时间立即抢占的优先权调度163.4.3常用的几种实时调度算法最早截止时间优先EDF（EarliestDeadlineFirst）算法最低松弛度优先即LLF（LeastLaxityFirst）算法17EDF算法基本思想：根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。EDF算法即可用于抢占式调度，也可用于非抢占式调度。18t134213421234EDF算法用于非抢占调度方式_适用于非周期实时任务开始截止时间任务执行任务到达B1最后期限时间t/ms固定优先级调度（A优先级高）0104020305060708090100B1A1A2A3A4A5B2A2最后期限A1最后期限A3最后期限A4最后期限A5最后期限B1最后期限到达时间、执行时间和最后期限0104020305060708090100时间t/msA1B1A2B1A3B2A4B2A4A5B2B1错过A1最后期限A5,B2A1,B1到达A2到达A3到达A4到达A5到达B2到达A2最后期限A3最后期限A4最后期限B1最后期限时间t/ms0104020305060708090100B1A1A2A3A4A5B1A2最后期限A1最后期限A3最后期限A4最后期限A5最后期限B1最后期限到达时间、执行时间和最后期限0104020305060708090100时间t/msB1A2A3B2A4A5B2固定优先级调度（B优先级高）A1错过A3A4错过A5,B2A1,B1到达A2到达A3到达A4到达A5到达B2到达A2最后期限B1最后期限B1最后期限时间t/ms0104020305060708090100B1A1A2A3A4A5B2A2最后期限A1最后期限A3最后期限A4最后期限A5最后期限B1最后期限到达时间、执行时间和最后期限抢占式EDF0104020305060708090100时间t/msA1B1A2B1A3A4B2A5B2A1,B1到达在t=0时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行；在t=10时，A1完成，又调度B1执行；在t=20时，A2到达，由于A2的截止时间比B1早，B1被中断而调度A2执行；在t=30时，A2完成，又重新调度B1执行；在t=40时，A3又到达，但B1的截止时间要比A3早，仍应该让B1继续执行直到完成（t=45），然后再调度A3执行；在t=55时，A3完成，又调度B2执行。A1最后期限A2最后期限B1最后期限A3最后期限A4最后期限A2到达A3到达A4到达A5到达B2到达22LLF算法基本思想：根据任务紧急（或松弛）程度，来确定任务的优先级。任务的紧急程度越高，为该任务赋予的优先级越高，以使之优先执行。例如：一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度（松弛程度）为100ms。又如，另一任务400ms时必须完成，它本身运行需要150ms，则其松弛程度为250ms。实现该算法时，要求系统中有一个按松弛度排序的实时任务队列，松弛度最低的任务排在队列最前面，调度程序总是选择队列中的队首任务执行。23LLF算法举例在实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B则要求每50ms执行一次，执行时间为25ms。任务A和B每次必须完成的时间A1,A2,A3…和B1,B2,B3…如下图所示。tA1A2A3A4A5A6A7A8020406080100120140160B1B2B3松弛度=必须完成时间-其本身的运行时间-当前时间A1(10)01020304050607080t1B1(20)A2(10)t2t3t4B1(5)A3(10)B2(15)t5t6t7t8A4(10)B2(10)t=0ms时，A1的松弛度是10ms，B1的松弛度是25ms，调度A1执行；t=10ms时，A2尚未到达，调度B1执行；t=30ms时，A2的松弛度是0ms，B1的松弛度是15（50-5-30）ms，调度A2执行；t=40ms时，A3的松弛度是10ms，B1的松弛度是5（50-5-40）ms，重新调度B1执行；t=45ms时，B1执行完成，A3的松弛度是5（60-10-45）ms，调度A3执行；t=55ms时，A尚未进入第4周期，B已进入第二周期，故再调度B2执行；t=70ms时，A4松弛度已减至0ms，而B2的松弛度为20（100-70-10）ms，故此时又应该抢占B2的处理机而调度A4执行。书上的解释25松弛度=必须完成时间-其本身的运行时间-当前时间A1(10)01020304050607080t1B1(20)A2(10)t2t3t4B1(5)A3(10)B2(15)t5t6t7t8A4(10)B2(10)t=0ms时，A1的松弛度是10ms，B1的松弛度是25ms，调度A1执行；t=10ms时，A2尚未到达，调度B1执行；t=20ms时，由于A1已完成，A2刚到达，故而没有比较A2和B1的松弛度，而是B1接着执行。并且还要时刻监控着A2的松弛度，等到松弛度为0，也就是30ms时，抢占B1的CPU。这种方法的效率并不高，原因在于A2刚到达时，没有和B1的松弛度比较，而是等A2到达后，不断监控A2的紧迫程度，等紧迫度升到最高，也就是松弛度最低时，才又抢占CPU。松弛度=必须完成时间-其本身的运行时间-当前时间t=0ms时，A1的松弛度是10ms，B1的松弛度是25ms，调度A1执行；t=10ms时，A2尚未到达，调度B1执行；t=20ms时，A2到达，A2的松弛度是10（40-10-20）ms，B1的松弛度是（50-5-20=25）ms，调度A2执行；t=30ms时，A3尚未到达，调度B1执行；t=40ms时，A3的松弛度是10（60-40-10）ms，B1的松弛度是5（50-5-40）ms，B1继续执行；t=45ms时，B1执行完成，调度A3执行；T=50ms时，B2到达，A3松弛度是（60-5-50=5），B2松弛度是25（100-25-50），A3继续执行；t=55ms时，A尚未进入第4周期，B已进入第二周期，故再调度B2执行；t=60ms时，A4到达，A4松弛度为10ms（80-10-60），B2松弛度是20（100-20-60），A4执行；A1(10)01020304050607080t1B1(10)A2(10)t2t3t4A3(10)B2t5t6t7t8A4(10)B1(15)B2(5)另一情况：调度发生在两种场合：①有新进程到达时，计算松弛度决定是否抢占；②有进程释放CPU（CPU空闲时）27本章主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除283.5.1产生死锁的原因和必要条件1.死锁的定义：是指多个进程运行过程中因争夺资源而造成的一种僵局（Deadly-Embrace），当进程处于这种僵持状态时，若无外力作用，它们将无法再向前推进。参与死锁的进程最少是两个参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源