CFS调度分析(内核版本:2.6.34)
CFS调度分析(内核版本:2.6.34)
1、时间记账
CFS不再有时间片的概念,他维护的是每个进程运行的时间记账
使用调度器实体结构来追踪进程运行记账:
<linux/sched.h>
无数统计变量… …,但是算法核心就是围绕vruntime设计。
调度器实体,作为进程的一个名为se的成员变量。
2、虚拟实时
CFS使用vruntime变量来记录一个程序到底运行了多长时间以及他要应该运行多久。
<kernel/sched_fair.c> 中,up_date_curr()实现这个功能。
update_curr()由系统定时器周期性调用,使得vruntime可以精准测量给定进程的运行时间。
delta_exec 执行时间,然后根据当前可运行进程总数队运行时间进行加权计算。
__update_curr()
3、进程选择
挑选一个最小的vruntime的进程。——红黑树。
rb_leftmost存储当前最小的vruntime。无需在红黑树上进行查询。
向树中插入进程
在进程变为可运行状态(被唤醒)或者fork()创建进程时,enqueue_entity()实现这个步骤。
先更新当前任务的运行时间和其他统计数据。
然后__enqueue_entity() 进行红黑树插入操作。
从树中删除进程
当进程阻塞,或者终止时:dequeuer_entity
同理先更新实时统计数据,然后在进程红黑树中删除。
4、调度器入口
调度器入口函数schedule(),<kernel/sched.c>
以优先级为序,从高到低,一次查看每一个调度类。其中,pick_next_task(),实现会调用pick_next_entity()。
5、睡眠和唤醒
当不愿意被执行的进程(进行文件I/0操作)进入睡眠状态。
添加睡眠等待队列。
唤醒:
<kernel/sched.c>
wake_up()调用try_to_wake_up()。
6、CFS完全公平调度算法分析
参考于Wikipedia
CFS主要由sched_entity 内含的 vruntime所决定,不再跟踪process的sleep time,并扬弃active/expire的概念, runqueue里面所有的进程都平等对待,CFS使用“虚拟运行时”(virtual running time)来表示某个任务的时间量。
CFS改使用红黑树算法,将执行时间越少的工作(即 sched_entity)排列在红黑树的左边[3],时间复杂度是O(log N),节点(即rb_node)的安插工作则由dequeue_entity()和enqueue_entity()来完成。当前执行的task通过呼叫 put_prev_task 返回红黑树,下一个待执行的task则由pick_next_task来呼叫。蒙内表示, CFS在百分之八十时间都在确实模拟处理器的处理时间。
最新文章
- Android之ListView性能优化——一行代码绑定数据——万能适配器
- Java Web技术之Cookie
- iOS runtime 知识点整理
- 数据注解和验证 &ndash; ASP.NET MVC 4 系列
- Centos6.5 Openvpn的安装与配置
- reactjs入门到实战(一)---- hello world例子
- python3 字符串方法(1-15)
- Delphi控件的显示内容与显示边框是两回事
- DELPHI下的SOCK编程
- Android性能测试——Allocation Tracker(Device Monitor)
- 整合微信小程序的Web API接口层的架构设计
- vmware 上ubuntu server连接外网
- RestTemplate的设置及使用
- 【nginx】中server配置说明
- Java基础实训
- 带着新人学springboot的应用01(springboot+mybatis+缓存 上)
- GiBbook实用配置以及插件
- Python入门学习例子——从Hao123获取图片
- java中增删改查(CRUD)总结
- object标签和embed标签