操作系统基础知识
内存分页
参考博客https://www.cnblogs.com/still-smile/p/14900409.html
1、分页
现代操作系统都使用分页机制来管理内存，这使得每个程序都拥有自己的地址空间。每当程序使用虚拟地址进行读写时，都必须转换为实际的物理地址，才能真正在内存条上定位数据。如下图所示：
内存地址的转换是通过一种叫做页表（Page Table）的机制来完成的
2、直接使用数组转换
最容易想到的映射方案是使用数组：每个数组元素保存一个物理地址，而把虚拟地址作为数组下标，这样就能够很容易地完成映射，并且效率不低。如下图所示：
但是这样的数组有 2^32 个元素，每个元素大小为4个字节，总共占用16GB的内存，显然这种方法很不现实。
3、使用一级页表
既然内存是分页的，而数据地址=数据所在页表地址 + 页内偏移，我们只需要知道其中这两项分别是多少，就可以转化为物理地址。例如一个变量保存在第5页，而页内偏移为10，页的大小为2^12，也就是4k，我们便可以计算出页的地址：2^12 * 5 + 10。
虚拟地址空间大小为4GB，总共包含2^32 / 2^12 = 2^20 = 1M个页面。我们可以定义这样一个数组，它包含1M个元素，每个元素大小为4个字节，也就是32位，整个数组总共占用4MB的内存空间，这样的数组称之为页表，它记录了所有页的编号。
虚拟地址的长度为32位，我们将高20位作为页表数组的下标，低12位作为页内偏移，如图所示：
那么为什么要这样切割呢？
因为页表数组总共有2^20也就是1M个元素，使用虚拟地址的高20位作为下标，正好能够访问数组中的所有元素，并且，一个页面的大小为2^12，使用低12位地址正好能表示所有的页内偏移情况。
表示页面标号只需要20位，而页表数组的每个元素长度为32位，多出了12位，而这12位是用来表示当前页相关属性的，例如是否有读写权限和是否被换出到硬盘等。
例如一个虚拟地址 0XA010BA01，它的高20位是 0XA010B，所以需要访问页表数组的第 0XA010B 个元素，才能找到数据所在的物理页面。假设页表数组第 0XA010B 个元素的值为 0X0F70AAA0，它的高20位为 0X0F70A，那么就可以确定数据位于第 0X0F70A 个物理页面。再来看虚拟地址，它的低12位是 0XA01，所以页内偏移也是 0XA01。有了页面索引和页内偏移，就可以算出物理地址了。经过计算，最终的物理地址为 0X0F70A * 2^12 + 0XA01 = 0X0F70A000 + 0XA01 = 0X0F70AA01。
伙伴算法
1、伙伴的定义
伙伴关系的定义为：由一个母实体分成的两个各方面属性一致的两个子实体，这两个子实体就处于伙伴关系。
在操作系统分配内存的过程中，一个内存块经常被分成两个大小相等的内存块，这两个大小相等的内存块就处于伙伴关系。
它满足3个条件：
- 两个块具有相同大小；
- 物理地址是连续的；
- 从同一个大块中拆分出来。
2、伙伴算法的思想
在分配内存的时候将所有的空闲页框分组为若干个链表，每个链表分别存放大小为2^0，2^1，2^2，2^3……2^n个页框的块，且每一块的第一个页框的物理地址是该块大小的整数倍。
伙伴算法每次只能分配2的幂次页的空间，因此，伙伴算法最多一次能够分配2^n个页大小的内存空间。而每页是否被分配的状态则由位图记录，若该页被分配了，位图上的相应二进制位则置1，否则为0。如图所示：
3、申请空间
在分配内存时，首先从空闲的内存中搜索比申请的内存大的最小内存块，如果这样的内存块存在，则将这块内存分配给应用程序，并将其对应的页在位图中置1。如果找不到，则向上寻找更大块的空闲内存（一般是乘以2），如果找到了更大的空闲内存，则先判断该申请的内存是否超过了空闲内存的一半，若超过，则将整块空闲内存分配给应用程序，否则该空闲内存对半分成两块，其中一块作为空闲内存块放回相应链表中，另一块继续判断该申请的内存是否超过了空闲内存的一半，重复上述操作，直到找到合适的可分配内存为止。分配内存示意图如图所示：
4、释放空间
在释放空间时，首先创建相应的空闲内存块，然后查询是否有互为伙伴的内存块，若无则直接将其放回相应链表中，若有则将两块内存块合并为一个大的内存块，继续查询该更大的内存块是否有互为伙伴的内存块，重复上述操作，直到无法再次合并为止。释放内存示意图如图所示：
