这是我在简书上的第一篇文章。最近在自学操作系统，然后发现网上很少有对内存规划这一块进行的比较直接简单完整的介绍。我想根据自己的理解写一些东西，作为记录，也可以和别人分享。其中自然会有许多理解上的错误，希望能得到指证。

从而说起呢？我想自己意淫下。

想象下，一开始的电脑是很简陋的。也就是只有几十几百KB的内存。所以这个内存就是程序所能用的空间的最大值。但是那时候程序也是很小的，所以够用。后来科技发展了，程序员写出了更加复杂的程序，这个时候，内存不够用了。于是问题就来了。

该怎么解决这个问题呢？

虚拟内存。

例子1，看电影的时候，有时候一部电影得5G朝上，那么我们开始看的时候，有必要把后面时间段的视频也载入内存吗？明显没必要。所以我们把现在需要的一个时间段（working set）的数据载入内存，然后不停地那新的视频数据来代替旧的数据，这样就大大节约了内存。

例子2，玩魔兽世界的时候，不可能一下子把32G的游戏全部载入内存。就是根据你在哪儿，把相关信息载入内存，然后你不停的去新的地点，他就不停的载入新的数据来替换掉旧的数据。

对于一台内存为256M的32bit x86主机来说，它的虚拟地址空间范围是0~0xFFFFFFFF（4G），而物理地址空间范围是0x000000000~0x0FFFFFFF（256M）

这就是虚拟内存。把内存的东西暂时存到硬盘里。需要的时候再取出来。

这就涉及到两个问题。

1.放在硬盘的数据，如果内存里的进程需要了，怎么找回来？

2.硬盘的速度是内存的几百分之一，很慢，如何设计系统才可以更好地提升计算机的效率。

问题二就可以分为两个小问题，

a.程序进入内存时，该给进程配置多少页

b.如果进程需要新的页，而分给他的空间已经满了，会用新页代替旧页，该选择哪个代替（page replacement）

首先看第一个问题。科学家发明了一种叫做MMU（Memory Management Unit）的硬件。他可以实现虚拟地址和物理地址之间的映射。

过去的时候，没有MMU，程序员写程序，编译器翻译时，会把相关地址直接翻译成物理地址，然后直接映射到内存的相应区域。现在有了MMU就不一样了。编译器可以把相关地址翻译成逻辑地址，然后再由MMU转换成相应的物理地址。这么做有什么好处呢？

如果没有MMU，首先是肯定不能使用虚拟内存这个思想。其次是，因为没有这么一个地址映射器，编译器翻译出来的地址就是物理地址，这样为了确保程序运行，程序的数据段啊，代码段啊，堆栈啊，必须放在一块连续的物理内存里，这样之后编译器才能比较容易实现定位。因为栈指针，帧指针，全局数据指针的地址都是存放在寄存器里面的，寄存器通过加一减一这样的简单操作来选择下面的数据。所以所有数据必须放在一块连续的内存里，否则很可能通过指针就很难找到对应数据了。

如果有了MMU，那么就不一样了。我只要保证逻辑地址是连续的就行了。把刚刚的那些问题重复在这个有MMU的环境下，那些问题就不再是问题了。逻辑地址连续，那么我的栈指针，帧指针，全局指针加一减一可以毫无问题的定位到相应的逻辑地址。而这些逻辑地址发到MMU里面，MMU把他们映射到不同的物理地址上，这样仍然可以找到所需的数据。所以，有了MMU，逻辑地址是连续的，进程在物理空间上的映像却再也不连续了。这有好处的，不连续的内存映像可以减少内存空洞（hole,内部的，外部的）的出现。这个原因具体自己查吧。

那么有了MMU之后，科学家又想出了一种软件机制，分页，（Page）。即把逻辑地址分页，分成一页一页的小内存。然后再把物理内存分帧，（Frame），Frame大小和Page相等，Page是逻辑地址上的基本单位，Frame是物理地址上的基本单位，两者通过MMU形成映射关系。

然后就必须要有页表（Page Table）了。页表记录了逻辑地址上的一页对应了物理地址上的一帧。一般是把逻辑地址输入进MMU，同时给MMU载入页表（这个过程下面会具体说），然后MMU输出相对应的物理地址，从而实现定位，或者说，映射。

那么，这样一个具体过程是怎么样的呢？我谈下自己的理解。

假设我们下载了一个程序。然后它会存在硬盘里。双击启动它，程序被激活，变成了进程，会向操作系统申请内存，进入等待队列。然后OS通过算法，根据该进程的页（Page），从free pool里面分配一定数目的帧（Free Frame）。这就会涉及到问题二的a，之后谈。

然后通过导入的页和其对应的帧生成页表，指向该页表的指针储存到该进程的PCB（Process Control Block）里面。这时候进程变成就绪状态，等待CPU。CPU处理后，执行又一条instruction，如果需要新的页，而分配给进程的空间已经满了，这时候就会涉及到问题二的b，需要那新页取代一些旧页，算法之后谈。进程进入等待队列。

