CPU虚拟化

前言

本章中的 CPU 虚拟化指的是将单个操作系统（Operating System，OS）中将物理 CPU 虚拟化成多个供多个进程共享一个物理 CPU，实际上讲的是进程管理，并不是指现代广义上的通过虚拟机监控器（Hypervisor）将物理 CPU（physical CPU，pCPU）虚拟化成多个虚拟 CPU（virtual vCPU），分配给多个虚拟机（Virtual Machine，VM），每个 VM 中再运行一个独立的 OS，这种也是当今云计算中应用十分广泛的技术。

进程

进程（process）是操作系统提供的一种基本的抽象，进程其实就是正在运行的程序。程序本身是没有生命周期的，它只是存在磁盘上的一些指令和一些静态数据，操作系统让这些字节运行起来发挥作用。
进程由以下几部分构成，这些都是程序在运行时可以读取或者更新机器的部分：

内存，程序的指令和读取或者更新的数据都在内存中，也就是进程可以访问的内存即地址空间（address space）
寄存器，程序读取或者更新的寄存器，比如程序计数器（Program Counter，PC）、指令指针（Instruction Pointer，IP）、管理栈帧的栈指针（stack pointer）和帧指针（frame pointer）
I/O 信息，程序当前已经打开的文件列表

创建进程

操作系统运行程序的第一步就是将代码和所有静态数据（比如初始化变量）加载（load）到内存中，加载进程的地址空间（操作系统分配）中。以下是操作系统加载的过程，将程序变为进程：

在早期或简单的操作系统中，加载过程尽早（eagerly）完成，即在运行程序之前就全部完成。现代操作系统会惰性（lazily）执行该过程，即仅在程序执行期间需要加载的代码或数据片段时才加载。
加载完代码和静态数据之后就会为程序在内存中创建运行时栈（runtime stack，stack），程序将会使用这个栈来存放局部变量、函数参数和返回地址。比如 C 语言程序的入口函数为 main()函数，操作系统运行一个 C 语言程序时就会分配内存空间给程序作为栈，然后还有可能会使用参数初始化栈，也就是将 argc、argv 参数填入 main()函数。
然后操作系统还会为程序在内存中创建堆（heap），为程序用于存放一些数据。比如 C 语言可以使用 malloc()来请求堆上的空间，使用 free()就可以释放申请的空间。
除此之外，操作系统还会处理一些 I/O 相关的任务。比如在 UNIX 系统中，默认情况下每个进程都会有 3 个打开的文件描述符（file description），用于标准输入、输出和错误。
最后，在做完初始化工作后，操作系统就会将 CPU 控制权转移到新创建的进程中，启动程序，进程在入口处运行，即 main()。

进程状态

进程状态有以下几种：

创建，新建（created，new）
就绪，等待（ready，waiting）
运行（running）
阻塞（blocked）
被换出并等待（swapped out and waiting）
被换出并阻塞（swapped out and blocked）
终止（terminated）

以下是这几种状态的转换图：

有关进程的数据结构，进程控制块（Process Control Block，PCB）

操作系统也是一个程序，和其他程序一样，它也需要一些数据结构来跟踪和进程进程相关的各种信息，我们将会学习常用 OS 内核是如何完成这一点的，以下是 vx6 内核的 proc 结构：

struct context {
  uint edi;
  uint esi;
  uint ebx;
  uint ebp;
  uint eip;
};

enum procstate {
  UNUSED,    // 未使用
  EMBRYO,    // 刚分配（正在初始化）
  SLEEPING,  // 睡眠（等待某个事件）
  RUNNABLE,  // 可以运行（等待被调度）
  RUNNING,   // 正在运行
  ZOMBIE     // 退出但尚未被回收
};

// Per-process state
struct proc {
  uint sz;                     // 进程使用的内存大小（以字节计）
  pde_t* pgdir;                // 进程的页目录表（地址空间）
  char *kstack;                // 进程专用的内核栈（位于内核空间）
  enum procstate state;        // 当前状态（如 RUNNING, SLEEPING）
  int pid;                     // 进程ID
  struct proc *parent;         // 父进程指针
  struct trapframe *tf;        // 系统调用时保存的寄存器信息（中断帧）
  struct context *context;     // 进程调度用的 context（swtch会跳转到这里）
  void *chan;                  // 如果进程正在睡眠，睡在哪个"事件"上
  int killed;                  // 进程是否被标记为终止
  struct file *ofile[NOFILE];  // 打开的文件表
  struct inode *cwd;           // 当前工作目录
  char name[16];               // 进程名（用于调试）
};

这里的 unused 表示当前 proc 结构并未被使用，是 xv6 中特有的，embryo 对应 new，sleeping 对应 blocked，runnable 对应 waiting，running 对应 running，zombie 对应 terminated，进程在退出后并不会立刻被回收而是进入 zombie 态用于其他进程检查该进程的返回代码。

这里是 xv6 on x86 中该结构体的源码

进程 API

我们将会通过讨论 UNIX 系统的进程 API，来了解如何通过系统调用对进程进行控制。

fork

使用 fork()系统调用会创建一个拷贝父进程的整个内存空间的子进程（传统实现），然后 fork()就会返回子进程的 pid 给父进程，返回 0 给子进程，如果创建失败就会返回-1，可见以下例子：

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main() {
    pid_t pid = fork();
    if (pid < 0) {
        // 失败
        perror("fork failed");
        return 1;
    } else if (pid == 0) {
        // 子进程
        printf("This is the child process. PID = %d\n", getpid());
    } else {
        // 父进程
        printf("This is the parent process. Child PID = %d\n", pid);
    }
    return 0;
}

由于子进程的内存空间是父进程的拷贝，所以子进程的指令和父进程一致，但是 fork 返回值不同，所以就走到了不同的分支上。
现代操作系统已经用了写时拷贝（Copy-On-Write，COW）技术，COW 就是在需要时才真正拷贝数据，而不是一开始就把数据全复制一遍，在 fork()时父子程序最初共享同一份物理内存，只读时不拷贝，当父子中有一方尝试写数据时，操作系统才会真正拷贝这一页内存，也就是惰性拷贝，比如以下情况：

fork()后：
父进程页表 ——> 物理页A（只读）
子进程页表 ——> 物理页A（只读）

子进程写数据时：
触发COW
分配新物理页B
子进程页表 ——> 物理页B（可写）
父进程页表 ——> 物理页A（保持）

