http://www.akaedu.org/bbs/redirect.php?tid=16229&goto=lastpostLinux Kernel 2.6进程调度的分析 2用来记录该CPU进程相关数据。具体作用如下
用来记录该CPU进程相关数据。具体作用如下 nr_running 记录该CPU上就绪进程总数，是active array和expired array进程总数和 nr_switches 记录该CPU运行以来发生的进程切换次数 nr_uninterruptible 记录该CPU不可中断状态进程的个数 timestamp_last_tick 记录就绪进程队列上次发生调度的时间，用于负载均衡 (6) struct list_head migration_queue 这个是存放希望迁移到其他CPU上的进程队列，实际迁移的数据类型是migration_req_t ，这里是通过将migration_req_t::list连接起来。详见"负载均衡"中"push"一节。 3. 进程标识task_struct(include/linux/sched.h) Linux是一个多任务的操作系统，在多任务操作系统中每一个进程都由一个PCB程序控 制块来标识在Linux中PCB实际上是一个名为task_struct的结构体。 task_struct有上百个域，主要包括了10个方面的信息：1.进程状态；2.调度信息， 如调度策略，优先级，时间片，交互值等；3.进程的通讯状况；4.进程树中的父子兄 弟的指针；5.时间信息，如睡眠时间，上一次发生调度时间等；6.标号，决定该进程 归属；7.打开的一些文件信息；8.进程上下文和内核上下文；9.处理器上下文；10. 内存信息。 由于task_struct结构体比较复杂，因此我们只注意它与进程调度相关的重要部分。 (1) volatile long state 进程所处的状态。在include/linux/sched.h中包含6种状态： #define TASK_RUNNING 0 #define TASK_INTERRUPTIBLE 1 #define TASK_UNINTERRUPTIBLE 2 #define TASK_STOPPED 4 #define TASK_ZOMBIE 8 #define TASK_DEAD 16 新增的TASK_DEAD是表示已经退出且不需父进程回收的进程的状态。 (2) struct thread_info *thread_info 当前进程运行的一些环境信息。其中有两个结构成员非常重要，与调度密切相关： __s32 preempt_count; unsigned long flags; preempt_count是用来表示内核能否被抢占的使能成员。如果它大于0，表示内核不能 被抢占；如果等于0，则表示内核处于安全状态（即没有加锁），可以抢占。 flags里面有一个TIF_NEED_RESCHED位，它和Kernel 2.4中need_resched作用一样。 如果此标志位为1，则表示应该尽快启动调度器。 (3) int prio, static_prio prio是进程的动态优先级，相当于Kernel2.4中用goodness()函数计算出来的结果； 在Kernel2.6 中不再是由调度器统一计算，而是独立计算；prio的计算和许多因素有 关，详见"进程优先级的计算"一节。 static_prio则是进程的静态优先级，与nice意义相同。nice的取值仍然是-20 ~ 19 ，数值越小，进程优先级越高。 kernel/sched.c中定义了两个宏来完成将nice转换到prio的取值区间和将prioity转 换到nice取值区间。 #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20) 可见prioity和nice的关系是： priority = MAX_RT_PRIO+nice+20 (4) struct list_head run_list 前面提到过，就绪进程都是按照优先级进行排列，prio_array中的queue[MAX_PRIO] 存放的是指向每个优先级队列的链头list_head；而同一优先级的进程则是通过run_list 链接在一起。 include/linux/list.h定义了一种抽象的双向链表struct list_head，通过它可以将 任意类型的结构体链接到一起。task_struct也是通过这种方式链接起来的。 (5) prio_array_t *array 指向当前CPU的active array的指针。在进程控制块里面又加了一个指向active array 的指针，看似重复，其实不然。比如说对于下面的代码（kernel/sched.c）： array = next->array; dequeue_task(next, array); recalc_task_prio(next, next->timestamp + delta); enqueue_task(next, array); 对于单处理器（UP）的情况，我们确实可以通过runqueue::active直接得到当前的active array；但是对于SMP，就不是这样了，需要引用next的thread_info，再依靠thread_info 中的cpu找到next所在的处理器，找到以后再找到这个cpu上的runqueue，最后得到active 。对于schedule这样频繁调用的函数，这种浪费是不能容忍的。 (6) unsigned long sleep_avg 进程的平均等待时间，单位是纳秒（nanosecond），在0 ~ NS_MAX_SLEEP_AVG范围内 。它的实质是进程等待时间和运行时间的差值。当进程处于等待或者睡眠状态时，该 值变大；当进程运行时，该值变小。 sleep_avg是Kernel 2.6中衡量进程的一个关键指标，它既可以用来衡量进程的交互 程度，也可以用来衡量进程的紧急程度。具体内容将在"平均等待时间sleep_avg"一 节作详细介绍。 (7) long interactive_credit 表示进程交互程度，取值范围在-CREDIT_LIMIT ~ CREDIT_LIMIT+1之间。进程创建的 时候值为1，以后根据不同的情况进行不同的增1、减1；如果一个进程的 interactive_credit 超过CREDIT_LIMIT之后，这个进程就会被认为是交互式进程，同时interactive_credit 的值也就不再改变了（恒为CREDIT_LIMIT+1）。下面将在"交互进程优化"一节详细介 绍。 (8) unsigned long long timestamp 进程发生调度的时间，单位和sleep_avg一样，也是纳秒。它负责纪录以下四种情况 的时间： a. 进程被唤醒的时间： 在activate_task()（kernel/sched.c）中记录（p->timestamp = now）。 b. 进程被切换到expired array的时间： 在schedule()（kernel/sched.c）中记录，当准备进行进程切换的时候，记录下该进 程被切换到expired array的时间（prev->timestamp = now）。 c. 进程被切换到active array的时间： 在schedule()（kernel/sched.c）中记录，进行进程切换的开始，记录下下一个进程 被切换到active array的时间（next->timestamp = now）。 d. 负载均衡相关的赋值 在进行负载均衡的时候，当把一个进程从其他CPU上pull过来的时候需要将该进程的 timestamp设成sched_clock() - (src_rq->timestamp_last_tick - p->timestamp) ，即相对于本CPU被切换下来的时间。 (9) int activated 表示该进程被唤醒的类别： actived=-1 表示该进程并非自愿sleep，其先前状态是TASK_UNINTERRUPTIBLE。在 try_to_wake_up ()中设置。 actived=0 缺省值，表示进程本来就是处于就绪状态。 actived=1 进程先前状态是TASK_INTERRUPTIBLE，但是不是由中断唤醒；这 样的进 程在第一次运行时有credit，以后就没有了。在activate_task()中设置。 actived=2 进程先前状态是TASK_INTERRUPTIBLE，进程被中断唤醒。这样的 进程非 常像交互式进程。在activate_task()中设置。 (10) unsigned long policy 进程的调度策略和2.4一样，有以下几种： SCHED_FIFO 先进先出式调度，除非有更高优先级进程申请运行，否则该进程 将保持运行至退出才让出CPU SCHED_RR 轮转式调度，该进程被调度下来后将被置于运行队列的末尾，以 保证其他实时进程有机会运行） SCHED_OTHER 常规的分时调度策略 (11) unsigned int time_slice, first_time_slice ime_slice是进程剩余的时间片，相当于Kernel 2.4里面counter，但是时间片不再影 响进程的优先级。 first_time_slice用来记录时间片是否是第一次分配（进程创建时），如果值不为0 ，进程退出时将时间片交还给父进程。 三、调度策略 1. 进程优先级 (1) 优先级的计算 前面已经说过，优先级由两部分构成，一是静态优先级static_prio，一是动态优先 级prio。静态优先级在进程创建的时候就被赋值，并且不变（除非用系统调用改变进 程的nice值）；而进程的动态优先级则是跟static_prio和sleep_avg有关。对于实时 进程的优先级在创建的时候就确定了，而且一旦确定以后就不再改变，所以下面部分 仅对于非实时进程而言。具体的计算由函数effecitve_prio()（kernel/sched.c）完 成。 函数将进程的sleep_avg映射成范围是-MAX_BONUS/2 ~ MAX_BONUS/2的变量bonus，而 MAX_BONUS是等于 ，可见sleep_avg仅能影响的优先级范围在-5 ~ 5之间。具体的映 射是由以下规则完成的： 那么进程的动态优先级就等于： （当然必须在MAX_RT_PRIO和MAX_PRIO-1之间 ）。可见，sleep_avg和bonus是一个线性关系。进程的sleep_avg越大，bonus越大， 从而进程的动态优先级也就越高。 (2) 何时计算优先级 计算进程的动态优先级一般调用两个函数，一个是effective_prio()，一个是 recalc_task_prio()。函数recalc_task_prio ()先要根据进程被唤醒前的状态 （即actived）、interactive_credit等来计算进程的sleep_avg （详见"平均等待时间sleep_avg"一节），在最后调用effective_prio()来计算函数 的动态优先级。总的来说，有以下几种情况需要计算进程的优先级： a. 创建新进程，使用函数effective_prio()（因为此时进程尚未进行调度，没有 sleep_avg和interactive_credit可言）； b. 唤醒等待进程时，使用函数recalc_task_prio ()来计算进程动态优先级。 c. 进程用完时间片以后，被重新插入到active array或者expired array的时候需要 重新计算动态优先级，以便将进程插入到队列的相应位置。此时，使用函数 effective_prio()； d. 其他情况，如IDLE进程初始化等时候。 2. 进程时间片 (1) 时间片的计算 进程的时间片time_slice是基于进程静态优先级的，静态优先级越高（值越小），时 间片就越大。计算时间片是同过函数task_timeslice()（kernel/sched.c）来完成的 MAX_BONUS是等于 ，可见sleep_avg仅能影响的优先级范围在-5 ~ 5之间。具体的映 射是由以下规则完成的： 那么进程的动态优先级就等于： （当然必须在MAX_RT_PRIO和MAX_PRIO-1之间 ）。可见，sleep_avg和bonus是一个线性关系。进程的sleep_avg越大，bonus越大， 从而进程的动态优先级也就越高。 |
