一、进程管理基本概念

在单处理器系统上，在给定时刻只有一个程序可以运行，在多处理器系统上，可以真正并行运行的进程数据，取决于物理CPU的数目；

进程优先级

在比较粗糙的划分中，进程分为实时进程和非实时进程；

1. 硬实时进程具有严格的时间限制，某些任务必须在指定的时间内完成；

2. 软实时进程是硬实时进程的一种弱化形式，尽快需要快速得到结果，但是仍然可以稍微延迟执；

3. 大多数进程是没有特定时间约束的普通进程，它们可以通过重要性来分配优先级；

下面为CPU时间分配图，进程的运行按照时间片调度，分给进程的时间片份额与其相对重要性相当；系统中的时间流动对应圆盘转动，CPU则对应圆周旁的扫描器；最终效果是，尽管所有进程都有机会运行，但是重要的进程会比次要的进程得到更多的CPU时间；

这种方式称之为抢占式多任务处理；各个进程都得到一定的时间运行，在运行时间到期后，内核会从进程收回控制权，让一个不同的进程运行，而不考虑前一个进程执行的上一个任务；被抢占进程的运行环境都会保存起来，在该进程恢复执行时，其进程环境也完全恢复；时间片长度会根据进程的重要性不同而变化；

进程生命周期

当调度器在进程之间切换时，必须知道系统中每个进程的状态；

进程可能有以下几种状态：

1. 运行：此刻进程正在执行；

2. 等待：进程能够运行，但是没有得到许可，因为CPU分配给了另外一个进程，调度器可以在下一次任务切换时选择该进程；

3. 睡眠：该进程正在睡眠，无法运行，因为它在等待一个外部事件，调度器无法在下一次任务切换时选择该进程；

4. 终止：程序执行终止后的状态；

5. 僵尸：子进程终止，但是父进程没有调用wait4回收资源；

路径1：进程必须等待某个事件发生，状态由运行态切换到睡眠态；

路径2：调度器从该进程上收回cpu资源时，状态由运行态切换到等待态；

路径3：进程无法从睡眠态之间切换到运行态，而是在所等待的事件发生后，先变回等待态；

路径4：调度器分配CPU时间给当前进程，则其状态由等待态切换到运行态；

路径5：程序执行终止后，状态由运行态切换到终止态；

抢占式多任务处理

Linux进程管理结构中还需要两种状态：用户态和内核态；

进程通常都处于用户态，只能访问他们自身的数据，无法干扰系统中其他应用程序；

如果进程想要访问系统的数据或者功能，需要从用户态切换到内核态；切换通过下面两种方式：

1. 系统调用，由进程主动发起，陷入内核态；

2. 中断，自动触发，其发生的次数多少不可预测；

内核的抢占调度模型建立了下面的层次，来判断哪些进程状态可被其他状态抢占；

1. 普通进程总可能被抢占，甚至由其他进程抢占；

2. 核心态的系统调用，其他进程无法抢占，但是中断可以抢占系统调用；

3. 中断可以抢占用户态和内核态的进程，其具有最高的优先级；

进程状态task_struct->state

内核涉及到进程相关的算法都围绕着task_struct结构建立，其成员将进程和内核子系统联系起来；

进程状态，涉及字段如下：

1 struct task_struct {
2 volatile long state;
3 }

state指定了进程的当前状态，可使用下面之之一：

TASK_RUNNING-进程处于可运行状态，进程可能已经由调度器分配了CPU时间正在运行，也可能在等待调度器进行下一次调度自己；该状态确保进程可以立即运行，无需等待外部事件；

TASK_INTERRUPTIBLE-进程需要等待某事件或者其他资源，进入可中断的睡眠状态，在内核发送信号给该进程表明事件已发生时，进程状态变为TASK_RUNNING，只要调度器选中该进程即可恢复执行；

TASK_UNINTERUPTIBLE-用于因内核指示而停用，进入不可中断的睡眠状态；这个状态的进程不能由外部信号唤醒，只能由内核亲子唤醒；

TASK_STOPPED-表示进程特意停止运行；

TASK_TRACED-用于区分调试进程和正常进程；

