朴素的UNIX之-调度器前传

Linux目前的进程调度算法是CFS算法，替换了之前的时间片轮转调度算法，CFS算法平滑了动态优先级的计算过程，使整个系统在任何时间都可以被任何 执行实体抢占，事实上这是分时系统的基本原则，试想，如何每一个进程/线程都像中断那样，依靠自己的优先级随时执行，那整个系统才真的成了"公平的"利他 系统。要想理解这种利他行为的本质，如果我们去研究CFS调度算法的各种统计数据，或者去研究其代码，那么其效果肯定是不好的，如果我们去研究 Windows NT内核的调度算法，无疑也会浪费大量的时间和精力，最终陷入了细节。
事实上，UNIX最朴素的早期版本便是这种思想的最佳体现，其代码及其简洁，逻辑及其简单。

0.分时系统

冯. 诺依曼的存储式机器有两个要点，更抽象得讲，这就是图灵机。CPU和内存，两大部件，如果想要实现分时系统，那么看看早期的人们是怎么使用计算机的，或者 怎么使用机床的，反正任意一台共享的机器...人们排着队，手里面拿着牌子，然后管理员叫号，其实就跟如今银行里办理业务一样...但是这些实现在计算机 里面，就简单多了，只有两点需要实现，即：如何使用CPU，如何使用内存。关于这两点，看似简单，其实还真的有些细节。如何使用CPU，那就必须一个个 来，一次性执行完任务，然后下一个，但是如果一个任务时间太久，后面的排队者难免长时间等待，于是按照任务的生命周期分时便显得粒度过于粗糙了，更细粒度 的分时系统便是需求，要想实现更细粒度的分时系统，就需要一个上下文，以便一个被管理员中断的任务接着执行，这个上下文必须有一个存储的位置，那就是内 存，这就涉及到了如何使用内存的问题。
谈到内存的使用，简单来讲就是整个物理内存被所有的进程共享，如何共享呢？当然要涉及到分配策略，即为一个进程分配一块内存区域，为另一个进程分配另一块 内存区域，按照这个思路来理解分段和分页就容易了，总之，分段一般用于一个进程内部不同的内存类型的区分，比如代码，数据，堆栈等，而分页一般用于进程之 间的内存页面划分，比如一个页面属于一个进程，另一个页面属于另一个区域，到底怎么划分，总得需要一张表来指示，对于现代操作系统而言，这张表就是我们熟 悉的页表，对于古老的PDP11来讲，就是APR寄存器组的内容。分时操作系统的任务就包括管理这些表以及管理整个物理内存。在一个进程切换到另一个进程 的时候，这些表的内容也必须随之切换，对于现代的x86平台，我们比较熟悉的就是CR3寄存器的切换，而CR3寄存器指向常驻物理内存的页表，无疑，这块 物理内存便不能被进程所用了，因为它存放的是进程元数据。早在PDP11年代，由于物理内存容量很小，不可能采用这种方式来存储元数据，它也并没有实现精 密的分页机制，只是实现了一个朴素的虚拟地址空间，由APR寄存器组来定义虚拟地址和物理内存页面的映射关系。因此在PDP11年代，都是整个进程全部换 入换出的，不存在一个进程的一部分驻留内存，而另一部分在交换空间，由缺页中断按需调入内存。
本质上讲，朴素的分时系统包括两方面内容，CPU分时使用，物理内存分时使用。当然如果物理内存足够大，那么可以将多个进程同时驻留内存，这样无疑会提高 效率，但是这并不是分时系统的本质，包括后来的按需调页机制也并非分时系统的本质，而只是一种MMU管理手段。
分时系统的实现，内存管理是极其重要的，因为内存是按空间来编排的，并非像CPU那样是按时钟嘀嗒驱动的，如何将空间使用和时钟嘀嗒联系起来并建立映射是 分时系统实现的关键，因此我才会花大量的篇幅来介绍内存管理方面的细节。分时系统的实现是递归分形的，因此出现了抢占的概念，如果说细粒度的分时系统实现 抢占了未完成的任务，那么动态优先级的计算导致出现更高优先级进程引发的切换则抢占了未完成的预分配给进程的时间片。

1.UNIX v6的进程调度

