Posts Tagged ‘Process’

内核函数copy_process()分析

January 11th, 2016

内核通过调用函数copy_process()创建进程,copy_process()函数主要用来创建子进程的描述符以及与子进程相关数据结构。这个函数内部实现较为复杂,在短时间内,对于内部详细代码原理和实现并不能全部理解。因此,接下来的分析侧重于copy_process()的执行流程。

1. 定义返回值变量和新的进程描述符。

2.  对clone_flags所传递的标志组合进行合法性检查。当出现以下四情况时,返回出错代号:

  • CLONE_NEWNS和CLONE_FS同时被设置。前者标志表示子进程需要自己的命名空间,而后者标志则代表子进程共享父进程的根目录和当前工作目录,两者不可兼容。
  • CLONE_NEWUSER和CLONE_FS同时被设置。
  • CLONE_THREAD被设置,但CLONE_SIGHAND未被设置。如果子进程和父进程属于同一个线程组(CLONE_THREAD被设置),那么子进程必须共享父进程的信号(CLONE_SIGHAND被设置)。
  • CLONE_SIGHAND被设置,但CLONE_VM未被设置。如果子进程共享父进程的信号,那么必须同时共享父进程的内存描述符和所有的页表(CLONE_VM被设置)。

3. 调用security_task_create()和后面的security_task_alloc()执行所有附加的安全性检查。

4. 调用dup_task_struct()为子进程分配一个内核栈、thread_info结构和task_struct结构。

 p = dup_task_struct(current);
        if (!p)
               goto fork_out;

这个dup_task_struct函数首先定义创建了指向task_struct和thread_inof结构体的指针。然后让子进程描述符中的thread_info字段指向ti变量;最后让子进程thread_info结构中的task字段指向tsk变量。然后返回tsk,这个时候子进程和父进程的描述符中的内容是完全相同的。在后面的代码中,我们将会看到子进程逐渐与父进程区分开。

static struct task_struct *dup_task_struct(struct task_struct *orig)
{
        struct task_struct *tsk;
        struct thread_info *ti;
        int node = tsk_fork_get_node(orig);
        int err;
 
        tsk = alloc_task_struct_node(node);
        if (!tsk)
                return NULL;

        ti = alloc_thread_info_node(tsk, node);
        if (!ti)
                goto free_tsk;

        err = arch_dup_task_struct(tsk, orig);
        if (err)
                goto free_ti;
        tsk->stack = ti;

5. 开始设置子进程的task_struct

根据clone_flags的值继续更新子进程的某些属性。将 nr_threads++,表明新进程已经被加入到进程集合中。将total_forks++,以记录被创建进程数量。

这部分工作还包含初始化双链表、互斥锁和描述进程属性的字段等,其中包括大量的与cgroup相关的属性,。它在copy_process函数中占据了相当长的一段的代码,不过考虑到task_struct结构本身的复杂性,也就不奇怪了。

如果上述过程中某一步出现了错误,则通过goto语句跳到相应的错误代码处;如果成功执行完毕,则返回子进程的描述符p。do_fork()执行完毕后,虽然子进程处于可运行状态,但是它并没有立刻运行。至于子进程合适执行这完全取决于调度程序schedule()。

 

http://lxr.free-electrons.com/source/kernel/fork.c#L1242

fork系统调用分析

January 9th, 2016

0 前言

在Linux中,主要是通过fork的方式产生新的进程,我们都知道每个进程都在 内核对应一个PCB块,内核通过对PCB块的操作做到对进程的管理。在Linux内核中,PCB对应着的结构体就是task_struct,也就是所谓的进程描述符(process descriptor)。该数据结构中包含了程相关的所有信息,比如包含众多描述进程属性的字段,以及指向其他与进程相关的结构体的指针。因此,进程描述符内部是比较复杂的。这个结构体的声明位于include/linux/sched.h中。

task_struct中有指向mm_struct结构体的指针mm,也有指向fs_struct结构体的指针fs,这个结构体是对进程当前所在目录的描述;也有指向files_struct结构体的指针files,这个结构体是对该进程已打开的所有文件进行描述。这里我们要注意进程在运行期间中可能处于不同的进程状态,例如:TASK_RUNNING/TASK_STOPPED/TASK_TRACED 等

1 fork调用

在用户态下,使用fork()创建一个进程。除了这个函数,新进程的诞生还可以分别通过vfork()和clone()。fork、vfork和clone三个API函数均由glibc库提供,它们分别在C库中封装了与其同名的系统调用fork()。这几个函数调用对应不同场景,有些时候子进程需要拷贝父进程的整个地址空间,但是子进程创建后又立马去执行exec族函数造成效率低下。