下面常量既可用于state的进程状态字段，也可用于exit_state字段，后者明确的用于退出状态；

EXIT_ZOMBIE-僵尸状态；

EXIT_DEAD-wait系统调用已经发出，而进程完全从系统移除之前的状态，只有多个线程对同一个进程发出wait调用时，该状态才有意义；

进程资源限制state->signal->rlim[]

Linux提供资源限制机制，对进程使用系统资源施加某些限制，其结构定义如下：

1 struct rlimit {
2 __kernel_ulong_t rlim_cur;
3 __kernel_ulong_t rlim_max;
4 };

rlim_cur-进程当前资源限制，称之为软限制；

rlim_max-该限制的最大允许值，称之为硬限制；

系统调用setrlimit来增减当前限制，但不能超过rlim_max指定的值，getrlimit系统调用用于检查当前限制；

1 #include <sys/time.h>
2 #include <sys/resource.h>
3
4 int getrlimit(int resource, struct rlimit *rlim);
5 int setrlimit(int resource, const struct rlimit *rlim);

进程资源限制参数如下：

如果某类资源没有使用限制（默认设置），则将rlmi_max设置为RLIM_INFINITY；例外情况如下：

1. 打开文件的数目-默认值是1024；

2. 每个用户的最大进程数，定义为max_threads/2；max_threads是一个全局变量，指定了在把八分之一可用内存用于管理线程信息的情况下，可以创建的线程数目；在计算时，提前给定了20个线程的最小可能的内存用量；

进程的产生

新进程使用fork和exec系统调用产生

1. fork生成当前进程的一个相同副本，该副本称之为子进程；

2. exec从一个可执行的二进制文件加载一个应用程序，来替代当前运行的进程；

Linux还提供了clone系统调用，与fork类似，但新进程不独立于父进程，可以与父进程共享某些资源，可以指定需要共享和复制的资源种类；clone用于实现线程，但仅仅该系统调用还不足以做到这点，还需要用户空间库才能完整的实现线程；

进程的退出

进程必须用exit系统调用终止，这使得内核有机会将该进程使用的资源释放回系统；该函数的实现就是将各个引用计数减1，如果引用计数为0，则说明没有进程继续使用对应的结构，那么将相应的内存区域返还给内存管理模块；

进程ID号

进程总会分配一个号码用于其命名空间的唯一标识，称为PID；用fork或者clone产生的每个进程都有内核自动的分配了一个新的唯一的PID；

分配一个空闲的PID，本质上等同于寻找位图中第一个值0的比特，接下来将该比特设置为1；反之，释放一个PID可以通过将对应的比特从1设置为0来实现；

除了PID之外，还有以下几种ID类型：

1. 线程组ID（TGID）：处于某个线程组中的所有进程都有统一的线程组ID；如果进程没有线程组，那么其PID和TGID相同；线程组中的主进程被称为组长，通过clone创建的线程的task_struct->group_leader成员指向组长的task_struct；

2. 进程组ID：独立进程可以合并成进程组（使用setpgrp系统调用），进程组成员的task_struct->pgrp属性都是相同的，即进程组组长的PID；进程组简化了向组所有成员发送信号的操作；另，用管道连接的进程包含在同一个进程组中；

3. 会话ID：几个进程组可以合并成一个会话；会话中所有进程都有相同的会话ID，保存在task_struct->session成员中；会话ID可以使用setsid系统调用设置；

对于命名空间而言，子命名空间中的所有PID对父命名空间是可见的，但是子命名空间无法看到父命名空间的PID；为此，需要区分局部ID和全局ID；

全局ID：内核本身和初始命名空间中的唯一ID号；

局部ID：属于某个特定命名空间，不剧本全局有效性；

二、进程调度

总览

进程调度的总览图如下，当进程被标记为运行状态时，会加入到就绪队列中；队列中的调度实体(进程)维护自己的虚拟时间，该虚拟时间与就绪队列虚拟时间的差值作为红黑树的键值，将调度实体存入红黑树中，其中左下节点为键值最小的节点，最急需被调度，越向右节点的优先级越低；

调度子系统总图如下，进程调度激活有两种方式：一种是直接的，如进程打算睡眠或者其他原因放弃CPU；另一种是通过周期性机制，以固定的频率运行，不时的检测是否有必要进行进程切换；

