Linux CFS调度器之队列操作--Linux进程的管理与调度(二十七） - 云+社区 - 腾讯云
4.1多任务多任务处理器上，能让多个进程处于阻塞或者睡眠状态，实际上不被调度，直到被唤醒
多任务操作系统分为抢占和非抢占两种多任务方式，linux是公平调度。
非抢占模式除非进程主动让出(yeild)否则会一直被执行，不会让出，但是绝大多操作系统是抢占式的。
4.2 linux进程的调度时间片调度，通过alrm 闹钟信号
void schedule(void)
{
int i,next,c;
struct task_struct ** p;
// 首先处理alarm信号，唤醒所有收到信号的可中断睡眠进程
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) {
// 如果进程设置了alarm，并且alarm已经到时间了
if ((*p)->alarm && (*p)->alarm < jiffies) {
// 向该进程发送SIGALRM信号
(*p)->signal |= (1<
(*p)->alarm = 0;// 清除alarm
}
//可屏蔽信号位图BLOCKABLE定义在sched.c第24行，(~(_S(SIGKILL) | _S(SIGSTOP)))
// 说明SIGKILL和SIGSTOP是不能被屏蔽的。
// 可屏蔽信号位图 & 当前进程屏蔽的信号位图 = 当前进程实际屏蔽的信号位图
// 当前进程收到的信号位图 & ~当前进程实际屏蔽的信号位图
//= 当前进程收到的允许相应的信号位图
// 如果当前进程收到允许相应的信号，并且当前进程处于可中断睡眠态
// 则把状态改成运行态，参与下面的选择过程
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}
// 下面是进程调度的主要部分
while (1) {undefined
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {// 遍历整个task[]数组
if (!*--p)// 跳过task[]中的空项
continue;
// 寻找剩余时间片最长的可运行进程，
// c记录目前找到的最长时间片
// next记录目前最长时间片进程的任务号
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
// 如果有进程时间片没有用完c一定大于0。这时退出循环，执行 switch_to任务切换
if (c) break;
// 到这里说明所有可运行进程的时间片都用完了，则利用任务优先级重新分配时间片。
// 这里需要重新设置所有任务的时间片，而不光是可运行任务的时间片。
// 利用公式：counter = counter/2 + priority
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) +
(*p)->priority;
// 整个设置时间片过程结束后，重新进入进程选择过程
}
// 当的上面的循环退出时，说明找到了可以切换的任务
switch_to(next);
}
注意到，当系统中现在没有可以投入运行的进程，但是存在就绪态，不过其时间片为0，此时，就需要重新为进程分配时间片。
linux 采用的是cfs，公平调度，允许进程运行一段时间，循环旋转。先择运行最少的进程优先运行
4.5 linux调度的实现四个重要组成部分：
时间记账、进程选择、调度器入口、睡眠和唤醒。
CFS使用调度器实体结构，来追踪进程运行记账
struct sched_entity {
struct load_weight load;
struct rb_node run_node;
struct list_head group_node;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
int depth;
struct sched_entity *parent;
struct cfs_rq *cfs_rq;
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
struct sched_avg avg ____cacheline_aligned_in_smp;
#endif
};
调度器实体作为一个名字是se的成员变量，嵌入在进程描述符task_struct里面。
2.虚拟实时update_curr实现了记账功能
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
schedstat_set(curr->statistics.exec_max, max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;// (1) 累计当前进程的实际运行时间
// 更新cfs_rq的实际执行时间cfs_rq->exec_clock
schedstat_add(cfs_rq, exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);// (2) 累计当前进程的vruntime
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
// 更新task所在cgroup之cpuacct的某个cpu运行时间ca->cpuusage[cpu]->cpuusage
cpuacct_charge(curtask, delta_exec);
// 统计task所在线程组(thread group)的运行时间：
// tsk->signal->cputimer.cputime_atomic.sum_exec_runtime
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
_update_curr()完成后，exec_start被设置为rq的时间
pdate_curr()函数只负责计算delta_exec以及更新exec_start。其它工作由__update_curr()函数完成：
1、更新当前进程的实际运行时间（抽象模型中的runtime）。
2、更新当前进程的虚拟时间vruntime。
3、更新cfs_rq->min_vruntime。
在当前进程和下一个将要被调度的进程中选择vruntime较小的值。然后用该值和cfs_rq->min_vruntime比较，如果比min_vruntime大，则更新cfs_rq为的min_vruntime为所求出的值。
红黑树上存储了所有可以运行的进程
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq);
struct sched_entity *se;
if (!left || (curr && entity_before(curr, left)))
{
left = curr;
}
se = left;
if (cfs_rq->skip == se)
{
struct sched_entity *second;
if (se == curr)
{
second = __pick_first_entity(cfs_rq);
}
else
{
second = __pick_next_entity(se);
if (!second || (curr && entity_before(curr, second)))
second = curr;
}
if (second && wakeup_preempt_entity(second, left) < 1)
se = second;
}
if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
se = cfs_rq->last;
if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
se = cfs_rq->next;
clear_buddies(cfs_rq, se);
return se;
}
向树中加入进程
enqueue_entity完成了进程真正的入队操作, 其具体流程如下所示
- 更新一些统计统计量, update_curr, update_cfs_shares等
- 如果进程此前是在睡眠状态, 则调用place_entity中首先会调整进程的虚拟运行时间
- 最后如果进程最近在运行, 其虚拟运行时间仍然有效, 那么则直接用__enqueue_entity加入到红黑树
首先如果进程最近正在运行, 其虚拟时间时间仍然有效, 那么(除非它当前在执行中)它可以直接用__enqueue_entity插入到红黑树, 该函数徐娅萍处理一些红黑树的机制, 这可以依靠内核的标准实现, 参见__enqueue_entity函数,
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
se->vruntime += cfs_rq->min_vruntime;
update_curr(cfs_rq);
enqueue_entity_load_avg(cfs_rq, se);
account_entity_enqueue(cfs_rq, se);
update_cfs_shares(cfs_rq);
if (flags & ENQUEUE_WAKEUP)
{
place_entity(cfs_rq, se, 0);
if (schedstat_enabled())
enqueue_sleeper(cfs_rq, se);
}
check_schedstat_required();
if (schedstat_enabled()) {
update_stats_enqueue(cfs_rq, se);
check_spread(cfs_rq, se);
}
if (se != cfs_rq->curr)
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
if (cfs_rq->nr_running == 1) {
list_add_leaf_cfs_rq(cfs_rq);
check_enqueue_throttle(cfs_rq);
}
}
从红黑树中删除，进程变为了挂起等待的进程
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
update_curr(cfs_rq);
dequeue_entity_load_avg(cfs_rq, se);
if (schedstat_enabled())
update_stats_dequeue(cfs_rq, se, flags);
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= cfs_rq->min_vruntime;
return_cfs_rq_runtime(cfs_rq);
update_min_vruntime(cfs_rq);
update_cfs_shares(cfs_rq);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
if (cfs_rq->rb_leftmost == &se->run_node) {
struct rb_node *next_node;
next_node = rb_next(&se->run_node);
cfs_rq->rb_leftmost = next_node;
}
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}
4.5.3 调度器入口
调度器的核心函数是schedule，调用pick_next_task选择下一个要被调度的进程
schedule->__schedule->pick_next_task
static inline struct task_struct *
pick_next_task(struct rq *rq， struct task_struct *prev， struct rq_flags *rf)
{
const struct sched_class *class;
struct task_struct *p;
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) { ........1
p = fair_sched_class.pick_next_task(rq， prev， rf); .....2
if (unlikely(p == RETRY_TASK))
goto again;
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq， prev， rf);
return p;
}
again:
for_each_class(class) { ...........................3
p = class->pick_next_task(rq， prev， rf);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}
}
4.5.4 函数唤醒和休眠
只记几个核心
//定义一个等待队列
DEFINE_WAIT
//加入等待队列
add_wait_queue
while (!concition) {
//设置当前进程可被唤醒状态
prepare_to_Wait
//调度
schedule()
}
//移除等待队列
finish_wait
唤醒使用wakeup系列就可以
4.6 上下文切换和 抢占上下文切换核心是context_switch
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next, struct rq_flags *rf)
{
prepare_task_switch(rq, prev, next);
arch_start_context_switch(prev);
if (!next->mm) { // to kernel
enter_lazy_tlb(prev->active_mm, next);
next->active_mm = prev->active_mm;
if (prev->mm) // from user
mmgrab(prev->active_mm);
else
prev->active_mm = NULL;
} else { // to user
membarrier_switch_mm(rq, prev->active_mm, next->mm);
switch_mm_irqs_off(prev->active_mm, next->mm, next);
if (!prev->mm) { // from kernel
rq->prev_mm = prev->active_mm;
prev->active_mm = NULL;
}
}
rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);
prepare_lock_switch(rq, next, rf);
switch_to(prev, next, prev);
barrier();
return finish_task_switch(prev);
}
上下文切换分为
根据引发context switch的原因，又分为两种情况——CSWCH（自愿上下文切换）和NVCSWCH（非自愿上下文切换），查看man pidstat中：
- 症状：上下文切换过多，会导致sys系统态CPU增加，换句话说CPU资源都被内核用了
- 如果是CSWCH过多，那要定位是什么资源短缺导致频繁context switch影响系统性能
- 如果是NVCSWCH过多，那要看是哪里导致那么多R态进程等待调度运行
switch_ mm负责把虚拟内存从旧进程切换到新进程，switch_to负责切换处理器状态
