计算机操作系统3-处理机调度与死锁(ppt83)-经营管理(编辑修改稿)

计算机操作系统3-处理机调度与死锁(ppt83)-经营管理(编辑修改稿)内容摘要：

ediate Preemption)的优先权调度算法。 ( a ) 非抢占轮转调度当前进程 实时进程实时进程请求调度实时进程枪占当前进程，并立即执行( d ) 立即抢占的优先权调度调度时间进程 1 进程 2实时进程要求调度进程 n 实时进程调度实时进程运行( b ) 非抢占优先权调度当前进程 实时进程实时进程请求调度 当前进程运行完成调度时间当前进程实时进程请求调度 时钟中断到来时调度时间( c ) 基于时钟中断抢占的优先权抢占调度调度时间实时进程图 36 实时进程调度 第三章 处理机调度与死锁 常用的几种实时调度算法 1. 最早截止时间优先即 EDF(Earliest Deadline First)算法 图 37 EDF算法用于非抢占调度方式 1 3 4 2开始截止时间任务执行任务到达1 2 3 41 3 4 2t第三章 处理机调度与死锁 2. 最低松弛度优先即 LLF(Least Laxity First)算法 该算法是根据任务紧急 (或松弛 )的程度 ， 来确定任务的优先级。 任务的紧急程度愈高 ， 为该任务所赋予的优先级就愈高 ， 以使之优先执行。 例如 ， 一个任务在 200ms时必须完成 ，而它本身所需的运行时间就有 100ms， 因此 ， 调度程序必须在100 ms之前调度执行 ， 该任务的紧急程度 (松弛程度 )为 100 ms。 又如 ， 另一任务在 400 ms时必须完成 ， 它本身需要运行 150 ms， 则其松弛程度为 250 ms。 在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列 ， 松弛度最低的任务排在队列最前面 ， 调度程序总是选择就绪队列中的队首任务执行。 该算法主要用于可抢占调度方式中。 假如在一个实时系统中 ， 有两个周期性实时任务 A和 B， 任务 A要求每 20 ms执行一次 ， 执行时间为 10 ms；任务 B只要求每 50 ms执行一次 ，执行时间为 25 ms。 第三章 处理机调度与死锁 图 38 A和 B任务每次必须完成的时间 A1A2A3A4A5A6A7A820 40 60 80 1 0 0 1 2 0 1 4 0 1 6 0B1B2B3t0第三章 处理机调度与死锁 在刚开始时 (t1=0)， A1必须在 20ms时完成 ， 而它本身运行又需 10 ms， 可算出 A1的松弛度为 10ms； B1必须在 50ms时完成 ， 而它本身运行就需 25 ms， 可算出 B1的松弛度为 25 ms， 故调度程序应先调度 A1执行。 在 t2=10 ms时 ， A2的松弛度可按下式算出： A2的松弛度 =必须完成时间 其本身的运行时间 当前时间 =40 ms10 ms10 ms=20 ms 第三章 处理机调度与死锁 类似地 ， 可算出 B1的松弛度为 15ms， 故调度程序应选择 B2运行。 在 t3=30 ms时 ， A2的松弛度已减为 0(即 401030)， 而 B1的松弛度为 15 ms(即 50530)， 于是调度程序应抢占 B1的处理机而调度 A2运行。 在 t4=40 ms时 ， A3的松弛度为 10 ms(即 601040)， 而 B1的松弛度仅为 5 ms(即 50540)， 故又应重新调度 B1执行。 在 t5=45 ms时 ， B1执行完成 ， 而此时 A3的松弛度已减为 5 ms(即 601045)， 而 B2的松弛度为 30 ms(即 1002545)， 于是又应调度 A3执行。 在 t6=55ms时 ， 任务 A尚未进入第 4周期 ， 而任务 B已进入第 2周期 ， 故再调度 B2执行。 在 t7=70 ms时 ， A4的松弛度已减至 0 ms(即 801070)， 而 B2的松弛度为 20 ms(即 1001070)， 故此时调度又应抢占 B2的处理机而调度 A4执行。 第三章 处理机调度与死锁 图 39 利用 ELLF算法进行调度的情况 t1A1( 1 0 )10 20 30 40 50 60 80t0t1＝ 0B1( 2 0 )t2t370A2( 1 0 ) A3( 1 0 ) A4( 1 0 )t4t5t6t7t8B1( 5 ) B2( 1 5 ) B2( 1 0 )第三章 处理机调度与死锁 多处理机系统中的调度 多处理器系统的类型 (1) 紧密耦合 (Tightly Coupted)MPS。 这通常是通过高速总线或高速交叉开关 ， 来实现多个处理器之间的互连的。 它们共享主存储器系统和 I/O设备 ，并要求将主存储器划分为若干个能独立访问的存储器模块 ，以便多个处理机能同时对主存进行访问。 系统中的所有资源和进程 ， 都由操作系统实施统一的控制和管理。 第三章 处理机调度与死锁 (2) 松散耦合 (Loosely Coupled)MPS。 在松散耦合 MPS中 ， 通常是通过通道或通信线路 ， 来实现多台计算机之间的互连。 每台计算机都有自己的存储器和 I/O设备 ， 并配置了 OS来管理本地资源和在本地运行的进程。 因此 ， 每一台计算机都能独立地工作 ， 必要时可通过通信线路与其它计算机交换信息 ， 以及协调它们之间的工作。 第三章 处理机调度与死锁 2. 对称多处理器系统和非对称多处理器系统 (1) 对称多处理器系统 SMPS(Symmetric MultiProcessor System)。 在系统中所包含的各处理器单元 ， 在功能和结构上都是相同的 ， 当前的绝大多数 MPS都属于 SMP系统。 例如 ， IBM公司的 SR/6000 Model F50, 便是利用 4片 Power PC处理器构成的。 (2) 非对称多处理器系统。 在系统中有多种类型的处理单元 ， 它们的功能和结构各不相同 ， 其中只有一个主处理器 ， 有多个从处理器。 第三章 处理机调度与死锁 进程分配方式 1. 对称多处理器系统中的进程分配方式 在 SMP系统中 ， 所有的处理器都是相同的 ， 因而可把所有的处理器作为一个处理器池 (Processor pool)， 由调度程序或基于处理器的请求 ， 将任何一个进程分配给池中的任何一个处理器去处理。 在进行进程分配时 ， 可采用以下两种方式之一。 1) 静态分配 (Static Assigenment)方式 2) 动态分配 (Dynamic Assgement) 第三章 处理机调度与死锁 2. 非对称 MPS中的进程分配方式 对于非对称 MPS， 其 OS大多采用主 —从 (MasterSlave)式 OS， 即 OS的核心部分驻留在一台主机上 (Master)， 而从机 (Slave)上只是用户程序 ， 进程调度只由主机执行。 每当从机空闲时 ， 便向主机发送一索求进程的信号 ， 然后 ， 便等待主机为它分配进程。 在主机中保持有一个就绪队列 ， 只要就绪队列不空 ， 主机便从其队首摘下一进程分配给请求的从机。 从机接收到分配的进程后便运行该进程 ， 该进程结束后从机又向主机发出请求。 第三章 处理机调度与死锁 进程 (线程 )调度方式 1. 自调度 (SelfScheduling)方式 1) 在多处理器系统中 ， 自调度方式是最简单的一种调度方式。 它是直接由单处理机环境下的调度方式演变而来的。 在系统中设置有一个公共的进程或线程就绪队列。