当需要进行切换时，调度器调用调度类中实现的代理方法，从就绪队列中选取一个进程，并完成任务切换；

这里调度器本身不涉及任何进程管理，工作都会委托给调度器类（比如完全公平调度器类）；

数据结构

task_struct成员

一些进程调度相关的成员如下：

/*

动态优先级，调度器考虑的优先级，比如进程需要提高优先级，

而保证静态优先级和普通优先级不受影响，则使用该字段

*/

int prio;

/* 静态优先级，进程启动时分配，也可以通过系统调用修改 */

int static_prio;

/* 普通优先级，基于静态优先级和调度策略计算得出，子进程会集成父进程的普通优先级 */

int normal_prio;

/* 实时优先级，这个值越大优先级越高，不同于nice值 */

unsigned int rt_priority;

/* 该进程所属的调度器类 */

const struct sched_class *sched_class;

/* 调度实体 */

struct sched_entity se;

/* 实时调度实体 */

struct sched_rt_entity rt;

/*

调度策略

SCHED_NORMAL-普通进程

SCHED_BATCH-用于次要进程，用于非交互，cpu使用密集的批处理进程

SCHED_IDLE-用于次要进程，该类进程重要性比较低，对应的权重总是最小的

上面三个为完全公平调度器使用

SCHED_RR-实现了循环方法

SCHED_FIFO-使用先进先出机制

上面两个为实时调度器使用

*/

unsigned int policy;

int nr_cpus_allowed;

/* 位域，用于限制该进程可以在哪些cpu上运行 */

cpumask_t cpus_allowed;

调度器类

调度器类定义了一些函数，调度类实例实现这些函数，当调度放生时，会实际调用实例的调度类函数来执行具体的调度任务；

struct sched_class {

const struct sched_class *next;

/* 向就绪队列添加新进程 */

void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);

/* 进程从就绪队列中移除 */

void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);

/* 自愿放弃处理器 */

void (*yield_task) (struct rq *rq);

bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

/* 新进程抢占当前进程 */

void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

/* 选择下一个将要运行的进程 */

struct task_struct * (*pick_next_task) (struct rq *rq,

struct task_struct *prev,

struct rq_flags *rf);

/* 一个进程代替当前进程之前调用 */

void (*put_prev_task) (struct rq *rq, struct task_struct *p);

/* 调度策略发生变化时调用 */

void (*set_curr_task) (struct rq *rq);

/* 每次激活周期性调度时调用 */

void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);

void (*task_fork) (struct task_struct *p);

void (*task_dead) (struct task_struct *p);

void (*switched_from) (struct rq *this_rq, struct task_struct *task);

void (*switched_to) (struct rq *this_rq, struct task_struct *task);

void (*prio_changed) (struct rq *this_rq, struct task_struct *task,int oldprio);

unsigned int (*get_rr_interval) (struct rq *rq, struct task_struct *task);

void (*update_curr) (struct rq *rq);

#define TASK_SET_GROUP 0

#define TASK_MOVE_GROUP 1

#ifdef CONFIG_FAIR_GROUP_SCHED

void (*task_change_group) (struct task_struct *p, int type);

#endif

};

就绪队列

就绪队列是核心调度器管理活动进程的主要数据结构，每个cpu都有自身的调度队列，每个进程只出现在一个调度队列中；多个cpu同时运行一个进程是不可能的，注意，但不同cpu可以同时运行由一个进程产生的多个线程；

就绪队列中嵌入了特定调度类的子就绪队列，用于管理调度的进程；

struct rq {

/* 队列上可运行的进程数 */

unsigned int nr_running;

#define CPU_LOAD_IDX_MAX 5

unsigned long cpu_load[CPU_LOAD_IDX_MAX];

/* 就绪队列的当前负荷 */

struct load_weight load;

/* 子就绪队列 */

struct cfs_rq cfs;

struct rt_rq rt;

struct dl_rq dl;

/* 当前运行进程和idle进程 */

struct task_struct *curr, *idle, *stop;

}

