操作系统课件(汤子瀛)——本科操作系统3.ppt

2、多级反馈队列调度算法 设置多个就绪队列，并为各队赋予不 同的优先权和时间片，第一个队列的优先 权最高时间片最小，新创建的进程进入第 一就绪队列尾，运行一个时间片后未完 成，进入第二就绪队列尾，最后一个队列 以时间片轮转方式运行，只当上一队列空 闲时才调度下一队列的进程。 3、多级反馈队列调度算法的性能 (1)终端型作业用户：可在第一队列所规定的时间片内完成。 (2)短批处理作业用户：通常在前三个队列中各执行一个时间片即可完成，周转时间短。 (3)长批处理作业用户：在n个队列中各运行一个时间片后，再按轮转方式运行，不会长期得不到处理。 S1 S2 S3 Sn 至CPU 至CPU 至CPU 至CPU 就绪队列1 就绪队列2 就绪队列3 就绪队列n S1 S2 S3 … Sn 3.4 实时调度 3.4.1 实现实时调度的基本条件 1、提供必要的信息 (1)就绪时间 (2)开始截止时间和完成截止时间 (3)处理时间 (4)资源要求 (5)优先级 2、系统处理能力强 设系统中有m个周期性的硬实时任务， 周期为Pi，处理时间为Ci，单处理机的限 制条件为： 多处理机的限制条件为： 3、采用抢占式调度机制 4、具有快速切换机制:(1)对外部中断的快 速响应能力(2)快速的任务分派能力。 3.4.2 实时调度算法的分类 1、非抢占式调度算法 适用于要求不太严格的实时控制系统中。 (1)非抢占式轮转调度算法 (2)非抢占式优先调度算法 2、抢占式调度算法 适用于要求较严格的实时系统中。 (1)基于时钟中断的抢占式优先权调度算法 在时钟中断到来时，抢占CPU分配给优 先权高的实时进程，适用于大多数的实时 系统中。 (2)立即抢占的优先权调度算法 优先权高的实时进程抢占当前进程并立 即执行。 实时进程 进程n … 进程2 进程1 实时进程请求调度 调度实时进程运行 调度时间 非抢占轮转调度 实时进程 当前进程 调度实时进程运行 调度时间 当前进程完成时 非抢占优先权调度 实时进程请求调度 调度实时进程运行 实时进程 当前进程 调度时间 时钟中断 实时进程 当前进程 调度实时进程运行 调度时间 当前指令完成时 实时进程请求调度 时钟中断抢占 立即抢占 3.4.3 常用的几种实时调度实例 1、最早截止时间优先即EDF算法 采用最早开始截止时间优先的调度策 略，可用于抢占式或非抢占式。 2 4 3 1 开始截止时间 执行任务 任务到达 1 3 4 2 1 2 3 4 2、最低松弛度优先即LLF算法 该算法根据任务紧急(或松弛)的程度确 定优先级。 松弛度=必须完成时间-运行时间-当前时间 松弛度越小越优先。 例：有两个周期性实时任务A和B,A每 20ms执行一次，运行时间10ms，B每 50ms运行一次，运行时间25ms.采用最低 松弛度优先的抢占调度。 A1 A2 A3 A4 A5 A6 A1 A7 A8 B1 B2 B3 0 20 40 60 80 100 120 140 160 A1(10) A2(10) A3(10) A4(10) B1(20) B1(5) B2(15) B2(10) 0 10 20 30 40 50 60 70 80 在10ms时还未进入A2的周期，计算了A2的 松弛度，同样在55ms时还未进入A4的周 期，而未计算A4的松弛度，前后不一致。 0 A1:20-10-0=10 B1:50-25-0=25 选A1 10 选B1 20 A2:40-10-20=10 B1:50-15-20=15 选A2 30 选B1 40 A3:60-10-40=10 B1:50-5-40=5 选B1 45 选A3 50 A3:60-5-50=5 B2:100-25-50=25 选A3 55 选B2 60 A4:80-10-60=10 B2:100-20-60=20选A4 70 选B2 80 A5:100-10-80=10 B2:100-10-80=10选B2 90 选A5 100 A1(10) A2(10) A3(10) A4(10) B1(10) B1(15) B2(5) B2(20) 0 10 20 30 40 50 60 70 80 90 A5(10) 3.5 产生死锁的原因和必要条件 3.5.1 产生死锁的原因 进程竞争资源和进程推进顺序非法。