wait

使用 wait()系统调用可以让父进程阻塞等待子进程进入僵尸状态，即子进程 exit()，当子进程 exit()后，就会唤醒父进程然后回收子进程的资源，然后返回子进程的 pid。

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
int main(){
    pid_t pid = fork();

    if (pid < 0) {
        perror("fork error");
        return 1;
    } else if (pid == 0) {
        printf("I am child pid = %d\n", getpid());
        sleep(1);
    } else {
        int wc = wait(NULL);
        printf("I am parent, wait for child pid = %d\n", wc);
    }
    return 0;
}

所以说每一个 fork()调用都要有一个 wait()或者 waitpid()对应，假设有个父进程的任务就是一直创建子进程而产生的子进程又很快就结束，但父进程又没有 wait()或者 waitpid()所有的子进程就会产生大量僵尸进程。另外，如果子进程还没结束，父进程就退出了，那所有子进程就会变成孤儿进程，然后就会被操作系统中的特殊进程（pid = 1 的 init/systemd）来接管，init/systemd 就会使用 wait()来回收它。
因此，如果父进程可以结束，那么就不会出现僵尸进程累计的问题，但是父进程要一直运行不能结束的话，我们可以使用信号机制或者让子进程被操作系统接管来解决僵尸进程累积的问题：

信号机制，子进程退出时操作系统会向父进程发送 SIGCHLD 信号，父进程每收到一个 SIGCHLD 信号就会执行一次 signal_handler，但是一个 SIGCHLD 可能对应多个子进程退出所以要循环回收所有子进程

void signal_handler(int signo) {
    pid_t pid;
    while ((pid = waitpid(-1, NULL, WNOHANG)) > 0)
        printf("child terminated pid = %d\n", pid);
}
int main(){
    signal(SIGCHLD, signal_handler);
    pid_t pid;

    for (int i = 0; i < 5; ++i) {
        pid = fork();

        if (pid < 0) {
            perror("fork error");
            exit(1);
        } else if (pid == 0) {
            printf("I am child pid = %d\n", getpid());
            sleep(1);
            exit(0);
        }
    }

    pid = fork();

    if (pid < 0) {
        perror("fork error");
        exit(1);
    } else if (pid == 0) {
        printf("I am child pid = %d\n", getpid());
        sleep(2);
        exit(0);
    }

    while (1) {
        sleep(1);
    }
}

两次 fork，使用 fork 创建一个子进程，然后子进程再 fork 创建一个孙子进程，然后子进程就退出，孙子进程执行具体任务

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
int main() {
    pid_t pid1 = fork();

    if (pid1 < 0) {
        perror("fork error");
        exit(1);
    } else if (pid1 == 0) {
        pid_t pid2 = fork();
        if (pid2 < 0) {
            perror("fork error");
            exit(1);
        } else if (pid2 == 0) {
            // 孙子进程
            sleep(5);
            printf("grandchild process done\n");
            exit(0);
        }
        // 子进程直接退出
        exit(0);
    }
    waitpid(pid1, NULL, 0);
    printf("child terminated\n");
    while (1) {
        sleep(1);
    }
}

waitpid

pid_t waitpid(pid_t pid, int *status, int options);

pid
- >0：等待指定子进程
- -1：等待任意子进程（和 wait 一样）
options
- 0：阻塞（默认）
- WNOHANG：不阻塞（如果没有子进程退出，立刻返回 0）

exec

exec()系统调用用于加载一个新的程序来替换当前进程的地址空间，exec 并不是只一个系统调用，而是多个：

函数名	是否查找 `$PATH`	参数传递方式	支持环境变量传递	说明
`execl`	否	列表形式	否	每个参数单独列出，以 `NULL` 结尾
`execlp`	是	列表形式	否	会在 `$PATH` 中查找可执行文件
`execle`	否	列表形式	是	可以指定新程序的环境变量
`execv`	否	数组（argv）形式	否	适合动态构造参数列表
`execvp`	是	数组（argv）形式	否	最常用形式之一，会查找 `$PATH`
`execve`	是	数组（argv）形式	是	可以设置环境变量

l 为 list，以列表传递参数，v 为 argv，以数组传递参数，p 为 path，查找 PATH 环境变量，e 为 environment，指定环境变量
以下为使用示例：

// execl
execl("/bin/ls", "ls", "-l", NULL);

// execlp（自动在 $PATH 查找 "ls"）
execlp("ls", "ls", "-l", NULL);

// execle（可以设置环境变量）
char *envp[] = {"MYVAR=value", NULL};
execle("/bin/env", "env", NULL, envp);

// execv
char *argv[] = { "ls", "-l", NULL };
execv("/bin/ls", argv);

// execvp
char *argv[] = { "ls", "-l", NULL };
execvp("ls", argv);

// execve
char *argv[] = { "env", NULL };
char *envp[] = {"MYVAR=value", NULL};
execve("/bin/env", argv, envp);

exit

使用 exit 系统调用结束当前进程（当前进程变成僵尸进程）并设置退出码以及将当前进程的所有子进程都移交给 init/systemd（由于父进程结束了所有子进程都变成了孤儿进程，所以要被 init/systemd 收养）
父进程需要调用 wait 来回收子进程并读取子进程状态码，wait 获取到的状态码中不只包含子进程的结束码，还会包含信号编码，具体结构如下：

bits 31 -------------------------------------- 0
      [ 高 16 位未定义 | 次低 8 位 | 第 8 位 | 低 7 位 ]
                               ↑                  ↑
                           exit code            signal

使用状态码宏定义来查看进程的结束信息，WIFEXITED(status)返回是否正常退出（调用了exit()或者返回），本质是(0x7f & status) == 0，WEXITSTATUS(status)返回退出状态（exit(x) 中的 x）,仅当 WIFEXITED(status) 为 1 时有意义，否则为未定义的值，本质是(0xff00 & status) >> 8。

vfork（不推荐使用）