  • 写时拷贝满足了这种需求,同时减少了地址空间复制带来的问题。
  • vfork 则是创建的子进程会完全共享父进程的地址空间,甚至是父进程的页表项,父子进程任意一方对任何数据的修改使得另一方都可以感知到。
  • clone函数创建子进程时灵活度比较大,因为它可以通过传递不同的参数来选择性的复制父进程的资源

系统调用fork、vfork和clone在内核中对应的服务例程分别为sys_fork(),sys_vfork()和sys_clone()。例如sys_fork()声明如下(arch/x86/kernel/process.c):

int sys_fork(struct pt_regs *regs)
{
        return do_fork(SIGCHLD, regs->sp, regs, 0, NULL, NULL);
}
int sys_vfork(struct pt_regs *regs)
{
        return do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD, regs->sp, regs, 0,
                       NULL, NULL);
}
sys_clone(unsigned long clone_flags, unsigned long newsp,
          void __user *parent_tid, void __user *child_tid, struct pt_regs *regs)
{
        if (!newsp)
                newsp = regs->sp;
        return do_fork(clone_flags, newsp, regs, 0, parent_tid, child_tid);
}

可以看到do_fork()均被上述三个服务函数调用。do_fork()正是kernel创建进程的核心()。通过分析调用过程如下,其中我分析的是最新版4.X Linux源码,在i386体系结构中,采取0x80中断调用syscall:

fork

 

从图中可以看到do_fork()和copy_process()是本文的主要分析对象。

do_fork函数的主要就是复制原来的进程成为另一个新的进程,在一开始,该函数定义了一个task_struct类型的指针p,用来接收即将为新进程(子进程)所分配的进程描述符。但是这个时候要检查clone_flags是否被跟踪就是ptrace,ptrace是用来标示一个进程是否被另外一个进程所跟踪。所谓跟踪,最常见的例子就是处于调试状态下的进程被debugger进程所跟踪。ptrace字段非0时说明debugger程序正在跟踪父进程,那么接下来通过fork_traceflag函数来检测子进程是否也要被跟踪。如果trace为1,那么就将跟踪标志CLONE_PTRACE加入标志变量clone_flags中。没有的话才可以进程创建,也就是copy_process()。

long _do_fork(unsigned long clone_flags,
              unsigned long stack_start,
              unsigned long stack_size,
              int __user *parent_tidptr,
              int __user *child_tidptr,
              unsigned long tls)
{
        struct task_struct *p;
        int trace = 0;
        long nr;
        if (!(clone_flags & CLONE_UNTRACED)) {
                if (clone_flags & CLONE_VFORK)
                        trace = PTRACE_EVENT_VFORK;
                else if ((clone_flags & CSIGNAL) != SIGCHLD)
                        trace = PTRACE_EVENT_CLONE;
                else
                        trace = PTRACE_EVENT_FORK;
                if (likely(!ptrace_event_enabled(current, trace)))
                        trace = 0;
        }

这条语句要做的是整个创建过程中最核心的工作:通过copy_process()创建子进程的描述符,并创建子进程执行时所需的其他数据结构,最终则会返回这个创建好的进程描述符。因为copy_process()函数过于巨大,所以另外开辟一篇文章讲解该函数实现。

 p = copy_process(clone_flags, stack_start, stack_size,
                        child_tidptr, NULL, trace, tls);

如果copy_process函数执行成功,那么将继续下面的代码。定义了一个完成量vfork,之后再对vfork完成量进行初始化。如果使用vfork系统调用来创建子进程,那么必然是子进程先执行。原因就是此处vfork完成量所起到的作用:当子进程调用exec函数或退出时就向父进程发出信号。此时,父进程才会被唤醒;否则一直等待。

 if (!IS_ERR(p)) {
                struct completion vfork;
                struct pid *pid;

                trace_sched_process_fork(current, p);

                pid = get_task_pid(p, PIDTYPE_PID);
                nr = pid_vnr(pid);
                if (clone_flags & CLONE_PARENT_SETTID)
                     put_user(nr, parent_tidptr);
                if (clone_flags & CLONE_VFORK) {
                     p->vfork_done = &vfork;
                        init_completion(&vfork);
                        get_task_struct(p);
                }

下面通过wake_up_new_task函数使得父子进程之一优先运行;如果设置了ptrace,那么需要告诉跟踪器。如果CLONE_VFORK标志被设置,则通过wait操作将父进程阻塞,直至子进程调用exec函数或者退出。

                wake_up_new_task(p);

                /* forking complete and child started to run, tell ptracer */
                if (unlikely(trace))
                        ptrace_event_pid(trace, pid);
                if (clone_flags & CLONE_VFORK) {
                    if (!wait_for_vfork_done(p, &vfork))
                               ptrace_event_pid(PTRACE_EVENT_VFORK_DONE, pid);
                }
                put_pid(pid);

如果copy_process()在执行的时候发生错误,则先释放已分配的pid;再根据PTR_ERR()的返回值得到错误代码,保存于pid中。 返回pid。这也就是为什么使用fork系统调用时父进程会返回子进程pid的原因。

        } else {
                nr = PTR_ERR(p);
        }
        return nr;
}