我 们知道UNIX出生在1969年，但是那个初生的UNIX并不是真正的UNIX，因为它没有著名的fork调用，它只能说是可以运行固定2个进程的分时系 统，另外因为这两个进程连接两个终端，而终端属于用户，此时的UNIX就算是一个多用户系统了。因此1969年的UNIX虽然不成熟，但确实是一个多进程 多用户的分时系统，现代操作系统的历史开篇了。第一个成熟的UNIX是为UNIX v6，也就是著名的莱昂氏神书介绍的那个版本，我称之为朴素的UNIX。
在理解朴素的UNIXv6调度机制之前，必须理解早期运行UNIX系统的内存管理机制，在PDP11中，并没有如今x86平台的那种精密的分页MMU设 施。PDP11通过一组叫做APR的寄存器来实现虚拟地址空间，注意，这里使用的是配置在一组寄存器的表，而不是常驻物理内存的表。由于寄存器数量的限 制，这类寄存器表的容量注定不可能太大，因此虚拟地址空间到物理地址空间的转换注定是简单的，你不可能用多级页表的理念去嘲笑PDP11的虚拟地址空间的 管理逻辑，即便是多级页表管理机制，也是一步一步发展起来的。关于虚拟内存地址空间，我会专门开辟一篇文章来讲述朴素的UNIX是如何定义虚拟地址的，在 本文，为了不喧宾夺主，我只能用短短几言来评价虚拟地址空间：如果说C语言为程序员提供了一套通用的工具，那么虚拟地址空间则为程序员提供了一块通用固定 大小的空间连续的场地，有了C语言和虚拟地址空间，程序员便可以不必关注机器的细节，C语言为程序员隔离了底层的处理器细节，虚拟地址空间为程序员隔离了 物理内存大小，类型等细节，程序员认为数据在内存中，但事实上这里的内存只是虚拟内存的意思，数据真正存在的位置可能是物理内存，也可能是磁盘，网络。
回到上面的话题，PDP11采用了朴素的一组寄存器来保存虚拟内存地址到物理内存地址的映射，这是在实现全面分页按需调页机制之前最全面最朴素的机制。因为它按分时系统的定义看来，实现及其简单高效。它只需要完成：
每一个进程都拥有一组APR寄存器，保存着虚拟地址到物理地址的映射，进程切换时切换APR寄存器组；
一个寄存器映射一个页面，将一个8k的虚拟页面映射到一个8k的物理页面，一组寄存器一共8对，映射8个页面，因此一个进程的虚拟地址空间总大小为8*8k；
上 面简述的朴素UNIXv6的MMU机制中直接蕴含了后来的多级页表机制，它们和PDP11的MMU唯一的区别就是多级页表使表项常驻内存，这是因为进程需 要越来越大的空间，使得多级页表成为了需求，而这种需求又因为内存越来越大而得到满足，而寄存器反而越来越不适合来做这种事情，MMU缓存TLB，也称快 表，这个设施某种程度上替代了APR之类的寄存器。值得注意的是，多级页表是狭义的，其实在PDP11的APR时期，MMU表就是多级的，一个寄存器映射 整整一个页面而不是一个地址，页面内的偏移直接由虚拟地址指定。
但是在物理内存很小的年代，进程不可能也不必拥有太大的虚拟地址空间，也不可能通过多级页表来构建MMU表的，因为它会浪费更多的物理内存来存储元数据。 有人说，多级页表节省内存，那是大错特错啊，多级页表节省内存存在一个前提，那就是巨大的4G地址空间很多页面都用不到，因此不用建立页表和页表项。如果 每一个虚拟地址空间的页面都被使用，那反而需要更多的内存来存储多级页表。另外，多级页表在实现了按需调页的精密虚拟内存管理之后才有比较大的用武之地。 后面专门描述朴素的UNIX内存管理的时候，我会详细描述。
好了，说了这么多的MMU相关的东西，终于开始说进程调度了。要知道，在PDP11年代，虚拟地址空间只有64k的大小，而物理内存总线宽度却有18位， 也就是256k，物理内存空间远大于虚拟内存空间，一般安装的物理内存都在64k以上，因此完全有能力让一个进程一次性完全驻留物理内存，一个进程在运行 的时候可以全部驻留内存，但是在长期不运行的时候就可以被换出到交换空间中。对于UNIXv6分时系统的实现，这种硬件架构促使伟大又朴素的进程调度系统 完美出炉。UNIXv6的调度机制如下图所示：
(我不得不在此忽略图示，因为我准备在下一篇文章中使用这张图，因为我要拿它来和其它的调度器作对比，这样显得更加紧凑，如果你能看懂下面的要点，你一定要在脑子里面想象一下那副图的样子)
这种调度机制有以下几个要点：

1)进程切换需要0号进程的协助，一个进程除非自己放弃CPU，否则必须将执行权交给0号进程，然后由0号进程决定接下来谁运行。

