学步园

linux内核代码中是通过一个叫vruntime的变量来实现上面的原理的，即：

每一个进程拥有一个vruntime,每次需要调度的时候就选运行队列中拥有最小vruntime的那个进程来运行，vruntime在时钟中断里面被维护，每次时钟中断都要更新当前进程的vruntime,即vruntime以如下公式逐渐增长：

 (1) vruntime +=  delta* NICE_0_LOAD/ se.weight;(if curr.nice!=NICE_0_LOAD)

 (2)vruntime +=  delta;                      (if curr.nice=NICE_0_LOAD)

在每次更新完vruntime之后，将会进行一次检查，要不要设置调度位TIF_NEED_SCHED,表示要不要被抢占或自动放弃cpu,其实在没有唤醒和CPU之间的进程迁移的时候，只有当前进程主动放弃CPU这种情况，即每个进程都会运行完自己的ideal_time.

即在这里设置抢占位。

通过以上分析，我们基本上已经分析了不开组调度的情况下，进程一般的调度的原理，这里没考虑到唤醒和进程歉意的情况，在后面的文章中会详细的介绍。

 

至此，我们可能还会有几个疑问：

1 这里只是设置了TIF_NEED_SCHED位，那么谁来检查这个抢占位，来实现进程切换的呢？

  这也是在时钟中断里面做的，当时钟中断要返回的时候，会显示的调用schedule()函数，这个函数会检查TIF_NEED_SCHED有没有被置位，来决定是否进行真正的进程切换。

2 还是 A B C这三个进程，如果不考虑唤醒和进程迁移的情况，A的理想的运行时间是3个时间单位，因为只有在

             if (delta_exec > ideal_runtime)
                     resched_task(rq_of(cfs_rq)->curr);

这个时候才设置调度位，那么A运行完这段时间后有没有运行完呢？我们先来仔细分析一下这个公式：

vruntime +=  delta* NICE_0_LOAD/ se.weight;(if curr.nice!=NICE_0_LOAD)

NICE_0_LOAD是个定值，及系统默认的进程的权值

se,weight是当前进程的权重

delta是当前进程运行的时间

我们可以得出这么个关系：

vruntime与delta成正比，即当前运行时间越长vruntime增长越快

vruntime与se.weight成反比，即权重越大vunruntime增长越慢

现在我们来考虑一种极端的情况：没有唤醒，没有进程迁移,A B C三个进程都是第一次运行

那么系统就会随机从A B C中选一个来运行，因为他们的vruntime第一次是相等的。假设选择B来运行，那么B将运行2个时间单位之后，在某一次时钟中断中发现他的运行时间>它理想运行的时间(runtime>ideal_time),那么将设置TIF_NEED_SCHED位，来进行进程切换；又假设第二次选中了C，那么A运行了稍大于3个时间单位，最后A运行了稍大于1个时间单位。在这种情况下，我们会问，这么运行后A B C有没有运行完啊？（因为我们的理想时间是经验值算出来的），如果没有运行完的话，那下一轮运行又是个什么情况呢？我的理解是经验吧，只有运行的时候才能知道，我们只能感觉上认为应该是对的吧，希望弄明白的同学给我留言！！！

(我想说的是怎么提出一种定量的评价好坏的方法)

3 我们再举一个极端的情况假设有两个用户A，B，注意这里使用户。A用户有1个进程a且a.weight=1;B用户也有1个进程b且b.weight=1000,根据上面的公平理论，我们可以发现B用户可能会一直霸占cpu，在用户更多的情况下，肯能会更糟。为了解决这种问题，CFS引入了组调度，即调度的对象不仅仅限于调度实体，而是可以以用户为调度单位，即A和B位调度单位的话，A B各占50%的CPU。而且只要一个组里的进程被调度，其他的进程也会跟着被调度，但是占用的CPU却至于用户有关。

上次主要讲了CFS调度的基本原理，并且没有分析有唤醒和进程迁移时候的调度流程，所以本文主要从内核中几个重要的调度点来详细的分析一下调度的基本流程，主要以流程图的形式给出。
    内核中主要有以下几个重要的切入点:
    (1)tick相关，即时钟中断

