配套教材：
Operating Systems: Three Easy Pieces Remzi H. Arpaci-Dusseau Andrea C. Arpaci-Dusseau Peter Reiher
参考书目：
1、计算机操作系统（第4版） 汤小丹 梁红兵 哲凤屏 汤子瀛 编著 西安电子科技大学出版社

在线阅读：
http://pages.cs.wisc.edu/~remzi/OSTEP/
University of Wisconsin Madison 教授 Remzi Arpaci-Dusseau 认为课本应该是免费的。
————————————————————————————————————————
这是专业必修课《操作系统原理》的复习指引。
需要掌握的概念在文档中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
文档下载地址：
链接：https://pan.baidu.com/s/1L-nvtuC5KQZIq_rScfrc5w
提取码：0000

十 多核心调度 基于事件的并发

这一章涉及到一些组成原理的知识。这里只粗略讲一些需要用到的内容。请认真学习《计算机组成原理》。

操作系统在多个核心上调度任务时，需要注意缓存一致性（cache coherence）的问题。
例如：一个程序在CPU 0上运行，从内存地址A中读到一个数据，写入CPU 0的缓存中；后来，程序修改内存地址A存储的值，但修改只在缓存中生效，操作系统在之后才会写入内存。这个原因在前面的章节中已经讲过了：暂缓写入到较慢的存储器中的操作，在要写入的数据凑成一块后再写入，速率会提高；而且，一旦很快就撤销修改，在更高速的存储器中操作就可以了，而无需在更低速的存储器中进行操作，又进一步提高了速率。
后来，由于调度器的作用，操作系统决定将该进程从CPU 0移到CPU 1上继续。这时，程序又要从内存地址A中读取数据；然而，在之前这个程序已经修改了该值，但修改操作还没有正式应用到内存；这一次，程序又读入了修改前的值。
解决方案是硬件提供的一种古老的技术：总线探听（bus snooping / bus sniffing）。具体来说，一个CPU核心通过总线注意到缓存中的数据有更新后，有两种实现：
·将自己拥有的副本将标记为无效。这种实现是最常用的。
·将修改在自己的缓存中同步。这种实现不太常用。

既然硬件会负责保持一致性的操作，这是不是意味着OS或程序本身就不需要做任何事情了呢？不是的。前面的章节已经学习过：程序（或操作系统）本身需要用互斥锁、条件变量，或者信号量来维持同步，确保数据的正确性。当然，也可以使用无锁的数据结构，但是无锁数据结构较为复杂，也不是在所有的场合都能使用。随着核心数的增长，在访问对同步要求较高的数据结构时，CPU的总利用率已经变得越来越低。

一个多核调度器需要考虑缓存亲和性（cache affinity），即：进程在某个给定的CPU上尽量长时间地运行，而不被迁移到其它CPU的倾向性。如果进程频繁在不同的CPU上继续运行，那么它需要重新将数据读入缓存（假如相应的缓存不是共享的），大大降低运行速率。在不同的核心上来回切换的过程本身也是需要耗费一定时间的，如果应用程序对时间敏感，可能会造成严重后果。
Linux的内核进程调度器支持软亲和性：这意味着进程通常不会在处理器之间频繁迁移。而硬亲和性，简单来说就是利用Linux内核提供给用户的API，强行将进程或者线程绑定到某一个指定的CPU核运行。

单队列多处理器调度（single-queue multiprocessor scheduling，SQMS）是一种在多核处理器上调度的方案。这个方案实现简单，只需要照搬在单核处理器上调度的很多策略，并补充少量的额外策略。
当然，它的缺点也很明显：一是需要用到较多的锁来保证调度器的正确性。随着CPU核心数的增加，需要的锁也更多，导致真正用于执行任务的CPU时间降低。二是需要额外的措施来保证缓存亲和性。
设有4个核心、5个进程（线程），如果队列中的项依次为：A、B、C、D、E，那么按排队顺序依次安排任务得到的调度方案是这样的：

那么每个进程（线程）都要在CPU之间来回切换，降低执行效率。增加了缓存亲和性的相关机制后，一种可能的调度方案如下：

进程（线程）A、B、C、D在继续运行时，有较长时间在同一个核心上继续。当然，也可以在一段时间后把在核心之间来回切换的进程（线程）E换成别的。

