进程优先级
硬实时进程
软实时进程
普通进程
O(1)调度、完全公平调度器
抢占式多任务处理(preemptive multitasking):各个进程都分配到一定的时间段可以执行。时间段到期后，内核会从进程收回控制权，让下一个不同的进程运行，而不考虑前一进程所执行的上一个任务。
进程生命周期
进程状态：运行、等待、睡眠、终止
抢占式多任务处理
从用户态进入核心态的方法：
系统调用：处于核心态时，与当前运行进程相关
硬件中断：处于核心态时，与当前运行进程不相关
普通进程总是可能被抢占，甚至是由其他进程抢占。
如果系统处于核心态并正在处理系统调用，那么系统中的其他进程无法夺取CPU事件
中断可以暂停处于用户态和核心态的进程
在内核2.5开发期间，一个称为内核抢占的选项添加到内核。该选项支持在紧急情况下切换到另一个进程，甚至当前是处于核心态执行的系统调用
进程表示
task_struct结构可分为各个部分，每个部分表示进程的一个特定方面。
- 状态和执行信息，如待决信号、使用的二进制格式、进程ID、到父进程及其他有关进程的指针、优先级和程序执行有关的时间信息
- 有关已经分配的虚拟内存的信息
- 进程身份凭据，如用户ID、组ID以及权限等。
- 文件系统相关信息
- 调度信息
- 进程通信信息
- 信号处理
task_struct中的state字段：
- TASK_RUNNING：进程处于可运行状态（其并不一定是在CPU上执行，进程可能会等待CPU选中他，然后立即运行）
- TASK_INTERRUPTIBLE：针对等待某事件的进程设置
- TASK_UNINTERRUPTIBLE：与TASK_INTERRUPTIBLE一样，但是不能由其他外部信号唤醒，只能由内核亲自唤醒。
- TASK_STOPPED：进程停止
- TASK_TRACED：用于从停止的进程中，将当前被调试的那些进程分离出来
进程类型
clone的工作原理基本上与fork相同，但新进程不是独立于父进程的，而可以与其共享某些资源。（可以指定需要共享和复制的资源种类）
命名空间
命名空间提供了虚拟化的一种轻量级形式，使得我们可以从不同的方面查看运行系统的全局属性。
概念
传统上，在Linux以及其他衍生的UNIX变体中，许多资源是全局的，比如全局PID列表。
本质上，命名空间建立了系统的不同视图。此前的每一项全局资源都必须包装到容器数据结构中，只有资源和包含资源的命名空间构成的二元组仍然是全局唯一的。
新的命名空间可以用下面两种方法创建：
- 在用fokr或clone系统调用创建新进程时，有特定的选项可以控制是与父进程共享命名空间，还是建立新的命名空间
- unshare系统调用将进程的某些部分从父进程分离，其中也包括命名空间。
实现
命名空间的实现需要两个部分：每个子系统的命名空间结构，将此前所有的全局组件包装到命名空间中;将给定进程关联到所属各个命名空间的机制。（子系统此前的全局属性现在封装到命名空间中，每个进程关联道一个选定的命名空间）
请注意，对命名空间的支持必须在编译时启用，而且必须逐一指定需要支持的命名空间。除非指定不同的选项，否则每个进程都会关联到一个默认命名空间，默认命名空间的作用类似于不启用命名空间，所有的属性都相当于全局的。
进程ID号
全局ID:是内核本身和初始命名空间中的唯一ID号。
局部ID：属于某个特定的命名空间。
全局PID和TGID直接保存在task_struct中，分别是task_struct的pid和tgid成员。
PID命名空间表示形式：struct pid_namespace;
<pid_namespace.h>
struct pid_namespace {
...
struct task_struct *child_reaper;
...
int level;
struct pid_namespace *parent;
};PID的管理围绕两个数据结构展开：struct pid 是内核对PID 的内部表示，而struct upid则表示特定的命名空间中可见的信息。
<pid.h>
struct upid {
int nr;
struct pid_namespace *ns;
struct hlist_node pid_chain;
};
struct pid
{
atomic_t count;
/* 使用该pid的进程的列表 */
struct hlist_head tasks[PIDTYPE_MAX];
int level;
struct upid numbers[1];
};内核提供的操作ID的函数，可分为：
- 提供局部ID和对应的命名空间，查找此二元组描述的task_struct结构。(hash局部ID和命名空间，再在hash表中找到对于的upid,在根据upid container_of得到pid（find_pid_ns函数）)
- 给出task_struct、ID 类型、命名空间、取得命名空间局部ID。(首先根据task_struct和ID类型，得到pid结构，然后根据pid与命名空间就能得到局部ID)
在建立一个新进程时，进程可能在多个命名空间中是可见的。对于每个这样的命名空间，都需要生成一个局部PID。（起始于建立进程的命名空间，一直到初始的全局命名空间）(struct pid alloc_pid(struct pid_namespace ns))
PID操作相关函数:
static inline struct pid *task_pid(struct task_struct *task);
pid_t pid_nr_ns(struct pid *pid, struct pid_namespace *ns);
struct pid * fastcall find_pid_ns(int nr, struct pid_namespace *ns);进程关系
task_struct数据结构提供了两个链表表头，用于实现这些关系:
struct task_struct{
struct list_head children;//子进程链表
struct list_head sibling;//连接到父进程的子进程链表
};进程管理相关的系统调用
fork、vfork，clone
COW：只要一个进程试图向复制的内存页写入，处理器会向内核报告访问错误。内核然后查看额为的内存数据结构，检查该页是否可以用读写模式访问。
task_struct->stack.通常栈和thread_info一同保存在一个联合中，union thread_union中
thread_info保存了特定于体系结构的汇编语言代码需要访问的那部分进程数据。
<asm-arch/thread_info.h>
struct thread_info {
struct task_struct *task;
struct exec_domain *exec_domain;
unsigned long flags;//eg.TIF_SIGPENDING,TIF_NEED_RESCHED
unsigned long status;
__u32 cpu;
int preempt_count;//内核所需的抢占计数器
mm_segment_t addr_limit;
struct restart_block restart_block;
}current_thread_info可以获得指向当前执行进程的thread_info实列的指针，其地址可以根据内核栈指针确定，因为thrad_info实列总是位于栈顶。
current：current_thread_info()->task;
惰性TLB处理(lazy TLB handing):没有mm指针的进程称为惰性TLB进程：假如内核线程之后运行的进程与之前的是同一个，在这种情况下，内核并不需要修改用户地址空间地址表，地址转换后备缓冲区中的信息仍然有效。
调度器的实现
可分为两个不同部分：一个涉及调度策略，另一个涉及上下文切换。
概观
内核必须提供一种方法，在各个进程之间尽可能公平地共享CPU时间，而同时又要考虑不同的任务优先级。
schedule函数是理解调度操作的起点。
Linux调度器的一个杰出特点是，它不需要时间片概念，至少不需要传统的时间片。当前的调度器只考虑进程的等待时间，即进程在就绪队列中已经等待了多长时间。
进程的task_struct有几个成员与调度相关
<sched.h>
struct task_struct{
int prio,static_prio,normal_prio;
unsigned int rt_priority;
struct list_head run_list;
const struct sched_class *sched_class;
struct sched_entity se;
unsigned int policy;
cpumask_t cpus_allowed;
unsigned int time_slice;
}调度器类:
<sched.h>
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
struct task_struct * (*pick_next_task) (struct rq *rq);
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);
void (*task_new) (struct rq *rq, struct task_struct *p);
};就绪队列:
kernel/sched.c
struct rq {
unsigned long 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 task_struct *curr, *idle;
u64 clock;
};调度实体：
<sched.h>
struct sched_entity {
struct load_weight load; /* 用于负载均衡 */
struct rb_node run_node;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
};处理优先级
在用户空间可以通过nice命来设置进程的静态优先级。进程的nice值在-20和+19。值越低，表明优先级越高。
内核使用一个简单些的数值范围，从0到139（包含），用来表示内部优先级。同样值越低，优先级越高。0-99转供实时进程使用。nice值-20～+19映射到100-139
static_prio是计算的起点。假设它已经设置好，而内核现在想要计算其他优先级。一行代码即可：
p->prio = effective_prio(p);
进程的重要性不仅是由优先级指定，而且还需要考虑保存在task_struct->se.load的负荷权重。set_load_weight负责根据进程类型及其静态优先级计算负荷权重。
核心调度器
调度器的实现基于两个函数：周期性调度器函数(scheduler_tick)和主调度器函数（schedule）。
完全公平调度类
完全公平调度类:
kernel/sched_fair.c
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
};CFS就绪队列:
kernel/sched.c
struct cfs_rq {
struct load_weight load;
unsigned long nr_running;
u64 min_vruntime;
struct rb_root tasks_timeline;
struct rb_node *rb_leftmost;
struct sched_entity *curr;
}完全公平调度算法依赖于虚拟时钟，用以度量等待进程在完全公平系统中所能得到的CPU时间。所有与虚拟时钟有关的计算都在update_curr中执行。
虚拟时钟计算:
vruntime+=((当前运行时间 - 上次运行时间)xNICE_0_LOAD)/Curr->load.weight红黑树根据(se->vruntime-cfs_rq->min_vruntime)值排序
用这种方法内核实现了下面对立机制：
1.在进程运行时，其vruntime稳定地增加，它在红黑树中总是向右移动，因此越重要的进程vruntime增加的越慢，因此他们向右移动越慢，这样其被调度的机会就比较大。
2.如果进程进入睡眠，则其vruntime保持不变。因为每个队列min_vruntime同时会增加（单调增加），那么睡眠进程醒来后，在红黑树中的位置会更靠左，因为其键值变得更小了。考虑各个进程的相比权重，将一个延迟周期(调度周期，如果进程过多，该值可能还会增加)的时间在活动进程之间进行分配：static u64 sched_slice(struct cfs_rq cfs_rq,struct sched_entity se);
队列操作
euqueue_task_fair:用place_entity确定了进程正确的虚拟运行时间之后，则用__enqueue_entity将其置于红黑树中。
选择下一个进程
pick_next_task_fair:
处理周期性调度器
task_tick_fair->entity_tick->check_preempt_tick
check_preempt_tick:主要是确保没有那个进程能够比延迟周期中确定的份额运行得更长。如果用的话，通过resched_task发出重调度请求。
唤醒抢占
try_to_wake_up和wake_up_new_task:--->调用check_preempt_curr查看新进程是否可以抢占当前运行的进程。
当运行进程被新进程抢占时,内核确保被抢占者至少已经运行了某一最小时间限额。如果新进程的虚拟运行时间,加上最小时间限额,仍然小于当前执行进程的虚拟运行时间,则请求重调度。
实时调度类
性质
实时进程与普通程序有一个根本不同之处：如果系统中有一个实时进程且可运行，那么调度器总是会选中它运行。
循环进程（SCHED_RR）有时间片,其值在进程运行时会减少，就像是普通进程
先进先出进程没有时间片，在被调度器选中之后，可以运行任意时间。
调度器增强
SMP调度（负载均衡）
首先找到工作量最大的队列，然后将该队列适当的进程移动到当前进程。如果上述失败，则调用该队列的迁移线程
调度域和控制组
进程置于不同的组中,调度器首先在这些组之间保证公平,然后在组中的所有进程之间
保证公平
内核抢占与低延迟相关工作
内核抢占的出现,使得同一处理器上的两个不同代码路径可以“准并发”地访问该变量,这与两个独立的处理器操作该值的效果是相同的。
内核抢占不像抢占用户空间进程那么容易实现，因为如果内核无法一次性完成某些操作，那么可能会出现竞态条件，导致系统不稳定。
如果内核可以被抢占，即使单处理器系统也会像是SMP系统。考虑正在临界区内部工作的内核被抢占的情况。下一个进程也在核心态操作，凑巧也想要访问同一个临界区。这实际上等价于两个处理器在临界区中工作,我们必须防止这种情形。每次内核进入临界区时,我们必须停用内核抢占。
内核如何跟踪它是否能够被抢占?回想一下,可知系统中的每个进程都有一个特定于体系结构的struct thread_info 实例。该结构也包含了一个抢占计数器(preemption counter)
:
<asm-arch/thread_info.h>
struct thread_info {
...
int preempt_count; /* 0 => 可抢占, <0 => BUG */
...
}还有更多的例程可用于抢占处理。
- preempt_disable 通过调用 inc_preempt_count停用抢占。此外,会指示编译器避免某些内存优化,以免导致某些与抢占机制相关的问题。
- preempt_check_resched 会检测是否有必要进行调度,如有必要则进行。
- preempt_enable 启用内核抢占,然后用 preempt_check_resched检测是否有必要重调度。
- preempt_disable_no_resched 停用抢占,但不进行重调度
如果抢占计数器大于0,那么抢占仍然是停用的,因此内核不能被中断,如果在某些重要的点上内核停用了硬件中断,以保证一次性完成相关的处理,那么抢占也是不可能的。
启用了抢占特性的内核能够比普通内核更快的用紧急进程代替当前进程。
内核中耗时长的操作不应该完全占据整个系统。相反，他们应该时不时的检查是否有另一个进程变为可用，可通过cond_resched()函数完成.