MIT6.828_JOS进程切换
进程状态
JOS共有5种进程状态：
enum {
ENV_FREE = 0,
ENV_DYING,
ENV_RUNNABLE,
ENV_RUNNING,
ENV_NOT_RUNNABLE
}
我个人觉得ENV_FREE这个状态其实不算是一个状态，这仅仅表示env数组中有一个空余的元素可以使用，前面的文章我也分析了fork和spawn的实现，它们都需要在env数组中找到一个空位置，然后“注册”一个新的进程。
当fork、spawn函数返回后，新的进程的状态就是ENV_RUNNABLE，表示它可以被调度器调度至CPU执行。当一个进程被调度至CPU执行时，它的状态就由ENV_RUNNABLE转变为ENV_RUNNING。
如果进程在执行过程中需要等待某种事件结束(或者等待某种资源)，那么它的状态将会被置为ENV_NOT_RUNNABLE，表示它将不会对调度器可见(见下一节)。JOS中比较典型的场景是：进程调用sys_ipc_recv，会阻塞本进程等待其他进程的消息。
当进程调用exit时，进程状态将会被置为ENV_DYING，相当于linux中的僵尸进程，但与linux不同，JOS的僵尸进程由本进程而不是父进程“收尸”。当释放了僵尸进程的资源后，该env结构又回到了ENV_FREE的状态。
各状态转换图如下所示：
进程切换
JOS的进程切换相对比较简单，因为JOS的内核栈是固定的。前面的文章讲过，在x86体系中，内核栈的位置由tss中的esp0指针指定，它在各cpu启动时已经被设置好了：
void
trap_init_percpu(void)
{
// 设置Tss的esp ss
thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - thiscpu->cpu_id * (KSTKSIZE + KSTKGAP);
thiscpu->cpu_ts.ts_ss0 = GD_KD;
thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);
// 在GDT中设置后NCPUS个的段描述符
gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id] = SEG16(STS_T32A, (uint32_t) (&(thiscpu->cpu_ts)),
sizeof(struct Taskstate) - 1, 0);
gdt[(GD_TSS0 >> 3) + thiscpu->cpu_id].sd_s = 0;
// 加载TR寄存器
ltr(GD_TSS0 + (thiscpu->cpu_id<<3));
// Load the IDT
lidt(&idt_pd);
}
而且IDT的门描述符都是中断门，表示当用户通过中断态进入内核态时，不会再响应外部中断，因此内核态代码是不会被打断的，所以JOS用不着保存内核栈，每次进程中断进入内核时都默认内核栈为空，所以整体逻辑会比xv6稍微简单一些。
还是举个例子吧，假设进程A通过时钟中断进入了内核态：
trap_dispatch(struct Trapframe *tf)
{
int ret ;
switch(tf->tf_trapno){
// ....
case IRQ_OFFSET+IRQ_TIMER: // 收到时钟中断就调度
lapic_eoi();
sched_yield();
前面的文章已经详细说过了通过中断进入内核时，中断栈帧(Trapframe)的构建流程。而且要知道，从trap(struct Trapframe *tf)到trap_dispatch(struct Trapframe *tf)的调用流程过程中，两个tf指针指向不同的内存地址。第一个tf指针指向内核栈中的trapframe，第二个tf指针指向curenv中的trapframe。这样做是为了方便后头的env_xx函数的实现。
再回到上面的代码，假设进程A通过时钟中断进入了内核态，在确认中断后(lapic_eoi)，就调用sched_yield()执行Round_Roubin调度：
// Choose a user environment to run and run it.
void
sched_yield(void)
{
struct Env *idle;
// 简单的round-roubin轮询调度
int i=0,j;
if(cpus[cpunum()].cpu_env)
i=ENVX(cpus[cpunum()].cpu_env->env_id);
// round-roubin 选择Env数组中的元素
// 只选择ENV_RUNNABLE的进程进行调度
for(j=(i+1)%NENV; j!=i; j=(j+1)%NENV) {
if(envs[j].env_status == ENV_RUNNABLE)
env_run(&envs[j]);
}
//如果不加下面这个判断，就少判断了env[i]的状态
//这样当所有用户环境只剩env[i]的状态是ENV_RUNNABLE时，cpu无法运行env[i]也无法halt，就一直在循环
if(j==i && envs[j].env_status == ENV_RUNNABLE)
env_run(&envs[j]);
// 找不到下一个可运行进程，那么本CPU再次运行当前进程
if(curenv && curenv->env_status == ENV_RUNNING){
env_run(curenv);
}
sched_halt();
}
调度器只选择进程状态为ENV_RUNNABLE的进程。然后调用env_run函数，执行上下文切换：
void
env_run(struct Env *e)
{
// 1. 将本进程状态设为ENV_RUNNABLE，被抢占了
if (curenv && curenv->env_status == ENV_RUNNING) {
curenv->env_status = ENV_RUNNABLE;
}
// 2. 设置即将运行的进程,
curenv = e;
curenv->env_status = ENV_RUNNING;
curenv->env_runs++;
lcr3(PADDR(curenv->env_pgdir)); // 切换页目录
env_pop_tf(&(curenv->env_tf)); // 中断返回至用户态
}
CR3寄存器存放页目录的物理地址，因此首先使用PADDR将curenv->env_pgdir从虚拟地址转换为物理地址，然后调用lcr3将新的页目录地址加载进CR3中:
static inline void
lcr3(uint32_t val)
{
asm volatile("movl %0,%%cr3" : : "r" (val));
}
最后调用env_pop_tf将会从新进程的中断上下文返回至用户态。
env_pop_tf(struct Trapframe *tf)
{
curenv->env_cpunum = cpunum();
unlock_kernel(); // 释放大内核锁
asm volatile(
"\tmovl %0,%%esp\n" // esp 指向trapframe 末尾
"\tpopal\n"
"\tpopl %%es\n"
"\tpopl %%ds\n"
"\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
"\tiret\n"// 从中断返回， eip 在load_icode()设置 或者 在trapentry.S中保存
: : "g" (tf) : "memory");
panic("iret failed"); /* mostly to placate the compiler */
}
进程调度
无论是JOS还是xv6，它们的调度策略都是简单的Round-Robin策略。但进程调度相关话题在面试中出现的频率很高，所以在这里首先整理以下关于进程调度的理论知识，然后试着分析一下，linux系统的调度策略。
理论
参考书籍：《Operating Systems: Three Easy Pieces》
衡量指标与负载类型
进程调度有两个衡量指标：
- 周转时间：任务完成的时间点减去到达的时间点
- 响应时间：任务首次完成时间减去到达时间点
通常情况下，这两种指标是不可兼得的，只能视工作负载的不同选择合适的衡量指标。对应上面的两个衡量指标，有两个工作负载类型：
- CPU密集型作业，需要大量CPU时间很少的IO时间。它要求有较低的周转时间
- IO密集型作用，需要大量的IO请求。这类作业通常对交互性的要求较高，也就是说要求响应时间较低。典型的应用程序：shell。
操作系统类型
批处理系统：作业成批装入计算机由计算机管理，作业执行的过程中用户不能干预交互。适合于前后程序结果依赖的作业。
分时系统：多个用户可以通过各自的终端共用一台计算机，同计算机进行交互操作，计算机以“分时”(划 分时间片)的方法轮流为每个用户服务。
实时系统：要求及时响应且高可靠的一类系统。
FIFO(先来先服务)
维护一个队列，将到来的队列依次加入其中，执行时依次从队列头取出。非抢占，适用于批处理系统，对耗时长的作业有优势。
可能出现护航效应：一些花费时间较少的资源，由于它”晚到“，因此一直等到一个运行时间很长的任务结束才会被调度。
此时的平均周转时间是比较高的。
最短任务优先
维护一个队列，每次cpu从中选择运行时间最短的那一个进行调度。
非抢占，适用于批处理系统，对耗时长的作业有优势。
同样有护航效应。
最短完成时间优先
为了缓解最短任务优先的护航效应，最短完成时间优先允许抢占。假设长任务A在0时刻到来，运行到10时刻时，有更短的作业B、C到来，则B、C抢占A。
如此，平均周转时间会缩短不少。
轮转(Round Roubin)
以上两个策略的响应时间指标都比较差。为了使得交互型程序(IO多)获得更好的表现，Round Roubin是个不错的策略。
轮转策略的基本思想：在一个时间片内运行某个程序一段时间，然后切换至队列中的下一个任务。
抢占式调度，比较公平，且重要的是响应时间短，当然了周转时间就显得比较长了。
缺点：时间片的选取比较棘手。如果时间片很短，那么进程上下文切换的花费占比就很重，比较浪费CPU资源。如果时间片很长，那么轮转策略的响应时间就会变长。
多级反馈队列(The Multi-Level Feedback Queue)
多级反馈队列调度策略是一种结合轮转和优先级的调度策略。
解决了两方面的问题：
- 在操作系统对任务的执行时间一无所知时，如何建立一个周转时间小的调度程序。
- 同时兼顾响应时间保证用户的体验。
MLFQ有许多独立的队列，每个队列维护一组优先级相同的作业，且从上至下，它们的优先级降低。如下图所示，A、B的优先级相同，且它们的优先级大于C，而C的优先级大于D。
多机反馈队列的规则如下：
- 如果A的优先级 > B的优先级，运行A
- 如果A的优先级=B的优先级，
轮转地运行A和B - 作业首次进入系统时，放在最高优先级的队列
- 一旦工作用完了其在某一层中地时间配额，无论主动放弃了多少CPU（
防止用户程序愚弄（game）调度程序而永远不降低优先级），就降低其优先级 - 经过一段时间S，就将系统中的所有工作重新加入最高优先队列（
防止饥饿问题）
linux调度策略
linux的task_struct中使用一个字段保存标识它自己是哪一类进程，大致有三类：
- FIFO
- RR
- OTHER
其中FIFO和RR是实时进程，OTHER则表示其他普通进程。
-
实时进程的优先级一定是比普通进程高的，因此linux调度器会优先调度实时进程。在实时进程的调度过程中，FIFO与RR策略与上节的原理部分一致。但是linux通过了两个选项限制了实时进程的运行时间：
/proc/sys/kernel/sched_rt_period_us /proc/sys/kernel/sched_rt_runtime_us表示FIFO和RR这些实时进程在总共period_us时间内，最多可以运行sched_rt_runtime_us时间。
这样普通进程被饿死的可能性就大大降低了。 -
接着是对普通进程的调度策略，linux在历史上对普通进程的调度过三种不同的调度策略。即O(n)、O(1)、CFS，其中O(n)、O(1)并不仅仅调度普通进程，它们还关注着实时进程，而CFS则专注于普通进程的调度。关于O(n)、O(1)、CFS出现的先后顺序，看这篇文章
-
O(n)调度器：维护一个链表头runqueue_head，将所有可运行进程串联起来。调度器在选择下一个要执行的进程时，则遍历runqueue_head链表，使用goodness()计算其中每个进程的权重，挑选权重值最大的那一个运行。很明显它的时间复杂度为O(n)，优点是简单，缺点是扩展性不高，并发度不高(runqueue_head全局共享，包括在多核系统下)。那么goodness到底怎样计算权重呢？
/*linux 2.4内核源码 sched.c*/ // p ： 候选task_struct // this_mm: 当前在此CPU上运行的进程的struct mm 结构，它表示了一个进程的地址空间(相当于JOS的PGDIR) static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm) { int weight; weight = -1; // 1. 如果是yield的进程，权重为-1 if (p->policy & SCHED_YIELD) goto out; // 2. 针对普通进程 if (p->policy == SCHED_OTHER) { // 如果下一个进程进程的时间片还没有用完，则奖励一些权重 weight = p->counter; if (!weight) goto out; // 如果候选task_struct使用的struct mm 与当前进程相同，表示它与当前执行流逻辑上属于同一个进程。加一些权重 if (p->mm == this_mm || !p->mm) weight += 1; // 最后通过nice值计算 weight += 20 - p->nice; goto out; } // 3.实时调度进程， RT进程表示自己有特权，权重直接加上1000，不更普通进程比，更其他实时进程比 weight = 1000 + p->rt_priority; out: return weight; }可以看到，对于实时进程，它根本不需要和普通进程比较，实时进程的权重永远比普通进程高，它只需要和其他实时进程比较rt_priority这个属性。
至于普通进程的权重，则是通过conter和nice值综合结算的结果， counter值越高(也就是时间片剩余越多，也就是喜欢IO的进程)、nice值越低的进程，其权重越高。其中nice的取值范围为[-20 - 19]，可以简单理解“越nice的进程，越得不到CPU的关注”。
-
O(1)调度器：使用了2个优先级数组，一个为active，另一个为expired，每个数组使用140位的bitmap表示，bitmap的每一位(如果它有效)都对应了一个队列，该队列中的进程优先级相同。bitmap的1-100的优先级分配给实时进程用，其余的优先级给普通进程，与O(n)相同，这里的实时进程同样拥有较高的优先级。调度器在选择下一个执行的进程时，只要找到优先级最高的队列选择一个进程执行即可。这个过程的时间复杂度是O(1),为什么呢？因为找到bitmap中的第一个有效位这个操作可以由一条CPU指令完成，时间复杂度为O(1)。此外每个CPU拥有的两个优先级数组，并发度有所提高。
当一个进程用完了它的时间片后，调度器重新计算并重置它的时间片，然后放入expired数组中。当active数组的每一位都无效时，交换active、expierd两个bitmap即可，这个交换操作只需要交换指针指向即可，时间复杂度还是O(1)。
此外，除了上述的静态优先级，O(1)调度器也会计算每个进程的动态优先级，目标也和O(n)调度器一样，对IO密集型的进程有利。但尽管如此，O(1)调度器对IO密集型进程的识别效果也欠佳。而且动态优先级的计算很复杂，可能使得O(1)调度器名不副实。
-
CFS调度器。该调度器专门用于普通进程的调度，CFS即为完全公平调度器，旨在对每个进程一视同仁。但是，即时是普通进程，他们的优先级有高也有低，同时调度器应该多照顾IO密集型任务，那么这里说的公平是指什么公平？指的是虚拟时间vruntime的相同：vruntime = 实际运行时间 * 1024 / 进程权重其中进程权重由nice值转换而来，nice值越低，权重值越高：
如果忽略系数，那么CFS的目标就使得进程的实际运行时间与进程权重的比值相同。
在具体实现上，linux使用红黑树维护每个进程的vruntime，红黑树O(logn)复杂度的插入、查找、删除操作是CFS的基础。位于红黑树左侧的节点vruntime相对较低，调度器选择vruntime值小的的进程运行一段时间后，随着实际运行时间的增加，vruntime也会增加，红黑树节点将慢慢向右移动。
从直觉上理解一下CFS，对于那些优先级高的进程，虽然它们的实际运行时间可能一直在增加，但是由于分母较大，所以它们向右移动的趋势比优先级低的进程小。对于那些IO密集型的进程，它们的实际运行时间就很少，所以也倾向于一直待在红黑树的左侧。所以CFS比较均衡地同时考虑了优先级和IO密集型进程。
-
TUDO: CFS调度器的缺点
参考资料：
- 宋华宝-打通Linux脉络系列：进程、线程和调度（讲的应该是2.6的调度策略，有些错误)
- Process Scheduling in Linux | Scaler Topics 有linux调度器的出现历史
- （五）Linux进程调度-CFS调度器 (qq.com) 图不错
- 04-SchedulingLinux.pdf (ohio-state.edu) ：
- 谈谈调度 - Linux O(1) - 知乎 (zhihu.com) 解决了O(1)调度器为什么是O(1)的疑问