Question

随笔之Android平台上的进程调度探讨

一由来

最近在翻阅MediaProvider的时候，突然想起之前碰到的一个问题，该问题是这样的：

• 一个Pad上有很多媒体文件，然后每次开机后的一段时间内，Home Screen的反应都特别慢，有时候还会报出ANR的错误。从ANR文件/data/anr/traces.txt分析，发现系统打印的cpu占有率中，android.process.media占用非常高。所以怀疑是MediaProvider做文件扫描占用CPU太多资源导致。
• 但是我们实际测试的时候，通过top –m 5查看cpu占有率的时候，发现只要一操作Home，android.process.media进程cpu占有率就会下降很多。

当时看到这个现象，直观感觉就是MediaProvider抢占CPU能力不够。直接把该现象告诉领导，这个事情也就结了。但是一直没在代码中找到依据：总有地方设置进程的优先级吧？？

后来，时间充裕了，想起这个问题。果不其然，在MediaScannerService中，找到答案：

public void run()
{
Process.setThreadPriority(Process.THREAD_PRIORITY_BACKGROUND +
                Process.THREAD_PRIORITY_LESS_FAVORABLE);
     ……
}

上面代码显示得将本进程的优先级设置为BACKGROUND+LESS_FAVORABLE。

那么这个优先级是什么呢？

本随笔将关注两个问题：

• Android平台提供的调度接口及其它的实现
• 调度一定是依靠Linux OS的，那么本随笔也会顺便介绍一下Linux OS中的进程调度相关的知识。

二 Android平台中的进程调度接口

从最上的Java层看，Anroid提供的Process类封装了进程调度优先级，调度策略等一些API。下图是整体调用流程和相关文件位置。

 

 

图1 进程调度的API以及调用分发流程

从上图我们可知：

• 重点讨论Process.java提供的setThreadPriority和setThreadGroup函数。
• 调用分发顺序从Java一直贯穿JNI,Native层后，setThreadPriority直接转移到setpriority系统调用，而setThreadGroup通过set_sched_policy处理后，再转移给sched_setscheduler系统调用。

 

2.1 设置调度优先级

进程调度的优先级，这个应该不难理解。简单地说：

l         OS在调度进程的时候是遵循一定规则的，优先级高的进程分配CPU的时间多，而优先级低的进程相对分配的CPU时间少。（这个仅是理论上的，具体如何分配是和OS相关的）

下面我们看看androidSetThreadPriority的实现。

int androidSetThreadPriority(pid_t tid, int pri)
{
#if defined(HAVE_PTHREADS)  //目前仅支持POSIX
//phtread_once保证这个线程创建时会首先执行一次（仅此一次，类似Class的constructor）
//checkDoSchedulingGroup函数，该函数判断系统是否设置了”debug.sys.noschedgroups”
    pthread_once(&gDoSchedulingGroupOnce, checkDoSchedulingGroup);
    if (gDoSchedulingGroup) {
        if (pri >= ANDROID_PRIORITY_BACKGROUND) {
            //设置调度策略。这个我们待会会碰到。
            rc = set_sched_policy(tid, SP_BACKGROUND);
        } else if (getpriority(PRIO_PROCESS, tid) >= ANDROID_PRIORITY_BACKGROUND) {
            rc = set_sched_policy(tid, SP_FOREGROUND);
        }
    }
  ……
   //设置调度优先级。
   if (setpriority(PRIO_PROCESS, tid, pri) < 0) {
        rc = INVALID_OPERATION;
} 
……
}

从上面代码发现，Android直接调用了系统API setpriority，其中有三个参数，其原型是：

int setpriority(int which, int who, int prio);

• 第一个参数which可选值为PRIO_PROGRESS,表示设置进程；PRIO_PGROUP表示设置进程组；PRIO_USER表示user。
• 第二个参数who，根据第一个参数的不同，分别指向进程ID；进程组ID和user id。
• 第三个参数学名叫nice值，从-20到19。是优先级的表示，越大表明越nicer，优先级越低。

看来，设置进程调度优先级还是很简单的嘛！

2.2 设置调度策略

Linux的进程调度除了简单的设置nice值外，还可以设置调度策略。这个问题我们放到最后讨论。先来看看上层API。