一些操作系统使用多队列多处理器调度（multi-queue multiprocessor scheduling，MQMS），每个核心一个队列。每个队列使用的调度算法可以是相同的，也可以是不同的。
MQMS的一个优势是可伸缩性（scalability，也译作可扩展性）。这个词的意思是：某种效果随着（硬件或软件）规模的扩大或缩小，成比例或接近成比例地增加或减少。在这里，自然是指MQMS在核心数增加时，也依然无需花费过多比例的CPU时间在调度器上。在缓存亲和性方面，MQMS的表现也很不错。
但是，MQMS也可能会引发负载不均衡。例如：有2个CPU核心和3个任务。那么调度方案可能会变成：

如果A提前完成了，情况就更糟了：CPU 0会直接空载。

解决办法也很直接：将任务迁移（migrate）到别的核心上。对上面的情况，可以直接将B或D移到空载的CPU 0。而对于再上面的图描述的情况，可以来回迁移任务：

当然，其它迁移的方法也是有的。
实现任务迁移的方法是工作窃取（work stealing）。如果一个队列中的任务数量较少，那么就查看其它队列的任务数量。如果有别的队列具有更多的任务，就把这个任务从那个队列中拿过来。当然，这个操作不能进行得太频繁，否则又会花上太多时间在调度器本身，还会影响可扩展性。如果尝试进行工作窃取的频率太低，部分核心又有较高的低负载概率。怎样快速在这两者之间找到平衡呢？或许只能借助于妖术了。

Linux社区中，还没有形成一个统一的多核调度方案。用得比较多的是三种调度器：O(1)调度器、完全公平调度器（Completely Fair Scheduler，CFS）和脑残调度器（Brain Fuck Scheduler，BFS）。
O(1)调度器使用的调度算法，保证每个进程都能在常数时间内被执行到。在它之前的调度器都被称为O(n)调度器。由Ingo Molnár（匈牙利Linux黑客）提出，在Linux 2.6.0时加入，在版本2.6.23后，被CFS取代。
O(1)调度器和CFS均采用多队列，但BF调度器使用单队列。可见两个方法都是可以成功的。O(1)调度器用于调度的队列基于优先级，很像MLFQ。它通过随时间改变进程优先级并调度，总是选择最高优先级的进程优先运行。进程与用户的交互频率是决定优先级的重要因素。相比之下，CFS则注重按比例分配，更像之前讲过的步幅调度（stride scheduling）。BFS只用一个队列，但也是按比例分配运行时间的，只是基于一个更复杂的策略（Earliest Eligible Virtual Deadline First，EEVDF）。
CFS是澳洲麻醉师、Linux爱好者Con Kolivas提出原始代码，由Ingo Molnár最终提出，在Linux kernel 2.6.23之後採用，取代先前的O(1)排程器，成為系統預設的排程器。它負責將CPU資源，分配給正在執行中的行程，目標在於最大化程式互動效能的同時，最小化整體CPU的運用。使用紅黑樹來實作，演算法效率為O(log⁡(n) )。在第三章简要介绍过CFS的工作机制。这里只简单补充一点关于CFS和BFS的内容。
CFS 是首支以公平佇列（fair queuing）的排程器，可應用於一般用途作業系統（general-purpose operating system）。
CFS排程器參考了Con Kolivas開發的楼梯调度器（staircase scheduler）與RSDL（The Rotating Staircase Deadline Schedule）的經驗，選取花費CPU執行時間最少的行程來進行排程。CFS主要由sched_entity內含的vruntime所決定，不再跟踪process的sleep time，並揚棄active / expire的概念，runqueue裡面所有的进程都平等对待。CFS使用“虚拟运行时间”（virtual running time）來表示某个任务的时间量。
因為在Linux 2.6.23 将CFS合并到mainline（mainline指由Linus B. Torvalds亲自制作的内核发布版，是官方当前最新版本的kernel source。在Torvalds对所有其他程序员所做出的重大变化进行整合，并且对先前版本的bug进行几轮修复之后，大约每十周正式发布一个新版本。），放棄了RSDL，这引起Con Kolivas的不滿。他一度宣布脫離Linux開發團隊。數年後，Con Kolivas 捲土重來，重新開發腦殘排程器來對決CFS。Jens Axboe（Linux内核黑客）寫了一個名为Latt.c的程序進行比對，發現BFS確實稍稍優於CFS，而且CFS的sleeper fairness在某些情況下會出現調度延遲。Ingo不得不暫時關閉該特性，很快在一周內提出新的Gentle Fairness，徹底解決該問題。
腦殘排程器（BFS，Brain Fuck Scheduler）是作業系統內部的行程調度器（process scheduler），由Con Kolivas所撰寫。
2009年8月31日，Kolivas創造了全新的排程器，並命名為Brain Fuck Scheduler。BFS调度器的原理十分简单，是为桌面交互式應用專門設計，使得用戶的桌面環境更為流暢，過去使用CFS編譯內核時，音訊視訊同時出現會出現嚴重的停頓（delay），而使用BFS則沒有這些問題。
BFS的原理是：將所有行程被安排到103組佇列（queue）之中。BFS本身是O(n)调度器，但大部份的時間比目前Linux上擁有O(log n)效能的主流調度器CFS還優異。Con Kolivas並沒有打算將BFS應用在mainline Linux。他再度以-ck的補丁來維護這套原始碼。Android曾經在試驗性的分支，使用BFS作为其操作系統排程器。但是經過測試發現對使用者並沒有明顯的改進，因此並未合入之後發表的正式版本。
Joseph T. Meehean的博士论文《Towards Transparent CPU Scheduling》对这三种调度器做了一个优秀的总结。学有余力的同学可以去阅读这篇论文。