vfork()是为了加速 fork()而存在的危险但快速的优化版，vfork()系统调用将会创建一个跟父进程共享同一片内存空间的子进程，然后阻塞父进程，当子进程调用 exit 后父进程就会被唤醒，由于父进程和子进程共享同一片内存空间，当子进程修改了栈和堆中数据父进程醒来时用的就是被篡改的数据，这样很可能导致父进程的异常、崩溃和难以发现的 bug，所以 vfork 仅适用于简单的场景，比如 fork 完后就调用 exec 的情况（终端启动其他程序），不会对父的内存空间做修改。
但由于现代操作系统都会使用 COW 技术，所以 fork 也已经很快了，新的代码中不推荐使用 vfork 因为它的危险性要远大于所带来的便利，除非你是极其优秀的程序员能够保证不出现以上问题。

程序、进程和线程

分时系统

现代操作系统都是分时系统。通过让一个进程只运行一个时间片，然后切换到其他进程，这样操作系统就提供了存在多个虚拟 CPU 的假象。这就是时分共享技术，允许用户并发的运行多个进程，潜在的开销就是性能损失，当 CPU 切换到其他进程中时就会产生开销。
要实现 CPU 的虚拟化，操作系统就需要一些低级机制和一些高级智能。机制就是一些低级方法或协议，实现了所需功能，比如上下文切换（context switch），它让操作系统能够停止运行一个程序并在给定的 CPU 上运行另一个程序。智能就是一些策略，是操作系统内做出某种决定的算法，例如给定一组可能的程序要在 CPU 上运行，操作系统应该要运行哪个程序？操作系统中的调度策略（schedule policy）会做出这样的决定，可能利用历史信息（比如哪个程序最后一分钟运行的更多）、工作负载知识（比如运行什么类型的程序）以及性能指标（比如系统是否针对交互式性能或吞吐量进行优化）来做出决定。
在许多操作系统中的通用设计范式是将高级策略和低级机制分离，底层机制解决怎么做（how）的问题，高级策略解决哪个的（which）问题，这种模块化的设计能够将这两者进行解耦，在设计策略的时候不需要关心机制的底层设计是什么，只需要关心策略本身。

机制：受限直接运行

为了程序尽可能快的运行，我们可以使用一种技术，受限直接运行（limited direct execute）。
我们将会从两个部分来了解这个技术，分别是受限的和直接运行。

直接运行

直接运行部分很简单，就是直接在 CPU 上运行程序即可。因此，当 OS 希望启动程序时，它会在程序列表中为其创建一个进程条目，为其分配一些内存，将程序代码（从持久化设备中）加载到内存中，找到程序的入口点（main()函数等类似的），跳转到那里，开始运行用户程序的代码，将 CPU 执行权交给用户程序，用户程序运行结束后就会将执行权交回 OS。下图为直接运行的示意图：

操作系统	程序
在进程列表上创建条目为程序分配内存将程序加载到内存中根据 argc/argv 设置程序栈
清除寄存器执行 call main()方法
	执行 main()方法从 main 中执行 return
释放进程的内存将进程从进程列表中清除

看起来非常简单，但是现在出现了两个问题：

OS 如何保证这个用户程序不做任何我们不希望的事情且高效的运行程序
当运行一个进程时，如何将其停下并切换到其他进程，实现虚拟 CPU 的时分共享

下面我们将会解决它们。

受限的操作

硬件上直接运行进程的优势就是快，但当进程希望执行一些受限的操作（比如向磁盘发出 I/O 请求，向系统申请更多资源）时，我们不应该直接简单地让任何进程向磁盘发出 I/O。
硬件通过提供不同的执行模式来实现这一点，在用户模式（user mode）下，应用程序不能完全访问硬件资源，如果应用程序这么做了就会导致处理器引发异常，操作系统可能就会终止进程，而在内核模式（kernel mode）下，操作系统可以访问机器的全部资源，操作系统在这个模式下可以进行任何它想进行的操作。
然后我们还缺少一个两种模式之间切换的方法，所以硬件还提供了陷入（trap）内核和从陷阱返回（return from trap）到用户模式的指令。操作系统会将那些受限的操作（比如访问系统文件、创建和销毁进程、与其他进程通讯，以及分配更多内存等）以系统调用（system call）的方式向外暴露，供用户程序调用。要执行系统调用，进程必须执行特殊的陷阱（trap）指令，该指令会跳入内核中并将执行模式更改为内核模式，进入内核后，系统就可以执行任何需要的受限操作（如果允许），从而为调用进程完成所需的工作，完成后，操作系统就会调用特殊的从陷阱返回（return from trap）指令，该指令会跳回调用进程并将执行模式更改回用户模式。在处理陷阱时，硬件需要将调用进程的寄存器保存好以便在返回时将调用者的状态恢复正常执行。例如，在 x86 中，处理器会将程序计数器（PC）、标志和一些其他寄存器压入每个进程的内核栈（kernel stack）中，从陷阱返回时将这些值弹出并恢复状态。在不同硬件平台上，这些约定是不一样的，但是基本概念是相似的。
以下为 xv6 for x86 对寄存器保存的实现：

#include "mmu.h"

  # vectors.S sends all traps here.
.globl alltraps
alltraps:
  # Build trap frame.
  pushl %ds
  pushl %es
  pushl %fs
  pushl %gs
  pushal

  # Set up data segments.
  movw $(SEG_KDATA<<3), %ax
  movw %ax, %ds
  movw %ax, %es

  # Call trap(tf), where tf=%esp
  pushl %esp
  call trap
  addl $4, %esp

  # Return falls through to trapret...
.globl trapret
trapret:
  popal
  popl %gs
  popl %fs
  popl %es
  popl %ds
  addl $0x8, %esp  # trapno and errcode
  iret

还有一个问题，陷阱如何知道要运行 OS 中哪部分代码，所以硬件还提供了让操作系统告诉硬件陷阱表（trap table）在内存中的位置的相应指令。这样就能让任何进程都不能随意指定要跳转到内核代码地址，不然的话如果进程指定跳转到受限操作的内核代码的检查部分后面就变成了直接执行受限操作了，那么受限就失效了。机器启动时默认是内核模式，然后加载内核，内核使用内核模式根据需求自由更改机器的硬件配置，进行设置陷阱表（trap table）告诉机器当出现不同的中断时应该执行哪个处理程序。一旦硬件被通知，它就会记住这些处理程序，直到下一次重启机器。

下面是受限直接运行的示意图：

启动时：

操作系统（内核模式）	硬件
初始化陷阱表
	记住陷阱处理程序的地址

运行时：

