现代操作系统第三章读书笔记
***3.3.1 分页
3.4 页面置换算法
3.5 分页系统中的设计问题
前面讨论了分页系统如何工作，介绍了基本的页面置换算法。当然，只了解基本机制是不够的。要设计一个系统，必须知道如何是这个系统工作的更好，需要从全局考虑一些问题。下面是一些能过使得整个系统工作得更好的策略。
3.5.1 局部分配策略和全局分配策略
之前关于页面置换算法的讨论，默认只有一个进程，但实际情况是，操作系统管理这多个进程，物理内存实际上容纳着多个进程。考虑一个简单的多进程模型，有A、B、C三个进程，它们各有一些页面在内存中，如下图所示：
局部分配就是每个进程只在自己圈子里折腾，全局分配策略就是统筹调度。一般情况下，全局分配工作得比局部分配好。因为局部分配时间长了，会在进程内部产生空闲页框，导致浪费。随着工作集的增长，会有颠簸产生。
3.5.2 负载控制
当然，即使用最有页面置换算法并对进程采用理想的全局页框分配，系统也会发生颠簸。因为一些进程需要更多的内存，但是没有进程需要更少的内存。所以这种情况下，唯一的解决方法就是暂时从内存中去掉一些进程，从而减少了资源竞争。一个可行的方法是将进程交换到磁盘中去，并释放它们的页面。所以，即使是分页，也需要交换，这个交换指的是整个进程交换出去，而不是交换只页面。
当然也要考虑多道程序设计的道数，总之，这是一个需要平衡的问题。
3.5.3 页面大小
页面大小也是操作系统的一个可以选择的参数。要确定最佳页面大小需要在几个相互矛盾的因素之间进行平衡。
利用率方面
一般而言，任意一个正文段、数据段或者堆栈段很可能不会恰好装满整个页面，平均的情况下，最后一个页面中有一半是空的。这就造成了浪费，这种浪费称为内部碎片（internal fragmentation）。内存中有n个段、页面大小为p字节时，会有np/2字节被内部碎片浪费掉。从这方面考虑，使用小页面好。
传输方面
但是，页面越小，页表就越大。一个32KB的程序只需要4个8KB的页面，却需要64个512字节的页面。内存和磁盘之间的传输一般是一次一页，传输中的大部分时间都花在了寻道和旋转延迟上，所以传输一个小页面所用的时间和传输一个大页面所用的时间是相同的。所以，装入64个512字节的页面可能需要64x10ms，而装入4个8KB的页面可能只需要4x10ms。
TLB方面
此外，小页面能够更好地利用TLB空间。假设程序使用的内存为1MB，工作单元为64KB。若使用4KB的页，则程序将至少占用TLB中的16个表项；而使用2MB的页时，1个TLB表项就足够了。由于TLB表项相对稀缺,且对于性能而言至关重要,因此在条件允许的情况下使用大页面是值得的。为了进行必要的平衡,操作系统有时会为系统中的不同部分使用不同的页面大小。例如,内核使用大页面,而用户进程则使用小页面。
数学角度分析
最后一点可以从数学上进行分析，假设进程平均大小是s个字节,页面大小是p个字节，每个页表项需要e个字节。那么每个进程需要的页数大约是s/p，占用了se/p个字节的页表空间。内部碎片在最后ー页浪费的内存是p/2。因此，由页表和内部碎片损失造成的全部开销是以下两项之和：
开销 = \frac{se}{p} + \frac{p}{2}
显然，当页面较小时，第一项大，在页面较大时，第二项大。最优值一定在页面大小中间的某个值时取得，通过对p一次求导，得到方程：
-se/p^2+1/2=0
从而可以从这个方程得到最优页面大小的公式，结果是：
P=(2se)^1/2
因此，对于s=1MB，每个页表项e=8B，最优页面大小是4KB。商用计算机使用的页面大小一般在512B到64KB之间，以前的典型值是1KB，而现在更常见的页面大小是4KB或8KB。
3.5.4 分离指令空间和数据空间
说白了，就是把进程的一个地址空间分成两个部分，一个是指令，一个是数据。这样做的好处是，可以使得指令和数据的访问模式不同，从而可以采用不同的页面置换算法。例如，指令一般是顺序执行的，所以可以采用FIFO算法，而数据一般是随机访问的，所以可以采用LRU算法。
不过这种做法也有缺点，就是会增加页表的大小，因为每个进程都有两个页表。
3.5.5 共享页面
让分页系统更高效的另一个方法是共享页面。共享页面就是多个进程共享同一个页面。显然，由于这样做避免了一份数据在内存中有两份副本，因此效率更高。而且并不是所以页面都可以共享，比如只读的代码段可以共享，但是可能被修改的数据段则不能贡献。
下面讲共享页面的实现。
如果实现了上述的指令空间和数据空间分离，让多个进程实现页面共享就会非常简单。一个典型的实现是，每个进程有两个指针，一个指向I空间页表，一个指向D空间页表。当一个进程被调度运行时，它使用合适的指针来定位页表，并设置MMU。当然没有分类的I空间和D空间也可以实现共享页面，只是机制较为复杂。
当两个或多个进程在共享页面的时候，存在一个问题。假设进程A和进程B在共享页面，当进程A退出时，A的页面会被回收，但是这些页面还在被进程B使用，这就会导致进程B发生大量的缺页中断，才能把这些页面重新调回。
所以，当进程A退出时，必须考虑它使用的页面当中，有哪些是共享页面。它需要遍历所有的页表，才能知道一个页面是否被共享。这是一个非常耗时的工作，且需要专门的数据结构。
共享数据段比共享代码段复杂，但也不是不可能。比如在UNIX系统中，一个进程使用fork()创建一个子进程后，父进程和子进程需要共享代码段和数据段。在分页系统中，通常的做法是，让这两个进程拥有各自的页表，但是页表指向相同的页面集合。这样在使用fork()进行进程的创建时，不会发生页面的复制，然后，两个进程映射到的数据内容都是只读的。
如果两个进程都不写数据，这种状况就可以一直保持下去。但是只要一个进程写了一点数据，就会触发“只读保护”，陷入内核。然后会生成一份需要修改的页面的副本，每个进程在其副本上写数据，这样就不会触发“只读保护”。这种策略意味着，那些从来不会执行写操作的页面是不需要复制的，只有实际修改的页面才需要复制。这种方法成为写时复制，它通过减少复制提高了性能。
*3.5.6 共享库
上面介绍了共享页面，总结就是，对于多次打开的程序，代码段可以多个进程共享一份，数据段则根据需要，对于要修改的部分，每个进程保有私有的部分，不需要修改的部分，则只有一份。
除了这个以外，还有一种更通用的方式，就是共享库。现代操作系统中，有很多大型库被使用。先来考虑一下传统的链接：
ld *.o -lc -lm
这个命令会链接目录下的所有目标文件，并扫描两个库，/usr/lib/libc.a和/usr/lib/libm.a。任何在目标文件中没有被定义的函数被称作外部未定义函数（undefined externals）。链接器会在这些库中寻找这些外部未定义函数。如果找到了，就将其加载到可执行文件中。
为每一个程序单独链接这些经常被使用的库，不仅会浪费大量的磁盘空间，在把这些程序装载进内存的时候也会浪费大量的内存，因为系统不知道可以共享哪些库。而这就是共享库被引入的原因。
当链接器链接共享库的时候，并不会把外部未定义函数加载进来，而是会在运行时加载一段可以绑定到被调用函数的例程存根（stub routine）。然后依赖于系统和配置，共享库和程序可能被一起装载进来，或者在其所包含的函数被调用的时候被加载进来。如果某个程序以进加载共享库了，那么这个共享库就没有必要再被加载进来了，这正式共享库的关键。
什么是“例程存根”？
值得注意的是，当一个共享库被加载使用时，并不是一次性把整个库装入内存，而是根据需要，以页面为单外进行装载，因此没有被调用的函数是不会被加载进内存的。
综上所述，使用了共享库之后，外部未定义函数的加载推迟到了运行时，但是多个进程可以共享一个库中被调用的函数。
此外，还有一个小问题需要解决。例如现在有两个进程都在使用一个库，进程A在地址36K处调用了库中的函数，而这个函数在库中的偏移量为12，那么这个函数会被重定位到36K+12。这在不使用共享库的时候没有问题，但是，此时第二个进程B也使用了库中的函数，而库在进程B中被重定位到了24K，那么同样的函数，在进程B中就会被重定位到24K+12，这显然是不行的。当然，可以对这种情况也使用写时复制，但这样做就和共享库的初衷违背了。
仔细理解上面这段话。
有一个更好的解决方法，就是通过一个选项告诉编译器不要使用绝对地址的指令。相反，只能使用相对地址的指令。例如，几乎总是使用向前（或者向后）调转n个字节。这样，通过避免使用绝对地址，这个问题就可以被解决。这里，只使用相对偏移量的代码，被称为位置无关代码（position-independent code, PIC，编译器选项：-fPIC）。
3.5.7 内存映射文件
其实上面的共享库，就是一种“内存映射文件”的特例。这种机制的核心思想是：进程发起一个系统调用，把文件映射到其虚拟地址空间的一部分。
在多数实现中，在使用映射共享页面时，不会实际读入页面的内容，而是在访问页面时才被每次一页地读入。当进程退出或者解除文件映射时，所改动的页面会被写入磁盘文件中。
扩展一下，当多个进程同时映射一个文件的时候，它们就可以通过共享内存来通信。一个进程在共享内存上完成写操作，此刻当另一个进程在映射到这文件的虚拟地址空间上执行读操作时，它就可以立刻看到上一个进程写操作的结果。显然，这个机制可以提供一个进程间高带宽的通道，而且这种应用很普遍。