参考:

http://cs.lmu.edu/~ray/notes/linuxsyscalls/

http://www.x86-64.org/documentation/abi.pdf

http://www.tldp.org/LDP/tlk/ds/ds.html

进程控制踩过的坑

July 1st, 2015

1. fork()与vfork()非常相似,但是使用场景有一些不同,vfork()主要用来创建子进程,然后执行exec()一个新的程序,不会发生COW(fork()出来的子进程exec()会产生COW,所以vfork()更加快速),vfork()可以保证子进程先运行,调用exec()、exit之后才会被调度,如果子进程依赖父进程产生一些动作的话,可能产生死锁

2. vfork()在父进程空间中运行,这个导致子进程可以修改父进程的值!

3. 之前在C/S模型下Server 中fork()的健壮性中说过,fork()产生的子进程退出后,发送SIGCHLD信号,如果不及时使用wait方式处理的话,会产生僵尸进程。反过来,如果父进程先停止,那么子进程退出时,会向init进程发送SIGCHLD信号。

4. wait()与waitpid()都可以接受终止子进程发送的信号,wait()是waitpid()的简化版本,wait()返回任意一个终止子进程的状态,waitpid()可以接受特定子进程的信号。

5. 按照之前第3条所叙述的,我们可以利用这个init领养子进程规则让init管理孤儿进程,这里有一个技巧:fork()两次!

int main(void)
{
        pid_t pid;
        if ((pid = fork()) < 0) {
             err_sys("fork error");
        } else if (pid == 0) { /* first child */
             if ((pid = fork()) < 0)
                  err_sys("fork error");
             else if (pid > 0)
                  exit(0); /* parent from second fork == first child */
//这个exit(0)退出的就是第一次fork()出来的子进程,也是第二次fork()的
//父进程,当这个进程退出后,也就意味着第二次fork()出来的子进程变成
//孤儿进程,直接由init接管!
/*
* We’re the second child; our parent becomes init as soon
* as our real parent calls exit() in the statement above.
* Here’s where we’d continue executing, knowing that when
* we’re done, init will reap our status.
*/
//下面这段是第二次fork()出来子进程执行的代码段
            sleep(2);//必须保证第二次fork()出来的父进程先退出!
            printf("second child, parent pid = %ld\n", (long)getppid());
            exit(0);
        }
        if (waitpid(pid, NULL, 0) != pid) /* wait for first child */
            err_sys("waitpid error");
/*
* We’re the parent (the original process); we continue executing,
* knowing that we’re not the parent of the second child.
*/
        exit(0);
}

这个代码设计的很精巧,开始我没有看懂,仔细分析才可以。

6. 对于某些父子进程拥有竞争条件的代码,必须要使用信号机制或者管道机制实现父子进程同步,其中TELL_WAIT(),TELL_PARENT(),WAIT_PARENT(),TELL_CHILD(pid),WAIT_CHILD()可以使用不同的机制定义,从而实现父子进程的有序执行!

     TELL_WAIT(); /* set things up for TELL_xxx & WAIT_xxx */
     if ((pid = fork()) < 0) {
      err_sys("fork error");
     } else if (pid == 0) { /* child */
     /* child does whatever is necessary ... */
     TELL_PARENT(getppid()); /* tell parent we’re done */
     WAIT_PARENT(); /* and wait for parent */
     /* and the child continues on its way ... */
     exit(0);
     }
    /* parent does whatever is necessary ... */
    TELL_CHILD(pid); /* tell child we’re done */
    WAIT_CHILD(); /* and wait for child */
    /* and the parent continues on its way ... */
    exit(0);

