888达人
官网
Portraits
Journal
Contact
linux内核实现了control group功能(cgroup,since linux 2.6.24),可以支持将进程分组,然后按组来划分各种资源。比如:group-1拥有30%的CPU和50%的磁盘IO、group-2拥有10%的CPU和20%的磁盘IO、等等。具体参阅cgroup相关文章。
cgroup支持很多种资源的划分,CPU资源就是其中之一,这就引出了组调度。
linux内核中,传统的调度程序是基于进程来调度的(参阅《linux进程调度浅析》)。假设用户A和B共用一台机器,这台机器主要用来编译程序。我们可能希望A和B能公平的分享CPU资源,但是如果用户A使用make -j8(8个线程并行make)、而用户B直接使用make的话(假设他们的make程序都使用了默认的优先级),A用户的make程序将产生8倍于B用户的进程数,从而占用(大致)8倍于B用户的CPU。因为调度程序是基于进程的,A用户的进程越多,被调度的机率就越大,就越具有对CPU的竞争力。
如何保证A、B用户公平分享CPU呢?组调度就能做到这一点。把属于用户A和B的进程各分为一组,调度程序将先从两个组中选择一个组,再从选中的组中选择一个进程来执行。如果两个组被选中的机率相当,那么用户A和B将各占有约50%的CPU。
相关数据结构
在linux内核中,使用task_group结构来管理组调度的组。所有存在的task_group组成一个树型结构(与cgroup的目录结构相对应)。
一个task_group可以包含具有任意调度类别的进程(具体来说是实时进程和普通进程两种类别),于是task_group需要为每一种调度策略提供一组调度结构。这里所说的一组调度结构主要包括两个部分,调度实体和运行队列(两者都是每CPU一份的)。调度实体会被添加到运行队列中,对于一个task_group,它的调度实体会被添加到其父task_group的运行队列。
为什么要有调度实体这样的东西呢?因为被调度的对象有task_group和task两种,所以需要一个抽象的结构来代表它们。如果调度实体代表task_group,则它的my_q字段指向这个调度组对应的运行队列;否则my_q字段为NULL,调度实体代表task。在调度实体中与my_q相对的是X_rq(具体是针对普通进程的cfs_rq和针对实时进程的rt_rq),前者指向这个组自己的运行队列,里面会放入它的子节点;后者指向这个组的父节点的运行队列,也就是这个调度实体应该被放入的运行队列。
于是,调度实体和运行队列又组成了另一个树型结构,它的每一个非叶子节点都跟task_group的树型结构是相对应的,而叶子节点都对应到具体的task。就像非TASK_RUNNING状态的进程不会被放入运行队列一样,如果一个组中不存在TASK_RUNNING状态的进程,则这个组(对应的调度实体)也不会被放入它的上一级运行队列。明确一点,只要调度组创建了,其对应的task_group就肯定存在于由task_group组成的树型结构中;而其对应的调度实体是否存在于由运行队列和调度实体组成的树型结构中,要取决于这个组中是否存在TASK_RUNNING状态的进程。
作为根节点的task_group是没有调度实体的,调度程序总是从它的运行队列出发,来选择下一个调度实体(根节点必定是第一个被选中的,没有其他候选者,所以根节点不需要调度实体)。根节点task_group所对应的运行队列被包装在一个rq结构中,里面除了包含具体的运行队列以外,还有一些全局统计信息等字段。
调度发生的时候,调度程序从根task_group的运行队列中选择一个调度实体。如果这个调度实体代表一个task_group,则调度程序需要从这个组对应的运行队列继续选择一个调度实体。如此递归下去,直到选中一个进程。除非根task_group的运行队列为空,否则递归下去一定能找到一个进程。因为如果一个task_group对应的运行队列为空,它对应的调度实体就不会被添加到其父节点对应的运行队列中。
最后,对于一个task_group来说,它的调度实体和运行队列都是每CPU一份的,一个(task_group对应的)调度实体只会被加入到相同CPU所对应的运行队列。而对于task来说,它的调度实体则只有一份(没有按CPU划分),调度程序的负载均衡功能可能会将(task对应的)调度实体从不同CPU所对应的运行队列移来移去。(参见《linux内核SMP负载均衡浅析》)
组的调度策略
组调度的主要数据结构已经理清了,这里还有一个很重要的问题。我们知道task拥有其对应的优先级(静态优先级 or 动态优先级),调度程序根据优先级来选择运行队列中的进程。那么,既然task_group和task一样,都被抽象成调度实体,接受同样的调度,task_group的优先级又该如何定义呢?这个问题需要具体到调度类别来解答(不同的调度类别,其优先级定义方式不一样),具体来说就是rt(实时调度)和cfs(完全公平调度)两种类别。
实时进程的组调度
从《linux进程调度浅析》一文可以看到,实时进程是对CPU有着实时性要求的进程,它的优先级是跟具体任务相关的,完全由用户来定义的。调度器总是会选择优先级最高的实时进程来运行。
发展到组调度,组的优先级就被定义为“组内最高优先级的进程所拥有的优先级”。比如组内有三个优先级分别为10、20、30的进程,则组的优先级就是10(数值越小优先级越大)。
组的优先级如此定义,引出了一个有趣的现象。当task入队或者出队时,要把它的所有祖先节点都先出队,然后再重新由底向上依次入队。因为组节点的优先级是依赖于它的子节点的,task的入队和出队将影响它的每一个祖先节点。
官网
Portraits
Journal
Contact