int androidSetThreadSchedulingGroup(pid_t tid, int grp)
{
……
#if defined(HAVE_PTHREADS)
    ……
  if (set_sched_policy(tid, (grp == ANDROID_TGROUP_BG_NONINTERACT) ?
                                          SP_BACKGROUND : SP_FOREGROUND)) {
#endif
}
int set_sched_policy(int tid, SchedPolicy policy)
{
    pthread_once(&the_once, __initialize);//先运行__initialize函数
#if POLICY_DEBUG
   ……
#endif
    //看看系统是否支持调度策略
    if (__sys_supports_schedgroups) {
        if (add_tid_to_cgroup(tid, policy)) {
            ……
        }
    } else {
        struct sched_param param; //调度参数，类型为sched_param
        param.sched_priority = 0;
        sched_setscheduler(tid,//如果系统不支持的话，直接调用OS的调度策略设置API
                           (policy == SP_BACKGROUND) ?
                            SCHED_BATCH : SCHED_NORMAL,
                           ¶m);
    }
}

initialize这个函数很关键，这里的__sys_supports_schedgroups用来检查android系统，而不是OS。

static void __initialize(void) {
char* filename;
//如果android手机上有/dev/cpuctl/tasks文件，则__sys_supports_schedgroups为1
//目前我的索爱手机并没有该文件。
    if (!access("/dev/cpuctl/tasks", F_OK)) {
        __sys_supports_schedgroups = 1;
        filename = "/dev/cpuctl/tasks";
        normal_cgroup_fd = open(filename, O_WRONLY);
        ……
        filename = "/dev/cpuctl/bg_non_interactive/tasks";
        bg_cgroup_fd = open(filename, O_WRONLY);
        ……
    } else {
        __sys_supports_schedgroups = 0;
    }
}

目前还没有找到解释/dev/cpuctl/tasks这个特殊文件的地方。有明白的网友请不吝赐教.

下面我们看看linux提供的设置调度策略的函数，其原型是：

int sched_setscheduler(pid_t pid, int policy,const struct sched_param *param);

• 第一个参数为进程id。
• 第二个参数为调度策略，目前android支持SCHED_OTHER,标准round-robin分时共享策略(也就是默认的策略)；SCHED_BATCH,针对具有batch风格（批处理）进程的调度策略；SCHED_IDLE，针对优先级非常低的适合在后台运行的进程。另外，linux还支持实时（Real-time）调度策略（SCHED_FIFO,先入先出调度策略，SCHED_RR，round-robin调度策略，也就是循环调度。）。
• param参数中最重要的是该结构体中的sched_priority变量。针对上面三种非实时调度策略，该值必须为零。

2.3 小结

从前面可以看出，Android上进程调度还是依赖OS提供的调度机制。当然上层API还是比较简单易懂的，但是Linux OS调度到底是怎么样的呢？不妨探讨一下。

三 Linux OS进程调度机制探讨

这里将探讨一下Linux OS的进程调度实现的原理，具体代码就不深挖了。

先来说说一些基础知识：

3.1 进程调度相关基础知识

• 在一个系统中，经常运行着多个进程，和CPU个数相比，当然是进程数远远大于CPU个数咯，那么就存在为进程分配CPU资源的问题。一般而言，有两种分配方式，一个是由进程间协调，例如一个比较友好的进程在一定的时刻主动让出CPU，这样其他进程就有机会使用CPU。但是这种类似道德上的约束往往行不通，因为总会有“恶意“进程存在嘛！另外一个比较难以克服的问题是友好的标准没法统一，例如什么时候该友好一下？除了这种不靠谱的道德约束外，大师们又引进了抢占式分配，这种分配方式类似法律约束。每个进程会分配一定的CPU资源，OS也会定时（处理时钟中断）+定点（比如系统调用返回到userspace前，）检查进程的CPU资源使用情况。一旦某个进程CPU资源消耗完毕，则会毫不留情地挑选下一个进程运行。
• 在操作系统理论中，CPU资源一般用时间片（time slice）来表示。直观意义就是分配给一个进程可以运行在CPU上的时间。也就是CPU资源是用时间单位来衡量的。

当然，进程调度是一套复杂的算法，图2展示了Linux上进程调度算法的演化历史。

               

图2 Linux进程调度算法演化史

• 从使用CPU的方式来看，进程大体可分为I/O-bound和CPU-bound。二者有什么不同呢？I/O-bound类型的进程大部分时间都处于等待I/O的状态，当然这种I/O是广义的，例如等待用户按键事件，等待磁盘读写完成。而CPU-bound对于那种需要大量计算的进程，例如一个软件编解码算法，最极端的就是一个while死循环。从用户体验来说，I/O-B这种进程大部分都是需要人机交互的。OS设计进程调度算法时，一般偏向于IO-B进程，这样至少用户用起来不会感觉不爽。

 

3.2 Linux进程调度研讨

1. 调度算法

我们先介绍下和进程调度息息相关的进程优先级相关的知识。

• 最直观的想法就是给每个进程设置一个调度优先级，然后按照round-robin方式每次挑选一个优先级最高的进程运行。

那么，在Linux中，这个调度优先级是通过nice值来反映的，从-20到19。值越大表示该进程越nice，这个nice是对其他进程的nice，所以优先级越低。

再解决优先级的概念后，我们再来看第二个基本问题：CPU资源：time-slice是什么？以及它如何与优先级结合起来？

• 最先想到的就是time-slice应该是一个时间单位，例如20ms。然后每种调度优先级的time-slice和该级别有某种计算关系，例如线性。假设0级对应的时间片是20ms，那么1级的就是15ms。
•  默认时间片（对应0度优先级）该取多大呢？太大的话（例如2秒）则会导致漫长（从CPU速度来看）的用户等待，例如每个进程都需要运行2秒才会让出CPU，这样的系统运行起来给人一顿一顿的感觉。而太小的话（例如1ms）则会导致CPU把大量时间浪费在进程上下文切换。前辈们经过长期的实际使用，一般系统设置的默认时间片在20ms或者10ms。

这种以时间（一般为ms）作为时间片单位，并且将时间片与优先级直接映射的方式有什么缺点呢？

我们考虑二个例子：

• 假设0级对应100ms的时间片，那么20级对应的时间片为5ms。现在系统上就一个0级进程和一个20级进程在运行。在105ms内，0级进程将运行100ms（占20/21），而20级进程将运行5ms（占1/21）。好。假设现在仅有2个20级进程，同样在105ms内，却要每5ms切换一下进程（因为20级进程每次只能运行5ms），那么105ms内切换了52次。从这个例子可以看出，简单的时间片映射对优先级低的进程极其不公平。例如在只有两个20级进程的105ms内，按道理应该也只需要切换两次进程即可。但是现在却切了52次。
• 假设0级进程时间片为100ms，每个优先级对应步进为5ms，则1级对应时间片为95ms。如此类推，18级优先级为10ms，19级优先级则为5ms。看出问题了吗？18级优先级进程时间片为19级的2倍！
• 第三个问题就直接剑指时间片了，如果简单地以绝对时间作为时间片的单位，那么算法就得考虑不同机器提供的时间精度了，有些高精度的机器能提供精确到1ms的时间，而有些是10ms。

那么Linux的CFS（Completely Fair Scheduler）算法是怎么做的呢？

CFS基于一种叫perfect multitasking模型来构建调度算法。

• 在一个能提供完美多任务能力的CPU中，每个进程能使用1/n的CPU时间。n是当前进程个数。不考虑调度时间（理论上的，这个时间被称为infinitely small schedule duration time），那么在任何相等时间段内，每次都会运行n个进程。

上面这段话实在不太好理解。我们举个例子：

• 在普通调度模型中，10ms时间内有两个进程，那么每个都将运行5ms。在单个5ms内，每个进程占据100%CPU
• 在PM（perfect multitasking）模型中，10ms内每个进程都运行了10ms，但是每个只用50%的CPU。更难理解了？可以想象CPU飞快地进行线程切换，一下运行进程A，一下运行进程B。在10ms内，似乎每个进程都运行了10ms，但实际上每个进程只占据了50%的CPU。

理解这种PM模型的关键在占据50%CPU这句话上，对于那种普通调度模型中，在一定时间内，进程占据了100%CPU。而在PM模型中，进程占据CPU却是1/n。

好了,CFS具体是实现这个模型的呢？

• 之前每个进程分配的固定时间的算法现在被替代成每个进程运行的时间将是全体进程个数的函数。这个对应为上面模型描述中的1/n。
• nice值不再直接对应时间片。在CFS中，nice值对应一个比重。优先级越高的进程，该比重越大。
•  有了这些参数，每个进程运行的“timeslice“将是它的比重和那个n(表示当前系统内所有处于可执行状态的进程/线程)的函数。

注意，Linux内核中，进程和线程用同一个结构体表示，所以线程也叫轻量级进程。调度的时候是不区分理论上的进程和线程的。

• 尽管CFS尽力避开以时间作为调度单位，但是实现中还是需要时间作为资源使用的考量。那么CFS将这个时间称之为target latency。用来对应PM模型中那个infinitly small schedule duration time。假设该值是20ms，那么2个同优先级进程运行时，每个进程使用10ms，4个同优先级进程的时候每个使用5ms。随着进程数增加，每个进程的时间会趋向于0。那么CFS的实现中，增加了一个minimum granularity，这个时间是最小时间，目前为1ms。

上面这些理论还是有点搞不清楚，下面我们看个例子。

•  一个0级进程和一个5级进程。最后计算出来5级进程的比重将是0级进程的1/3。那么20ms的target latency情况下，0级进程分配15ms，5级进程分配5ms。此时nice值不再直接对应时间值，而仅仅是一个相对CPU时间的比重。所以，假设这两个进程一个是10级，一个是15级，最后计算出来的时间也是15ms和5ms。

PM这个模型还是没说清楚，目前根据《Linux Kernel Development》只能得出上面的结论。

2. 调度策略和调度class

sched_setscheduler函数用来设置进程的调度策略。

在实际的内核代码中，我们发现在选择下一个可运行的进程时，存在这一个for循环：

[->kernel/sched.c]
static inline struct task_struct * pick_next_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;
//调度算法是一个集合，每次使用优先级最高的调度算法。这个算法类在代码中用
//sched_class表示
	class = sched_class_highest; 
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		class = class->next;
	}
}

