1 进程的概念

Linux内核把进程称为任务(task)，进程的虚拟地址空间分为用户虚拟地址空间和内核虚拟地址空间，所有进程共享内核虚拟地址空间，每个进程有独立的用户虚拟地址空间。
内核线程是没有用户虚拟地址空间的进程。·
共享用户虚拟地址空间的进程称为用户线程，通常在不会引起混淆的情况下把用户线程简称为线程。共享同一个用户虚拟地址空间的所有用户线程组成一个线程组。

1.1 进程术语对应关系

1.2 task_struct

结构体task_struct是进程描述符，结构体部分变量定义如下：

struct task_struct {
  volatile long state; //进程的状态
  void *stack; //指向内核栈
  pid_t pid; //全局的进程号
  pid_t tgid; //全局的线程组标识符
  struct pid_link pids[PIDTYPE_MAX];  //进程号，进程组标识符号和会话标识符号
  struct  task_struct __rcu *real_parent;  //指向真实的父进程
  struct  task_struct __rcu *parent;  //指向父进程，如果当前进程被其他进程使用ptrace跟踪，那么父进程就是跟踪进程
  struct task_struct *group_leader;  //指向线程组的组长
  const struct cred __rcu *real_cred;  //真实权限证书
  const struct cred __rcu *cred; //有效客体证书，可被临时改变
  char comm[TASK_COMM_LEN]; //进程名称
  int prio, static_prio, normal_prio;  //调度策略和优先级
  unsigned int rt_priority;
  unsigned int policy;
  struct mm_struct *mm, *active_mm;
  struct fs_struct *fs; //文件系统信息，主要是进程的根目录和当前工作目录
  struct files_struct *files;  //打开文件表
  struct nsproxy *nsproxy;  //命名空间
  struct signal_struct *signal; // 信号处理相关
  struct sighand_struct *sighand;
  sigset_t blocked, real_blocked;
  sigset_t saved_sigmask;
  struct sigpending pending;
  struct sysv_sem sysvsem; //UNIX系统5信号量和共享内存
  struct sysv_shm sysvshm;
}

1.3 命名空间

和虚拟机相比，容器是一种轻量级的虚拟化技术，直接使用宿主机的内核，使用命名空间隔离资源。

通过以下两种方法创建新的命名空间：

1. 调用clone创建子进程时，使用标志位控制子进程是共享父进程的命名空间还是创建新的。
2. 调用unshare创建新的命名空间，不和已存在的任何其他进程共享命名空间。
   进程也可通过系统调用setns，绑定到一个已经存在的命名空间。
   task_struct中的nsproxy成员指向一个命名代理空间，命名空间代理包含除了用户以外的所有其他命名空间的地址。如果父进程和子进程共享除了usr之外的所有其他命名空间，那么共享同一个命名空间代理。

struct nsproxy {
    atomic_t count;
    struct uts_namespace *uts_ns;
    struct ipc_namespace *ipc_ns;
    struct mnt_namespace *mnt_ns;
    struct pid_namespace *pid_ns_for_children;
    struct net       *net_ns;
};

进程号命名空间用来隔离进程号，每个进程号命名空间独立分配进程号，进程号命名空间按层次组织成一棵树，初始进程号命名空间是树的根，对应全局变量init_pid_ns，所有进程默认属于初始进程号命名空间。

1.4 进程标识符

进程标识符：进程所属的进程号命名空间到根的每层命名空间，都会给进程分配一个进程标识符。
线程组标识符：多个共享用户虚拟地址空间的进程组成一个线程组，线程组中的主进程称为组长，线程组标识符就是就是组长的进程标识符。
当系统调用clone传入标志CLONE_THREAD以创建新进程时，新进程和当前进程属于一个线程组。
进程组标识符：多个进程可以组成一个进程组，进程组标识符就是组长的进程标识符。进程可以使用系统调用setpgid创建或者加入一个进程组。会话和进程组被设计用来支持shell作业控制，shell为执行单一命令或者管道的进程创建一个线程组。进程组简化了系那个进程组的所有成员发送信号的操作。
在进程组间移动，调用进程，pid指定的进程及目标进程组必须在同一个会话之内。
会话标识符：多个进程组可以组成一个会话。
Linux是多用户操作系统，用户登陆时会创建一个会话，用户启动的所有进程都属于这个会话。登陆shell是会话首进程。
进程描述符task_struct中，pid成员存储全局进程号，即初试进程号命名空间分配的进程号。
pids[PIDTYPE_PID].pid指向结构体pid，存放其他PID命名空间分配的进程号。
pids[PIDTYPE_PGID].pid指向进程组组长的结构体pid。
pids[PIDTYPE_SID].pid指向会话首进程的结构体pid。