操作系统（内核模式）	硬件	程序（用户模式）
在进程列表上创建条目为程序分配内存将程序加载到内存中根据 argc/argv 设置程序栈用寄存器/程序计数器填充内核栈从陷阱返回
	从内核栈恢复寄存器转向用户模式跳到 main
		运行 main …… 调用系统调用陷入操作系统
	将寄存器保存到内核栈转向内核模式跳到陷阱处理程序
处理陷阱做系统调用的工作从陷阱返回
	从内核栈恢复寄存器转向用户模式跳到陷阱之后的程序计数器
		……从 main 返回陷入操作系统（通过 exit()）
释放进程内存将进程从进程列表中清除

进程间切换

直接执行还有一个问题就是如何实现进程间切换，现在当一个进程在 cpu 上运行时，意味着操作系统完全没有运行，那么操作系统应该如何重获 CPU 的控制权。

协作方式：等待系统调用

在这种方式下，操作系统会默认相信系统的进程会合理运行，一个运行时间过长的进程被假定会定期方式 CPU，让操作系统可以决定运行其他任务。
因为进程大多数都要依赖系统调用，当进程进行系统调用时就会将 CPU 的控制权交给操作系统。像这样的系统一般会包含一个显式的 yield 系统调用，这个调用什么都不干，就是将控制权交回操作系统，以便系统能运行其他进程。
如果进程执行了某种非法操作，也会将控制权转移给操作系统。例如，应用程序以 0 为除数，或者尝试访问应该无法访问的内存，就会陷入操作系统，操作系统就会再次控制 CPU 并有可能终止进程。

非协作方式：操作系统控制

为了实现这一点，硬件提供了时钟中断这一功能，时钟设备可以被编程为每隔几毫秒产生一次中断。产生中断时，当前进程暂停，操作系统中预先配置的中断程序（interrupt handler）会运行。此时操作系统重获了 CPU 的控制权，因此它可以做它想做的事：停止当前进程，并启动另一个进程。
中断操作和陷入操作一致，硬件需要保存寄存器状态，在从陷入返回时需要恢复这些状态。

保存和恢复上下文

在切换时，操作系统会执行一些底层代码，也就是上下文切换（context switch），和我们在上续中讨论的陷入时保存寄存器值和返回时恢复寄存器值类似，而是在切换进程时，操作系统将会为当前进程保存一些寄存器值到它的内核栈中，然后为即将要执行的进程恢复一些寄存器值从它的内核栈中，这样操作系统就能完成进程的切换了。

下面是时间中断的受限直接执行示意图：

启动时：

操作系统（内核模式）	硬件
初始化陷阱表
	记住以下地址：系统调用处理程序时钟处理程序
启动中断时钟
	启动时钟每隔 xms 中断 CPU

运行时：

操作系统（内核模式）	硬件	程序（用户模式）
		进程 A……
	时钟中断将寄存器（A）保存到内核栈（A）转向内核模式跳到陷阱处理程序
处理陷阱调用 switch()例程将寄存器（A）保存到进程结构（A）将进程结构（B）恢复到寄存器（B）从陷阱返回（进入 B）
	从内核栈（B）恢复寄存器（B）转向用户模式跳到 B 的程序计数器
		进程 B……

以下是 xv6 for x86 中上下文切换的实现：

# Context switch
#
#   void swtch(struct context **old, struct context *new);
#
# Save the current registers on the stack, creating
# a struct context, and save its address in *old.
# Switch stacks to new and pop previously-saved registers.

.globl swtch
swtch:
  movl 4(%esp), %eax
  movl 8(%esp), %edx

  # Save old callee-saved registers
  pushl %ebp
  pushl %ebx
  pushl %esi
  pushl %edi

  # Switch stacks
  movl %esp, (%eax)
  movl %edx, %esp

  # Load new callee-saved registers
  popl %edi
  popl %esi
  popl %ebx
  popl %ebp
  ret

策略：进程调度

有了以上的机制，我们可以进行进程间的切换等操作了，现在我们开始讨论在机制之上的策略。
在后面讨论进程调度策略时我们会有以下假设：

所有的进程都只用 CPU（即它们不进行 I/O 操作）
每个工作的运行时间都是已知

调度指标

评判调度算法之间的优劣会用以下度量指标：

周转时间，越小越好

$$ T*{周转时间}=T*{完成时间}-T_{到达时间} $$

响应时间，越小越好

$$ T*{响应时间}=T*{首次运行}-T_{到达时间} $$

先进先出（FIFO）

先进先出（First In First Out，FIFO）调度有时候也被称为先到先服务（First Come First Served，FCFS）调度。具体来说就是优先服务最先到的任务，在服务途中不会考虑是否要切换到一个新到达的任务，这种也被叫做非抢占式（non-preemptive）调度，不过现代化的操作系统都是抢占式（preemptive）调度的。
现在假设有三个任务（A、B、C）在 t=0s 到达，A、B、C 均耗时 10s，那么 A 会在 10s 时完成，B 会在 20s 时完成，C 会在 30s 时完成，平均周转时间为$(10+20+30)/3=20s$，但如果 A 耗时变成了 100s，那么平均周转时间就会变成了$(100+110+120)/3=110s$，所以说 FIFO 并不是一个很好的算法。

最短任务优先（SJF）

最短任务优先（Shortest Job First，SJF）调度是 FIFO 的优化版，具体来说就是优先服务时间最短的任务，在服务途中同样不会考虑是否要切换到一个新到达的任务，这种策略对于处理同时到达的任务确实是最优的。
在上续例子中，使用 SJF 策略，平均周转时间变为$(10+20+120)/3=50s$。但是如果任务并不是同时到达的呢，现在 B、C 变为在 t=10s 时到达，那么在 10s 时正在服务 A，B、C 需要等到 A 处理结束，平均周转时间就会变为$(100+(110-10)+(120-10))/3=103.33s$，同样是不好。

最短完成时间优先（STCF）

最短完成时间优先（Shortest Time-to-Completion First）调度，又称为抢占式最短作业优先（Preemptive Shortest Job First，PSJF）策略，这是一种抢占式策略，每当新的任务到达时就会确定剩余工作和新工作的剩余时间中，然后调度剩余时间最少的哪个。
比如在以上例子中，在 t=10s 时，B、C 同时到达，此时策略就会确定 A 的剩余时间为 90s、B 为 10s、C 为 10s，然后调度时间最少的 B，当 B 结束，时间来到了 20s，此时 A 的剩余时间为 90s、C 为 10s，调度 C，最后 C 结束再调度 A，这个策略使得平均周转达到了$(120+10+20)/3=50s$，成功在任务同时到达和不同时达到的情况下做到了平均周转时间最好，但是如果我们看向另外一个指标响应时间呢，STCF 在上续情况下平均响应时间为$(0+0+10)/3=3.33s$，好像并不是很好，如果 C 任务是一个交互性任务，你在点下鼠标后需要等 10s 后才能得到响应，这样体验显然不是很好。

