一个run_queue(可执行队列)。如果一个进程处于TASK_RUNNING状态(可执行状态),则它会被加入到其中一个run_queue(且同一时刻仅会被加入到一个run_queue),以便让调度程序安排它在这个run_queue对应的CPU上面运行。一个CPU对应一个run_queue这样的设计,其好处是:
1、一个持续处于TASK_RUNNING状态的进程总是趋于在同一个CPU上面运行(其间,这个进程可能被抢占、然后又被调度),这有利于进程的数据被CPU所缓存,提高运行效率;
2、各个CPU上的调度程序只访问自己的run_queue,避免了竞争;
然而,这样的设计也可能使得各个run_queue里面的进程不均衡,造成“一些CPU闲着、一些CPU忙不过来”混乱局面。为了解决这个问题,load_balance(负载均衡)就登场了。
load_balance所需要做的事情就是,在一定的时机,通过将进程从一个run_queue迁移到另一个run_queue,来保持CPU之间的负载均衡。
这里的“均衡”二字如何定义?load_balance又具体要做哪些事情呢?对于不同调度策略(实时进程 OR 普通进程),有着不同的逻辑,需要分开来看。
实时进程的负载均衡
实时进程的调度是严格按照优先级来进行的。在单CPU环境下,CPU上运行着的总是优先级最高的进程,直到这个进程离开TASK_RUNNING状态,新任的“优先级最高的进程”才开始得到运行。直到所有实时进程都离开TASK_RUNNING状态,其他普通进程才有机会得到运行。(暂时忽略sched_rt_runtime_us和sched_rt_period_us的影响,见《linux组调度浅析》。)
推广到SMP环境,假设有N个CPU,N个CPU上分别运行着的也必须是优先级最高的top-N个进程。如果实时进程不足N个,那么剩下的CPU才分给普通进程去使用。对于实时进程来说,这就是所谓的“均衡”。
实时进程的优先级关系是很严格的,当优先级最高的top-N个进程发生变化时,内核必须马上响应:
1、如果这top-N个进程当中,有一个离开TASK_RUNNING状态、或因为优先级被调低而退出top-N集团,则原先处于(N+1)位的那个进程将进入top-N。内核需要遍历所有的run_queue,把这个新任的top-N进程找出来,然后立马让它开始运行;
2、反之,如果一个top-N之外的实时进程的优先级被调高,以至于挤占了原先处于第N位的进程,则内核需要遍历所有的run_queue,把这个被挤出top-N的进程找出来,将它正在占用的CPU让给新进top-N的那个进程去运行;
在这几种情况下,新进入top-N的进程和退出top-N的进程可能原本并不在同一个CPU上,那么在它得到运行之前,内核会先将其迁移到退出top-N的进程所在的CPU上。
具体来说,内核通过pull_rt_task和push_rt_task两个函数来完成实时进程的迁移:
pull_rt_task – 把其他CPU的run_queue中的实时进程pull过来,放到当前CPU的run_queue中。被pull过来的实时进程要满足以下条件:
1、进程是其所在的run_queue中优先级第二高的(优先级最高的进程必定正在运行,不需要移动);
2、进程的优先级比当前run_queue中最高优先级的进程还要高;
1、一个持续处于TASK_RUNNING状态的进程总是趋于在同一个CPU上面运行(其间,这个进程可能被抢占、然后又被调度),这有利于进程的数据被CPU所缓存,提高运行效率;
2、各个CPU上的调度程序只访问自己的run_queue,避免了竞争;
然而,这样的设计也可能使得各个run_queue里面的进程不均衡,造成“一些CPU闲着、一些CPU忙不过来”混乱局面。为了解决这个问题,load_balance(负载均衡)就登场了。
load_balance所需要做的事情就是,在一定的时机,通过将进程从一个run_queue迁移到另一个run_queue,来保持CPU之间的负载均衡。
这里的“均衡”二字如何定义?load_balance又具体要做哪些事情呢?对于不同调度策略(实时进程 OR 普通进程),有着不同的逻辑,需要分开来看。
实时进程的负载均衡
实时进程的调度是严格按照优先级来进行的。在单CPU环境下,CPU上运行着的总是优先级最高的进程,直到这个进程离开TASK_RUNNING状态,新任的“优先级最高的进程”才开始得到运行。直到所有实时进程都离开TASK_RUNNING状态,其他普通进程才有机会得到运行。(暂时忽略sched_rt_runtime_us和sched_rt_period_us的影响,见《linux组调度浅析》。)
推广到SMP环境,假设有N个CPU,N个CPU上分别运行着的也必须是优先级最高的top-N个进程。如果实时进程不足N个,那么剩下的CPU才分给普通进程去使用。对于实时进程来说,这就是所谓的“均衡”。
实时进程的优先级关系是很严格的,当优先级最高的top-N个进程发生变化时,内核必须马上响应:
1、如果这top-N个进程当中,有一个离开TASK_RUNNING状态、或因为优先级被调低而退出top-N集团,则原先处于(N+1)位的那个进程将进入top-N。内核需要遍历所有的run_queue,把这个新任的top-N进程找出来,然后立马让它开始运行;
2、反之,如果一个top-N之外的实时进程的优先级被调高,以至于挤占了原先处于第N位的进程,则内核需要遍历所有的run_queue,把这个被挤出top-N的进程找出来,将它正在占用的CPU让给新进top-N的那个进程去运行;
在这几种情况下,新进入top-N的进程和退出top-N的进程可能原本并不在同一个CPU上,那么在它得到运行之前,内核会先将其迁移到退出top-N的进程所在的CPU上。
具体来说,内核通过pull_rt_task和push_rt_task两个函数来完成实时进程的迁移:
pull_rt_task – 把其他CPU的run_queue中的实时进程pull过来,放到当前CPU的run_queue中。被pull过来的实时进程要满足以下条件:
1、进程是其所在的run_queue中优先级第二高的(优先级最高的进程必定正在运行,不需要移动);
2、进程的优先级比当前run_queue中最高优先级的进程还要高;