分时多任务

多道程序成功地实现了进程的并发执行, 但这种并发不一定是公平的. 如果一个进程长时间不触发I/O操作, 多道程序系统并不会主动将控制权切换到其它进程, 这样其它进程就得不到运行的机会. 想象一下, 如果你在开黑的时候, Windows突然在后台进行自动更新, 队友就打电话问你是不是掉线了, 你一定会非常不爽. 所以多道程序系统更多还是用在批处理的场景当中, 它能保证CPU满负荷运转, 但并不适合用于交互式的场景.

如果要用于交互式场景, 系统就要以一定的频率在所有进程之间来回切换, 保证每个进程都能及时得到响应, 这就是分时多任务. 从触发上下文切换的角度看, 分时多任务可以分成两类. 第一类是协同多任务, 它的工作方式基于一个约定: 用户进程周期性地主动让出CPU的控制权, 从而让其它进程得到运行的机会. 这件事需要操作系统提供一个特殊的系统调用, 那就是我们在PA3中实现的SYS_yield. 在PA3中看似没什么用的SYS_yield, 其实是协同多任务操作系统中上下文切换的基石.

说是"协同", 是因为这个机制需要所有进程一起合作, 共同遵守这个约定, 整个系统才能正确工作. 一些简单的嵌入式操作系统或者实时操作系统会采用协同多任务, 因为这些系统上运行的程序都是固定的那么几个, 让它们共同遵守约定来让出CPU并不困难. 但试想一下, 在多用户操作系统中, 如果有一个恶意进程故意不遵守这个约定, 不调用SYS_yield, 或者无意陷入了死循环, 整个系统将会被这个进程独占. 某些上古时期的Windows版本就采用了协同多任务的设计, 操作系统经常会被一些有bug的程序弄垮.

之所以协同多任务会出现这样的问题, 是系统将上下文切换的触发条件寄托在进程的行为之上. 我们知道调度一个进程的时候, 整个计算机都会被它所控制, 无论是计算, 访存, 还是输入输出, 都是由进程的行为来决定的. 为了修复这个漏洞, 我们必须寻找一种无法由进程控制的机制.

来自外部的声音

回想起我们考试的时候, 在试卷上如何作答都是我们来控制的, 但等到铃声一响, 无论我们是否完成答题, 都要立即上交试卷. 我们希望的恰恰就是这样一种效果: 时间一到, 无论正在运行的进程有多不情愿, 操作系统都要进行上下文切换. 而解决问题的关键, 就是时钟. 我们在IOE中早就已经加入了时钟了, 然而这还不能满足我们的需求, 我们希望时钟能够主动地通知处理器, 而不是被动地等着处理器来访问.

这样的通知机制, 在计算机中称为硬件中断. 硬件中断的实质是一个数字信号, 当设备有事件需要通知CPU的时候, 就会发出中断信号. 这个信号最终会传到CPU中, 引起CPU的注意.

第一个问题就是中断信号是怎么传到CPU中的. 支持中断机制的设备控制器都有一个中断引脚, 这个引脚会和CPU的INTR引脚相连, 当设备需要发出中断请求的时候, 它只要将中断引脚置为高电平, 中断信号就会一直传到CPU的INTR引脚中. 但计算机上通常有多个设备, 而CPU引脚是在制造的时候就固定了, 因而在CPU端为每一个设备中断分配一个引脚的做法是不现实的.

为了更好地管理各种设备的中断请求, IBM PC兼容机中都会带有Intel 8259 PIC(Programmable Interrupt Controller, 可编程中断控制器). 中断控制器最主要的作用就是充当设备中断信号的多路复用器, 即在多个设备中断信号中选择其中一个信号, 然后转发给CPU.

第二个问题是CPU如何响应到来的中断请求. CPU每次执行完一条指令的时候, 都会看看INTR引脚, 看是否有设备的中断请求到来. 一个例外的情况就是CPU处于关中断状态, 此时即使INTR引脚为高电平, CPU也不会响应中断. CPU的关中断状态和中断控制器是独立的, 中断控制器只负责转发设备的中断请求, 最终CPU是否响应中断还需要由CPU的状态决定.

CPU的关中断状态可以通过软件来控制, 不同的ISA对此有不同的定义, 具体地:

• 在x86中, 如果EFLAGS中的IF位为0, 则CPU处于关中断状态
• 在mips32中, 如果status中的IE位为0, 或EXL位为1, 或ERL位为1, 则CPU处于关中断状态
• 在riscv32中, 如果sstatus中的SIE位为0, 则CPU处于关中断状态
  • 事实上, riscv32标准的中断响应机制还有更多内容, 在PA中我们进行了简化. 如需了解完整的中断响应机制, 请查阅相关手册.

如果中断到来的时候, CPU没有处在关中断状态, 它就要马上响应到来的中断请求. 我们刚才提到中断控制器会生成一个中断号, CPU将会保存中断上下文, 然后根据这个中断号在IDT中进行索引, 找到并跳转到入口地址, 进行一些和设备相关的处理. 这个过程和之前提到的异常处理十分相似.

对CPU来说, 设备的中断请求何时到来是不可预测的, 在处理一个中断请求的时候到来了另一个中断请求也是有可能的. 如果希望支持中断嵌套 -- 即在进行优先级低的中断处理的过程中, 响应另一个优先级高的中断 -- 那么堆栈将是保存中断上下文信息的唯一选择. 如果选择把上下文信息保存在一个固定的地方, 发生中断嵌套的时候, 第一次中断保存的上下文信息将会被优先级高的中断处理过程所覆盖, 从而造成灾难性的后果.

抢占多任务