页表的每一项逻辑地址都会有几个状态标记位。如，reference flag(1 被引用过 0 未被引用过)，modified flag(1 被修改过 0 为被修改过)， value bit（1 在内存里 0 无效页或者在硬盘里） 还有一个标志位用来标志该页在内存还是在硬盘里。

当上述情况发生时，OS会看该页是否在内存里。如果在，那没事了，直接通过逻辑地址和MMU定位到相应的物理地址上。如果在硬盘里，会触发一个中断，page fault，然后OS会去硬盘里调出相关的页（同时将其value bit 设置为1），然后踢掉内存里相关的页，将其value bit设置为0（还有种情况是进程空间未满，那就不用踢了，这里不讨论了），拿新页代替。如果被代替的页被修改过（modified flag = 1）,那么它得再次回写到硬盘里（backing store），如果未被修改过，那么直接把对应的frame放回free pool里面。下次直接覆盖里面的内容即可。然后当页条件满足时，CPU会 restart the instruction，重新跑一下刚刚那条指令。

当然这里也有一个知识点，如果刚巧这个frame之后没被用掉，然后那个页又进内存了，那他可以直接找到该frame，也不需要从硬盘把数据复制到该内存块上了，因为之前的还未被覆盖。所以frame也有个标志位叫做dirty bit用来表示上面这个信息。然后frame的信息（哪些在被用，哪些已经被污染过了，哪些free）都保存在一个叫做frame table的数据结构中，然后OS知道它的位置。

感觉这就基本是OS-Memory Management的流程了。每个进程都有一个页表，存在内存的不连续位置里。指向该页表的指针存在PCB里。

需要调入新页的时候，CPU会生成一个虚拟地址送给MMU，MMU生成页表表项（PTE）地址，并从高速缓冲/主存中得到页表。然后把该页表返回给MMU，MMU通过该页表和虚拟地址构造物理地址，并把该物理地址传送给高速缓冲/主存，请求数据。所以需要访问两次主存。

然后，现在的虚拟空间一般很大，如果page size小的话，有时候用来储存信息的页表也过大。但是我们不想用一段连续的内存来存储它，一般就会对应有三种解决方法。

1.采用分级的方法，两级页表等等。

2.采用Hashed Page Tables,每个表项里用链表连接。

3.采用反转页表，Inverted Page Table (IPT)，采用物理内存顺序（块号）排序。用进程标识符和页号来检索该反向页表。即通过物理内存来找对应的进程的页号。这样每次都得检索一下整个反向页表来找所需要的东西，费时，但是该反向页表却比页表要小很多（这里我不知道为什么小很多。）

有了分页技术，也就出现了，shared pages。共享内存。即不同的程序可以通过页号指向相同的frame，以此共享该块数据。然后通过修改该共享数据，也可以实现进程间的通信。

自然，shared pages也便宜了申请子进程的开销。当父进程fork()出子进程后，有一个叫做copy-on-write的技术。一开始子进程的页和父进程指向相同的内存块。如果在子进程中修改了某个内存数据，OS会把该修改的信息拷贝到另外一个内存地址里，原内存不变，所以此时本来共享某内存块的页，父进程仍指向原来的内存块，而子进程指向了新的内存块。其他未被修改过的页仍指向同一个内存块。这样大大减少了申请子进程的开销，因为一开始不需要为其分配过多的内存。

共享数据还有一个叫做 Memory-Mapped Files，即把磁盘里面的文件直接拷贝到进程空间里，避免了之后频繁从磁盘加载到内存，回写等步骤，而且进程间可以通过该内存映射文件实现通信。

第一个问题差不多谈到这里吧，下面说说第二个问题。分配算法。

a.程序进入内存时，该给进程配置多少页

b.如果进程需要新的页，而分给他的空间已经满了，会用新页代替旧页，该选择哪个代替（page replacement）

a.分配时必须给进程保证最少数目的页 = 进程中单条指令最多所需的页数

如果分配的不好，会出现thrash现象，即OS不断地收到page fault中断，不断地向硬盘demand paging。造成效率降低。所以一般会根据不同的系统有一个working set，他有初始值，之后不断变化。在一个working-set里面统计所有进程所需要的页数，如果他大于目前物理内存还剩的空间，那么就得按照replacement算法，选择一个进程，将其设为无效，把它的frame全部freee掉，空出足够的空间来应对thrash。

b

Page-replacement Algorithm有好多种。比如 FIFO,OPT(不可能实现)，LRU等等，再次不多说了

当然刚刚谈的都是用户空间，内核空间是完全不一样的。

首先内核空间的数据结构大小不同，很多小于one-page size，如果采用分页，浪费空间，而内核空间寸土寸金。