struct pid
{
    atomic_t count;
    unsigned int level;
    /* lists of tasks that use this pid */
    struct hlist_head tasks[PIDTYPE_MAX];
    struct rcu_head rcu;
    struct upid numbers[1];
};

pid结构体中，成员count是引用计数，level是进程所属的进程号命名空间的层次，numbers数组中元素numbers[i].nr是进程号命名空间分配的进程号，numbers[i].ns指向进程号命名空间的结构体pid_namespace,numbers[i].pid_chain用来把进程加入进程号散列表pid_hash,根据进程号和命名空间计算散列值。

1.5 进程关系

一个进程的所有子进程被链接在一条子进程链表上，头节点是父进程描述符的成员children,链表节点是子进程的成员sibling。
一个线程组的所有线程链接在一条线程链表上，头节点是组长的成员thread_group,链表节点是线程成员thread_group。线程的成员group_leader指向组长的进程描述符，成员tgid是线程组标识符，成员pid存放自己的进程标识符。

2 创建新的进程

在linux内核中，新进程时从一个已经存在的进程复制出来的。系统调用fork和clone可以创建新的进程。
fork: 子进程是父进程的一个副本，采用了写时复制的技术。
clone: 可以精确地控制子进程和父进程共享了哪些资源。
创建新进程的进程p和生成的新进程的关系有三种情况：
(1)新进程是进程p的子进程。
(2)如果clone传入标志位CLONE_PARENT,那么新进程和进程p拥有同一个父进程。
(3)如果clone传入标志位CLONE_THREAD,那么新进程和进程p属于同一个线程组。
创建新进程的系统调用，会把工作委托给函数_do_fork。
vfork与fork的主要区别：
(1)fork:子进程拷贝父进程的数据段，代码段；vfork:子进程与父进程共享数据段。
(2)fork:父子进程的执行次序不确定；vfork:保证子进程先运行，在调用exec 或exit 之前与父进程数据是共享的，在它调用exec 或 exit 之后父进程才可能被调度运行；如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

2.1 _do_fork

函数原型：

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);

参数如下：
(1) 参数clone_flags是clone标志，最低字节指定了进程退出时发给父进程的信号，创建线程时，该参数的最低字节是0，表示线程退出时不需要向父进程发送信号。
(2)参数stack_start,stack_size只在创建线程时有意义，用来指定新线程的用户栈的起始地址和大小。stack_size已废弃。
(3)如果参数clone_flags指定了标志位CLONE_PARENT_SETTID,那么调用线程需要把新线程的进程标识符写到参数parent_tidptr指定的位置。
(4)参数child_tidptr只有在创建线程的时候有意义，存放新线程保存自己的进程标识符的位置。
(5)参数tls只在创建线程时有意义，如果参数clone_flags指定了标志位CLONE_SETTLS,那么参数tls指定新线程的线程本地存储地址。

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)
{
    ...
    p = copy_process(clone_flags, stack_start, stack_size,
             child_tidptr, NULL, trace, tls, NUMA_NO_NODE);

    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(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);
    } else {
        nr = PTR_ERR(p);
    }
    return nr;
}

主要流程如下：
(1)调用copy_process以创建新进程。
(2)调用wake_up_new_task以唤醒新进程。
(3)如果系统调用是vfork，那么当前进程等待子进程装载程序。

2.2 copy_process

主要流程示意如下：

