知识卡片

问题卡 · 3613.d.12 · 生成模型:未记录

优先级老化还要维护堆序

理解等级:中级

高优先项持续到达时,低优先项可能长期无法到达堆顶,形成饥饿。优先级老化根据等待时间提高低优先项的等级,试图让久等项获得处理机会;具体提升速率与可达保证还需调度规则和负载条件。

若以堆保存任务,改变某项比较所用的优先值之后,还需更新该项位置或重建相关堆序。本章接口只有insert/extract/peek,并未提供自动随时间变化的更新机制,不能只改字段后继续相信原堆顶正确。

这是原题的调度改进思路,不表示本书已实现公平调度,亦不能在无限高优先到达且资源不足的任意模型下保证所有任务按时完成。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      饿死”。为了解决这个问题,通常系统要采取某种机制来提高任务的等级(随着任务在队列中待的时间变得越来越长)。这样的话,即使在一个充斥着高优先级任务的繁忙系统中,低优先级的任务最终都将获得足够高的优先级,从而排到队列的顶部。操作系统会频繁地使用这种方法来确保低优先级的进程不会完全“停止”。

    参考来源

    - 位置:《算法精解:C语言描述》第10章《问与答》(spine1319;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1286.html;u183-ch10-013)。 - 结论依据:183最后问答完整实读,以前述堆序不变量说明老化后的维护需求,不补造未给出的change-priority API或实时保证。 - 原始内容:饿死”。为了解决这个问题,通常系统要采取某种机制来提高任务的等级(随着任务在队列中待的时间变得越来越长)。这样的话,即使在一个充斥着高优先级任务的繁忙系统中,低优先级的任务最终都将获得足够高的优先级,从而排到队列的顶部。操作系统会频繁地使用这种方法来确保低优先级的进程不会完全“停止”。