Linux内核目前使用了两个调度算法类，一个是fair_sched_class，对应于非实时的调度。另外一个是rt_sched_class，对应于实时调度算法。从上面的函数中可知：

• 按照调度算法本身的优先级，获得一个可运行进程。如果该算法没有得到一个进程，则运行下一个调度算法。

按照刚才所说，一共只有两个调度算法，那么我们在sched_setscheduler设置的BATCH/IDLE/NORMAL又有什么用呢？

static void
__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
{
	……
	if (rt_prio(p->prio))
		p->sched_class = &rt_sched_class;
	else //IDLE/BATCH/NORMAL等设置的都是fair_sched_class
		p->sched_class = &fair_sched_class; 
	set_load_weight(p);
}
//set_load_weight就是根据policy(NORMAL/IDLE/BATCH)，得到一个比重
static void set_load_weight(struct task_struct *p)
{
	if (task_has_rt_policy(p)) {
		p->se.load.weight = prio_to_weight[0] * 2;
		p->se.load.inv_weight = prio_to_wmult[0] >> 1;
		return;
	}
	if (p->policy == SCHED_IDLE) {
		p->se.load.weight = WEIGHT_IDLEPRIO;
		p->se.load.inv_weight = WMULT_IDLEPRIO;
		return;
	}
	p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
	p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

根据我们前面所说，再结合上面的代码，sched_setscheduler实际上：

• 设置该进程的调度算法类为fair_sched_class
• 根据policy，设置该进程的weight。（这个weight的作用，以后在介绍kernel sched的时候再来讨论）

四 总结

本随笔从Java层提供的进程调度API开始，介绍了Linux OS上的进程调度相关的知识。对于那些仅需要知道工作原理的人来说，这些知识应该是足够了。

最难理解的还是那个PM模型，希望以后有机会去看看原始的论文。

下面是本随笔的参考文章：

[1] Linux Kernel Development 3^rd Edition,chapter 4

[2] http://en.wikipedia.org/wiki/Completely_Fair_Scheduler