轮转（RR）

轮转（Round-Robin）调度，基本思想很简单：RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。所以 RR 有时被称为时间切片（time-slicing）。有一个需要注意的地方，时间片长度一定要为时钟中断周期的整数倍数，比如时钟中断周期为 10ms 那么时间片长度可以 10ms、20ms 或 10ms 的任何整数倍数。
假设现在有三个任务（A、B、C），每个任务都耗时 5s，都在 t=0s 到达系统，设置时间片长度为 1s，那么在 t=0s 时就会服务 A，t=1s 就会服务 B，t=2s 就会服务 C，以此类推，直到 15s 时全部任务结束，此时平均响应时间为$(0+1+2)/3=1s$，如果是 STCF 的话，平均响应时间为$(0+5+10)/3=5s$。如你所见，时间片长度对于 RR 来说是十分重要的，越短，RR 在响应时间上表现越好，但是时间片太短也是有问题的，因为上下文切换是有成本的，过多的上下文切换会影响整体的性能，较长的时间片能摊销上下文切换成本又不会使得系统不及时响应，假设上下文切换的成本为 1ms，如果设置时间片长度为 10ms，那么整个系统就会浪费大约 10%的时间在上下文切换中，如果增加时间片长度到 100ms，那么就只会浪费不到 1%的时间在上下文切换中，实际上下文切换的性能成本也是不小的，进程运行时，不只有寄存器的状态，还会在 CPU 高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态，进程切换需要将这些状态全部刷新，引入新进程的状态。
但是 RR 是一个好的策略吗，对于响应时间来说，RR 确实做的非常好，但是我们回到周转时间上，RR 在上述例子中，A 会在 13s 完成，B 会在 14s 完成，C 会在 15s 完成，平均响应时间为 14s，这非常不好，在很多情况下甚至连最简单的 FIFO 都不如。

解决假设

以上的讨论都是建立在两个假设下，但是实际应用上这些假设都并不成立，我们来解决这些假设不存在的问题

结合 I/O

假设有两个任务，A 每运行 10ms 后都要发起 I/O，I/O 耗时 10ms，A 总耗时 50ms，B 不使用 I/O，总耗时 50ms。在调度时，我们应该要把 A 看成 5 个独立的每个耗时 10ms 的小任务，当 t=0s 时，A 运行，当 t=10ms 时，A 发起 I/O，转入阻塞状态，B 运行，当 t=20ms 时，A 的 I/O 结束转入就绪状态，此时对于 STCF 来说，A 剩余 10ms，B 剩余 40ms，A 运行，依次类推，这样就能在 A 进行 I/O 的时候运行其他进程，实现了重叠（overlap）。

无法预知

在实际应用中，操作系统对每个作业的长度都知之甚少，所以我们如何能建立一个没有预知的 SJF/STCF，或者更进一步，将一些已经看到的想法和 RR 调度结合起来，这些将会在后面来解决。

多级反馈队列（MLFQ）

多级反馈队列（Mulit-level Feedback Queue，MLFQ），MLFQ 的提出是为了在无法预知工作长度的前提下，同时减少响应时间和周转时间。MLFQ 中有多个队列（queue），每个队列都有不同的优先级（priority level）。在每个队列中会有多个工作，它们具有相同的优先级，因此我们将会对这些工作采用轮转（RR）调度。MLFQ 并不会为工作指定固定不变的优先级，而是根据观察到的行为来调整它的优先级。所以我们尝试构建一下 MLFQ 的规则：

如果 A 的优先级 > B 的优先级，运行 A（不运行 B）
如果 A 的优先级 = B 的优先级，轮转运行 A 和 B
工作进入系统时，放在最高优先级（最上层队列）
工作用完整个时间片后，降低其优先级（移入下一个队列），如果工作在其时间片以内主动释放 CPU，则优先级不变

我们来看看这几条规则是如何解决问题的，现在假设只有 3 级优先级（Q2、Q1、Q0）：

单个长工作

该工作先会进入最高优先级队列 Q2，执行一个 10ms 的时间片后调度程序将工作优先度减 1，在 Q1 执行一个时间片之后进入 Q0，然后一直待在 Q0 中。

来了个短工作

此时系统正在运行长工作 A，A 当前已经处在 Q0 中，这时来了个短工作 B 就会加入到最高优先级队列 Q2 中，然后执行一个时间片到 Q1，在 Q1 中再执行一个时间片，如果这两个时间片内能完成 B 那么，B 就执行完毕，否则就进入 Q0 和 A 一起轮转，所以当有一个工作进入系统，系统无法预知它是长工作还是短工作，就先假设它是短工作，如果不是则消耗完高优先级队列的短时间片之后就会进入低优先级队列和其他长工作一起轮转，通过这种方式，MLFQ 近似于 SJF。

如果有 I/O

如果短工作带有 I/O 操作呢，假设进入系统的交互型工作有大量的 I/O 操作（比如等待用户的鼠标键盘输入），它会在时间片结束之间放弃 CPU，这种情况我们不行处罚它，只是保持它的优先级不变。

我们当前已经构建出了基础的 MLFQ，它看上去还不错，长工作之间可以公平地分享 CPU，又能给短工作或交互型工作很好的响应时间。但是我们仍然会有一下问题：

会有饥饿（starvation）问题，如果系统有太多的交互型工作，就会不断占用 CPU，导致长工作永远无法得到 CPU
如果些聪明的用户重写应用程序，通过在进程时间片用完之前，调用一个 I/O 操作（比如访问一个无关的文件），从而主动释放 CPU，来保持高优先级，比如在运行了 99%的时间片时间之后主动放弃一次 CPU，那么此工作就可以做到几乎独占 CPU 了
一个计算密集的进程可能在某段时间表现为一个交互型的进程，我们现在无法让这个进程享受到系统中其他交互型工作的待遇

我们在之前的基础上更改一下 MLFQ 的规则：

