简岩
摘要:一个操作系统的核心是进程调度。那么操作系统最重要的程序之一则是进程调度程序,同时进程调度程序也是多任务操作系统执行频度最高的一部分,操作系统的整体性能也决定于进程调度程序的性能。本文剖析了从O(1)算法到CFS算法的演变。最后用测试工具对CFS的稳定性和计算速度进行了分析。
关键词:Linux调度O(1)CFS调度器红黑树
1 linux进程调度的概述
所谓进程调度就是指操作系统正确的匹配CPU时间之后来准确的执行等待中的进程。怎样从若干个可运行的进程里面找到其中最优先的进程执行的同时又能保证响应时间短、吞吐量高是进程调度的核心所在。进程调度有何时启动调度器和调度器执行什么调度算法两部分。
进程调度的要求就是吞吐量大、响应时间快、周转时间短以及效率高。由进程的响应时间Linux内核可以把进程分为三类:实时进程、批处理进程和交互进程。根据这三类进程内核又产生了三种不同的调度方法:先进先出策略(SCHED_FIFD)、轮转策略(SCHED_RR)和适合交互分时的程序(SCHED_OTHER)。
2 进程调度算法
①当CPU运行进程时,调度是被禁止的;只有当CPU处于无进程运行时,可以进入调度。
②当准备队列空闲时,执行缺省的idle-task、进程。
③当准备队列非空闲时,执行的进程需要调度器在准备队列中挑选出来。这时,goodness()函数将会从调度器在准备队列中挑选出来的进程中计算其权值,只有权值最大才能有执行的优先级。
④如果经过goodness()函数计算之后每个进程的权值均是0,则说明CPU所提供给实时进程的准备队列中进程的时间片全部用光了,需要进行重置之后返回步骤①,继续执行调度。……