THU《操作系统》学习笔记——原理3：物理内存管理：连续内存分配
1.计算机体系结构和内存层次
1.1 计算机体系结构
计算机系统当中除了处理能力以外，还有存储能力，存储能力相当于我们有一系列的基本存储介质，我们要在这些介质当中来存代码和数据。对于计算机系统来讲，它的体系结构当中就约定了哪些地方可以用来存数据，这些地方既包括CPU里的寄存器，也包括内存和外存。这几种不同的介质，它的容量，速度和价格都是不一样的，为了组织一个合理的系统，我们把计算机系统当中的存储组织成了一个层次结构，针对这种层次结构下的存储单元，操作系统需要对它进行管理。操作系统当中的存储管理实际上就是用来管理这些存储介质的。最基本的管理要求是说我们一个进程需要使用存储单元的时候，需要从操作系统分一块给它，等它不用的时候还给操作系统，这是它最基本的分配和释放的管理要求。针对这种管理要求，我们来看在计算机体系结构当中有哪些因素对它有影响。
在CPU里，我们可以往寄存器里存内容，但是寄存器的容量是非常小的，通常是32位、64位的寄存器，那一共能存的数据也就几十个字节，或者说几百个字节。内存是能存储更多数据的地方，计算机系统当中内存的最小访问单位是字节，也就是8bit。而通常我们所说的计算机是32位总线，那32位(数据)总线也就相当于一次读写可以从内存当中读或写32位，也就是4个字节，这样的话读写速度就会快了。如果针对这种特点，在一次读写32位时有地址对齐的事，那么就不能从任意一个地方开始读写一个4字节，有可能这个读写就被分为两次。
在CPU里还有高速缓存(cache)，在进行读写指令的过程当中，访问数据都需要从内存里读数据，这个时候如果说有大量数据要读写，而且会重复利用的话，在CPU里加上高速缓存，这样的话它的读写速度会更快，这个时候整个读写效率会提高。
图片里的这几个部分都对存储管理有至关重要的影响。所以大家在实际做操作系统的存储管理实现的时候，必须很准确地了解对应CPU的结构。
1.2 内存层次
CPU里有两级缓存(L1 Cache和L2 Cache)，如果说我们在读写指令时在缓存里已有相应的内容（事先已经读过），那这个时候就可以从缓存里拿到，这时速度是最快的。然后如果在这里缓存不命中，就必须到内存里去读。而我们在写程序的时候，是感觉不到L1,L2 Cache的存在，原因在于这部分完全是由硬件在做控制，你写的程序不能显式地使用到它们。
而内存的访问就需要使用到操作系统的控制，如果在内存里仍然找不到，这个时候可能是存到外存里了，那么从外存把它读进来再进行访问，这个时候就需要用到操作系统的控制。
那在这个体系结构当中，我们可以看到从CPU内部一直到外存，这几个速度差得是非常大的，差将近是百万倍的数量级。所以在这套体系当中，要想把它协调成一个有机的整体，实际上对于存储管理来讲，它的挑战性还是很大的。
1.3 操作系统的内存管理
对于操作系统来说，存储管理最后想要达到什么效果呢？
首先我们看到系统当中的存储，内存我们刚才说了是以字节为单位进行访问,每一个字节都有一个自己的地址，这个地址是物理地址。而外存，比如磁盘，磁盘的访问有扇区编号，每一个扇区是512字节最小单位。那么这些是你能够读写存储的最基本的内容，而写程序我们希望看到的情况是我有若干个进程，每一个进程它们都有共同的一部分地址空间，是操作系统内核，而每一个应用程序的自己又是不一样的，它们各自有各自的内容，我们希望在写它们各自的内容的时候它们的地址是可以重叠的，相互之间是不干扰的，这是我们希望看到的状态。
那么把内存的状态转变成我们上面逻辑的理想状态，我们在中间加了一层存储管理单元(MMU-Memory Management Unit)。那存储管理单元就把逻辑地址空间转变成物理地址空间。实际的操作系统通常情况下是在内存里头的，而进程的地址空间随着它们运行的转换，有些是在内存，有些是在外存。这个转换的过程由中间的存储管理单元来完成。如果说我们能做到这样一步，实际就相当于存储管理要达到的效果是：
实际上想要实现存储管理的抽象，保护，共享和虚拟化，实际上这几个目标还是很有挑战的。
1.4 操作系统的内存管理方式
具体说起来，我们在操作系统里可能采用一些什么样的方法进行内存管理呢？
实际上在最早的计算机系统，它是直接使用总线上的物理地址来写程序。我要想读写某个内存单元，它在什么位置，我们在程序里见到就是它的物理地址。但是这种做法实际上有很大局限，你写的程序只能在指定类型的机器上运行。那我们第一个可以让它变灵活，实际上相当于我们可以整块地搬，也就是重定位。如果说我们现在看到的地址访问说每一个地址是一个段地址加一个偏移来表示的，实际上就是从这个重定位地方来的。有了重定位之后，我们只需要改段寄存器的地址，那么这个程序就能运行了。这是第一种做法，为了实现它，在程序和操作系统里都要有一些相应的支持，这些支持后面会来说。
重定位的一个问题是一个进程分的存储空间，它是一个连续的存储空间，不能把两个进程交错起来，实际上这是一个很大的限制。我们希望它能不连续，实际上我们在写程序的时候，它的逻辑结构不是一片必须连续的区域，而是说我们把程序分成了数据，代码，堆栈，这三个部分是相对独立的。不会说我从堆栈段直接去访问代码段里的内容。基于这种情况，至少可以把代码，数据和堆栈分成三块，每一块需要的空间就会变小了，这就是分段。不过分段仍然还是需要连续的存储空间，这个要求仍然足够高。
分页实际上就是把内存分成最基本的单位，就比如说我们要在Minecraft盖一栋楼，我们需要的最基本的材料就是一块一块的方砖，你可以把它们加在一起之后变成你想要的各种各样的形状。我们也希望是从最小的单位——1页来构建你需要的存储区域。如果说我们的最小的单位就用一个字节不是挺好的吗，但实际上这个时候最小单位只有一个字节的话，你在 访问的时候，它开销就粒度太细，以至于管理的时候难度很高。所以我们在这需要选一块合适的大小，这一块最基本的单位是一个连续区域，这是我们这里的页，基于这个来构造你所需要的存储空间的内容。
我们希望把数据存在硬盘上，而硬盘上的数据和内存上的数据它们俩之间的倒换是由操作系统内部来实现的。这时候希望看到的是程序是一个逻辑地址空间，甚至这个逻辑地址空间是大于物理地址的空间，那这样就是虚拟存储了。
在我们操作系统里，基本就是以这几种方式来管理内存。所有这些管理方法对硬件的依赖程度都是非常高的。比如说MMU里的结构是什么样子的，然后我们CPU能够识别的页表是什么样子的，这些都能够直接影响到存储管理方式的实现。
2.地址空间和地址生成
2.1 地址空间定义
我们在机器里总线上看到的地址是物理地址，所有的物理地址所构成的空间叫做物理地址空间，它是由硬件支持的。通常情况下，比如说我们机器里有多少位地址总线，指的就是这里物理地址总线的条数。比如说32位的，通常情况下就是32条地址线。物理地址编号是从0开始，比如说32位是0到4G-1(最大编号)。这个编号在存储单元角度来讲是唯一的，这种唯一对我们写程序来讲是不太容易来使用的。因为我到底用哪个地址，在程序写成之前我可能是不知道的，那么这样一来，我们在这里用到第二个地址是逻辑地址。
逻辑地址是CPU运行的时候进程看到的地址空间，那通常情况下对应的是我们可执行文件的那一段区域。加载程序的时候，程序加载到内存当中它变成进程，这个时候在你的可执行文件里的0到它的最大值（地址编号），这个地方在相应的地址空间里有一段区域，这个区域就是我们的逻辑地址空间。
那么我们说一条指令在执行的过程当中，它会访问相应的内存单元，这些内存的地址从哪来呢？就是从逻辑地址转换成物理地址，最后在总线上访问相应的存储单元。
2.2 逻辑地址的生成
现在我们写程序都是用高级语言，高级语言里图中就是一个小例子。一个程序它有一个保留字，prog到end这是它的开始和结束标志，中间调用了一个函数，这个函数就是一个地址，我们通常在写函数时不会写成地址0x多少来作它的名字，这个很不好记，我们会用一个符号来表示。那么用符号之后，不同的函数之间它们就没有一个先后顺序的关系，把它放在内存里可以把它放在任意一个位置，这是我们在写程序源代码的时候所希望见到的状态。
源代码里的这些语句CPU没办法认识，所以之后要进行一次编译，转变成机器能认识的汇编指令。转换过来之后，我们会看到它变成函数调用，jmp或者是call都是会有的，而后面仍然用的是符号名字，这还只是汇编的源代码。我们会对它再进行一次汇编，汇编之后实际上就变成二进制的代码了，这个时候就是实实在在是机器能认识的指令，这个时候里头的符号就不能再是字符串了，而必须是地址空间里的某一位置。比如图中jmp后就是75，那么就是从当前的位置跳到75，这个地方用到的就是编号。如果从模块A调用模块B里的一个函数，在做汇编的时候，另一个模块的位置可能不知道，这时需要再有一个链接的过程，把多个模块和用到的函数库搁到一起排成一个线性的序列，排了之后就可以知道要跳转的另一个符号的位置在哪。比如说在这里代码自己会移动，模块之间也会有，那么这个时候前面放了个函数库，原本要跳的位置向后挪了100，那75就变成了175，不过这里的175只是对于这一个文件内来说的。如果说程序去运行，它文件的起始地址不一定能放在0的地方，那在加载的时候还会再有一个重定位，比如说原先文件中的0把它加载到了1000的位置，如果还是跳到175，那跳的位置就错了。这时要统一把这些位置都平移一遍，175就变成1175了，这就是在加载时操作系统提供的重定位的功能干的事情。有了这个之后，程序在跑的时候它就变成是实实在在的地址了。
2.3 地址生成时机和限制
地址生成机会有这样几个情况：
假定知道最后要放的位置，在编译时就可以把这个地址写死。但如果是这种情况，起始地址发生变化，那就必须重新编译了。这种情况现在在什么地方出现呢？像功能手机的话，里面的程序地址是写死的，不允许你买了手机之后再装软件，这就是地址写死的。
还有一种情况是允许加载到不同地方，比如说智能手机，可以买到手机之后再往里加自己的程序，那这时候写程序的人就没法知道程序最后会加载到什么地方。如果是这种情况，那么在加载的时候就必须做重定位，也就是说根据装到内存位置里的不同，要把程序里那些符号的名字或者跳转的地址重新捋一遍。通常情况下在可执行文件里有一个重定位表，那这个重定位表里包含的内容就是在这个程序里到底哪些地方是需要改的，加载的时候把这些都改成绝对地址，那程序就可以跑了。
最后一种情况是执行时生成，意思就是我们在前面用的一直就是相对地址，那么在执行到这一条指令的时候才可以去知道它确切访问的是什么地方。那么这种情况出现在使用虚拟存储的系统里，也就是说我执行一条指令，到指令访问的位置之后，有可能当时把这一块区域放到内存的某一个位置，这个时候它有一个映射，映射过去之后找到相应的位置，那这个时候只是在执行这条指令的时候才会做这种映射。这样做就有一个什么样的好处？这个程序在执行的过程当中，就可以把它在物理存储的位置挪动。而如果是前面两种情况的话，不但要求程序所在的地址空间是连续的，运行起来之后也是不能再动它的地址的。所以从灵活性来讲，我们在执行的时候生成地址是最好的，而前面两种它有的好处是简单。所以不同系统里这几种做法，现在都是有采用的。
2.4 地址生成过程
下面我们通过一个图示来看一下地址的生成过程。
这是我们之前说到过的系统结构：CPU，内存，I/O设备。比如CPU正在执行一条movl指令(movl %eax,$0xfffa620e)，这条指令在执行的时候里头有地址，这个地址在CPU里先看到了，然后这个时候MMU依据页表来把CPU这边见到的逻辑地址翻译成物理地址。翻译成物理地址之后，CPU里有一个控制器，这个控制器负责把得到的物理地址和相关总线控制信号送到总线上去。然后这个时候存储芯片会识别总线上的地址和控制信号，依据信号是读还是写，那总线上有一组相应的持续逻辑的交互。如果是写，就会把CPU送过来的数据写到内存当中指定的单元上。如果是读，那就从指定的内存单元当中读出数据，放到数据总线上，然后CPU拿回去。这是它的一个交互过程，在这个交互过程当中，CPU能干什么呢？CPU能对地址转换过程产生影响，实际上在每一次访问的时候，它是不依赖于软件的，是由硬件来完成这个转换的。但这个转换的表我们是可以通过操作系统来建立逻辑和物理地址两者之间的映射关系，这就是页表的功劳。
2.5 地址检查
这是一个图示，说明CPU在执行指令时它的地址生成过程。
这是一条movl指令，movl指令在CPU执行的过程当中，它会产生逻辑地址，比如它访问的是数据段的数据，数据段它有一个段基址和段的长度。如果说从数据段去访问偏移量超过这个长度，那这个时候这个访问是非法的。在每一条指令访问的时候，它都会去检查段长度和偏移量是不是有效范围，如果不是就告诉你内存访问异常，指令执行失败，之后操作系统做进行相应的错误处理。如果检查完的结果是访问的偏移量在0和最大长度之间，那么认为这是合法的，这个时候偏移量会和段基址加在一起得到物理地址。
那么在这个过程当中，操作系统可以通过指令来设置相应的段长度和段基址，这是我们可以通过软件方法来影响地址检查。有了这个检查之后，就有了从符号到逻辑地址，逻辑地址在执行过程中转变为物理地址，并且在这个过程中有相应的检查机制，这是我们这里说到的地址生成和检查。
3.连续内存分配
在分配内存空间的时候，在没有其他的技术支持的情况下，分配给一个进程的地址空间必须是连续的。那么为了提高利用效率，我们希望分的位置有适度的选择。那动态分配算法实际上就是选择地址空间的算法，而选择完之后，每一个进程可能用的时间长短不一样，有的进程先结束有的后结束，这个时候可能先结束的会留下一些空，后面一个在分配的时候又会再去找，这个过程的执行就会在中间留下一些碎片，这些碎片对于后续的分配是会有影响的。那我们就从如何去找要用的空闲分区和如何来处理这些不能利用的小的空闲分区的两个角度来看连续内存分配算法。
3.1 连续内存分配和内存碎片
连续内存分配时指给进程分配一块不小于指定大小的连续的物理内存区域。那这里有一个图示，是说进程不断地分配回收，分配了三个，进程二就释放掉了，这个时候是内存分配时候的状态。每一个进程的地址空间里我们可能存放的是代码，数据，堆栈这些内容。那在这中间我们就会有一些区域没办法利用了，比如说像图里（稍长的横杠作分界），p3上一块，p3和p1中间一块和一个三块的区域。中间如果你要分配四块的话，那么这三块的区域也没法用了。对于这些没法利用的区域，我们就称之为是碎片。那这些碎片是没办法利用的，这个没办法利用是相对而言的，如果说你要的小块，那其中这块还是可以利用的，但是有一些是无论如何用不起来的。那这些碎片呢，我们把它分为两种情况：
外碎片是说两块之间的这一块，那实际上它也是一个小的空闲块，只是因为它过小，而其它进程申请的区域大小都大于它，导致没法利用。
内碎片是分配给进程的区域内部的一些没法利用的区域。什么情况下会出现呢？如果说分配的时候，并不是说可以准确地分配指定的大小，比如说想分配510字节，但是实际上在分配的时候只能按512字节这种2的整数幂为单位的大小来分配的话，那剩下的2个字节就没法利用了。像图中p1和p3上面剩的这段就是这种情况，那是由于它要取整所导致的，我们在分配的时候就希望尽可能减少这种碎片的出现。
3.2 动态分区分配
动态分区分配实际上是说在分配的时候可以指定大小，并且这个大小是用户指定时可变的。那我们分配出来结果叫一个分区,也可能叫内存块或块，分配出来的地址是连续的。
那么图中是个例子，刚开始顺序分配6个进程地址空间，在用的过程当中，某些进程(p2,p5)就会结束，那结束掉就还回来了。对于这种情况，现在我想再分配的话，我就必须知道我哪些内存区域已经分配给了进程，哪些内存区域还是空闲的。那么我们的操作系统就要维护两个数据结构，一个是已分配的分区,我们需要知道哪些是已经分配出去的，它分配给了谁；一个就是空闲分区，我需要知道空闲分区的位置和大小。对于不同的查找方法，这两个数据结构的组织形式是会有一些变化的，那么在不同的组织形式下，在找分区或者把分区释放的时候，放回到空闲分区列表里的时候它的开销是不一样的，这是我们需要考虑的问题。
对于找分区的不同，我们在这就有这样几种动态分区的分配策略：
大家通常想是我要分配一块区域，我就给系统一个指定大小，这个时候系统去找，先碰着哪一个就找哪个。这就是第一种情况：最先匹配。
把所有的空闲分区看一遍，看看这里哪一个是比指定的大，又大得最少的那一个。如果说这些空闲分区是按地址顺序排的，那就得全部找一遍，而如果是按照空闲分区的大小排的，那就只需要从小往大找到第一个就行了。那这是空闲分区的排序方法不同导致开销不同。
最差匹配就是与最差匹配相反，每次用的时候都是去用最大的空闲分区。如果用最大的，空闲分区按由大到小排序，那么第一个就是该要的分区了。
下面我们会具体来看三种分配策略。
3.3 最先匹配(First Fit Allocation)策略
最先匹配的思路很简单，你要分配多少字节，系统就去空闲分区里找第一个比它大的。比如说图例是按照地址顺序排序的，黄颜色是空闲分区，我想找一个400字节的分区，那么系统上来看之后第一个是1K的空闲分区，它就是比我想要的大，那就是它了。分配完了之后一块(400字节空间)被我们申请的进程所占用，把它放到已分配分区的列表里，并且注明它是被哪个进程所占用的。而这里还剩一点空间，又把它描述成另外一个空闲分区，接着把它放到空闲分区列表里去，这个思路就是这样的。
那么我们再来看它的实现方法。首先，空闲分区列表是按地址顺序排序的。分配的时候从前往后找，找到第一个大于指定大小的空闲分区就可以了。释放的时候，按照地址把分区放回去，并且看它前后是否有临近的空闲分区，那就把它们合并在一起，找和合并的开销都是比较小的。
因为最先匹配每一次都是从头找，这样的话都能在前面找到的时候，它就不会往后找，这样的话另外一个好处是在高地址里会留下一些比较大块的空闲分区。在后续需要申请大块空闲分区的时候都是可以找着的，而如果大块都切成了小块就找不着了。这是它的优点。
它的缺点是会容易产生外部碎片，如果大小不合适容易切成两，这个时候中间就会留下一个小的空闲分区，如果这个小的空闲分区多到一定程度，那么在后面往下分配大块的时候，从前往后找也就相当于前面很长一段找不到合适的分区，由于找不到就只能往后找，那这时候往后找的这个过程开销就会越来越大。也就相当于越往后，在前面搜索的时间就会越长。
3.4 最佳匹配(Best Fit Allocation)策略
最佳匹配也就是说找到一个比它大，并且是最小的空闲分区。还是之前的例子，我要分配400字节，1K，2K，500字节的空闲分区比较起来，500字节是比它大且最小的，那我们在这里分配。分配完后留下一个100字节的空闲分区，另外一个作为已分配的，对它做相应的标识告诉它分配给了哪个进程。
我们来说它需要维护的数据结构是怎么样的。首先第一个，空闲分区怎么来排序？因为是找比指定大小大的最小的一个，找的时候是从小往大找，所以空闲分区列表应按照大小排序。如果列表前边比指定大小要小的分区比较少，那么很快就能找着。分配时就是在按大小排序的空闲分区列表从前往后找。释放时，查找并且合并临近的空闲分区，这里所说的临近是指地址上的，而不是大小。
这种做法它的好处是大部分分配的块的尺度都是比较小的，那么这时候效果就会很好。这样做可以避免大的空闲分区被拆分，因为我们每次找的是比指定大小大的最小的一个，然后它可以减少外碎片的大小，也就是说剩下的一块绝对是最小的那一块。然后相对来说最佳匹配策略也比较简单。
缺点是说剩的那一块边角料是小了，但剩的越小越没法利用，所以它有外碎片，并且它释放分区的时候比较复杂，然后剩下的哪些小碎片基本上也没办法用了。
3.5 最差匹配(Worst Fit Allocation)策略
最差匹配的做法就是找最大的空闲分区来进行分配，之前的例子，要分配400字节，就使用第2个空闲块(2K)来进行分配。分配之后，一块被标记为已分配，剩下的一块空闲分区还有1600字节，还能有很多被利用的机会。
在最差匹配策略中，空闲分区列表按从大到小排序，每次找的时候，若第一个满足要求就是要找的，若第一个不满足要求，就没有比指定大小大的空闲分区了，分配的时候就是找最大的一个，找的速度是最快的。释放的时候，要检查是否有临近的空闲分区可以合并，因为不是按地址排序的，找临近的时候就需要去顺序找了，找着临近的，然后把它合并在一起，放回到空闲分区列表的时候还要去找插入的位置，以保持有序性。
如果说中等尺度的分配比较多时，效果最好。因为用掉的那块分区不是很大，剩的那块多的话还能利用起来，相当于剩的小块就比较少了。
缺点是释放的过程比较慢，因为释放之后合并是需要搜索的，因为空闲分区列表不是按地址排序的，所以只能按顺序遍历列表来找临近的空闲分区。然后最差匹配也会有外部碎片。最差匹配由于每次都是找最大的，所以容易破坏大的空闲分区，如果在后边想分配大的空闲分区的话，可能就变得比较困难了。
这些就是连续存储分配它的几种做法，这几种做法的出发点就是空闲分区的列表按什么来排序，然后我们需要考虑的是在分配的时候它的查找开销和释放的时候它合并的开销，以及把合并完的结果放回到空闲分区列表里的时候找合适位置的开销。
4.碎片整理
碎片整理是想说我们已经把内存分区分配给了进程，它们也已经占定了某一个位置，但是这个时候我正在执行的应用进程，或新创建的应用进程需要内存空间，这时候没有了，或者说空间都剩下在小的碎片里，这个时候怎么办？那我们可以通过碎片整理来获取更大的可用内存空间，以便于满足进程的应用空间需求。
4.1 紧凑(compaction)
碎片整理是指我们通过调整已分配给进程的内存分区的位置来减少碎片的一种做法，那么这种做法有一个图示。图里深蓝色的地方，就是我们的空闲分区，这里最大的空闲分区剩的是三块，但是现在我要分配一个连续四块的空间那就没有了，这个时候怎么办呢？我们把分配给进程的内存分区压缩到一起，然后剩的这块就可以满足要求了。但是要把正在内存当中的这些进程的位置挪动，这事是不可以随便弄的，原因在于进程里可能有各种各样的地址引用，这些引用用的是绝对地址的话，那么挪动后是没办法正确运行的。所以在这里要进行碎片紧凑，它是需要一些条件，也就是所有的进程都可以动态重定位，这样才可以去搬动它们的位置的。当然这种搬动也是有开销的，不可以正在处于运行的时候去搬，通常情况下是对处于等待状态的进程进行搬动。然后并不是说为了一小块区域，就要把整个内存中的很多进程都给它挪一遍，这个开销也是大的。关于具体的做法，在大家需要用到相应的技术的时候再仔细去了解。
4.2 分区对换（Swapping in/out)
刚才我们把内存里的这些分区不管怎么挪，最后的结果它都是在内存里，如果说这时仍然不够用那还是没办法。内存分区对换是指把处于等待状态的进程占用的地址空间给它抢占了，然后把这个等待进程占用的数据存到外存里，在这里就是指对换到对换区，这个时候内存里的空间也就变大了。我们也通过一个图示来看：
在这个图示里，底下是内存和外存的状态，中间这个图实际上说的是系统里进程在执行过程当中我们维护的进程状态信息。
我们看每创建一个进程，创建的时候它要在内存里占一块区域，同时操作系统需要维护的数据结构都建好，然后这个时候它可以投入到运行状态。
(P1)它在运行的过程当中可能会有另外一个进程(P2)要创建，它也需要在内存分配相应的存储区域，然后进到就绪状态，第一个还在运行。
这个过程可以继续进行下去，之后由于某种原因P1处于等待状态，这时P2和P3又进内存里。如果说这种状态下再有一个P4进来，那它要的空间就不够了。
那么P4要进来怎么办呢？我们会把处于等待状态的P1搬到外存里，这样内存空出一块区域来可以把p4放进去，我们就可以让它更多进程在系统里交替运行，使得可用空间能变大。
实际上大家注意的话，在你的linux或者说unix系统里它有一个分区叫对换区，实际上这个对换区在早期的时候它就是一种充分利用内存的做法，那么在这张图里我们可以看到，在早的时候操作系统里只有一个应用进程可以在内存的状态下，它就可以用对换来实现多进程的交替运行。在这是这样的，任何一个时候只有一个进程在内存当中运行，而处于暂停的是把它放到外存里。如果说当前进程主动让出处理机使用权限，这个时候做法是把它(P1)对换到外存当中，再把外存当中这一个(P2)进程搬回去,这个时候就可以继续运行下去了。用这种办法实际上是在比较早的时候内存紧张的情况下，在系统里就可以实现多进程的交替运行。当然这个交替它的开销是非常大的，原因在于内存和外存的速度差得很远。即使是这样，由于计算机系统它的成本非常高，所以这样做的开销也是可以接受的。当然在对换的时候到底把谁对换出来，这时开销有多大，在系统里就得做仔细的权衡，所以要花很大的精力去解决到底是对换哪一个进程。这是在早期的时候计算机系统里的多进程通过对换区的方式来做的一种实现。
5.伙伴系统
伙伴系统是一个连续内存分配的实例，我们在这会分成两部分，一个是对它的基本做法有个介绍，第二个是说在Ucore实验系统里它的伙伴系统是怎么实现的接口。
5.1 伙伴系统(Buddy System)
伙伴系统把整个可以分配的分区大小约定为必须是2的幂，这样做之后，任何一块分区要分的时候只是把它从中间切开，它不会以其他方式来切。如果说在分配的时候，实际上可用的块比你需要大小的2倍还大的话，就把它切一半然后再跟指定的大小作比较。如果说你需要的大小比它的二分之一还大，但没到当前大小的话，它就直接把这块分区给你。具体说起来就是，如果它比你要的2倍还大，那就把它切半，切半后仍然比你2倍大，那就继续切半，一直切到某一个状态，那再切下去你要的就比它大了，而当前状态是比你要的2倍小，那就把这块分给你。那这个时候形成内碎片最大可能会是你要的大小的二分之一减一。也就是你正好需要该空闲块的二分之一的时候系统就可以把空闲块分半，你再多要一个字节系统可能就给了你差不多一倍的大小，而这样就是最大内碎片的情况。
5.2 伙伴系统的实现
首先我们来看伙伴系统中要维护的数据结构。在这里我们空闲块需要维护的是一个二维数组，这个二维数组第一维是空闲块的大小，第一维由小到大排序，而二维是按照空闲块的地址来排序的。然后在起始的时候，整个系统里只有一个空闲块，这是整个空闲内存区域。在分配的时候是由从小到大去找比需要大小更大的空闲块。如果说在初始状态下，找到的只有整个一大块，这个时候就会有第二步，也就是找到之后会判断空闲块大小。如果空闲块过大，也就是需要大小的二倍比给出的这块空闲块还小，那就把它切一半，变成2的u-1次幂，然后继续判断是不是比需要的二倍还大，如果还大就继续分，分成两个空闲块，把它放到空闲块列表里。之后一直到找到需要的大小是空闲块的二分之一还大，但是又没空闲块本身大，就把该块分配掉。接下来我们通过实际的例子来看分配流程。
假定最开始的时候空闲块的大小是1M，然后我们需要的是100K空间，那么1M不断切成一半，切到128K的时候能够满足我们的要求，那么就把128K这块分配给我们。第二个分配请求是240K，256K比240K要大，而且比240K的2倍要小，所以256K的空闲块满足我们的要求，把该块分配掉。第三个分配请求是64K，这时我们看64K比128小，那128的1/2是64正合适，这个时候我们就把它分了。第四个分配请求是256K，那我们在这里空闲的只有512K比它大且满足要求，那就把它分配掉。接下来释放B，按照我们原来连续分区的分配有一个合并的问题，B这块释放之后没法和临近的64K合并，因为合完之后的大小不满足2的整数幂，也没办法放回到空闲分区的数组里。接下来再释放A，把A的128K还回去，它也没有办法和别的空间合并，因为它的临近空间没有空闲分区。接下来申请一个75K空间，75K仍然可以放到128K那。接下来释放C，这个C释放掉时，C是64K，和旁边的64K它们合起来时正好是原来128K（2的整数幂），可以把它们合在一起。接下来再释放E，E和旁边的128K，256K会合并在一起变成512K。最后再释放D，整个1M被合并在一起，过程结束。
接下来我们把合并的事再明确一下。合并的时候满足的条件首先是两空闲块必须大小相同，第二个是地址相邻，第三个是起始地址较小的块的起始地址必须是2^(i+1)的倍数，也就是必须是块大小*2的整数倍。若遇到多个相同大小的相邻空闲块，有了第三个条件之后，像图中的3个256K，释放D后，按第三个条件来看，块大小的2倍为512K，起始地址较小的块必须是512K的整数倍，也就是较小的块应是D本身，所以D应与右边的256K进行合并，这样也是正确地进行了被二等分前的还原（可以看图中的分支）。
有了这三个条件之后，我们的伙伴系统就可以在实际系统当中来进行使用了。目前在我们用到的linux，unix系统都有Buddy System的实现，它是用来做内核里的存储分配。
5.3 ucore中的物理内存管理
在Ucore系统里，把物理内存的管理提供了一个标准的接口，在这个接口里实现了一组函数和相应的一些标准信息。第一个是管理算法的名字(name)，给了一个字符串做标识，然后有一个初始化(void(*init)(void))和一个检查(void(*check)(void))，这个基本上是辅助性的函数。初始化是这个数据结构的起头，检查是包含了数据结构中函数的一些测试。中间我们关心主要的函数是两个，分配(*alloc_pages)和回收(*free_pages)，当然在分配和回收分给一个进程之后，我们在用的时候还得把它映射到进程的地址空间里，所以会有上边的一个函数(*init_memmap)和底下的(*nr_free_pages)函数。(*nr_free_pages)函数是告诉你这个空闲分区里还有多大空间，我们在这里要实现的时候，实际上就实现分配和回收两个函数就行了。