copy_process
  -->检查clone标志是否冲突
  -->dup_task_struct：为新进程的进程描述符分配内存，分配内核栈
  -->检查用户创建的进程数量是否超过了限制
  -->copy_creds：复制或共享证书，证书存放进程的用户标识符，组标识符和访问权限
  -->检查线程数量是否超过限制
  -->初试化task_struct
  -->shed_fork：为新进程设置调度器相关的参数
  -->复制或共享资源
    -->copy_semundo：同一个线程组的线程之间共享UNIX5信号量
    -->copy_files：复制或共享打开文件表，同一个线程组之间的线程共享打开文件表
    -->copy_fs：复制或共享文件系统信息，同一个线程组之间才会共享
    -->copy_sighand：复制或共享信号处理程序，同一个线程组之间才会共享
    -->copy_ signal：复制或共享信号结构体，同一个线程组之间才会共享
    -->copy_mm：复制或共享虚拟内存，同一个线程组之间才会共享
    -->copy_namespaces：创建或共享命名空间
    -->copy_io：创建或共享I/O上下文
    -->copy_thread_tls：复制当前线程寄存器的值，并修改一部分
  -->设置进程号和进程关系

2.2.1 补充：thread_info 结构体

struct thread_info {
    unsigned long flags;        /* low level flags */
    int preempt_count;      /* 0 => preemptable, <0 => BUG */
    struct task_struct *task;   /* main task structure */
    mm_segment_t addr_limit;    /* thread address space */
    __u32 cpu;          /* current CPU */
    unsigned long thr_ptr;      /* TLS ptr */
};

成员flags：底层标志位，常用的标志位是_TIF_SIGPENDING和_TIF_NEED_RESCHED,前者表示进程有需要处理的信号，后者表示需要重新调度。
preempt：抢占计数器。0表示可抢占，小于0是缺陷。
addr_limit：地址限制。

2.2.2 补充：copy_thread_tls保存寄存器

从用户模式切换到内核模式：用户模式的各种寄存器保存在内核栈底部的结构体pt_regs中。
进程调度器调度进程时：切换出去的进程把寄存器值保存在进程描述符的成员thread中。
因为不同处理器架构的寄存器不同，所以各种处理器架构需要自己定义结构体pt_regs和thread_struct，实现copy_thread_tls。
copy_thread_tls把主要工作委托给copy_thread，copy_thread代码如下：

int copy_thread(unsigned long clone_flags, unsigned long stack_start,
        unsigned long stk_sz, struct task_struct *p)
{
    struct pt_regs *childregs = task_pt_regs(p);

    memset(&p->thread.cpu_context, 0, sizeof(struct cpu_context));
    fpsimd_flush_task_state(p);

    if (likely(!(p->flags & PF_KTHREAD))) {
        *childregs = *current_pt_regs();
        childregs->regs[0] = 0;
        asm("mrs %0, tpidr_el0" : "=r" (*task_user_tls(p)));

        if (stack_start) {
            if (is_compat_thread(task_thread_info(p)))
                childregs->compat_sp = stack_start;
            /* 16-byte aligned stack mandatory on AArch64 */
            else if (stack_start & 15)
                return -EINVAL;
            else
                childregs->sp = stack_start;
        }
        if (clone_flags & CLONE_SETTLS)
            p->thread.tp_value = childregs->regs[3];
    } else {
        memset(childregs, 0, sizeof(struct pt_regs));
        childregs->pstate = PSR_MODE_EL1h;
        p->thread.cpu_context.x19 = stack_start;
        p->thread.cpu_context.x20 = stk_sz;
    }
    p->thread.cpu_context.pc = (unsigned long)ret_from_fork;
    p->thread.cpu_context.sp = (unsigned long)childregs;

    ptrace_hw_copy_thread(p);

    return 0;
}

