题目： L4 Microkernels: The Lessons from 20 Years of Research and Deployment
作者： GERNOT HEISER and KEVIN ELPHINSTONE
单位： NICTA and UNSW, Sydney, Australia
出版： Journal ACM Transactions on Computer Systems (TOCS) Volume 34 Issue 1, April 2016, Article No. 1
这篇笔记的目的是用于探讨：如何设计出一个好的操作系统？笔记内容主要围绕微内核的发展展开。
假定读者对主流的类宏内核模型FreeBSD、Linux和混合内核模型Mac OS X、Windows的操作系统设计有了一定了解。
导读：
宏微内核之争在上世纪90年代最为激烈。究竟什么是微内核，以及为什么要研究微内核，个人见解如下： 在现代信息领域的发展中，人们关注的大体可以分为三个板块：数据的计算、数据的存储和数据的传输。由此有了计算机科学、电子信息科学、通信科学等分支。每一块都可以分为物理层（硬件，机械或电气设备、元件）和协议层（软件，指令或代码）两个抽象。操作系统就是贴合在物理硬件上最近的一层软件，通常认为是基础软件，在协议栈上起支撑作用。这里的“操作系统”概念指的是狭义上的内核，糅杂着硬件的固件和驱动，负责对硬件（中央处理器、中断控制器、总线、外围设备）进行“对话”，对资源进行统一的管理和分配。 谈到计算、存储和传输(通信)，具体对应着操作系统常见的组成模块：
- 任务调度器
- 内存管理器
- 网络协议栈
- 文件系统
究竟这些模块要不要被放到内核中，还是作为一个单独的用户进程来实现，是现代操作系统设计者要考虑的问题。
回顾
第0代：
将存储（文件系统）和通信（网络，注：那时候还没有互联网）移出内核。内核只提供基本的抽象（任务，进程管理）和进程间的交互方式（IPC）。 根据 The Nucleus of a Multiprogramming System 一文，提供服务的进程有：实时时钟、打字机、穿孔纸带I/O、行式打印机、磁带。 在24位机器上用汇编指令写就，内核部分（basic operating system）只有1400~个word(24-bit)。 评价：微核的设计思想在当时过于超前，70年代的硬件设备还不足以很好的支持（猜测：可能和中断系统实现有关）。
随后在74年，Hydra系统提出了“策略与机制分离”的思想，然而性能问题依旧饱受诟病。原因主要出在IPC通信上。
问：为什么微内核的设计者要如此关心IPC的性能开销？
微内核设计下，上下文切换次数要比单内核系统高出许多（注意，真的是很多~！）。切换比自陷（trap）要做的工作更多，涉及到两次Protection Domain的切换、存储器eviction，同时执行Int中断指令消耗的时钟周期一般长于别的指令。
随后，微核的发展主要围绕IPC性能展开。
第1代：
代表产物：80年代中期，卡耐基梅隆大学实现了第一代微核操作系统，谓之Mach，对上层用户提供UNIX接口。 Mach实际上是对宏核系统（主要是4.3 BSD）的精简改造，内核中依然保留有一部分设备驱动，基本文件系统和虚拟存储管理（网络协议栈是单个用户进程）。最致命的是，一次IPC消息的通信代价大约有100μs（L4内核在现代处理器上的IPC不超过5μs）！ 评价：Mach首次将进程抽象为“任务”和“线程”两个概念，在一个任务内并行多个线程（Mach 1已支持多处理器架构），是真正意义上的多线程模型（实现上）。
第2代：
90年代，Liedtke提出更加激进的KISS（Keep it simple, stupid!）方法，尽可能地把策略（做什么）移出内核，对微核进行了重新设计与实现。 评价：人们重新审视了微核的意义和价值，开始了更加激烈的争辩和思考。
第3代：
操作系统的安全性开始受人们关注（病毒、木马等大量涌现，黑客开始引起人们注意）。微核代码的小型化在形式化验证工作上具有得天独厚的优势，不仅易于测试，还可以通过基于严密的数学定理验证其可靠性。 评价：微核的实现者不再拘泥于汇编语言，开始使用高级语言（其初衷是为了使用形式化工具），在可移植性上迈出了重要一步。微核的商业化系统在嵌入式实时工业控制领域（OKL4）、汽车驾驶领域（QNX）、航空电子、轨道交通领域（PikeOS）上都有显著成功，而不再只是一个大学实验室的产物。
回顾过去才能更好地展望未来。一路坎坷，到底扬弃了什么？
微核的设计思想与其说精致，不如说优雅。Liedtke（第一版L4的作者）提出，要将所有的策略都移除内核。这意味着，内核将以一个极其精简的形式出现在应用开发者面前：内核不必对那么多事都亲力亲为；它只要提供很少的抽象，就可以构建出整个帝国。这里做一个不恰当的比喻：如果说Win、*NIX这些系统是给硬件穿上一件华丽的外衣的话，微核系统就是件丁字裤。
问：那么微核究竟有什么好处呢？为什么有那么多人研究它？
- 更少的代码意味着更好维护。（运维）
- 更少的代码意味着更好验证。（测试）
- 更少的代码意味着更好学习。（教育）
问：如何保证微核内核的最小化？
微核设计中“最激进”的指导思想就是将所有策略驱逐出内核。内核就是CPU设备的驱动器，只包含很少的告诉CPU怎么做的机制，而策略几乎由用户自己定义。
这个想法雄心勃勃。然而当前研究还没有找到一个具体高效可行的方法，将调度策略放在用户态来施行。
思考：现代操作系统的调度策略偏向于公平，也就是保证了低优先级的进程不会被“饿死”。如果完全由用户来提供调度策略，那么一旦这个进程失控，整个操作系统几乎不可能恢复正常运作（理由：总有办法可以避开看门狗，模拟正常喂狗而逃离复位；况且内核对预设的调度一无所知，哪怕监视也无法热备恢复）。
为了保证可用性，当前L4家族将时钟管理和中断管理放在内核中。一方面是因为内核要负责进程的调度策略，另一方面是IPC的高效性是依赖中断来实现的。
- IPC有同步和异步之分。究竟用户向别的进程发送请求后，到底是选择阻塞还是非阻塞调用，内核要不要立马发生调度，都值得思考。
- IPC发生之频繁决定了IPC数据传输越短越好，充分利用硬件资源，能用寄存器解决就不要用内存（零拷贝），需要拷贝就尽量一次搞定（在接受方内开辟空间，发送方直接写入，基于页面直接映射机制）。对于多核模型，同步IPC可能都太奢侈，一般有把大锁用于同步，但是开销过大。为此最新内核使用IRQ来发送信息，同时也在I/O上实现了相对高效的select机制。
思考：在多核平台上，由于各个线程间并行执行，彼此之间依赖IPC机制通信。整个过程好比RPC（远程过程调用）。
问：为什么seL4内核不采用嵌套中断？
并发/并行是一种非常难模拟的行为。它的可靠性验证对于形式化几乎是不可能的。seL4团队认为，嵌套中断（可抢占式内核）会给内核引入并发，从而威胁其安全性。
问：如何将设备驱动移到用户态后又能保证其高效性？
当设备支持DMA时，此时完全由中断来实现IPC。
内存分配器不在内核中，内核提供内存地址的映射能力(ABI)。用户态服务器来完成page-fault handling。
问：如果完全由用户来决定内存分配，这种设计会有什么风险？
如果由用户来决定内存分配，那么对内核的DOS攻击无可避免。
如果内核提供IPC，那么当有大量来自恶意客户端的请求到达时，服务器遭受DOS攻击，内核无力保护。亦或者任意一端有意不按协议回复，也将导致服务失败。对于后者，看门狗将大量使用。很可惜，缺乏具体的理论，指导如何合理地设置超时时间，最终IPC超时机制被弃用。然而看门狗机制还是需要的，用于检查死锁。
问：为什么微核系统可以很自然地设计为Hypervisor？
如果全由OS来决定进程的地址空间布局，将限制可加载的可执行文件格式，不利于多应用移植。因此L4社区致力于将自己打造成Hypervisor，把其他系统当做VMM来运行各OS的各种Apps。
因为文件系统不在内核中，内核不需要知道如何加载，从何加载；具体地址空间的分配也不参与，为此根本不需要将加载器和动态链接器放到内核中。
问：为什么有些操作系统系统用难以移植的汇编语言进行开发？
因为操作系统讲求效率。汇编为什么快？汇编是机器语言的助记符。汇编开发要求编程人员对体系结构有更好的理解，贪心的本质决定了汇编代码更清楚如何利用机器资源，更小化地使用寄存器来保存上下文。高级语言编译器通常要准备通用范式来满足代码生成的需要，并不区分特定用途，因此生成的代码更臃肿，故消耗的CPU指令数也就更多。
论文总结：
L4将微内核设计带向新高度。微内核将很多在内核做的事情（如网络协议栈、文件系统）移到了用户态做，应用请求服务就通过消息传递来，因此IPC机制是核心的东西。微内核在设计理念上更超前，安全性也可以更好保证。90年代在OS上的争论就是宏微内核孰优孰劣，IPC则是微内核的阿格硫斯之踵。
OS设计者可能首先考虑可用性，其次是安全，然后才是性能。现代OS发展已经对这些特质有了更高的要求。
回顾20年L4微内核的发展。在实时性以及安全性上，L4是微内核设计中迄今为止最棒的实现。微内核的发展依旧会在小型化、通用化和高IPC性能上继续推进。
L4的家族发展：和Windows、Linux相比，他们的代码量与日俱增，如果要精简，需要大规模重构。而微内核精致优雅，重构难度较低，演进过程中并没有发生“代码爆炸”现象。
这篇综述行文优美。包含了诸多微内核设计的哲学理念，不仅是对操作系统设计更深层次的思考，更是对单内核设计人员有极佳的参考价值。
个人体会：
微内核的实现常见“from scratch”的字样，与活泼的Linux社区不断添砖加瓦的欣欣向荣的景象不同，微核不断经历“否定之否定”的螺旋上升，每一步推进都是历经百转千回的深思熟虑和大刀阔斧的回炉再造。匠人手艺在微核社区里演绎得淋漓尽致。由衷热爱这种精益求精、止于至善的精神，希望在科研教学和工业发展上，微核和宏核如两颗明珠，在软件的系统论和控制论上互成其美，相得益彰。
畅想：
如果你尝试给一个硬件从头开发软件，你会发现有很多可以重用的代码。你会在重构的时候及时把它们整理、抽取出来，做成独立的库，方便自己调用。由于学过软件工程，你尝试封装它们内部的数据结构，并设计好对外交互的接口。在你着手整理文档的时候，manual手册和对外定义良好的API已经呼之欲出了（不要以为这一步没用，是给未来的开发者用的，也包括未来的你）。接着你把自己的库开放给别的同事使用，他们觉得你根据日常工作经验整理出来的公有库很好用，越来越多人加入开发的行列，逐渐壮大为社区。
然而社区开发者良莠不齐，好些没受过系统学习的初学者也把自己的应用发布出来，这些应用肆无忌惮地消耗硬件资源，严重干扰了别的应用的运行。用户抱怨这实在是个烂的不能再烂的系统了。你觉得很生气。这并不是你的错。为了惩罚那些不守规矩者，你不得不对它们进行约束。现在你需要添加一个管理作业，在运行时对别的应用进行监视，专门充当“世界警察”的角色。为了保护你这个作业不被干扰（那些拙劣的设计最喜欢吃资源了，你写的应用也无能为力），你向硬件设计者提出了想法，用硬件机制保护你这个应用。为了抢夺先机，你这个管理作业必须优于其它应用运行。贪心的思路让你觉得这个管理作业首先得把所有的资源都吃下来，别的应用只能向它按需申请。申请的时候自然可以看出是谁的问题比较多。由于你的这个超级应用第一个拿到硬件资源，而且是寡头垄断，大家忿忿不平地称呼你是个独裁者，你的超级应用是有后门的“内核”。
但是你的欲望催使你并没有就此罢休，你很享受管理一切的感觉，你就是规则的制定者，软件世界的操纵者。为了这个目标，你投入更多精力，开始重新设计这整套系统。随着更多硬件平台的出现，你的野心让你很自然地在可移植性上大胆进军。很可惜，你的精力有限，不得不再次将自己的内核作业代码整理成库，开放API并邀请别的开发者来帮你完成移植（主要是驱动代码的编写）。可怕的事情再一次出现了：那些不合格的驱动代码直接导致了你的“内核”崩溃，你会彻底失去对系统的控制能力！类似的经历发生了不止一次，你琢磨着是不是又该做些什么改变了。没有办法，你觉得内核还是由你自己来控制好，那些体系结构、组成原理相关的都滚到内核之外的太空里去吧！很可惜，这个想法只能止步于愿望，目前的硬件和软件工程还不足以支持你的野心。所以，“路漫漫其修远兮，吾将上下而求索”。
忽然社区里有个同学跳出来，反对你的“内核”想法。然而它反对的不是你的独裁，而是你代码的低效。高效的思路却同样是要你放弃做大家长的权利。他说：你就单做一个多路复用器，压根不用管硬件是如何被管理的。这样的设计固然优雅，然而你觉得你将彻底失去的控制权。关于控制权是否保留你还在犹豫。毕竟英明的独裁者比一堆愚民的民主统治要好些。如果人民可以证明自己的自我管理能力，那么民主之势不可逆。为此你暂时把系统设计放在一边。开始考虑代码生成工具，如果有一件宝物可以验证社区贡献的代码无害，那么那个斗胆进言的同学的意见也不是不可接受。所以，编程语言的分析工具开始在你大脑里酝酿。一个包裹着更大野心的帝国版图正在你面前徐徐展开……
注：库是大家共享的一份代码。内核也是大家共享的，只不过它更象一个进程实体。
题目： Exokernel: An Operating System Architecture for Application-Level Resource Management
作者： Dawson R. Engler, M. Frans Kaashoek, James O’Toole
单位： M.I.T. Laboratory for Computer Science, Cambridge, MA
出版： SOSP 1995
一言以蔽之：ExoKernel: Exposed hardware explicitly to extensions living above it (LibOS)
Exokernel内核设计哲学将抽象剥离出内核，即OS只是提供一个资源管理的中控器而已（微内核假设自己是CPU的驱动，因此最初实现时和平台高度耦合）。Exokernel的文章只用来WWW服务器来作示例，尽管引燃了微内核设计者的激情，但最终以一片哀鸿遍野收场。Exokernel没有考虑文件系统在底层不提供抽象时如何实现，而且关于frame buffer显卡的硬件假设也是不切实际的。整体设计上的不成熟、不够缜密也导致了实现后更大的不尽如人意。
为了高效，现代浏览器会自己实现虚拟Cache，数据库中间件也会自己用驱动管理文件系统。这些都和Exokernel的志趣殊途同归。
- SPIN的想法和LKM很像。内核就像个解释器，随时可以下载代码到内核解释执行。这加强了扩展性和灵活性。
- SPIN对内核模块进行了隔离。在下载时对代码进行静态分析，确定即将执行的代码不会破坏系统完整性（包括内核、加载的其他模块和用户态代码）。SPIN的核心core只包含处理器和内存的管理。别的都是依赖这些的扩展。
- SPIN和Exokernel都是下载代码到内核里来，无疑给后来的Linux提供了新的指导思路。
和Microkernel的比较: 在Microkernel中，一旦产生中断，做什么呢？不知道。但是怎么做，是知道的：转发到用户服务那里去。