为 什么非要通过0号进程中转呢？如果理解了上面我大费口舌描述的PDP11的内存管理机制，就会马上理解通过0号进程中转的原因了。因为朴素的PDP11上 的UNIXv6-并没有按需调页机制的实现，它必须确保将要运行的进程的所有页面是完全驻留内存的，因此必须通过0号进程来确保这一点。0号进程也叫 swap进程，也叫调度进程，它只要被唤醒就会执行进程的换入换出，将将要运行的进程换入内存，将长期不运行的进程换出内存，如果这么做了，并且实在没有 进程需要换入换出了，0号进程才会将控制权转交给最高优先级的进程，自己则睡眠，如果一开始就没有这样的事情要做，便把执行权交给一个最高优先级的进程， 自己直接睡眠。

2)进行的优先级是实时重新计算的，只要有更高优先级进程就绪，进程在用户态是随时可抢占的，进程在内核态是绝对不能被强占的

朴 素的UNIXv6定义了一个原则，那就是，进程一定是可抢占的(因为它没有时间片的概念)，但是有一个限制，处在内核态的执行流是不能被抢占的。 UNIXv6的每一个进程优先级是在每N个时钟中断处理中实时重计算的，手册上说是N的值是HZ，即1秒，但是也是可以在编译前修改的，这种重计算的意义 在于发现更值得运行的进程，抢占当前的进程！这个思想其实就是当前的Linux的CFS调度思想以及Windows NT的调度思想，只是实现策略不同罢了。但是，为了保护内核的数据结构，定义了一个例外，即内核态的执行流不能被用户进程抢占，这就是刑不上大夫策略，这 个策略虽然最后被内核抢占打破，但事实上在服务器领域，特别是需要高吞吐量的环境下，它依然是最棒的。体制(抢占式)是不变的，但政策(刑不上大夫)却是 与时俱进的。

3)进程的执行间隔是平滑的，进程饿死的几率很小

我们可以评估一下Linux 2.4的O(n)调度以及Linux 2.6的O(1)调度，这两种算法的最大问题就是进程饥饿，于是出现了各种复杂繁琐的重新计算优先级的所谓"小技巧"，最终适得其反，幸亏CFS此时犹抱 琵琶半遮面，否则....其实问题并不大，因为Win7也面临的同样的问题，但是基于Windows NT构建的系统有一个平衡器，类似一个内核线程，它会定期扫描饥饿线程，将其优先级提升，就这样，在Linux的O(1)在尽力补偿交互进程的时 候，Windows便倾注全力高捧而不是补偿交互进程，Windows一直都有服务器版本和家用版本，其实跟Linux在编译时是否启用内核抢占之类的区 别是差不多的，Windows NT的服务器和家用版本的不同还体现在时间片长短的不同上。朴素的UNIX并没有这样的问题，进程的优先级是实时计算的，只要有更高优先级进程，随时抢 占，这只是其一，其二就是内核执行流的优先级是和用户态执行流优先级有所区别的。
再次值得注意的是，朴素的UNIX进程调度并非基于时间片的，每一个进程都没有在运行前计算好的时间片，之有有更适合的进程就绪，马上抢占当前进程(排除 内核态的进程)。这种平滑的调度机制要求调度策略必须是抢占式的，内核非抢占(刑不上大夫只是暂时在没有更好的办法之前为了保护机要数据，一旦有了更好的 保护机制，内核必定也是可抢占的！)

4)进程处在内核态时，一旦阻塞，其唤醒时的优先级由阻塞原因而定，由于内核态优先级比用户态优先级高，内核机要机构快速出入

关 于这一点，我觉得Windows NT内核和Solaris内核做的超级棒！它们都是将所有的执行流都映射到一定的优先级之上，即便是中断也有自己的优先级，即便是普通的进程，在执行某件 事情的时候，也可以处在中断的优先级上，Solaris走得更远，它将中断作为线程来调度...但是你可知道，早在1975的UNIXv6，这种思想便已 经体现了系统中了。UNIXv6将睡眠进程唤醒后的优先级和睡眠原因关联，如果你同时也看过《Windows Internals》这本书，你就会发现，Windows在"I/O完成以后优先级的提升"也是和I/O原因关联的，比如磁盘I/O完成后线程优先级的提 升值就没有声卡I/O完成后线程优先级提升的高，这个UNIXv6是多么类似。

2.何谓朴素

我说UNIXv6是朴素的，但是何谓朴素？
所谓朴素，就是精简。在下一篇文章中，你会发现，几乎所有的现代操作系统的调度机制的思想，都可以关联到UNIXv6的调度机制，甚至还不如UNIXv6。比如Linux的早期版本。比较类似的有：
UNIXv6调度器与Windows NT的所有版本调度器
UNIXv6调度器与Linux CFS调度器