进程调度
进程调度相关概念
多任务操作系统就是能同时并法地交互执行多个进程的操作系统，多任务系统分为两类：
- 非抢占式操作系统
- 抢占式操作系统
linux是抢占式的多任务模式，它由调度程序决定什么时候停止一个进程的运行，以便其他的进程能够得到执行机会
策略
策略决定调度程序在何时让什么进程运行
进程可以分为I/O消耗型和处理器消耗型，I/O消耗型指的是进程的大部分时间用来提交IO请求或是等待IO请求，所以进程常处于可运行状态，但通常是运行短短一会，因为它在等待更多的IO请求时最后总会阻塞
而处理器消耗型进程把更多时间用在执行代码上，除非被抢占，都则会一直不停运行，所以系统调度器策略往往是尽量降低他们的调度频率，延长其运行时间
优先级
Linux采用了两种不同的优先级范围：
- nice值
- 实时优先级
nice值：nice值的范围是-20到+19,默认值为0,越大的nice值意味着越低的优先级，默认为0。低nice值的进程获得更多的处理器时间
实时优先级：默认情况下他的变化范围是0～99,与nice值相反，越高的实时优先级代表着进程的优先级越高，任何实时进程的优先级都高于普通的进程，也就是说实时优先级和nice优先级处于互不相交的两个范畴
时间片
时间片表明进程被抢占前所能持续运行的时间，时间片过长会导致系统对交互的响应表现欠佳，让人觉得无法并法执行应用程序；时间片过短会明显增加进程切换带来的处理器耗时，会有相当一部分系统时间浪费在进程切换上
Linux系统并不是直接分配时间片给每个进程，而是将处理器的使用比例划分给每个进程
抢占式多任务处理
linux进程管理的结构中有两种进程状态：用户态和核心态
进程通常处于用户态，只能访问自身的数据，无法干扰系统中的其他应用程序
如果进程想要访问系统数据或功能，则必须切换到核心态，这是在受限情况下完成的，实现方法有系统调用。第二种方法是通过中断，这种切换是自动触发的，而系统调用是程序有意调用的。
内核的抢占调度模型建立了一个层次结构，用于判断哪些进程可以由其他状态抢占
- 普通进程总是可能被抢占，甚至是由其他进程抢占，在一个重要进程变为可运行时，例如编辑器接收到了等待已久的键盘输入，调度器可以决定是否立即执行该进程
- 如果系统处于核心态并正在处理系统调用，那么系统中的其他进程无法夺取其CPU时间，调度器必须等待系统调用执行完成，才能去选择另一个进程执行，但中断可以中止系统调用
- 中断可以暂停处于用户状态和核心态的进程，中断具有最高优先级，因为在中断触发后需要尽快处理
进程状态
创建、就绪、执行、阻塞、终止 是进程的一般5种理论状态
linux有7中状态：
1.运行状态， 包括就绪态和运行态,进程切换只能在运行状态
2.可中断睡眠状态， 也就是阻塞状态，收到信号后可以执行信号处理函数，可以变成running状态
3.不可中断的睡眠状态， 磁盘IO时会出现这种状态，进程无法被中断，不能响应信号
4.停止状态
5.退出状态
6.僵尸状态， 子进程先于父进程退出，并且父进程没有调用wait或waitpid回收子进程。此时子进程即处于僵尸状态
7.跟踪状态， 当利用gdb调试某个程序，程序停留在某个断点处时，就处于跟踪状态
ps -aux 查看进程状态
#define TASK_RUNNING 0 // 进程正在运行或已准备就绪，就绪态+运行态
#define TASK_INTERRUPTIBLE 1 // 进程处于可中断等待状态
#define TASK_UNINTERRUPTIBLE 2 // 进程处于不可中断等待状态，主要用于 I/O 操作等待
#define TASK_ZOMBIE 3 // 进程处于僵死状态，已经停止运行，但父进程还没发信号
#define TASK_STOPPED 4 // 进程已停止进程调度代码实现
这里基于linux0.1内核，它实现的调度算法本身不复杂，重要的是学习进程调度的思想。代码主要是在kernel/sched.c主要的是schedule函数
/*
* 'schedule()' is the scheduler function. This is GOOD CODE! There
* probably won't be any reason to change this, as it should work well
* in all circumstances (ie gives IO-bound processes good response etc).
* The one thing you might take a look at is the signal-handler code here.
*
* NOTE!! Task 0 is the 'idle' task, which gets called when no other
* tasks can run. It can not be killed, and it cannot sleep. The 'state'
* information in task[0] is never used.
* 进程调度
*/
void schedule(void)信号唤醒进程
int i,next,c;
struct task_struct ** p;
/* check alarm, wake up any interruptible tasks that have got a signal */
// ========== 根据信号唤醒进程 ===========
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
if (*p) { // 如果任务的 alarm 时间已经过期(alarm<jiffies),在信号位图中置 SIGALRM 信号，然后清 alarm
if ((*p)->alarm && (*p)->alarm < jiffies) {
(*p)->signal |= (1<<(SIGALRM-1));
(*p)->alarm = 0;
}
if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && //则置任务为就绪状态
(*p)->state==TASK_INTERRUPTIBLE)
(*p)->state=TASK_RUNNING;
}在schedule函数一开始先去一个一个遍历task_struct链表，查看是否有设置的alarm到时间，如果有的话就给当前进程一个SIGALRM信号
接着就会唤醒因信号而睡眠的进程：如果该进程有未阻塞的待处理信号（比如刚设置的 SIGALRM），并且它当前处于可中断的等待状态（TASK_INTERRUPTIBLE），那么就将它唤醒（置为 TASK_RUNNING），让它有机会在调度中运行并处理这个信号
在 Linux 0.1 中，alarm 是内核为每个进程提供的唯一的、简易的定时机制。
优先级时间片轮转调度算法
/* this is the scheduler proper: */
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c) //get counter_max 值
c = (*p)->counter, next = i;
}
if (c) break; //如果有不为0的时间片，那么就退出
for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) //calculate counter
if (*p)
(*p)->counter = ((*p)->counter >> 1) + //优先级时间片轮转调度算法
(*p)->priority;
}使用一个大的while循环去获取最大时间片，这里本质就是一个寻找最大值的遍历算法。通过内部的while能够得到当前可运行态的进程中时间片最大的那一个，如果最大时间片不为0则退出循环进入后续步骤，如果为0（所有进程时间片都为0）则重新分配时间片
优先级时间片轮转调度：这里使用的是一个for循环，遍历系统中的所有进程，而不仅仅是正在运行的进程！
笔者最开始看到这里认为经过if(c)的判断之后这里的所有时间片都已经为0了，所以每俄国进程分配得到的时间片就是他的优先级，不需要再去写((*p)->counter >> 1) +
但是却忽略了其他态的进程：对于正在睡眠（TASK_INTERRUPTIBLE 等）的进程：它们可能刚进入睡眠不久，counter 还没有被消耗完（可能还剩一些值）。这个 for 循环同样会处理它们！
所以，((*p)->counter >> 1) + (*p)->priority 这个公式的精妙之处在于：
- 对于运行进程（
counter为 0）：它等效于直接赋值priority，重置时间片。 - 对于睡眠进程（
counter非 0）：它保留了部分剩余时间片并加上基础优先级，作为一种“奖励”，让那些因为等待 I/O 而主动让出 CPU 的进程（如交互式程序）能获得更高的调度优先级，从而提升系统的响应速度。
这是一套非常经典的兼顾公平与响应速度的调度算法，远比简单的“用完就重置”要高明得多。作者之所以这样写，正是为了统一处理这两种情况，实现这套优先级动态调整的逻辑。
进程切换
在schedule函数最后会进行进程切换，调用的switch_to
这是一个由汇编代码组成的宏定义，实现效果是把 CPU 从当前进程交给另一个进程，同时保证所有状态（寄存器、内存映射、协处理器等）正确转移。
xchgl %%ecx, _current:原子地交换 ECX 和 _current 的值。执行后，_current 变成新任务的指针（切换完成），而 ECX 变成旧任务的指针（留作后面判断协处理器用）。
/*
* switch_to(n) should switch tasks to task nr n, first
* checking that n isn't the current task, in which case it does nothing.
* This also clears the TS-flag if the task we switched to has used
* tha math co-processor latest.
* 切换任务
*/
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,_current\n\t" \
"je 1f\n\t" \
"movw %%dx,%1\n\t" \
"xchgl %%ecx,_current\n\t" \
"ljmp %0\n\t" \
"cmpl %%ecx,_last_task_used_math\n\t" \
"jne 1f\n\t" \
"clts\n" \
"1:" \
::"m" (*&__tmp.a),"m" (*&__tmp.b), \
"d" (_TSS(n)),"c" ((long) task[n])); \
}这里通过远跳转指令ljmp切换任务
Intel 80386 支持通过远跳转（ljmp）到 TSS 描述符来自动完成任务切换。CPU 会：
- 自动保存当前任务的所有寄存器到当前 TSS；
- 加载新任务的 TSS 内容到寄存器；
- 然后从新任务的地方继续执行。
这比手工保存/恢复所有寄存器要省事，Linux 0.1 正是利用了这一硬件特性。
sleep函数
在sched.c中有一个将进程休眠的sleep_on函数，笔者最开始看这个代码的时候误以为它和用户态的sleep函数一样是休眠一段时间，但是sleep_on 不是一个“定时睡眠”函数，而是一个“资源等待”函数。它的作用是让当前进程永久睡眠，直到它等待的特定内核资源（如磁盘数据、内存缓冲区）可用为止。
// 将当前任务置为不可中断的等待状态,并让睡眠对象的任务指针指向当前任务，只有明确地唤醒时才会返回
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE;
schedule();
if (tmp)
tmp->state=0;
}函数的参数传递的是一个task_struct的指针的指针，或者叫做等待队列头指针的指针
在里面使用一个tmp指向数组头元素，然后将当前进程task_struct存放进入等待队列头
然后再将当前进程的状态设置为不可中断等待状态，再去执行调度。当下一次轮到当前进程执行时候将tmp指向的进程变为运行态
在初看这部分代码时笔者有一堆疑问，下面我将列出我的疑问以及对应解答：
为什么 tmp = *p; *p = current;？
这里实现的是一个栈的等待队列实现
tmp = *p;：先把当前队列头（即之前排在第一个的进程）保存下来。*p = current;：把当前进程放到队列的最前面（成为新的队头）。
因为 Linux 0.11 的等待队列是单链表且没有显式的 next 指针，它利用每个进程内核栈上的临时变量来串联。tmp 实际上充当了“指向下一个等待者的指针”的角色。
为什么要设置当前进程为不可中断睡眠？
因为当前进程就是要等待资源的那个进程。设置 current->state = TASK_UNINTERRUPTIBLE，是为了告诉调度器：“我现在要睡觉了，而且我睡得很死（不能被信号打断），在没有被明确唤醒之前，不要再把我放进去运行。”
为什么要执行 schedule()？
设置状态只是“贴标签”，CPU 并不会自动切换。必须调用 schedule()，让调度器去选择另一个进程运行，当前进程才能真正停下来（因为它的状态已经不是 TASK_RUNNING 了，调度器会跳过它）。
为什么调度返回后，只设置 tmp->state=0？
第一步（睡眠时）：
假设有两个进程 A 和 B 先后等待同一个资源：
- B 先进来：
tmp = NULL，*p = B。B 睡眠。 - A 后进来：
tmp = B（保存了旧的队头 B），*p = A。A 睡眠。
现在的队列是：队列头 p 指向 A，A 的栈上 tmp 指向 B。
第二步（唤醒时）：
当资源可用时，中断处理程序会调用 wake_up(struct task_struct **p)。
void wake_up(struct task_struct **p) {
if (p && *p) {
(**p).state = 0; // 只唤醒队头！
*p = NULL;
}
}注意！wake_up 只唤醒了队头 *p（也就是进程 A），并清空了队列头指针。
第三步（A 被调度回来，执行 if(tmp) tmp->state=0;）：
此时 A 在 schedule() 后面醒来，它发现自己 tmp 里保存的是 B。于是它执行 tmp->state = 0;，顺便把 B 也唤醒了。
这就形成了一个“链式唤醒”（后进先出）：
资源可用 -> 唤醒最后睡眠的 A -> A 运行完或让出资源前 -> A 唤醒 B -> B 再运行。
在 Linux 0.11 的单核简陋环境下，同时唤醒所有进程会导致“惊群效应”，且多个进程争抢同一个资源（比如一个内存块）会让状态难以管理。
采用“唤醒链”，资源就像接力棒一样，严格地依次传递给下一个等待者，不会出现多人争抢的混乱。而且不需要复杂的链表 next 指针维护，仅靠栈上的 tmp 变量就串起了所有等待者，非常节省内存和代码量。
关于内核的理解
笔者在之前一直以为内核是一个单独的大的进程，时时刻刻一直运行，当有系统调用来就是这个大进程执行系统调用，以及中断等，但是在看上面的sleep_on函数的时候看到每个进程都有内核栈，并且都可以设置tmp，每个tmp不同，就发现似乎理解有问题。实际上我的理解确实不对
- 内核是代码和数据：内核本质上是操作系统常驻内存的那部分代码（函数）和数据结构（任务数组、内存管理表等）。它本身没有“进程控制块（PCB）”，也不参与进程调度。
- 进程是“运行中的程序”：进程（任务）是在用户态运行的实体，它们需要执行I/O、申请内存等特权操作时，主动陷入（通过系统调用）或被动陷入（通过中断） 内核，让内核代码替它做事。
- 内核线程（特殊例外）：Linux 0.11 中确实有“任务0”（idle进程）和“任务1”（init进程），它们看起来像进程，但任务0是内核的一部分（死循环），任务1是内核启动的第一个用户态进程。但“内核本身”作为整体，绝不是一个大进程。
内核代码的“运行载体”取决于进入内核的途径，分为三种情况：
- 情况一（最常见）：借宿在用户进程体内
当你的应用程序调用read()时，CPU 陷入内核，此时运行内核代码的载体就是当前这个用户进程。内核使用这个进程自己的内核栈（就是task_union里的 4KB），current指针指向这个进程。内核此时就像这个进程的“私人律师”，替它办事。 - 情况二（中断上下文）：随机寄宿
当硬盘中断发生时，CPU 无论当前在运行哪个用户进程，都会立刻打断它，转而执行中断处理程序。此时，内核代码运行在被中断的那个进程的上下文里，使用被中断进程的内核栈。这和进程主动调用系统调用不同，进程是被动地“被借用”了。 - 情况三（例外）：确实有“纯粹的内核进程”
在 Linux 中，确实存在内核线程（Kernel Thread）。在 Linux 0.11 中，任务 0（idle 进程） 就是这样一个例子。它没有对应的用户程序，永远只运行内核代码（死循环调度）。现代 Linux 还有kswapd、kworker等内核线程。这些才是“单独的”内核进程，但它们只负责后台杂务，绝对不负责执行用户进程的系统调用。
以sleep_on函数的运行为例：
- 假设进程 A 调用
read()进入内核，发现自己要等磁盘数据，于是调用sleep_on(&wait_queue)。 - 此时，内核是在进程 A 的内核栈上运行的！
current指向 A。 - 执行
current->state = TASK_UNINTERRUPTIBLE;，把进程 A 置为睡眠。 - 执行
schedule()，CPU 切换到进程 B。
当磁盘中断发生，中断程序调用 wake_up 唤醒进程 A。此时 CPU 正运行在进程 B 的内核栈上（因为中断打断了进程 B），但 wake_up 修改的是进程 A 的状态。
发现了吗？ 同一个内核函数 wake_up，在中断时是借用了进程 B 的“肉身”在运行，但它操作的数据却是进程 A 的。并没有一个独立的“内核进程”来替它做这件事。
内核代码不是在一个固定的“内核进程”里运行，而是像“幽灵”一样，附身在当前正在运行的进程（或被打断的进程）身上运行。 每个进程都自带一个“内核栈”（躯壳），内核代码走到哪里，就借用哪个进程的躯壳，直到返回用户态，再把躯壳还给该进程。只有少数专门的内核线程（如任务 0）才是“独立行走的幽灵”。
