kernel笔记——进程调度

调度器完成以下任务：

• 时钟中断(或类似的定时器)时间内刷新进程的时间片，设置进程调度标志
• 系统调用返回或中断完成时检查调度标志

schedule函数

内核代码中完成进程调度的函数为schedule()，该函数中包含以下调用：

put_prev_task(rq, prev);
next = pick_next_task(rq);
context_switch(rq, prev, next);

schedule首先将当前执行函数放入运行队列，然后选择下一个要运行的进程(怎么选择下一个进程，这部分就是调度算法的工作)，最后完成进程上下文切换。

 

由A进程进入schedule函数，从函数出来将变成B进程，A进程调用schedule相当于放弃cpu资源，进程从R状态变成S等其他状态都会经过schedule。在vmcore中，我们可以看到S状态进程进入S状态前最后一个调用的函数为schedule：

crash> ps | grep sshd
1300      1   0  ffff81024fba1810 IN 0.0   26088   1380  sshd
crash> bt 1300
PID: 1300   TASK: ffff81024fba1810  CPU: 0   COMMAND: "sshd"
#0 [ffff81026a2e9cd8] schedule at ffffffff802d9025
#1 [ffff81026a2e9da0] schedule_timeout at ffffffff802d9a6b
#2 [ffff81026a2e9df0] do_select at ffffffff801935f2
#3 [ffff81026a2e9ed0] sys_select at ffffffff80193880
#4 [ffff81026a2e9f80] system_call at ffffffff8010ad3e
……

进程可以是“被调度”，而有的进程或线程主动调用schedule，放弃cpu，例如ksoftirqd内核线程。

 

进程优先级

早期的调度算法根据进程优先级计算进程运行的时间片、选择被调度的进程。对于普通进程(normal process)而言，nice表示其优先级，nice的取值范围为-20~19，nice值越大优先级越低；对于实时进程(real time process)而言，优先级的取值范围为0～99，同样值越大优先级越低。

 

内核代码中nice取值范围对应100~139，MAX_RT_PRIO宏定义了实时进程优先级与nice取值的分界点，实时进程的优先级比普通进程优先级高。

通过top、ps等命令我们可以查到进程的优先级，以下为top命令输出的下半部分，进程信息的查询结果：

   PID USER   PR  NI    VIRT  RES  SHR   S  %CPU %MEM      TIME+  COMMAND
     22  root   20    0        0     0      0   R      1.9      0.0  60:23.34  ksoftirqd/9
  8689  root   20    0  273m 67m  11m  S       0.0      0.4   2:04.01  java
11058  root   39   19       0     0      0   S       0.0      0.0   1:45.68  kipmi0
11771  root  -98    0 20388  19m 7256   S       0.0      0.1   0:16.06  had
      3  root   RT    0        0     0      0   S       0.0      0.0   0:00.00  migration/0

其中(PR列值+100)指示进程优先级，以上输出中，java进程优先级为120，为普通进程；had进程优先级为2，为实时进程。RT表示该进程为实时进程，并且优先级为0。

 

可以使用renice命令设置普通进程的优先级：

linux # renice 10 -p 21691
21691: old priority -20, new priority 10

 

调度算法

从最初的遍历O(n)算法，到2.5版kernel的O(1)算法，再到2.6版kernel的CFS(completely fair scheduler)，调度算法被不断地改进。

 

O(1)调度算法使得调度器选择下一个执行进程的时间变为常量，不随可运行进程数量变化，但其有以下缺点：

1. 动态调整进程优先级的算法很复杂，不易于代码维护
2. 不“偏袒”交互型程序，假如响应鼠标移动的进程与某后台进程有同一优先级，在鼠标被移动时，另一进程可能更先获得调度，这使得鼠标移动响应慢或有重影

因而应用于服务器，O(1)调度算法表现尚可，在交互性更强的桌面应用方面就强差人意。

 

CFS解决了以上O(1)算法问题，它的核心数据结构为红黑树，该红黑树的key为进程的虚拟运行时间(vruntime)。每次调度时选择具有最小vruntime的进程执行，即红黑树最左边的结点相应的进程。

 