多线程并不是实现并发的唯一方式。基于事件的并发（event-based concurrency）常被用于带有GUI的应用程序和一些网络服务器中。一些服务端的框架，例如node.js，也使用这种方式。不过这种方式也起源于UNIX系统。
实现并发是非常具有挑战性的。例如在该加锁的地方没有加锁、产生死锁和其它问题都可能引发严重错误。而应用程序开发者们也基本无法控制调度器层面的行为。并且，程序员总是希望创建线程之后，OS能够帮助做好足够多的事情。

基于事件的并发，说白了也就是那些东西：你仅仅等待一些事件发生。事件发生后，你检查它是哪种类型的事件，并视情况做一点别的（例如：发起I / O请求、安排其它事件以备后续处理，等等）。
事件循环（event loop）是实现基于事件的并发的最基本的结构。每一论循环只做两件事：获取事件、处理事件。当事件处理程序（event handler）处理一个事件时，它是系统中唯一的活动任务。因此，决定接下来要处理哪个事件，和调度进程或线程是等效的。

怎样接收一个事件？绝大多数系统都提供了相应的API，例如select()和poll()系统调用。
这些接口能使应用程序做到：检查是否有到来的I / O。譬如说，一个网络应用程序（比如Web服务器）希望检查是否收到了数据包，若收到就进行处理。
在终端下输入man select，查看使用手册中关于select()的条目。
select()和pselect()允许程序监测多个文件描述符，等待直到有文件描述符为I / O操作就绪。当文件描述符可以执行相应I / O操作时，认为其就绪。poll()的作用类似。

阻塞（同步，synchronous）接口在返回到调用者之前需要结束全部工作，而非阻塞（异步，asynchronous）接口在被调用后立即返回，在后台继续执行需要的工作。阻塞式调用在一些I / O中常用，比如在磁盘读写结束前阻塞。非阻塞接口可以用于任何风格的编程（线程式并发亦可），但在基于事件的并发中是必须的。因为阻塞式调用会令程序暂停。
基于事件进行并发的服务器对任务调度具有细粒度（fine-grained）的控制（粒度，granularity / graininess，是指一个物体或系统被划分并处理的精细程度）。但为了维持这种控制，不允许进行任何会在返回前引发阻塞的调用，否则整个服务器都会停下来，使客户端长期等不到结果，引发一系列严重问题。

如果基于事件的应用程序运行在单核CPU上，前面提到的并发问题就全部不用考虑了：因为同一时间只能同时处理一个事件，不再需要考虑锁的使用；基于事件的服务器在处理过程中也不允许被另一线程打断，因为基于事件的并发模式决定了它是单线程的。

