彻底理解Linux 进程调度所有知识点( 二 ) _Linux

struct cfs_rq { ... struct rb_root_cached tasks_timeline ...};

sched_entity：可被内核调度的实体。每个就绪态的调度实体sched_entity包含插入红黑树中使用的节点rb_node ，同时vruntime成员记录已经运行的虚拟时间。

struct sched_entity {  ...  struct rb_node    run_node;        ...  u64          vruntime;                ...};

这些数据结构的关系如下图所示：

文章插图

调度时刻调度的本质就是选择下一个进程，然后切换。在执行调度之前需要设置调度标记 TIF_NEED_RESCHED ，然后在调度的时候会判断当前进程有没有被设置 TIF_NEED_RESCHED ，如果设置则调用函数 schedule 来进行调度。
1. 设置调度标记为 CPU 上正在运行的进程 thread_info 结构体里的 flags 成员设置 TIF_NEED_RESCHED 。
那么，什么时候设置TIF_NEED_RESCHED呢？

scheduler_tick 时钟中断

文章插图

wake_up_process 唤醒进程的时候

文章插图

do_fork 创建新进程的时候

文章插图

set_user_nice 修改进程nice值的时候

文章插图

smp_send_reschedule 负载均衡的时候

【文章福利】需要C/C++ linux服务器架构师学习资料加群812855908（资料包括C/C++ ， Linux ， golang技术，内核， Nginx ， ZeroMQ ， MySQL ， redis ， fastdfs ， MongoDB ， ZK ，流媒体， CDN ， P2P ， K8S ， Docker ， TCP/IP ，协程， DPDK ， ffmpeg等）

文章插图

2. 执行调度Kernel 判断当前进程标记是否为 TIF_NEED_RESCHED ，是的话调用 schedule 函数，执行调度，切换上下文，这也是上面抢占(preempt)机制的本质。那么在哪些情况下会执行 schedule 呢？

用户态抢占

ret_to_user 是异常触发，系统调用，中断处理完成后都会调用的函数。

文章插图

内核态抢占

文章插图

可以看出无论是用户态抢占，还是内核态抢占，最终都会调用 schedule 函数来执行真正的调度：

文章插图

还记得调度的本质吗？调度的本质就是选择下一个进程，然后切换。如上图所示，用函数 pick_next_task 选择下一个进程，其本质就是调度算法的实现；用函数 context_switch 完成进程的切换，即进程上下文的切换。下面我们分别看下这两个核心功能。
调度算法字段版本O(n) 调度器linux0.11 - 2.4O(1) 调度器linux2.6CFS调度器linux2.6至今
O(n)O(n) 调度器是在内核2.4以及更早期版本采用的算法， O(n) 代表的是寻找一个合适的任务的时间复杂度。调度器定义了一个 runqueue 的运行队列，将进程的状态变为 Running 的都会添加到此运行队列中，但是不管是实时进程，还是普通进程都会添加到这个运行队列中。当需要从运行队列中选择一个合适的任务时，就需要从队列的头遍历到尾部，这个时间复杂度是O(n) ，运行队列中的任务数目越大，调度器的效率就越低。