(1) 首先把新进程的进程描述符的成员thread.cpu_context清零，在调度进程时切换出去的进程使用这个成员保存通用寄存器的值。
(2)假如是新进程是用户进程：
a.子进程把当前进程内核栈底部的pt_regs结构体复制一份。当前进程从用户模式切换到内核模式时，把用户模式的各种寄存器保存一份存放在内核栈底部的pt_regs结构体中。
b.把子进程的X0寄存器设置为0，因为X0寄存器存放系统调用的返回值，调用fork或clone后，子进程返回0。
c.把子进程的TPIDR_EL0寄存器设置为当前进程的TPIDR_EL0寄存器。
d.如果使用系统调用clone创建线程时指定了用户栈的起始地址，那么新线程的栈指针寄存器SP_EL0设置为用户栈的起始地址。
e.如果使用系统调用clone创建线程时设置了标志位CLONE_SETTLS，那么把新线程的TPIDR_EL0寄存器设置为系统调用clone第四个参数tls指定的线程本地存储的地址。
(3)如果内核线程：
a.把子进程内核栈底部的pt_regs结构体清0。
b.设置子进程状态：使用SP_EL1和异常等级设为1.
c.把子进程的X19寄存器设置为线程函数的地址，stack_start存放线程函数的地址，即用来创建内核线程的函数kernel_thread的第一个参数fn。
(4)把子进程的X20寄存器设置为传给线程函数的参数。
(5)设置子进程的thread.cpu_context.pc和thread.cpu_context.sp。使子进程被调度唤醒时，从ret_from_fork开始执行；设置SP_EL1为内核栈底部pt_regs结构体的起始地址。

2.3 wake_up_new_task

设置进程状态；在smp系统上选择一个负载最轻的处理器；检查新进程是否可以抢占当前进程；调用调度类的task_woken方法。

3 新进程执行

3.1 新进程第一次执行

新进程第一次执行，是从函数ret_from_fork开始执行。ARM64架构定义的ret_from_fork函数如下：

ENTRY(ret_from_fork)
    bl  schedule_tail
    cbz x19, 1f             // not a kernel thread
    mov x0, x20
    blr x19
1:  get_thread_info tsk
    b   ret_to_user
ENDPROC(ret_from_fork)

(1)调用schedule_tail，为上一个进程执行清理操作。
(2)根据x19寄存器的值是否为0，判断当前进程时用户进程还是内核线程。
(3) 内核线程：设置参数跳转到x19。
(4) 用户进程：设置thread_info，并跳转到ret_to_usr，返回到用户模式。

3.2 装载程序

返回到用户模式后，返回值为0。之后，通过系统调用execve装载程序。
Linux内核提供了连个装载程序的系统调用，分别为execve和execveat，两个系统调用最终都调用函数do_execveat_common。

do_execveat_common
  -->do_open_execat：打开可执行文件
  -->sched_exec：因为此时进程在内存和缓存中的数据最少，适合进行处理器负载均衡
  -->bprm_mm_init：创建新的内存描述符，分配临时的用户栈
    -->mm_alloc
    -->__bprm_mm_init
  -->prepare_binprm：设置进程证书
  -->把文件名称、环境字符串和参数字符压倒用户栈
  -->exec_binprm：尝试注册过的每种二进制格式的处理程序，直到正确识别为止
    -->search_binary_handler

3.2.1

在linux内核中，每种二进制格式都表示为下面的数据结构的一个实例。

struct linux_binfmt {
    struct list_head lh;
    struct module *module;
    int (*load_binary)(struct linux_binprm *);
    int (*load_shlib)(struct file *);
    int (*core_dump)(struct coredump_params *cprm);
    unsigned long min_coredump; /* minimal dump size */
};

每种二进制格式必须提供下面三个函数：
(1)load_binary：用来加载普通程序。
(2)load_shlib：用来加载共享库。
(3)core_dump：用来在进程异常退出时生成核心转储文件。
每种二进制格式，必须通过使用函数register_binfmt向内核注册。

3.2.2 装载elf程序

load_elf_binary函数负责装载elf程序，主要步骤如下：