这就是上篇文章中讲的每次中断中，更新vruntime的整个过程，可以理解为是在中断的上半部分做的，很显然我们会想到前一篇文章中讲到的检查TIF_NEED_SCHED位并显示调用schedule()的地方就是中断的下半部分了，为了更好的理解我把中断的整个处理流程也做了个流程图(以时钟中断为例)：

 

(这些流程图很大的，如果看不清可以下载下来放大看，应该相当清晰)

与中断相关的部分，我会在以后的文章里详细介绍，在这里就不具体接讲解了。

现在来总结一下这个切入点的整个过程：

当来一个时钟中断的时候，概括来说内核做了两个操作(参见上图中)：

 

(1)do_timer():它主要来更新系统的时间

(2)update_progress_times():一方面去执行我们上面谈到的scheduler_tick()，另一方面他又去触发一个软中断

执行完上面几个步骤后，时钟中断就要返回了，因为其他的任务留给软中断做了。具体怎么做我会在中断一部分在分析。我们来看看中断返回时的一段代码：

     call do_IRQ
     jmp ret_from_intr  #执行完do_IRQ后跳到ret_from_intr 

ret_from_intr:

     ..............
     cmpl $USER_RPL, %eax  #判断返回用户态还是内核态
     jb resume_kernel  # not returning to v8086 or userspace

ENTRY(resume_userspace)
     ..............

 

     jne work_pending
     jmp restore_all

ENTRY(resume_kernel)
     ..........

need_resched:
     movl TI_flags(%ebp), %ecx # need_resched set ?
     testb $_TIF_NEED_RESCHED, %cl     #检查TIF_NEED_SCHED有没有被置位
     jz restore_all
     testl $X86_EFLAGS_IF,PT_EFLAGS(%esp) # interrupts off (exception path) ?
     jz restore_all
     call preempt_schedule_irq          #在这里显示调用了schedule()
 jmp need_resched

到这里我们已经跟踪了在时钟中断里面的一个完整的调度过程。

(2)当前进程主动放弃CPU

   既然是主动放弃，直接主动调用schedule()就行了，内核里面的很多地方都是这么做的，只要搜一下schedule的调用点就会看到。下面是从schedule()开始的一个调用

流程图:

 

总结一下执行的流程：

(1)清除TIF_NEED_SCHED

(2)判断一下当前进程应该被继续设置为TASK_RUNNING状态，如果不是的话就把它从运行队列中删除

(3)看一下当前运行队列是否还有可运行进程，没有的话，调用idle_balance(cpu, rq)平衡负载

(4)把当前进程放回运行队列，并设置当前进程的指针为空。

(5)选择下一个进程作为当前进程

(6)判断如果当前进程不等于选择的进程的话，就进行进程切换，执行swtich_to,这部分将在下次讲解。

 

先说这么多，因为有很多细节我也不怎么理解，下面提出几个问题，希望能和大家一块讨论:

(1)schedule()函数中的这段代码及其展开

if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)){
  /*prev->state >0 即当前进程处在stopped状态下，而且可抢占的情况下*/
  if (unlikely(signal_pending_state(prev->state, prev)))
   prev->state = TASK_RUNNING;/**/
  else
   deactivate_task(rq, prev, 1);/*从红黑树中删除prev*/
  switch_count = &prev->nvcsw;

 

这部分的意思是如果当前进程还需要呆在运行队列中就设置其prev->state = TASK_RUNNING，否则把它从

红黑树中删除。

问题一：继续留在运行队列的那个判断条件具体是什么意思？

if (unlikely(signal_pending_state(prev->state, prev)))

猜测应该是，TASK_INTERRUPTIBLE这种状态时，可随时接受信号来继续运行。

问题二: 如果不留在运行队列就要从红黑树种删除，跟踪删除函数最后到了dequeue_entity()的这段代码

  /*清除伙伴*/
 clear_buddies(cfs_rq, se);
       /*大部分情况下二者是相等的，不执行，
       因为当前进程一直就不在运行队列中
       问题的关键是什么情况下执行呢?*/
 if (se != cfs_rq->curr)
  __dequeue_entity(cfs_rq, se);

 

这个判断条件是什么意思？se不就是当前进程吗？什么情况下这个判断条件才能成立，最好能有个具体的例子。

我是这么想的，大部分情况下se = cfs_rq->curr，那么出队操作就不执行，因为当前进程是不在运行队列中的，这一点可以从新选择一个进程来运行的时候要先把它出列得到印证，具体可见pick_next_task().