CFS调度算法中，交互型的进程将获得更大的权重、更多被执行的机会。假如现在有一个vruntime为1ms的交互型进程，另有一个vruntime为10ms的cpu消耗型进程，调度器连续调度交互型进程10次，再调度vruntime为10ms的cpu消耗型进程。Android中使用的调度方法亦为CFS。

 

之前的调度算法中，nice优先级决定进程的时间片大小，在CFS中，nice与进程权重关联，权重大的进程获得的运行时间就长。prio_to_weight数组定义了nice与权重的对应关系，该数组在中定义。

 

调度策略

kernel提供了5种调度策略，针对普通进程，有以下3种：

SCHED_OTHER
SCHED_BATCH
SCHED_IDLE

这3种调度策略对应的进程，按CFS方式调度，优先级依次降低。

针对实时进程，有以下2种：

SCHED_FIFO
SCHED_RR

FIFO即先到先服务，具备该调度策略的进程将一直运行，直至其被I/O请求挂起或被具有更高优先级的实时进程抢占。

RR即轮叫调度(Round Robin)，除设定了进程运行的最大时间片外，其他调度方式与FIFO相同。

因实时进程的优先级比普通进程的优先级都要高，具备以上调度策略的进程变为可运行状态时，都将抢占以CFS方式调度的普通进程。

 

CFS调度算法相关的代码在sched_fair.c中，实时进程相关的调度算法在sched_rt.c中定义。

 

与进程调度策略相关的函数调用有以下两个，分别用于获取、设置进程调度策略：

sched_getscheduler
sched_setscheduler

以下程序示例使用sched_setscheduler调用，将程序自身的优先级设置为最高的实时优先级：

// sched_test.c
#include
#include
#include
int main()
{
    struct sched_param param;
    param.sched_priority = sched_get_priority_max(SCHED_FIFO);
    sched_setscheduler(getpid(), SCHED_FIFO, ?m);
    printf("running...\n");
    while(1);
    return 0;
}

执行程序之后，我们在top中可以看到

    PID USER  PR  NI   VIRT   RES  SHR  S  %CPU  %MEM    TIME+    COMMAND
24484   root  RT    0   3704   400   316  R     100      0.0   1:32.51    sched_test

设置实时进程的优先级只能通过函数调用，不像设置nice值，可使用renice命令。

 

负载均衡

对于多核cpu，kernel的调度器还需要解决另一个问题：如何在多核间做到负载平衡。若一个核忙于跑程序，而其他核是空闲的，那么就失去了多核存在的意义。

 

对于对称多处理(symmetric multiprocessing,SMP)架构的cpu，同一物理cpu中，多核间可共享cache，物理cpu之间则不能。因而在同一物理cpu多核间移动进程，相比物理cpu间移动进程，开销要小。

 

migration内核线程完成平衡多核工作负载的工作，migration以以下方式拉起：

1. 时钟中断处理函数timer_interrupt调用scheduler_tick函数
2. 在scheduler_tick中，trigger_load_balance函数被调用
3. 若满足调整cpu负载条件，trigger_load_balance通过raise_softirq调用产生一个软中断
4. 后续软中断得到处理， migration线程被拉起，完成负载平衡工作

另外我们可以通过taskset命令设置某进程在某个特定cpu上执行，并且不参与负载平衡调度：

linux # taskset -cp 0 ./sched_test

以上命令设置sched_test在0号cpu上运行，使用top我们可以看到执行的效果：

linux # ps -elf | grep test | grep -v grep
4 R root 24502 24053 99 -40   - -   633 -      12:49 pts/7    00:00:15 ./sched_test

linux # top -p 24502

top - 12:50:19 up 5 days,  3:04,  7 users,  load average: 1.55, 1.86, 2.16
Tasks:   1 total,   1 running,   0 sleeping,   0 stopped,   0 zombie
Cpu0  :100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu1  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu2  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Cpu3  :  0.0%us,  0.0%sy,  0.0%ni,100.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:     23980M total,      375M used,    23604M free,       37M buffers
Swap:     2055M total,        0M used,     2055M free,      221M cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM   TIME+  COMMAND
24502 root      RT  0  2532  364  292 R  100  0.0   0:40.73 sched_test

Reference: Chapter 4 - Process Scheduling,  Linux kernel development.3rd.Edition