load_elf_binary
  -->检查magic number
  -->load_elf_phdrs：读取程序的首部段
  -->查找和处理解释器段（在已读取的程序首部段中查找）
  -->检查并读取解释器的程序首部段
  -->flush_old_exec：终止线程组的其他线程，释放旧的用户虚拟地址
  -->setup_new_exec：设置内存布局，从两种内存布局中选择一种。
  -->setup_arg_pages：设定用户栈，并更新用户栈的标志位和访问权限，把用户栈移动到最终到最终位置，并扩大
  -->把所有可加载段映射到进程的虚拟地址空间
  -->setbrk：把未初始化数据段bss映射到进程的用户虚拟地址空间，并填充0，并设置堆的起始虚拟地址
  -->得到程序的入口：解释器的入口or目标程序本身的入口
  -->create_elf_tables：设置解释器传来的复制向量，envp，argv和argc
  -->start_thread：设置pt_regs中的pc和sp

4 进程退出

进程退出分两种情况：进程主动退出和终止进程。
Linux内核提供了以下两个使进程主动退出的系统调用：
(1)exit用来使一个线程退出。
(2)exit_group用来使一个线程组的所有线程退出。
终止进程时通过给进程发送信号实现的，Linux内核提供了发送信号的系统调用：
(1)kill用来发送信号给进程或进程组。
(2)tkill用来发送信号给线程，参数tid是线程标识符。
(3)tgkill用来发送信号给线程，参数tgid是线程组标识符，参数tid是线程标识符。

当进程退出时，根据父进程是否关注子进程退出事件，处理存在如下差异：
(1)如果父进程关注子进程退出事件，那么子进程退出时释放各种资源，只留下一个空的进程描述符，变成僵尸进程，发送信号SIGCHLD通知父进程，父进程在查询进程终止的原因以后回收子进程的进程描述符。
(2)如果父进程不关注子进程退出事件，那么进程退出时释放各种资源，释放进程描述符，自动消失。

Linux内核提供了3个系统调用来等待子进程的状态改变，状态改变包括：子进程终止，信号SIGSTOP使子进程停止执行，或者信号SIGCONT使子进程继续执行。这3个系统调用如下：
(1)waitpid
(2)waittid
(3)wait4(已废弃)
子进程退出后需要父进程回收进程描述符，如果父进程先退出，子进程成为“孤儿”，需要其他进程来进行领养，按以下顺序选择领养“孤儿”的进程：
(1)如果进程属于一个线程组，且该线程组还有其他线程，那么任意选一个线程。
(2)选择最亲近的充当“替补领养者”的祖先进程，进程可以使用系统调用prctl把自己设置为“替补领养者”。
(3)选择进程所属的进程号命名空间中的1号进程。

4.1 exit_group

exit_group系统调用把主要工作委托给do_group_exit。

void
do_group_exit(int exit_code)
{
    struct signal_struct *sig = current->signal;

    BUG_ON(exit_code & 0x80); /* core dumps don't get here */

    if (signal_group_exit(sig))
        exit_code = sig->group_exit_code;
    else if (!thread_group_empty(current)) {
        struct sighand_struct *const sighand = current->sighand;

        spin_lock_irq(&sighand->siglock);
        if (signal_group_exit(sig))
            /* Another thread got here before we took the lock.  */
            exit_code = sig->group_exit_code;
        else {
            sig->group_exit_code = exit_code;
            sig->flags = SIGNAL_GROUP_EXIT;
            zap_other_threads(current);
        }
        spin_unlock_irq(&sighand->siglock);
    }

    do_exit(exit_code);
    /* NOTREACHED */
}

(1)如果线程组正在退出，那么从信号结构体的成员group_exit_code取出退出码。
(2)如果线程未处于正在退出的状态，并且线程组至少有两个线程，那么处理如下：
a. 关中断并申请锁。
b.如果线程组正在退出，那么从信号结构体的成员group_exit_code取出退出码。
c.如果线程组未处于正在退出的状态，那么把退出码保存在信号结构体的成员group_exit_code中，传递给其他线程、把线程组设置正在退出的标志、向线程组的其他线程发送kill信号，然后唤醒线程，让线程处理kill信号。
(3)当前线程调用函数do_exit以退出。
函数do_exit的执行流程：
(1)释放各种资源，把资源对应的数据机构的引用计数减一，如果引用计数变成0，那么释放数据结构。
(2)调用函数exit_notify，先为成为：“孤儿”的子进程选择“领养者”，然后把自己的死讯通知父进程。
(3)把进程状态设置为死亡。
(4)调用__schedule调度进程。