7. 使用信号机制来实现父子进程同步的话,可以自定义SIGUSR1,SIGUSR2的方式,在main()开始部位,设置中断处理函数,函数修改一个全局volatile sig_atomic类型的变量sigflag,然后在等待函数中,轮训挂起等待信号,直至进程处理信号,跳出这个循环:

while (sigflag == 0)
       sigsuspend(&zeromask); /* and wait for parent */
sigflag = 0;

8.使用pipe,可以在等待函数中读管道,在通知函数中写管道,达到父子进程的同步!

void TELL_PARENT(pid_t pid)
{
    if (write(pfd2[1], "c", 1) != 1)
        err_sys("write error");
}
void WAIT_PARENT(void)
{
    char c;
    if (read(pfd1[0], &c, 1) != 1)
        err_sys("read error");
    if (c != ’p’)
        err_quit("WAIT_PARENT: incorrect data");
}

 

 

参考:
APUE P185,P270,P402

信号处理函数所踩过的坑

June 16th, 2015

Update 2015-6-24

最近在看APUE的信号章节,在这里我总结下进程信号处理中应该注意的一些坑。Unix中有很多的信号是可以被进程接管,然后跳到信号处理函数中。

1. 有两个信号是无法被接管或者被忽略的SIGKILL与SIGSTOP

2. SIGHUP 是要出现在远程ssh一台主机时,连接意外断开时,系统会向所有与这个终端相关的控制进程发送SIGHUP。

3. 在liunx中SIGIO与SIGPOLL相同,默认是终止这个进程。

4. SIGTERM可以由进程编写者定义,当收到这个信号那么,进程可以自行做退出操作的扫尾工作,然后退出程序。

5. signal与sigaction功能相似,但是signal在不同平台上实现不同,应该使用sigaction进程信号的接管。

6. 交互式进程后台运行时,shell会将后台进程设置为对于中断和退出信号的处理方式设置为忽略SIG_IGN。也就是说当向进程发送SIGINT时,捕捉这种类型的代码:

void sig_int(int), sig_quit(int);
if (signal(SIGINT, SIG_IGN) != SIG_IGN)
    signal(SIGINT, sig_int);
if (signal(SIGQUIT, SIG_IGN) != SIG_IGN)
    signal(SIGQUIT, sig_quit);

7. 当父进程fork()一个子进程,子进程将会继承父进程的信号处理函数,这种方式在早期fork()一个子进程后会把这个子进程信号处理函数复位到默认值,我们不必在代码中这么做:

int sig_int(); /* my signal handling function */
...
signal(SIGINT, sig_int); /* establish handler */
...
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
... /* process the signal ... */
}

8. 信号会发生在任何时刻,我们不能设置flag来使得进程进行忙等。下面这种代码在大多数情况下是正确的,但是如果信号发生在while()与pause()之间,会直接导致进程陷入睡眠,无法醒来。

int sig_int(); /* my signal handling function */
int sig_int_flag; /* set nonzero when signal occurs */
main()
{
     signal(SIGINT, sig_int); /* establish handler */
...
     while (sig_int_flag == 0)
            pause(); /* go to sleep, waiting for signal */
...
}
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
    sig_int_flag = 1; /* set flag for main loop to examine */
}

9. 被中断的syscall(通常是慢速系统调用:read,write,open()(如果open不返回,就意味着进程会被永久的阻塞) etc.)必须显式的处理出错返回,在linux中被中断的syscall,会重启这个syscall,但是在当次的调用中,会将errno设置为EINTR,所以我们要对这个EINTR进行处理。如下面的代码:

again:
if ((n = read(fd, buf, BUFFSIZE)) < 0) {
    if (errno == EINTR)
        goto again; /* just an interrupted system call */
    /* handle other errors */
}

10. 信号处理函数的可重入性。如果在信号处理函数中调用,会对进程主体的程序执行流造成破坏,产生Sigment fault。在内核中的实现,我发现为了实现进程处理函数在用户态执行,会将内核态的堆栈数据复制到用户空间的堆栈保存,返回用户空间,执行完sys_sigreturn() 再次陷入到内核,将正常程序的用户态堆栈硬件上下文拷贝到内核堆栈,并将之前备份在用户空间的堆栈还原到内核空间,完成这次中断处理函数。

