《现代操作系统》精读与思考笔记 第三章 内存管理
本系列博文是《现代操作系统（英文第三版）》（Modern Operating Systems，简称MOS）的阅读笔记，定位是正文精要部分的摘录理解和课后习题精解，因此不会事无巨细的全面摘抄，仅仅根据个人情况进行记录和推荐。由于是英文版，部分内容会使用英文原文。
课后习题的选择标准：尽量避免单纯的概念考察（如：What is spooling?）或者简单的数值计算，而是能够引起思考加深理解的题目。为了保证解答的正确性，每道题都会附上原书解答，而中文部分会适当加入自己的见解。原书答案（需注册）
注：本文部分内容需要读者对页式、段式、段页式内存管理有基本了解。
概念回顾
交换技术(Swapping)：内存紧缩、用于内存管理的位图和链表、匹配算法：首次匹配、下次匹配、最佳匹配、最坏匹配；
虚拟内存：前身是手工完成的覆盖技术(overlays)；内存管理单元MMU及地址转换：页表、TLB（转换检测缓冲区，也称为关联存储器，俗称快表）、多级页表；
页面调度算法
共享库(shared libraries)/动态链接库(DLL,Dynamic Link Libraries)
段式内存管理、段页式
1.TLB的译名
如果之前学习过国内的操作系统教材，TLB一般被称为快表，而不是转换检测缓冲区（Translation Lookaside Buffer）或关联存储器（associative memory）。对于国内常见的称呼，容易知道它是做为整个页表的一个部分缓存，从而加快虚地址向实地址转换的速度。因此，它和页表的条目结构很类似。具体解释见于P195~197，另外段式存储管理中也可以使用TLB加速访问。对于不同地方出现的TLB，它缓冲的内容与其应用场景有关（MULTICS、Pentium等等）。可以看出，这个译名比较形象，不过原名更具体些。
2.倒排页表（Inverted Page Tables）
本科时学习“操作系统”的”基本分页存储管理方式”时，对于64位计算机、单个页面4KB（即212B），两级页表已经过大而不能装入内存。汤子瀛版《计算机操作系统》介绍了2种处理方式：使用三级或以上的页表、将寻址空间降低到45位左右而不是64位。前者仍然比较繁琐，后者可行性比较高。那时我就对前者心存疑惑：虽然能够将需要用的页表调入内存，可是它们总大小仍然很大，有没有更好的实现？接下来看一看《现代操作系统》提供的方式：倒排页表。下面这部分内容取自原书P200~201的整理。
先简述下问题所在：64位计算机中，如果页面大小为4KB，那么64位寻址空间需要252个页表项。假设每个页表项大小为8B，那么需要30PB的空间，在目前计算机发展阶段显然是不现实的。
倒排页表是一种解决方案，正如其名所揭示的：普通的页表是将虚地址映射成物理地址，提供的是将页号(page number)转化为页框号(page frame number)的对应；这个转化由MMU完成；而倒排页表正相反，提供的是将页框号转化为页号的对应。页框号是实际内存的大小/页面大小，因此1GB内存只需要262,144个项即可，远远小于252这个数字。
个人认为，这个解决思路的妙处在于：32位下，页表项总和比较少，至多两级页表也已够用；而64位下，内存的大小（也即物理地址空间）与寻址空间（虚地址空间）相比反而显得小了，这样干脆来个倒转，不失为一个很好的方法。
当然这种解法虽然节约了大量的存储空间，但是内存管理中需要的是将虚地址转化成物理地址的机制，而不是正相反啊？这种映射是单向的，总不能每次转化都把这个表遍历一次吧？那样做的开销实在是太大了。
一种解决方法是使用TLB，但是TLB也有失效(miss)的时候，这时还是需要进行查找。一个可行的方法是将所有用到的虚地址hash掉，形成一个hash表来加速查找，同样哈希值的虚地址形成一个链。如果hash表的槽数与物理内存的页框数一样多，那么哈希表各表项平均长度为1，这样提高了查找速度。这个解决方法的演变可以见下图3-14。
3.LRU和NFU的算法实现(1)LRU算法实现
LRU，汤子瀛《计算机操作系统》译为“最近最久未使用”，也即在缓冲的所有页面中，缺页中断发生时，将最久未被使用的页面置换出去。不过按照字面意思，Least Recently Used似乎应是《现代操作系统》中译版的“最近最少使用”，似乎是需要统计页面使用频率的。这里有必要先探讨下这个翻译问题。这个翻译的区别在于，副词least修饰的是recently还是used。P206原文：
A good approximation to the optimal algorithm is based on the observation that pages that have been heavily used in the last few instructions will probably be heavily used again in the next few. Conversely, pages that have not been used for ages will probably remain unused for a long time. This idea suggests a realizable algorithm: when a page fault occurs, throw out the page that has been unused for the longest time. This strategy is called LRU (Least Recently Used) paging.
这前半段和后半段意思并不是很一致。按照前半段的意思，用的最多的(heavily used)最应该保留；而后半段，也即LRU的定义，反而是指“最久未使用”。假设这样一种情况，内存只能容纳两个页，如果考察的时间跨度大于2，对于0,0,…,0,1的页面访问序列，此时访问页面2，前半段会认为0的使用频率最高，应该保留0，而后半段认为0是最久未被使用的，应该保留1。这样就产生了矛盾。不过既然是一个近似，按后半段更合适一些，这样反而显得“最近最久未使用”是一个更合适的译法。《现代操作系统》提到的3种算法，其实都是符合定义的：
一种实现是用一个特殊链表，将最近最多使用的放在表头，最近最少使用的放在表尾，每次使用到的页面如果在链表中，就把它取出并放到表头。不过这个实现一方面很耗时，并且实际上是“最近最久未使用”。
尝到你和你在一起的快乐，你是唯一能让我尝到酸甜苦辣的人。