5 进程调度

5.1 进程的状态

进程主要有以下状态：
(1)就绪状态：进程描述符中state为TASK_RUNNING(linux内核没有严格区分就绪态和运行态)，正在运行队列中等待调度器调度。
(2)运行状态：进程描述符中state为TASK_RUNNING，被调度器选中，正在处理器上运行。
(3)轻度睡眠：也称为可打断的睡眠状态，进程描述符的字段state是TASK_INTERRUPTIBLE，可以被信号打断。
(4)中度睡眠：进程描述符的字段state是TASK_KILLABLE，只能被致命的信号打断。
(5)深度睡眠：也称为不可打断的睡眠状态，进程描述符的字段state是TASK_UNINTERRUPTIBLE，不能被信号打断。
(6)僵尸状态：进程描述符的字段state是TASK_DEAD，字段exit_state是EXIT_ZOMBIE。
如果父进程关注子进程退出事件，那么子进程在退出时发送SIGCHLD信号通知父进程，变成僵尸进程，父进程在查询子进程的终止原因之后回收子进程的进程描述符。
(7)死亡状态：进程描述符的字段state是TASK_DEAD，字段exit_state是EXIT_DEAD。如果父进程不关注子进程退出时间，那么子进程退出时自动消亡。

5.2 进程调度

5.2.1 调度策略

Linux内核支持的调度策略如下：
(1)限期进程使用限期调度策略(SCHED_DEADLINE)。该策略有三个参数，运行时间runtime，截止期限deadline和周期period，每个周期运行一次，在截止期限之前执行完，一次运行时间长度是runtime。
(2)实时进程支持两种调度策略：先进先出调度(SCHED_FIFO)和轮流调度(SCHED_RR)。先进先出调度没有时间片，如果没有更高优先级的实时进程，并且不休眠，进程退出之前将一直霸占处理器。轮流调度有时间片，进程用完时间片以后加入优先级对应运行队列的微博，把处理器让给优先级相同的其他实时进程。
(3)普通进程支持两种调度策略：标准轮流分时(SCHED_NORMAL)和空闲(SCHED_IDLE)。标准轮流分时策略使用完全公平调度算法，把处理器时间公平地分配给每个进程。空闲调度策略用来执行优先级非常低的后台作业，优先级比使用标准轮流分时策略和相对优先级为19的普通进程还要低。

5.2.2 进程优先级

限期进程的优先级比实时进程高，实时进程的优先级比普通进程高。
限期进程的优先级是-1。
实时进程的实时优先级是1 ~ 99，优先级数值越大，表示优先级越高。
普通进程的静态优先级是100 ~ 139，优先级值越小，表示优先级越高。相对优先级nice值，取值范围-20 ~ 19，优先级=120 + nice。
优先级继承：如果优先级低的进程占有实时互斥锁，优先级高的进程等待实时互斥锁，将占有实时互斥锁的进程的优先级临时提升到等待实时互斥锁的进程的优先级。

5.2.3 调度类

Linux内核抽象了一个调度类sched_class，目前实现了5种调度类。

(1)停机调度类：停机进程(stop-task)是优先级最高的进程，可以抢占所有其他进程，其他进程不可以抢占停机进程。停机的意思就是使处理器停下来，做更紧急的事。目前只有迁移进程属于停机调度类。
迁移进程：用来把进程从当前处理器迁移到其他处理器，对外伪装为实时优先级99的先进先出实时进程。
(2) 限期调度类：使用红黑树把进程按照对截止日期从小到大排序，每次调度时选择绝对截止期限最小的进程。如果用完它的运行时间，它将让出处理器，并且从运行队列中删除，在下一个周期的开始，重新把它添加到运行队列中。
(3)实时调度类：通过bitmap用来快速查找优先级最高的第一个非空队列。
(4)公平调度类：完全公平调度算法引入虚拟运行时间的概念：
虚拟运行时间 = 实际运行时间 * nice0对应的权重 / 进程的权重。
通过红黑树按虚拟运行时间从小到大排序，每次调度时选择虚拟运行时间最小的进程。
(5)每个处理器上有一个空闲线程，即0号线程。空闲调度类的优先级最低，仅当没有其他进程可以调度的时候，才会调度空闲线程。