如果 A 的优先级 > B 的优先级，运行 A（不运行 B）
如果 A 的优先级 = B 的优先级，轮转运行 A 和 B
工作进入系统时，放在最高优先级（最上层队列）
一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次 CPU），就降低其优先级（移入低一级队列）
经过一段时间 S，就将系统中所有工作重新加入最高优先级队列

更改规则 4，调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时，我们解决了问题 2

加入规则 5，我们在一段时间 S 后，提升系统所有工作的优先级到最高优先级中，来解决问题 1 和 3

现在我们仍然存在一个大问题，如何配置这个调度程序：

配置多少队列
每一层队列的时间片配置多大
为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级

这些问题都没有一个显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会达到令人满意的平衡。
例如，大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如 10ms 或者更少），因而这一层的交互工作可以更快地切换，低优先级队列中更多的是 CPU 密集型工作，配置更长的时间片会取得更好的效果。
Solaris 的 MLFQ 实现（时分调度类 TS）很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。管理员可以通过这些表，让调度程序的行为方式不同。该表默认有 60 层队列，时间片长度从 20ms（最高优先级），到几百 ms（最低优先级），每一秒左右提升一次进程的优先级。

这里是表的结构和默认值：

- ts_quantum: Length of the time-slice (in the actual table, this value is specified in 10ms clock ticks; in the output from running dispadmin, the value is specified in units of 1ms).
- ts_tqexp: Priority level of the new queue on which to place a process if it exceeds its time quantum. Normally this field links to a lower priority time-sharing level.
- ts_slpret: the priority to change to (generally a higher priority) when the job returns from sleeping (i.e., from the blocked queue) if ts_dispwait exceeds ts_maxwait (see next entry).
- ts_maxwait: A per process counter, ts_dispwait, is initialized to zero each time a process is placed back on the dispatcher queue after its time quantum has expired or when it is awakened (ts_dispwait is not reset to zero when a process is preempted by a higher priority process). This counter is incremented once per second. If a process’s ts_dispwait value exceeds the ts_maxwait value for its level, the process’s priority is changed to that indicated by ts_lwait. The purpose of this field is to prevent starvation.
- ts_lwait: the priority to change to (generally a higher priority) if the starvation timer expires before the job consumes its time-slice (i.e., if ts_dispwait exceeds ts_maxwait).

# ts_quantum ts_tqexp ts_slpret ts_maxwait ts_lwait #PRIORITY LEVEL
200 0 50 0 50 # 0
200 0 50 0 50 # 1
200 0 50 0 50 # 2
200 0 50 0 50 # 3
200 0 50 0 50 # 4
200 0 50 0 50 # 5
200 0 50 0 50 # 6
200 0 50 0 50 # 7
200 0 50 0 50 # 8
200 0 50 0 50 # 9
160 0 51 0 51 # 10
160 1 51 0 51 # 11
160 2 51 0 51 # 12
160 3 51 0 51 # 13
160 4 51 0 51 # 14
160 5 51 0 51 # 15
160 6 51 0 51 # 16
160 7 51 0 51 # 17
160 8 51 0 51 # 18
160 9 51 0 51 # 19
120 10 52 0 52 # 20
120 11 52 0 52 # 21
120 12 52 0 52 # 22
120 13 52 0 52 # 23
120 14 52 0 52 # 24
120 15 52 0 52 # 25
120 16 52 0 52 # 26
120 17 52 0 52 # 27
120 18 52 0 52 # 28
120 19 52 0 52 # 29
80 20 53 0 53 # 30
80 21 53 0 53 # 31
80 22 53 0 53 # 32
80 23 53 0 53 # 33
80 24 53 0 53 # 34
80 25 54 0 54 # 35
80 26 54 0 54 # 36
80 27 54 0 54 # 37
80 28 54 0 54 # 38
80 29 54 0 54 # 39
40 30 55 0 55 # 40
40 31 55 0 55 # 41
40 32 55 0 55 # 42
40 33 55 0 55 # 43
40 34 55 0 55 # 44
40 35 56 0 56 # 45
40 36 57 0 57 # 46
40 37 58 0 58 # 47
40 38 58 0 58 # 48
40 39 58 0 59 # 49
40 40 58 0 59 # 50
40 41 58 0 59 # 51
40 42 58 0 59 # 52
40 43 58 0 59 # 53
40 44 58 0 59 # 54
40 45 58 0 59 # 55
40 46 58 0 59 # 56
40 47 58 0 59 # 57
40 48 58 0 59 # 58
20 49 59 32000 59 # 59

其他一些 MLFQ 调度程序没用表，甚至没用本章中讲到的规则，有些采用数学公式来调整优先级。例如，FreeBSD 调度程序（4.3 版本），会基于当前进程使用了多少 CPU，通过公式计算某个工作的当前优先级。另外，使用量会随时间衰减，这提供了期望的优先级提升，但与这里描述方式不同。阅读Epema 的论文，他漂亮地概括了这种使用量衰减（decay-usage）算法及其特征。
最后，许多调度程序有一些我们没有提到的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议（advice），比如通过命令行工具 nice，可以增加或降低工作的优先级（稍微），从而增加或降低它在某个时刻运行的机会。

比例份额调度也成为公平份额（fair-share）调度。比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。比例份额调度有很多种实现，我们这里介绍其中两个：彩票调度和步长调度。

彩票调度（lottery scheduling）