不可重入性:(a) they are known to use static data structures, (b) they call malloc or free, or (c) they are part of the standard I/O library. Most implementations of the standard I/O library use global data structures in a nonreentrant way.

所以按照定义,为了保证函数是可重入的,需要做到一下几点:

  • 不在函数内部使用静态或者全局数据
  • 不返回静态或者全局数据,所有的数据都由函数调用者提供
  • 使用本地数据,或者通过制作全局数据的本地拷贝来保护全局数据
  •  如果必须访问全局数据,使用互斥锁来保护
  • 不调用不可重入函数

getpwnam()函数是非可重入函数,他在中断处理函数中使用的话,就会修改原来应用程序的数据,导致程序出错

#include "apue.h"
#include <pwd.h>
static void
my_alarm(int signo)
{
       struct passwd *rootptr;
       printf("in signal handler\n");
       if ((rootptr = getpwnam("root")) == NULL)
           err_sys("getpwnam(root) error");
        alarm(1);
}
int main(void)
{
       struct passwd *ptr;
       signal(SIGALRM, my_alarm);
       alarm(1);
       for ( ; ; ) {
           if ((ptr = getpwnam("sar")) == NULL)
               err_sys("getpwnam error");
           if (strcmp(ptr->pw_name, "sar") != 0)
               printf("return value corrupted!, pw_name = %s\n",ptr->pw_name);
       }
}

这段代码中的rootptr其实最后都是指向ptr,这就是造成不可重入的关键!我们使用getpwnam_r()函数便可以正常工作。

void sig_handler(int signo)
{
   struct passwd root_ptr;
   struct passwd *result;
   int s;
   char *buf;
   size_t bufsize;

   bufsize = sysconf(_SC_GETPW_R_SIZE_MAX);
   if(bufsize==-1)
      bufsize = 16384;

   buf = malloc(bufsize);
   if(buf==NULL){
      perror("malloc");
      exit(EXIT_FAILURE);
   }

   printf("in sig_handler\n");
   s = getpwnam_r("root",&root_ptr,buf,bufsize,&result);
   if(result == NULL){
      if(s==0)
          printf("Not found\n");
      else{
          // errno = s;
          perror("getpwnam_r");
      }
      exit(EXIT_FAILURE);
   }
   printf("pw_name = %s\n", root_ptr.pw_name);
   alarm(1);
}

11. SIGCHLD这个信号非常特殊,这个信号很多时候与系统的信号实现相关。在linux平台上 SIGCHLD与SIGCLD等同,这里查看C/S模型下Server 中fork()的健壮性文章,我们需要在父进程信号处理函数中调用pid = wait(&stat);实现对于子进程退出的等待。

void sig_zchild(int signo)
{
      pid_t pid;
      int stat;

      while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
           printf("child %d terminated\n", pid);
      return;
}

12. kill() 函数负责将信号发送给进程或者进程组,raise()是进程向自己发送信号。一个程序全局只能有一个alarm()函数,如果多次调用,那么alarm()登记的值被新值代替。pause()使得调用进程挂起直至捕捉到一个信号,只有执行了一个信号处理函数返回后,pause()才返回。

#include <signal.h>
#include <unistd.h>
static void
sig_alrm(int signo)
{
/* nothing to do, just return to wake up the pause */
}
unsigned int
sleep1(unsigned int seconds)
{
      if (signal(SIGALRM, sig_alrm) == SIG_ERR)
               return(seconds);
      alarm(seconds); /* start the timer */
      pause(); /* next caught signal wakes us up */
      return(alarm(0)); /* turn off timer, return unslept time */
}

这个函数看似正确,但是有一个竞争条件,如果alarm()后调用被阻塞,然后超时,pause()没有捕捉到信号,那么调用到pause()将永久挂起,这里我们要使用到longjmp() 与 setjmp() 可以使得信号处理函数返回到主函数中指定位置,在longjmp第二个参数设置返回值,在setjmp()中检查这个返回值。可以做到跨函数跳跃,类似于函数内部的goto。

所以使用alarm() pause() 慢速系统调用三者很有可能产生竞争,Linux中syscall是被中断后自启动的。

13. 使用sigprocmask() 可以用来屏蔽,或者取消屏蔽某个信号,但是如果在sigprocmask()之后调用sleep() 函数,程序进入睡眠,这个期间产生的某个屏蔽信号,他会被投递到这个进程,进行处理! APUE 10-11