但是，如果有程序确实需要用到会引发阻塞的系统调用，怎么办？例如：客户端向服务器发来一个请求，要求从磁盘读出一个文件，并将全部内容传输至客户端。对于基于线程的并发式服务器，这没有问题：在等待I / O请求执行完毕的过程中，其它线程可以继续运行。但是基于事件的服务器的运行框架说白了只有那个事件循环。难道要一直等到I / O结束吗？当然不用。许多现代操作系统已经引入许多处理磁盘I / O的方法，统称异步I / O（asynchronous I / O）。当进行引发阻塞的操作时，控制权立刻被移交给调用者。查询I / O是否完成则有专门的接口。
以Mac系统（其它系统也有相似的API）为例。这些API基于一个基础的结构：结构体aiocb，即AIO控制块。它至少包含以下信息：

struct aiocb {
int aio_fildes; // File descriptor
off_t aio_offset; // File offset
volatile void aio_buf; // Location of buffer
size_t aio_nbytes; // Length of transfer
};
当需要发起异步读取文件请求时，程序需要先在AIO控制块的一个实例中填入必要的信息：需要读取的文件、读取的偏移、缓冲区长度和内存的目标位置（用于存储读取的内容）。之后，调用专门的API正式请求读取：
int aio_read(struct aiocb aiocbp);
也有专门的API来检查读取请求是否执行完毕或出错：
int aio_error(const struct aiocb*aiocbp);
如果循环调用该API检查，也很浪费CPU。一些系统提供了更好的方式：中断。这个方法使用UNIX信号（UNIX Signals）在I / O完毕后通知应用程序。
异步I / O是实现事件并发的必要机制。但也有混合使用线程和事件驱动的方法。

实现事件并发需要的代码一般比传统的线程并发更复杂。当事件处理程序发起一个异步I / O时，它必须：
·保存当前任务的执行状态
·开始会引发阻塞的操作
·执行其它任务
当异步I / O完成时，还需要：
·恢复原任务的执行状态
·重建全局常量（需要时）
·在正确的断点继续执行任务
这称为手动栈管理（manual stack management）。在基于线程的并发中，线程各自的局部数据保存在各自的栈中，切换线程时不用人工管理的介入。

实现基于事件的并发还有一些其它困难。举例：当系统升级到多核时，原有的一些只考虑单核情形的比较简化的方法就不管用了。为了充分利用多CPU，需要运行多个事件处理程序。但是这也就会重新引入传统的线程并发遇到的问题：临界区、死锁……。
而且，事件并发与操作系统的一些必要机制也结合得不太好，比如分页。如果事件处理程序缺页了，它将会阻塞，直到处理完缺页异常。即使服务器被设计为避免显式阻塞，但这种隐式阻塞也难以避免。这种阻塞会导致很大的性能问题。
随着时间的推移，事件并发型程序的代码维护会变得困难，因为过程的语义会改变。假如一个过程更新后需要阻塞，那么调用这个过程的事件处理程序就要配合这种改变。在基于事件并发的服务器上出现阻塞是很严重的问题，程序员必须总是留意API的改变（注意API是否会引发阻塞）。
最后，虽然异步磁盘I / O在许多平台已经可以实现，但这也是花了很长时间才达成的，而且它与异步网络I / O也配合得不是太好。

信号（signals）是在全体UNIX系统及其衍生物中的大型基础设施。信号提供了一种进程通信方式。具体来说，可以向一个应用程序传递信号；这导致程序暂停（如果正在进行的操作为非原子操作）并转而运行信号处理程序（signal handler）。由此可见：信号是一种异步的通知机制。
每个信号都有自己的名称，例如HUP (hang up)、INT (interrupt)、SEGV (segmentation violation)，等等。有时候，内核自己也会发出信号。假如发生段错误，操作系统会送出一个SIGSEGV（在信号名前添加SIG很常见）；如果你的程序具有捕获这个信号的代码，你就可以运行自己的代码做出相应处理（这对调试很有用）。如果进程没有相应的代码，操作系统就代为执行默认操作。对SEGV，默认操作是结束进程。
信号类似于中断，不同之处在于：中断由处理器调解并由内核处理，而信号由内核调解（可能通过系统调用）并由进程处理。内核可以将中断作为信号传递给导致中断的进程。
对于嵌入式程序，也许信号对于进程间通信很有用，因为信号的计算和内存占用很小。
关于信号的编程，请阅读《Advanced Programming in the Unix Environment》（W. Richard Stevens and Stephen A. Rago）。