5.2.4 运行队列

每个处理器有一个运行队列，结构体是rq，定义的全局变量如下：

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

结构体rq中嵌入了公平运行队列cfs，实时运行队列rt和限期运行队列dl；停机调度类和空闲调度类在每个处理器上只有一个内核线程，不需要运行队列，直接定义成员stop和idle分别指向迁移线程和空闲线程。

struct rq {
  ...
    struct cfs_rq cfs;
    struct rt_rq rt;
    struct dl_rq dl;
  ...
    struct task_struct *curr, *idle, *stop;
  ...
};

5.2.5 任务分组

内核支持的任务分组的方式(需要宏配置)：
(1)自动组，创建会话时会创建一个自动组，会话里面的所有进程是自动组的成员。启动一个终端窗口时就会创建一个会话。
(2)CPU控制组，即控制组(cgroup)的CPU控制器。可以使用cgroup创建任务组和把进程加入任务组。
任务组的结构体是task_group
。默认的任务组是根任务组(全局变量root_task_group)，默认情况下所有进程属于根任务组。
引入任务组后，调度实体是进程或者任务组。
进程描述符中嵌入了公平，实时和限期3种调度实体，成员sched_class指向进程所属的调度类，进程可以更换调度类，并且使用调度类对应的调度实体。

任务组在每个处理器上有公平调度实体，公平运行队列，实时调度实体，实时运行队列，根任务组比较特殊：没有公平调度实体和实时调度实体。
任务组的下级公平(实时)调度实体加入任务组的公平(实时)运行队列，任务的公平(实时)调度实体加入到上级任务组的公平(实时)运行队列。

5.2.6 调度进程

进程调度的核心函数是__schedule，函数原型如下：

static void __sched notrace __schedule(bool preempt)

参数preempt表示是否抢占调度，值为true表示抢占调度，强制剥夺当前进程对处理器的使用权；值为false表示为主动调度，当前进程主动让出处理器，主动调度进程的函数是schedule，它会把主要工作委托给__schedule。
函数__schedule的主要处理过程如下：
(1) 调用pick_next_task以选择下一个进程。

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    const struct sched_class *class = &fair_sched_class;
    struct task_struct *p;
    
    if (likely(prev->sched_class == class &&
           rq->nr_running == rq->cfs.h_nr_running)) {
        p = fair_sched_class.pick_next_task(rq, prev);
        if (unlikely(p == RETRY_TASK))
            goto again;
        if (unlikely(!p))
            p = idle_sched_class.pick_next_task(rq, prev);
        return p;
    }

again:
    for_each_class(class) {
        p = class->pick_next_task(rq, prev);
        if (p) {
            if (unlikely(p == RETRY_TASK))
                goto again;
            return p;
        }
    }
    BUG(); /* the idle class will always have a runnable task */
}

从优先级最高的调度类开始，调度调度类的pick_next_task方法来选择下一个进程。并针对公平调度类做了优化。
(2) 调用context_switch以切换进程。
主要流程：首先switch_mm_irqs_off切换进程的用户虚拟地址空间，然后switch_to负责切换处理器的寄存器。

static inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
           struct task_struct *next)
{
    struct mm_struct *mm, *oldmm;

    prepare_task_switch(rq, prev, next);

    mm = next->mm;
    oldmm = prev->active_mm;
    arch_start_context_switch(prev);

    if (!mm) {
        next->active_mm = oldmm;
        atomic_inc(&oldmm->mm_count);
        enter_lazy_tlb(oldmm, next);
    } else
        switch_mm_irqs_off(oldmm, mm, next);

    if (!prev->mm) {
        prev->active_mm = NULL;
        rq->prev_mm = oldmm;
    }
    lockdep_unpin_lock(&rq->lock);
    spin_release(&rq->lock.dep_map, 1, _THIS_IP_);

    /* Here we just switch the register state and the stack. */
    switch_to(prev, next, prev);
    barrier();
    return finish_task_switch(prev);
}