14. 使用sigaction(int signum, const struct sigaction *act,struct sigaction *oldact)对于信号进行处理,struct sigaction下的成员变量sa_flags可以定义各种中断的动作,包括被中断的系统调用是否会重启(SA_INTERUPT)还有信号处理函数只执行一次后复位等(SA_RESETHAND)默认sigaction()函数不再重启被中断的系统调用。

 15. 使用int sigsuspend(const sigset_t *mask)函数可以挂起当前进程,但是当进程收到mask以外的信号并从中断处理函数返回,那么进程从这个函数返回!mask中的信号,进程会屏蔽掉[4]。

16. sleep() 函数与alarm()函数混用,实现需要依赖于具体实现。

17. SIGSTOP、SIGCONT不允许被接管,如果我们需要在SIGSTOP后自定义一些操作,那么我们可以自定义一个信号和信号处理函数。只要跳转到信号处理函数,那么就可以阻止进程访问错误内存地址,进而可以进行一些处理。

 

 

参考:

[1] http://www.cnblogs.com/mickole/p/3187770.html

[2] http://www.man7.org/linux/man-pages/man3/getpwnam.3.html

[3] http://blog.csdn.net/feiyinzilgd/article/details/5811157

[4] http://blog.sina.com.cn/s/blog_6af9566301013xp4.html

__schedule()调度分析

January 22nd, 2015

主实现代码:http://lxr.free-electrons.com/source/kernel/sched/core.c#L2765

调度这一块,因为存在很多的调度policy,kernel为了分离mechanism与具体policy,在__schedule()中实现task的切换,具体policy在pick_next_task() 中实现。

内核中对进程调度的方法有两种,其一为周期性调度器(generic scheduler),它对进行进行周期性的调度,以固定的频率运行;其二为主调度器(main scheduler),如果进程要进行睡眠或因为其他原因主动放弃CPU,那么就直接调用主调度器。

其中,主调度器是__schedule() ,而周期性调度器是void scheduler_tick(void)。这个函数负责每个rq的平衡,保持每个cpu都有task可以运行,这个程序由timer调度。http://lxr.free-electrons.com/source/kernel/sched/core.c#L2524

__schedule()是调度的核心函数,在这个函数里面是主要是从rq队列中,选择进程。除了切换上下文状态,还要使用 pick_next_task() 使用这个选择下一个进程,具体到使用哪种调度policy都在这个struct sched_class结构体里保存着。

目前kernel在SMP环境下使用的调度算法是CFS算法。具体我们先来看pick_next_task()函数。
我们发现具体的policy在fair_sched_class 定义,GNU C的语法就是用C 的strut来模拟C++的class方式,然后在fair.c中定义了众多的函数,这种方式就是一种钩子函数。具体CFS策略这里不再细讲,之后我会专门来分析CFS调度算法。

2692 static inline struct task_struct *
2693 pick_next_task(struct rq *rq, struct task_struct *prev)
2694 {
2695         const struct sched_class *class = &fair_sched_class;
2696         struct task_struct *p;
2697 
2698         /*
2699          * Optimization: we know that if all tasks are in
2700          * the fair class we can call that function directly:
2701          */
2702         if (likely(prev->sched_class == class &&
2703                    rq->nr_running == rq->cfs.h_nr_running)) {
2704                 p = fair_sched_class.pick_next_task(rq, prev);
2705                 if (unlikely(p == RETRY_TASK))
2706                         goto again;
2707 
2708                 /* assumes fair_sched_class->next == idle_sched_class */
2709                 if (unlikely(!p))
2710                         p = idle_sched_class.pick_next_task(rq, prev);
2711 
2712                 return p;
2713         }
2714 
2715 again:
2716         for_each_class(class) {
2717                 p = class->pick_next_task(rq, prev);
2718                 if (p) {
2719                         if (unlikely(p == RETRY_TASK))
2720                                 goto again;
2721                         return p;
2722                 }
2723         }
2724 
2725         BUG(); /* the idle class will always have a runnable task */
2726 }

const struct sched_class fair_sched_class(kernel/sched/fair.c)

在CFS算法中,我们看下面有两个比较特殊:

7944 #ifdef CONFIG_SMP
7945 .select_task_rq = select_task_rq_fair,
7946 .migrate_task_rq = migrate_task_rq_fair,

