前面我们已经详细学习了操作系统的进程调度模块，其中多次提到了进程的内存抽象，不妨来回顾一下。如图所示，我们把进程的内存抽象表示为下面的结构：
stack存放程序的局部变量heap可以用来动态申请空间data存放全局变量、静态变量text存放代码那么，这个内存抽象该如何提供呢？需要哪些物理硬件？如下所示。
要知道，CPU 只能访问物理内存。如果物理内存不够，那么可以借助磁盘来提供存储空间。
那么，当有一个物理内存和一块磁盘来为多个进程提供内存抽象时，该怎么让它们正常运行呢？ 其实，这就是操作系统内存管理模块所做的任务。
尝试回答下面的问题。 Question1：能不能把所有的内存都分配给用户呢？ Answer1：显然不能，我们必须给操作系统预留一部分内存，其余的部分可以分配给用户。 Question2：既然我们把内存分成给用户的部分、给操作系统的部分，那这两部分是否平等呢？ Answer2：显然不是平等的，如果任何用户都可以修改内核的内存，系统还怎么正常运行呢？所以用户进程不可以访问操作系统的内存。 同时我们要提供一定的保护机制，比如分配给一个用户进程的内存，不可以被其他的进程读取或修改，除非向操作系统请求。
有了以上的构想，我们要设计一个内存管理模块，还需要解决下面问题： Question3：如何记录哪些内存已分配/未分配？这些信息存在哪里？ Question3.1 && 3.2：上面这个问题衍生出的问题是，新的请求到达时，如何分配内存给它？进程消亡时又该如何收回内存？ Question4：如何把程序的逻辑地址转换成实际存储的物理地址？
物理内存分配方案主要有以下几种，后面会依次讲解每一种分配方案。
连续分配存储管理分页存储管理虚拟存储管理分段存储管理我们能想到最直接和最简单的分配方式，是单一连续分配。
方法：
在这种分配方式中，我们把内存分成了系统区和用户区，用户区的全部内存分配给进程使用。我们不需要进行地址转换，程序生成时使用的是绝对地址，它的逻辑地址就等于物理地址。然而，用户区内存全部分配给了进程，所以这种分配方式只适用于单用户、单任务的操作系统。在单用户的环境下，机器由用户独占，如果有其他任务想要运行，必须等待正在运行的任务运行结束或强行终止。同时，在这种分配方式中，如果没有提供保护机制，用户进程是可以修改系统内存的，如MS-DOS。优点：
简单基本不需要硬件支持缺点：
只适用于单用户、单任务环境为了克服单一连续分配的缺陷，解决它只适用于单用户单任务的情形，我们引入了固定分区分配。
方法：
在固定分区分配中，我们把内存分成了若干个大小相等或不等的分区，每个区域可以装入一道程序，只要分区的大小大于等于进程的大小即可。在固定分区分配方案中，逻辑地址和物理地址不再相等，它们之间的转换过程如下图所示。对于当前进程，CPU检查它的逻辑地址范围是否在当前分区的大小限制之内，如果超出分区大小则报错。否则，取出当前分区的起始地址，与逻辑地址相加就得到了物理地址。优点：
简单，支持多道程序开始支持内存保护缺点：
分区的大小应该如何确定内存的利用率较低。任何程序即使很小，都需要占据一个完整的分区，如果它没有占满当前分区的话，就会导致分区内部有空间浪费，这种现象称为内存存碎片。为了克服固定分区的缺点，出现了动态分区的方法。
方法：
对于动态分区来说，分区的长度和数目是可变的。 当进程被装入内存时，系统会分配给它一块容量相等的内存空间。
内存空洞的形成和动态变化： 最开始时内存是完整的一块（一整个hole）。当进程请求内存时，将会从hole中选出一个分配给它，进而更新hole。 当进程结束时，将会释放这一块hole，并更新hole。 如图所示，8号进程运行结束之后释放内存，这时候内存当中就形成了一块hole，可以装下9号、10号进程。
可变分区地址转换的过程和固定分区分配的过程相同，此处不再赘述。
空闲内存分配：
在可变分区分配中，内存中可能存在大小不一致的若干个空洞。那么，当一个新进程进来的时候，我们应该给它分配哪一块内存呢？这就涉及到可变分区分配的空闲内存分配算法。
空闲内存的分配有以下几种算法：
首次适应 在首次适应算法中，每次分配内存都要从头开始扫描内存，选择大小足够的第一个可用块。因此，首次适应算法不仅是最简单的，而且通常是最快和最好的。 首次适应算法的缺点在于有可能每次都在分割同一个hole （最前面的），容易产生内存碎片，而循环首次适应算法则克服了这个缺点。循环首次适应 循环首次适应算法则从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块。 从本质上来说，它和首次适应算法没有太大的差别，但它能够防止每次都分割同一个hole。 不过循环首次适应算法常常会在内存的末尾分配空间，导致通常位于存储空间末尾的最大空闲存储会很快被分成小碎片。最佳适应 另一种分配的算法是最佳适应，即选择与要求的大小最接近的块。 最佳适应算法克服了前面两种算法的缺点，它可以保证产生的碎片尽可能的小。 不过，通常它的性能是最差的，因为它需要查找满足要求的最小块，这不仅会产生一定的开销，而且可能会导致内存中产生许多非常小的块，这些块通常小到不能满足任何内存的分配请求。最坏适应 最后一种方法是最坏适应，每次都寻找内存当中最大的hole分配给进程。 这个方法看似奇怪，实际上能够保证每次分割之后产生的新hole比较大，足以满足下一个请求进程的内存需求。碎片和紧凑：
通过讨论以上的分配方案，我们可以发现，不论是哪一种方案，都无法避免内存碎片的产生。进程运行一段时间后，一定会产生碎片，那么就需要对碎片进行紧凑。紧凑操作，又称压缩操作，它不时的移动进程，使得进程占用的空间连续，并且可以把所有空闲空间连成一片。但是紧凑操作并不是那么容易实现的，因为涉及到移动其他进程的内存空间，需要消耗一定的时间。紧凑操作会导致物理地址发生变化，此时该如何进行地址转换？紧凑操作需要动态重定位的能力，必须能够把内存的一块区域移动到另一块区域，且不会使程序中的内存访问无效。（附录7A）思考： 内存碎片这个词是不是有点耳熟？malloc/free机制是否会产生内存碎片呢？ 我们平常写程序时，在堆上申请内存是会产生一定代价的。滥用内存的后果也是比较严重的，一定得关注内存碎片的问题。
我们知道指令是顺序执行的，如果将程序离散分配在内存的各个角落，该如何对它进行管理呢？ 如图所示，连续内存当中逻辑地址为1的代码块执行了call命令，此处call的地址为2。 当程序被分散开时，逻辑地址2对应的物理地址是6，这时候通过call 2还可以访问到mov指令吗？
在离散内存分配中，我们必须回答物理内存管理的以下几个问题。 Question1：假设物理内存512 MB，页框的大小为4 KB，内核占用128 MB,剩余的空闲内存该如何进行管理呢？ Question2：应该用什么样的数据结构管理空闲的页框？ Question3：在保证离散存储，且程序执行正确的情况下，如何将逻辑地址转换成物理地址？
如图所示，0，1，2是逻辑地址空间的页面号，10，11，6，7，12是装入内存之后的物理地址，5#，3#，6#是物理地址空间中的页框号。 当我们把程序装入内存之后，call 2 这条指令的执行过程为:
首先找到逻辑地址2，它在0号页面中，偏移量为1。而0号页对应的页框号是5#。由此可以计算出物理地址为5×2+1=11。 计算过程： 因此我们需要做的就是寻找一个数据结构，能够存储页号到页框号的对应关系。因此我们需要做的就是寻找一个数据结构，能够存储页面号到页框号的对应关系。
如图所示，页表用于记录页面和页框的对应关系。逻辑地址到物理地址转换的思想就是查表加偏移。 那么这个数据结构应该如何存储呢？ 我们可以看到页号从0开始，而且是连续的，因此我们可以直接把页号作为数组的下标，这样就不用额外存储页号，只需要按顺序存储页框号即可。页表除了保存页框号以外，还要存储其他的信息，比如标志代码的操作权限，只读 or 只写 or 可读可写？还需要包括一些特权等级等信息。每个进程都应该有一个独立的页表，这个页表存储在哪里呢？ 回顾我们之前学过的进程相关概念，可以知道这个页表存储在PCB中。 PCB占用的内存大概是几百KB，是否能够存储页表呢？这个问题将在后面回答。先来几个简单的计算： 那么把公式一般化一下： 上述的计算是谁来完成的呢？是MMU。
让我们来回顾一下之前提出来的问题，一个进程的页表有多大？
假设一页的大小是4 KB，逻辑地址空间是32位，那么逻辑地址空间可以划分成个页，因此，页表一共有220个项。每个页表项存储的是对应的物理页框号，这个物理页框号占20比特。因此，假设不存储其他额外信息的情况下，每个页表项至少需要占据20比特。（实际上，32位机存在对齐机制需要占据四个字节，即32比特）一个页框可以容纳多少个页表项呢？4KB÷4B=1k，也就是说，只能存储1024个页表项。我们总共需要存储220个页表项，所以需要的页框数为1024个页框（220/ 210 = 1024)。通过上面的计算，我们可以得出结论，一个页表需要装在1024个物理页框中。
因为我们使用数组的下标，作为页号，所以页表必须是连续的，也就是说，我们必须找到1024个连续的物理页框（4 MB），这就涉及到了操作系统中连续内存分配的问题。前面提到我们将页表存储在PCB中，一张页表需要4 MB的空间，但PCB只有几百K的大小，这是为什么呢？在我们假设逻辑地址为32位的情况下，虚拟地址空间可以让每个进程都认为自己运行在4G的地址空间中，但问题是，一个进程真的会需要一整个虚拟地址空间来存放吗？再看看地址转换中存在的问题： 从页表寄存器中取出页表基地址基地址 + 页号 * 页表项大小 = 页表项地址访问这个页表项地址，得到对应的物理页框号 f页框号 f 和页内偏移 d 拼接 得到物理地址访问这个物理地址 上述过程需要访内两次，一次是访问页表，另一次访问对应物理地址。综上，我们得到了分页方法存在的两个问题：
太慢（两次访存）页表太大（如果一个页框装不下页表会带来什么问题？）快表的命中率直接影响了访存时间，那么如何提高命中率？ 应该注重程序的局部性原理，结构化编程，不要乱跳。
一个页框最多可以容纳多少个页表项？
页框 4KB=212B每个页表项 >=20 bit ( 物理内存大小/页大小 ）页表项数 <= 212 * 8 / 20 = 1638 <210.67一个页表至少需要多少个页框？
共有页表项：220至少需要 220-10.67=29.63针对页表过大的问题，我们引入了多级页表来解决：
通过前面的计算，可知我们需要1024个物理页框。因此为进程添加一级页表，用来记录这1024个物理页框号。一级页表共1024项，每项4字节，所以一级页表的大小为4 KB，因此一个页框刚好能装下一级页表。这时候重新来看一下逻辑地址的构成:
首先需要存储一级页表中的页号，因为一共有1024个项，所以占10个比特。其次，需要存储二级页表中的页码，也是10个比特。剩下12个比特存储页内偏移量。逻辑地址到物理地址转换： 注：CR3是页目录表地址寄存器 地址转换过程如图，这里不用文字赘述啦：
二级页表的好处：
节省内存（尤其当地址空间中有空洞时，页目录项中指明对应页表是否存在）思考：
背景如下：
页表、页目录表中的页框号均是物理地址，而CPU产生的每个地址均是逻辑地址。页目录的逻辑地址存在pcb的pgdir指针中。Question：如果OS想将页面0对应的页框号修改为3，请问c语言代码怎么写？