彩票调度正如它的名字一样，通过分配彩票和开奖来决定应该调度哪个程序。假设有两个程序 A、B，我们期望 A 占用 75%的 CPU 时间，B 占用 25%的 CPU 时间，那么我们就给 A 分配 75 张彩票序号为 0-74，B 分配 25 张彩票序号为 75-99，当需要决策调度时我们生成一个 0-99 的随机数，拥有这个数为序号的彩票的程序获得 CPU 的使用权，由于这个调度之中使用到了随机性，所以短期结果不一定符合我们的预期，但是随着这两个工作运行时间越长，它们获得 CPU 时间比例就会越接近期望。
彩票机制还提供了一些机制，以不同且有效的方式来调度彩票。一种方式是利用彩票货币（ticket currency）的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币（局部货币），将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。假设用户 A 和用户 B 每人拥有 100 张彩票。用户 A 有两个工作 A1 和 A2，他以自己的货币，每个工作 500 张（共 1000 张）。用户 B 只运行一个工作，用 B 自己的货币，给它 10 张彩总共 10 张）。操作系统将进行兑换，将 A1 和 A2 拥有的 A 的货币 500 张，兑换成全局货币 50 张。类似地，兑换给 B1 的 10 张彩票兑换成 100 张。然后会对全局彩票货币（共 200
张）举行抽奖，决定哪个工作运行。
另一个有用的机制是彩票转让（ticket transfer）。通过转让，一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端进程向服务端进程发送消息，为了加速服务端执行，客户端进程可以将自己的彩票转让给服务端进程，从而加速执行，服务端执行结束后会将这部分彩票归还给客户端
最后，彩票通胀（ticket inflation）有时也很有用。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。当然在竞争环境中，进程之间互相不信任，这种机制就没什么意义。一个贪婪的进程可能给自己非常多的彩票，从而接管机器。但是，通胀可以用于进程之间相互信任的环境。在这种情况下，如果一个进程知道它需要更多 CPU 时间，就可以增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。
彩票调度的实现也非常的简单，假设现在有 A、B、C 这 3 个进程，A 有 100 张、B 有 50 张、C 有 250 张，A、B、C 进程信息都记录在进程列表链表中，当需要决策时就从总数 400 中选择一个随机数，然后遍历链表，找到那个抽中彩票的进程。

进程队列：

head -> A -> B -> C -> NULL

int counter = 0;
int winner = getrandom(0, totaltickets);
node_t *current = head;
while (current) {
    counter += current -> tickets;
    if (counter > winner) break;
    current = current -> next;
}

步长调度（stride scheduling）

步长调度也很简单。系统中的每个工作都有自己的步长，这个值与票数值成反比。在上面的例子中，A、B、C 这 3 个工作的票数分别是 100、50 和 250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用 10000 除以这些票数值，得到了 3 个进程的步长分别为 100、200 和 40。我们称这个值为每个进程的步长（stride）。每次进程运行后，我们会让它的计数器（称为行程（pass）值）增加它的步长，记录它的总体进展。

current = remove_min(queue); // pick client with minimum pass
schedule(current); // use resource for quantum
current -> pass += current -> stride; // compute next pass using stride
insert(queue, current); // put back into the queue

3 个进程初始行程值都为 0。因此，最初，所有进程都可能被选择执行。假设选择 A（任意的，所有具有同样低的行程值的进程，都可能被选中）。A 执行一个时间片后，更新它的行程值为 100。然后运行 B，并更新其行程值为 200。最后执行 C，C 的行程值变为 40。这时，算法选择最小的行程值，是 C，执行并增加为 80（C 的步长是 40）。然后 C 再次运行（依然行程值最小），行程值增加到 120。现在运行 A，更新它的行程值为 200（现在与 B 相同）。然后 C 再次连续运行两次，行程值也变为 200。此时，所有行程值再次相等，这个过程会无限地重复下去。

行程值（A）（步长=100）	行程值（B）（步长=200）	行程值（C）（步长=40）	谁运行
0	0	0	A
100	0	0	B
100	200	0	C
100	200	40	C
100	200	80	C
100	200	120	A
200	200	120	C
200	200	160	C
200	200	200	……

可以看出，C 运行了 5 次、A 运行了 2 次，B 一次，正好是票数的比例——200、100 和 50。彩票调度算法只能一段时间后，在概率上实现比例，而步长调度算法可以在每个调度周期后做到完全正确。步长调度算法可以做到精确控制，但是彩票调度对于步长调度有一个没有的优势，不需要全局状态。假如一个新的进程进入系统，那么应该将其行程值设置为什么，如果设置为 0 那么新的进程就会独占 CPU 了。而彩票调度算法不需要对每个进程记录全局状态，只需要用新进程的票数更新全局的总票数就可以了。因此彩票调度算法能够更合理地处理新加入的进程。

多处理器调度

现代计算机中多核处理器是十分常见的，因为计算机的架构师们当时难以让但单核 CPU 更快，同时又不增加太多功耗，所以就提出了多核 CPU。
当然，多核 CPU 也带来了许多问题，主要困难是典型的应用程序都只用一个 CPU，添加更多的 CPU 并没有让这类程序运行得更快。为了解决这个问题，不得不重写这些应用程序，使之能并行（parallel）执行，也许使用多线程。多线程应用可以将工作分散到多个 CPU 上，因此 CPU 资源越多就运行越快。
前面我们讨论的进程调度都是单处理器调度，而在多处理器系统中又应该如何拓展我们之前的想法来实现多处理器调度（multiprocessor scheduling）。我们先看看在多处理器系统中会遇到什么与单处理器系统中不一样的问题：

缓存（cache）
并发（concurrent）
缓存亲和度（cache affinity）

下面我们一个个介绍这些问题由来和大致的解决思路。

缓存（cache）

在单 CPU 系统中，存在多级的硬件缓存（hardware cache），一般来说会让处理器更快地执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热的数据的备份。相比之下，内存很大且拥有所有的数据，但访问速度较慢。所以将频繁访问的数据放在缓存当中，可以极大的提高 CPU 对数据的访问速度。举一个例子，程序第一次读取数据时，数据在内存中，因此需要花费较长的时间（可能是数十或数百 ns）。处理器判断该数据很可能会再次被使用，于是将其放入 CPU 缓存中。如果之后程序再次需要使用同样的数据，CPU 会先查找缓存。因为在缓存中找到了数据（缓存命中），所以取数据快得多（比如几纳秒），程序也就运行更快。
缓存是基于局部性（locality）的概念，局部性有两种，即时间局部性和空间局部性。时间局部性是指当一个数据被访问后，它很有可能会在不久、的将来被再次访问，比如循环代码中的数据或指令本身。而空间局部性指的是，当程序访问地址为 x 的数据时，很有可能会紧接着访问 x 周围的数据，比如遍历数组或指令的顺序执行。这些局部性存在大多数程序当中，硬件系统可以很好的预测哪些数据可以放入缓存，从而运行好程序。