系统中所有就绪队列都在runqueues数组中，该数组中的每个队列都对应着一个cpu，即每个cpu一个就绪队列；

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

struct sched_entity {

/* For load-balancing: */

/* 实体的权重，决定了各个实体占总负荷的比例 */

struct load_weight load;

/* 红黑树节点 */

struct rb_node run_node;

struct list_head group_node;

/* 标志当前实体是否在调度器上调度 */

unsigned int on_rq;

/* 调度开始时间 */

u64 exec_start;

/* 进程运行消耗的时间 */

u64 sum_exec_runtime;

/* 进程消耗的虚拟时间 */

u64 vruntime;

/* 上一次调度进程消耗的时间 */

u64 prev_sum_exec_runtime;

u64 nr_migrations;

struct sched_statistics statistics;

};

处理优先级

优先级的内核表示

用户空间可以使用nice值设置进程的静态优先级，内部会调用nice系统调用；nice值在[-20,19]之间，值越低表明优先级越高；

内核使用一个简单的数值范围[0-139]来表示内部优先级，同样是值越低，优先级越高；[0-99]范围的值专供实时进程使用，普通进程的nice值[-20,19]映射到范围[100,139]；实时进程的优先级总比普通进程更高；

计算优先级

各种类型优先级的计算如下表

计算负荷权重

进程的重要性不仅由优先级指定，而且还需要考虑保存在task_struct->se.load中的负荷权重；

内核不仅维护了负荷权重本身，还维护了一组数值，用于计算被负荷权重除的结果；

一般概念为，进程每降低一个nice值，则多获得10%的cpu时间，每升高一个nice值，则放弃10%的cpu时间；为执行该策略，内核将优先级转换为权重值；

如下图所示，内核使用范围[-20,19]的每个nice值都对应一项权重值；

另外，不仅进程，就绪队列也关联到一个负荷权重，每次进程被加到就绪队列时，内核会将进程的权重值加到就绪队列的权重中；

核心调度器

调度器的实现基于两个函数：周期性调度器函数和主调度器函数；这两个函数根据现有进程的优先级分配CPU时间；

周期性调度器

周期性调度器在scheduler_tick中实现，如果系统正在活动中，内核会按照频率HZ自动调用该函数；如果没有进程在等待调度，也可以关闭调度器减少消耗；

周期性调度函数完成两个任务：

1. 管理内核中与整个系统和各个进程调度相关的统计量；

2. 激活负责当前进程调度类的周期性调度方法；

调度器实际上最终调用的是调度类实现的task_tick函数，如，完全公平调度器会在该方法中检查是否进程已经运行太长时间，以避免过程的延迟；

如果当前进程应该被重新调度，那么调度器类方法会在task_struct中设置TIF_NEED_RESCHED标志，以表示该请求，而内核会在接下来的适当时机完成该请求；

主调度器

内核中很多地方，如果要将cpu分配给与当前活动进程不同的另一个进程，都会直接调用主调度函数(schedule)；在从系统调用返回之后，内核也会简称当前进程是否设置了重新调度标志TIF_NEED_RESCHED，如果设置了，内核会调用schedule；该函数假定当前活动进程一定会被另一个进程取代；

schedule函数首先确定当前就绪队列，保存当前活动进程；然后使用调度器类的函数选择下一个应该执行的进程，最后执行硬件级别的进程切换；

static void __sched notrace __schedule(bool preempt)

{

struct task_struct *prev, *next;

unsigned long *switch_count;

struct rq_flags rf;

struct rq *rq;

int cpu;

/* 获取cpu */

cpu = smp_processor_id();

/* 获取cpu对应的就绪队列 */

rq = cpu_rq(cpu);

/* 保存当前活动的进程 */

prev = rq->curr;

schedule_debug(prev);

if (sched_feat(HRTICK))

hrtick_clear(rq);

local_irq_disable();

rcu_note_context_switch(preempt);

/*

* Make sure that signal_pending_state()->signal_pending() below

* can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)

* done by the caller to avoid the race with signal_wake_up().

*/

smp_mb__before_spinlock();

rq_lock(rq, &rf);

/* Promote REQ to ACT */

rq->clock_update_flags <<= 1;

update_rq_clock(rq);

switch_count = &prev->nivcsw;

if (!preempt && prev->state) {

/* 可中断睡眠状态，有接收信号，则提升为运行进程 */

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

prev->state = TASK_RUNNING;

} else {

/* 进程停止活动，会调用dequeue */

deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);

prev->on_rq = 0;

if (prev->in_iowait) {

atomic_inc(&rq->nr_iowait);

delayacct_blkio_start();

}

/*

* If a worker went to sleep, notify and ask workqueue

* whether it wants to wake up a task to maintain

* concurrency.

*/

if (prev->flags & PF_WQ_WORKER) {

struct task_struct *to_wakeup;

to_wakeup = wq_worker_sleeping(prev);

if (to_wakeup)

try_to_wake_up_local(to_wakeup, &rf);

}

}