其次，用户空间的程序对时间要求不高，但内核对响应时间有着严格的要求，所以如果采用分页太浪费时间了，只能用连续空间来储存。

因此有两种分配算法。Buddy System 和 Slab Allocation，具体自己查吧。

最后说个题目，如果这道题理解了，那么基本对内存规划也理解了。

one system, page size: 128 words, 整型（int）size: 1word

代码1，

int i,j;

int[128][128]data;

for(j = 0;j < 128;j++)

   for(i = 0;i < 128;i++)

       data[i][j] = 0;

代码2，

int i,j;

int[128][128]data;

for(i = 0;i < 128;i++)

for(j = 0;j < 128;j++)

data[i][j] = 0;

你觉得这两种算法哪个效率更高？

后记：这是修改过的文章，我一开始发表的时候不知道为什么后面一大段全部没了，这让我对简书的印象大打折扣。本着做一件像一件事的原则，我又重新打了。

写完这篇万丈感觉印象又加深了，但是感觉文章顺序不太好，可能也是自己没有准备提笔就写的结果吧。希望有人会看吧，更加希望有人可以一起交流学习。

下面我就打算开始学习File Systems。加油

后记：

第一次写文章，现在重读，觉得写的太差了。该突出的重点也没有突出出来。有一块甚至遗漏了。就是translation look-aside buffer (TLB), 中文翻译应该就是快表。

OS会先去检索快表，如果没有命中，再根据页号去内存请求数据。请求的数据先导入cache，然后更新快表，最后将所需要的数据送入CPU。

快表是一个键值对，page-frame。他之所以快是因为快表本身就在cache里面，和他相关的数据也全部都在cache里面。然后CPU需要什么，就检索快表，找到了直接送入CPU。

真正的优势在于，cache运行比内存快，而且距离CPU的物理距离近。

今天上课听老师说冯诺依曼结构的瓶颈就在于内存和CPU的物理距离过大，现在CPU和内存的速度越做越快，但是他们之间的距离却无法改变，而传输数据的速率-光速也无法改变。所以我们得把计算机经常用到的东西导入cache，避免计算机去内存要东西，更不应该让计算机去硬盘要东西。

说到了cache，我今天也查了下，加深了理解。cache和buffer有啥区别呢？

1、Buffer（缓冲区）是系统两端处理速度平衡（从长时间尺度上看）时使用的。它的引入是为了减小短期内突发I/O的影响，起到流量整形的作用。比如生产者——消费者问题，他们产生和消耗资源的速度大体接近，加一个buffer可以抵消掉资源刚产生/消耗时的突然变化。

2、Cache（缓存）则是系统两端处理速度不匹配时的一种折衷策略。因为CPU和memory之间的速度差异越来越大，所以人们充分利用数据的局部性（locality）特征，通过使用存储系统分级（memory hierarchy）的策略来减小这种差异带来的影响。

3、假定以后存储器访问变得跟CPU做计算一样快，cache就可以消失，但是buffer依然存在。比如从网络上下载东西，瞬时速率可能会有较大变化，但从长期来看却是稳定的，这样就能通过引入一个buffer使得OS接收数据的速率更稳定，进一步减少对磁盘的伤害。

4、TLB（Translation Lookaside Buffer，翻译后备缓冲器）名字起错了，其实它是一个cache.

该段摘录自 知乎 的一个匿名网友，写的挺好的。我觉的buffer就是一个编程上的概念，让我们解决速率突然暴增的问题。不只是计算机，通信系统，银行，日常生活其实都有buffer的思想。而cache就是一个硬件设备。

最后再谈一个问题，之前的文章没有说清楚。

逻辑地址，虚拟地址，线性地址，物理地址之间的关系是什么？

我觉得我们在编译器上写的代码，编译器翻译出来的最初版本是逻辑地址。然后通过一个 segmentation unit，将其分段。因为咱们的代码里面有，有代码段，数据段，栈，堆，还有一些库函数，系统文件等，我们需要将其分段，即把一个程序分成各个不同的部分。这时候程序就变成了一个整体，有，系统空间，代码段，数据段，堆栈等。这时候的地址就是虚拟地址，又称为线性地址。（虚拟地址 = 线性地址）， 然后在经过MMU就可以得到物理地址了。

送几个截图加深印象。

还有一篇刚刚看到的文章，具体地讲述了cache运行的机理和硬件上的构造。有兴趣可以看下。我是看懂了，但是很快会忘掉，其实有个大体的印象就可以了。其中有句话我思考了下，他说，每个进程都认为自己有4G的内存空间。为什么。因为每个进程的虚拟空间都有4G。虚拟空间是分页的，你可以把程序写成4G（此说法不太严谨，毕竟还有操作系统得占空间），然后会给你分页的。你也可以写成4M，然后没用的空间首先就不会给你分页。毕竟是虚拟地址。所以不会有多大影响。

链接如下：

http://www.cnblogs.com/pengdonglin137/p/3362274.html