多CPU必然存在进程并行运行的情况,7945行是公平的选择特定的task,7956行是进行rq中task的迁移,我们知道每个cpu都对应着一个rq队列,这个不一定是quenu,而是red-black tree。对于rq中task的迁移,在

select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)

这个函数正是真正的完全公平调度算法! 

__schedule()函数是进程的主调度器,下面我们来分析这个的实现

2765 static void __sched __schedule(void)
2766 {
2767         struct task_struct *prev, *next;
2768         unsigned long *switch_count;
2769         struct rq *rq;
2770         int cpu;
2771 
2772 need_resched:
2773         preempt_disable();
2774         cpu = smp_processor_id();
2775         rq = cpu_rq(cpu);
2776         rcu_note_context_switch(cpu);
2777         prev = rq->curr;
2778 
2779         schedule_debug(prev);
2780 
2781         if (sched_feat(HRTICK))
2782                 hrtick_clear(rq);
2783 
2784         /*
2785          * Make sure that signal_pending_state()->signal_pending() below
2786          * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
2787          * done by the caller to avoid the race with signal_wake_up().
2788          */
2789         smp_mb__before_spinlock();
2790         raw_spin_lock_irq(&rq->lock);
2791 
2792         switch_count = &prev->nivcsw;
2793         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
2794                 if (unlikely(signal_pending_state(prev->state, prev))) {
2795                         prev->state = TASK_RUNNING;
2796                 } else {
2797                         deactivate_task(rq, prev, DEQUEUE_SLEEP);
2798                         prev->on_rq = 0;
2799 
2800                         /*
2801                          * If a worker went to sleep, notify and ask workqueue
2802                          * whether it wants to wake up a task to maintain
2803                          * concurrency.
2804                          */
2805                         if (prev->flags & PF_WQ_WORKER) {
2806                                 struct task_struct *to_wakeup;
2807 
2808                                 to_wakeup = wq_worker_sleeping(prev, cpu);
2809                                 if (to_wakeup)
2810                                         try_to_wake_up_local(to_wakeup);
2811                         }
2812                 }
2813                 switch_count = &prev->nvcsw;
2814         }
2815 
2816         if (task_on_rq_queued(prev) || rq->skip_clock_update < 0)
2817                 update_rq_clock(rq);
2818 
2819         next = pick_next_task(rq, prev);
2820         clear_tsk_need_resched(prev);
2821         clear_preempt_need_resched();
2822         rq->skip_clock_update = 0;
2823 
2824         if (likely(prev != next)) {
2825                 rq->nr_switches++;
2826                 rq->curr = next;
2827                 ++*switch_count;
2828 
2829                 context_switch(rq, prev, next); /* unlocks the rq */
2830                 /*
2831                  * The context switch have flipped the stack from under us
2832                  * and restored the local variables which were saved when
2833                  * this task called schedule() in the past. prev == current
2834                  * is still correct, but it can be moved to another cpu/rq.
2835                  */
2836                 cpu = smp_processor_id();
2837                 rq = cpu_rq(cpu);
2838         } else
2839                 raw_spin_unlock_irq(&rq->lock);
2840 
2841         post_schedule(rq);
2842 
2843         sched_preempt_enable_no_resched();
2844         if (need_resched())
2845                 goto need_resched;
2846 }

在2773 禁止进程抢占调度器,在2774 ~ 2777 获取当前cpu的id,并获取当前cpu的rq,切换RCU,获取当前rq运行的task,并赋值为prev。

203 #define TASK_RUNNING            0
204 #define TASK_INTERRUPTIBLE      1
205 #define TASK_UNINTERRUPTIBLE    2

我们发现TASK_RUNNING 值为0,这就使得2793行,如果判断当前的进程在运行,就不会进行调度,只会更新rq的clock。
反之如果当前占用cpu的task处于TASK_INTERRUPTIBLE态,却收到了某个唤醒它的信号,那么当前进程的标志被更新为TASK_RUNNING,等待再次被调度。否则,通过deactivate_task()将当前进程prev从就绪队列中删除。

之后在2819行使用pick_next_task()函数,去的当前rq的新的进程,然后清除之前prev进程的标志位。
获取要调度的新的进程,之后就是各种调度了。从2824~2839 这段代码会判断当前的选择的进程与之前的进程是否相同,相同就不用再切换上下文了。

一切调度完成,放开preempt_enable ,系统可以开始抢占。
参考:
http://www.makelinux.net/books/lkd2/ch09lev1sec9