11、任务管理与调度概论.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 时间片轮转调度 采用时间片轮转调度算法时，任务的时间片大小要适当选择。 时间片大小的选择会影响系统的性能和效率： 时间片太大，时间片轮转调度就没有意义； 时间片太小，任务切换过于频繁，处理器开销大，真正用于运行应用程序的时间将会减小。 不同的实时内核在实现时间片轮转调度算法上可能有一些差异： 有的内核允许同优先级的各个任务有不一致的时间片； 有的内核要求相同优先级的任务具有一致的时间片。 第四节优先级反转 优先级继承协议 优先级天花板协议 理想情况下 高优先级任务就绪后，能够立即抢占低优先级任务而得到执行。 但在有多个任务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞，并等待低优先级任务执行的现象。 优先级反转（priority inversion）：高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象。 优先级反转 通常的同步互斥机制为信号量（semaphore）、锁（lock）和Ada中的Rendezvous（汇合）等。 为保护共享资源的一致性，或是确保非抢占资源在使用上的合适顺序，使用这些方法是非常必须的。 直接应用这些同步互斥机制将导致系统中出现不定时间长度的优先级反转和比较低的任务可调度性情况。 优先级反转 t0 t0 t1 t2 t3 t4 t5 t6 t7 t8 Critical section guarded by S time T1 T2 T3 t9 t0 t10 t11 t12 t13 t14 t15 t16 t18 t17 假定T1和T3通过信号量S共享一个数据结构。 在时刻t1，任务T3获得信号量S，开始执行临界区代码。 在T3执行临界区代码的过程中，高优先级任务T1就绪，抢占任务T3，并在随后试图使用共享数据，但该共享数据已被T1通过信号量S加锁。在这种情况下，会期望具有最高优先级的任务T1被阻塞的时间不超过任务T3执行完整个临界区的时间。 但事实上，这种阻塞时间的长度是无法预知的。这主要是由于任务T3还可能被具有中等优先级的任务T2所阻塞，使得T1也需要等待T2和其他中等优先级的任务释放CPU资源。 优先级 高 低 任务T1的阻塞时间长度不定，可能会很长。 如果任务在临界区内不允许被抢占，这种情况可得到部分解决。但由于形成了不必要的阻塞，使得这种方案只适合于非常短的临界区。 比如，一旦一个低优先级任务进入了一个比较长的临界区，不会访问该临界区的高优先级任务将会被完全不必要的阻塞。 优先级反转 Lampson在1980年发表的题为“Experiences with processes and monitors in Mesa”的论文中首先讨论关于优先级反转的问题： 建议临界区执行在比可能使用该临界区的所有任务的优先级更高的优先级上。 解决优先级反转现象的常用协议为： 优先级继承协议（priority inheritance protocol）； 优先级天花板协议（priority ceiling protocol）。 优先级反转 优先级继承协议 优先级继承协议的基本思想是： 当一个任务阻塞了一个或多个高优先级任务时，该任务将不使用其原来的优先级，而使用被该任务所阻塞的所有任务的最高优先级作为其执行临界区的优先级。 当该任务退出临界区时，又恢复到其最初的优先级。 t0 t0 t1 t2 t3 t4 t5 t6 t7 t8 Critical section guarded by S time T1 T2 T3 t9 t0 t10 t11 t12 t13 t14 t15 t16 t18 t17 如果任务T1被T3阻塞，优先级继承协议要求任务T3以任务T1的优先级执行临界区。这样，任务T3在执行临界区的时候，原来比T3具有更高优先级的任务T2就不能抢占T3了。当T3退出临界区时，T3又恢复到其原来的低优先级，使任务T1又成为最高优先级的任务。这样任务T1会抢占任务T3而继续获得CPU资源，而不会出现T1无限期被任务T2所阻塞的情形。 优先级 高 低 优先级继承协议 优先级继承协议的定义 如果任务T为具有最高优先级的就绪任务，任务T将获得CPU资源。 在任务T进入临界区前，任务T需要首先请求获得该临