switch_count = &prev->nvcsw;

}

/* 选择下一个应该执行的进程 */

next = pick_next_task(rq, prev, &rf);

clear_tsk_need_resched(prev);

clear_preempt_need_resched();

/* 选择新进程之后，进行上下文切换 */

if (likely(prev != next)) {

rq->nr_switches++;

rq->curr = next;

++*switch_count;

trace_sched_switch(preempt, prev, next);

/* Also unlocks the rq: */

/* 特定体系结构的上下文切换 */

rq = context_switch(rq, prev, next, &rf);

} else {

rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

rq_unlock_irq(rq, &rf);

}

balance_callback(rq);

}

上下文切换

内核选择新进程之后，必须处理与多任务相关的技术细节，这些细节称为上下文切换；

上下文切换本身通过调用两个特定于处理器的函数完成：

1. switch_mm更换通过task_struct->mm描述的内存管理上下文；该工作的细节取决于处理器，主要包括加载页表，刷出地址转换后备缓冲器，向内存管理单元提供新的信息；

2. switch_to切换处理器寄存器内容和内核栈；

由于用户空间的寄存器内容会在进入核心态时保存在内核栈上，在上下文切换期间无需显示的操作；而因为每个进程首先都是从黑心态开始执行，在返回到用户空间时，会使用内核栈是哪个保存的值自动回复寄存器数据；

内核线程没有自身的用户空间内存上下文，可能在某个随机进程地址空间的上部执行；其task_struct->mm设置为NULL；从当前进程借来的地址空间记录在active_mm中；

0. 权重

进程的优先级与内核的nice值对应，nice值降低对应权重增加；

内核根据进程类型和静态优先级计算权重值；

内核不仅维护进程自身的权重，还维护调度队列的权重，当进程被加入到调度队列时，也要该进程的权重增加到队列权重中；

1. 完全公平调度延时周期

内核可以通过参数sysctl_sched_latency配置一个时间间隔，用来保证每个可运行进程在此间隔下都能至少运行一次；
控制参数sched_nr_latency控制在上述时间间隔下最大的活动进程数目；如果活动进程的数目超过该配置数，则延时间隔时间成比例的进行扩展；

sysctl_sched_latency = sysctl_sched_latency * nr_running / sched_nr_latency

进程分配到的时间根据进程权重在就绪队列中权重的比例进行分配；

slice = slice * se->load / rq->load

2. 周期调度器扫描

周期调度器每个HZ扫描一次，更新当前进程的运行时间，并检查当前进程的运行时间是否超过了进程分配到的运行时间，如果超过了则标记进行重新调度标记；

在系统调用返回、中断返回等时机，会检查该标记，调用注册的实际调度方法的函数（比如公平调度注册的处理函数）处理进程，并进行实际的进程上下文切换；

3. 完全公平调度红黑树

完全公平调度就绪队列将进行维护在一棵红黑树中，调度器每次获取最左侧节点进程进行调度；
调度会从红黑树中删除该节点（仍可通过curr关联队列），当调度结束之后将该节点插入树中；得到调度进程的运行时间增加，使其重新插入的时候右移，未得到调度的进程实际不变，则相对左移，更容易得到调度；

对于权重大的进程，其运行时间增加的慢，向右移动的速度也慢，调度的机会要更大；

睡眠的进程的运行时间保持不变，这样当唤醒之后，位置更靠左，更容易得到调度；