先判断下一个进程，如果是内核线程(成员mm为空指针)，内核线程没有用户虚拟地址空间，那么需要借用上一个进程的用户虚拟地址空间，把借来的用户虚拟地址空间保存在成员active_mm中。如果下一个进程是用户进程，那么调用函数switch_mm_irqs_off切换进程的用户虚拟地址空间。
函数switch_to是每种处理器架构必须定义的函数负责切换处理器的寄存器。
函数finish_task_switch负责在进程切换后执行清理工作。

5.2.7 调度时机

(1)进程主动调用schedule函数。
(2)周期性调度，抢占当前进程，强迫当前进程让出处理器。
(3)唤醒进程的时候，被唤醒的进程可能抢占当前进程。
(4)创建新进程的时候，新进程可能抢占当前进程。
(5)内核抢占，当前进程在内核模式下运行时可以被其他进程抢占。每个进程的thread_info结构体中有一个类型为int的成员preempt_count，称为抢占计数器；当进程在内核模式下运行时，如果抢占计数器的值不是0，那么其他进程不能抢占。
内核抢占点：在调用preempt_enable开启抢占的时候、在调用local_bh_enable开启软中断的时候、在调用spin_unlock释放自旋锁的时候、在中断处理程序返回内核模式的时候。

5.2.8 带宽管理

(1)限期调度类的带宽管理：每个限期进程都有自己的带宽，不需要更高层次的带宽管理。目前，内核把限期进程的运行时间统计到根实时任务组的运行时间里，限期进程共享实时进程的带宽。
(2)指定实时进程的带宽有两种方式：a.指定全局带宽，带宽包含两个参数是周期和运行时间，即在指定在每个周期内所有实时进程的运行时间总和。b.指定每个实时任务组的带宽。
(3)公平调度类：可以使用周期和限额指定一个公平任务组的带宽。在每个指定的周期内，允许一个任务组最多执行多长时间(即限额)。当任务组在一个周期内用完了带宽时，这个任务组将会被节流，不允许继续运行，直到下个周期。

6进程的安全上下文

一个对象操作另一个对象时通常要做安全性检查，例如进程操作一个文件，要检查进程是否有权限操作文件。一个对象访问另一个对象，前者称为主体，后者称为客体。
证书是访问对象所需权限的抽象，主体提供自己权限的证书，客体提供访问自己所需权限的证书，根据主客体提供的证书和操作做安全性检查。
证书用数据结构cred表示。在进程描述符中，realc_cred指向主体和真实客体证书，cred指向有效客体证书。通常情况下，cred和real_cred指向相同的证书，但cred可能被临时修改为另一个证书。

真实用户标识符和真实组标识符：标识了进程属于哪一个用户和哪一个组，即登陆时使用的用的用户标识符和用户所属的第一个组标志符。
有效用户标识符和有效组标识符：用来确定进程是否有权限访问共享资源，和大多数UNIX系统不同的是，访问文件时Linux使用文件系统标识符和文件系统组标识符。
通常情况下，有效用户标识符和真实用户标识符相同，有效组标识符和真实组标识符相同。但是，如果为可执行文件设置了set-user-ID模式位，那么在创建进程的时候，进程的有效用户标识符等于可执行文件的用户标识符；如果为可执行文件设置了set-group-ID模式位，那么在创建进程的时候，进程的有效组标识符等于可执行文件的组标识符。
保存用户标识符和保存组标识符：用来保存可执行文件的用户标识符和组标识符。
文件系统用户标识符和文件系统组标识符：它们是Linux私有，和附加组标志符一起用来确定进程是否有权限访问文件。通常情况下，文件系统用户标识符和有效用户标识符相同，文件系统标识符和有效标识符相同。进程可以调用setfsuid以设置和有效用户标识符不同的文件系统用户标识符，调用setfsgid以设置和有效组标识符不同的文件系统组标识符。
附近组标识符：访问文件和其他共享资源时用来检查权限的附加组标识符的集合。进程可以调用getgroups以读取附加组标识符的集合，可以调用setgroups以修改附加组标识符的集合。