分时多任务的第二类就是抢占多任务, 它基于硬件中断(通常是时钟中断)强行进行上下文切换, 让系统中的所有进程公平地轮流运行. 在抢占多任务操作系统中, 中断是其赖以生存的根基: 只要中断的东风一刮, 操作系统就会卷土重来, 一个故意死循环的恶意程序就算有天大的本事, 此时此刻也要被请出CPU, 从而让其它程序得到运行的机会,

在NEMU中, 我们只需要添加时钟中断这一种中断就可以了. 由于只有一种中断, 我们也不需要通过中断控制器进行中断的管理, 直接让时钟中断连接到CPU的INTR引脚即可. 而对于时钟中断的中断号, 不同的ISA有不同的约定. 时钟中断通过nemu/src/device/timer.c中的timer_intr()触发, 每10ms触发一次. 触发后, 会调用dev_raise_intr()函数(在nemu/src/device/intr.c中定义). 你需要:

• 在cpu结构体中添加一个bool成员INTR.
• 在dev_raise_intr()中将INTR引脚设置为高电平.
• 在exec_once()的末尾添加轮询INTR引脚的代码, 每次执行完一条指令就查看是否有硬件中断到来:

  if (isa_query_intr()) update_pc();
  

• 实现isa_query_intr()函数(在nemu/src/isa/$ISA/intr.c中定义):

#define IRQ_TIMER 32          // for x86
#define IRQ_TIMER 0           // for mips32
#define IRQ_TIMER 0x80000005  // for riscv32

bool isa_query_intr(void) {
  if ( ??? ) {
    cpu.INTR = false;
    raise_intr(IRQ_TIMER, ???);
    return true;
  }
  return false;
}

• 修改raise_intr()中的代码, 让处理器进入关中断状态:
  • x86 - 在保存EFLAGS寄存器后, 将其IF位置为0
  • mips32 - 将status.EXL位置为1
    • 你还需要修改eret指令的实现, 将status.EXL置为0
  • riscv32 - 将sstatus.SIE保存到sstatus.SPIE中, 然后将sstatus.SIE位置为0
    • 你还需要修改sret指令的实现, 将sstatus.SPIE还原到sstatus.SIE中, 然后将sstatus.SPIE位置为1

在软件上, 你还需要:

• 在CTE中添加时钟中断的支持, 将时钟中断打包成_EVENT_IRQ_TIMER事件.
• Nanos-lite收到_EVENT_IRQ_TIMER事件之后, 调用_yield()来强制当前进程让出CPU, 同时也可以去掉我们之前在设备访问中插入的_yield()了.
• 为了可以让处理器在运行用户进程的时候响应时钟中断, 你还需要修改_ucontext()的代码, 在构造上下文的时候, 设置正确中断状态, 使得将来返回到用户进程后CPU处于开中断状态.

基于时间片的进程调度

在抢占多任务操作系统中, 由于时钟中断以固定的速率到来, 时间被划分成长度均等的时间片, 这样系统就可以进行基于时间片的进程调度了.

我们会发现, 给仙剑奇侠传分配更多的时间片之后, 其运行速度有了一定的提升. 这再次向我们展现了"分时"的本质: 程序之间只是轮流使用处理器, 它们并不是真正意义上的"同时"运行.

真实系统中的调度问题比上面仙剑奇侠传的例子要复杂得多. 比如双十一节, 全国一瞬间向阿里巴巴的服务器发起购物请求, 这些请求最终会被转化成上亿个进程在成千上万台服务器中被处理. 在数据中心中如何调度数量如此巨大的进程, 来尽可能提高用户的服务质量, 是阿里巴巴一直都面临的严峻挑战.

抢占和并发

如果没有中断的存在, 计算机的运行就是完全确定的. 根据计算机的当前状态, 你完全可以推断出下一条指令执行后, 甚至是执行100条指令后计算机的状态. 中断本质上是计算机的一种外部输入, 除了作为抢占多任务操作系统的根基之外, 其不确定性也给计算机带来了不少有趣的特性. 比如GNU/Linux内核会维护一个entropy pool, 用于收集系统中的熵(不确定性). 每当中断到来的时候, 就会给这个pool添加一些熵. 通过这些熵, 我们就可以生成真正的随机数了, /dev/random就是这样做的. 有了真正的随机数, 恶意程序的攻击也变得相对困难了(比如ASLR), 系统的安全也多了一分保障.

但另一方面, 中断的存在也不得不让程序在一些问题的处理上需要付出额外的代价. 由于中断随时可能会到来, 如果两个进程有一个共享的变量v(比如迅雷多线程下载共享同一个文件缓冲区), 一个进程A往v中写0, 刚写完中断就到来, 但当下次A再次运行的时候, v的值就可能不再是0了. 从某种程度上来说, 这也是并发惹的祸: 可能进程B在并发地修改v的值, 但A却不知情. 这种由于并发造成的bug, 还带有不确定性的烙印: 如果中断到来的时机不一样, 就不会触发这个bug了. 所以这种bug又叫Heisenbug, 和量子力学的测不准原理类似, 你想调试它的时候, 它可能就不出现了.

不但是用户进程之间可能会有共享变量, 操作系统内核更是并发bug的重灾区. 比如并发写同一个文件的多个用户进程会共享同一个文件偏移量, 如果处理不当, 可能就会导致写数据丢失. 更一般地, 用户进程都会并发地执行系统调用, 操作系统还需要保证它们都能按照系统调用的语义正确地执行.

啊, 还是不剧透那么多了, 大家到了操作系统课再慢慢体(xiang)会(shou)乐(tong)趣(ku)吧, 也许到时候你就会想念PA单线程的好了.