而多 CPU 的情况下缓存就要复杂得多。例如，假设一个运行在 CPU 1 上的程序从内存地址 A 读取数据。由于不在 CPU 1 的缓存中，所以系统直接访内存，得到值 D。程序然后修改了地址 A 处的值，只是将它的缓存更新为新值 D’。将数写回内存比较慢，因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给 CPU 2，重新读取地址 A 的数据，由于 CPU 2 的缓存中并没有该数据，所以会接从内存中读取，得到了旧值 D，而不是正确的值 D’。这一普遍的问题称为缓存一致性（cache coherence）问题。这个问题的解决方案有很多，但是在硬件上解决更好一些，大多数现代多核处理器使用 MESI、MOESI 等协议来维护缓存一致性。当 CPU 1 修改地址 A 的缓存行时，其状态变为 Modified (M)，当 CPU 2 试图读取地址 A 时，它会通过总线嗅探发现 CPU 1 拥有 A 的最新版本，CPU 1 会将 D’ 回写到内存，或直接把 D’ 传给 CPU 2。

并发（concurrent）

跨 CPU 访问（尤其是写入）共享数据或数据结构时，需要使用互斥原语（比如锁），才能保证正确性（其他方法，使用无锁（lock-free）数据结构，很复杂，偶尔才使用）。例如，假设多 CPU 并发访问一个共享队列。如果没有锁，即使有底层一致性协议，并发地从队列增加或删除元素，依然不会得到预期结果。需要用锁来保证数据结构状态更新的原子性。比如以下代码：

typedef struct __Node_t {
    int value;
    struct __Node_t *next;
} Node_t;
int List_Pop() {
    Node_t *tmp = head;
    int value = head->value;
    head = head->next;
    free(tmp);
    return value;
}

如果线程 1 执行第一行，会将 head 的当前值存入它的 tmp 变量。如果线程 2 接着也执行第一行，它也会将同样的 head 值存入它自己的私有 tmp 变量（tmp 在栈上分配，因此每个线程都有自己的私有存储）。因此，两个线程会尝试删除同一个链表头，而不是每个线程移除一个元素，这导致了问题（比如在第 4 行重复释放头元素，以及可能两次返回同一个数据）。让这类函数正确工作的方法就是加锁（locking）。这里只需要一个互斥锁（即 pthread_mutex_t m;），然后在函数开始时调用 lock(&m)，在结束时调用 unlock(&m)，确保代码的执行如预期。这样仍然有问题尤其是性能问题。随着 CPU 数量的增加，访问同步共享的数据结构会变得很慢。

缓存亲和度（cache affinity）

一个进程在某个 CPU 上运行时，会在该 CPU 的缓存中维护许多状态。下次该进程在相同 CPU 上运行时，由于缓存中的数据而执行得更快。相反，在不同的 CPU 上执行，会由于需要重新加载数据而很慢。因此多处理器调度应该考虑这种缓存亲和性，并尽可能将进程保持在同一个 CPU 上。

单队列调度

现在我们来讨论如何设计一个多处理器系统的调度程序。最基本的方式是简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列中，我们称之为单队列多处理器调度（Single Queue Multiprocessor Scheduling，SQMS）。这个方法最大的有点就是简单。它不需要太多修改，就可以将原有的策略用于多个 CPU，选择最适合的工作来运行。
但是 SQMS 有几个明显的短板。第一个是缺乏可扩展性（scalability）。为了保证在多 CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性，保证结果的正确，然而，锁可能带来巨大的性能损失，尤其是随着系统中的 CPU 数增加时。随着这种单个锁的争用的增加，系统花费了越来越多的时间在锁的开销上，较少的时间用于系统应该完成的工作。第二个问题就是缓存亲和性，假设我们现在有 5 个工作（A、B、C、D、E）和 4 个处理器。

进程队列如下：

head -> A -> B -> C -> D -> E -> NULL

每个 CPU 都简单地从全局共享的队列中选取下一个工作执行，因此每个工作都不断在不同 CPU 之间转移，这与缓存亲和的目标背道而驰，每个 CPU 可能的调度序列如下：

为了解决这个问题，大多数 SQMS 调度程序都引入一些亲和性机制，尽可能让进程在同一个 CPU 上运行。保持一些工作的亲和度的同时，可能需要牺牲其他工作的亲和度来实现负载均衡。例如，针对同样的 5 个工作优化后的调度如下：

这种调度中，A、B、C、D 这 4 个工作都保持在同一个 CPU 上，只有工作 E 不断地来回迁移（migrating），从而尽可能多地获得缓存亲和度。为了公平起见，之后我们可以选择不同的工作来迁移。但实现这种策略可能很复杂。
我们看到，SQMS 调度方式有优势也有不足。优势是能够从单 CPU 调度程序很简单地发展而来，根据定义，它只有一个队列。然而，它的扩展性不好（由于同步开销有限），并且不能很好地保证缓存亲和度。

多队列调度

正是由于单队列调度程序的这些问题，有些系统使用了多队列的方案，比如每个 CPU 一个队列。这种被称为多队列多处理器调度（Multi-Queue Multiprocessor Scheduling，MQMS）。在 MQMS 中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个 CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。例如，假设系统中有两个 CPU（CPU 0 和 CPU 1）。这时一些工作进入系统：A、B、C 和 D。由于每个 CPU 都有自己的调度队列，操作系统需要决定每个工作放入哪个队列。进程队列如下：

Q0 -> A -> C -> NULL
Q1 -> B -> D -> NULL

根据不同队列的调度策略，每个 CPU 从两个工作中选择决定谁将运行。例如，利用轮转，调度结果可能如下所示：

MQMS 比 SQMS 有明显的优势，它天生更具有可扩展性。队列的数量会随着 CPU 的增加而增加，因此锁和缓存争用的开销不是大问题。此外，MQMS 天生具有良好的缓存亲和度。所有工作都保持在固定的 CPU 上，因而可以很好地利用缓存数据。
但是，MQMS 带来了一个新问题，负载不均（load imbalance）。假定和上面设定一样（4 个工作，2 个 CPU），但假设一个工作这时执行完毕。现在调度队列如下：

Q0 -> A -> NULL
Q1 -> B -> D -> NULL

如果对系统中每个队列都执行轮转调度策略，会获得如下调度结果:

可以看到 A 获得了 B 和 D 两倍的 CPU 时间，这不是期望的结果，如果情况更加极端一些，A 和 C 都执行完毕了，系统中只剩下 B 和 D，那么调度队列如下：

Q0 -> NULL
Q1 -> B -> D -> NULL

因此调度结果如下：

如何解决这个问题，最显然的方法就是让工作跨队列移动，我们称之为迁移（migration）。通过这项技术我们可以真正实现负载均衡。如果是以下例子：