（备战招聘）操作系统之物理内存管理
大家好，今天来讲讲物理内存管理的一些方案。
首先给大家一个空闲的内存空间图
如该图所示，由常理我们知道，划分方式分为两类：一类是等长划分，一类是不等长划分，我们需要一种数据结构来记录空闲内存的使用状况，来提供给进程。
对于等长划分，我们常常采用位图来表示使用情况，对每个分配的区块对应于位图中的一位，用0表示空闲、1表示占用（或者相反）
对于不等长划分，显然数据结构会复杂一些，这时我们常常使用空闲区表或者已分配区表来表示使用情况，表中每一项记录了空闲区（或已分配区）的起始地址、长度、标志。
那么当进程进入内存中，知道了哪些区域是空闲可用的，又该如何分配呢？这个时候就需要内存分配算法了，内存分配算法主要有以下四种：
1、首次适配 first fit
在空闲表中找到第一个满足进程要求的空闲区
2、下次适配 next fit
从上次找到的空闲区处接着查找
3、最佳适配 best fit
查找整个空闲区表，找到能够满足进程要求的最小空闲区
4、最差适配 worst fit
总是分配满足进程要求的最大空闲区
实际上，找到一个空闲区后，一般会将空闲区再次分为两部分，一部分供进程使用，一部分作为新的空闲区。
如下图所示，可以直观的理解空闲区表的概念
物理内存的管理不仅仅是空闲区的分配，当进程使用完内存某些区域的时候，还需要将相应区域释放还给内存为空闲区，所以需要引入内存回收算法。
内存回收算法负责当某一块内存空间归还时，合并前后的空闲空间，并且修改相关的空闲区表。根据释放内存区块与其他区块的相对位置，回收算法会面临四种情况：回收区块上方有相邻空闲区块、回收区块下方有相邻空闲区块、回收区块上下都有空闲区块、回收区块与上下空闲区块都不相邻。
下面我们来介绍一下Linux操作系统中一种经典的内存分配方案及回收策略，简称为伙伴系统。
该算法的原理是将内存按2的幂次方进行划分，组成若干空闲块链表；查找该链表找到能满足进程需求的最佳匹配块
算法：
1、将整个可用空间看做一块：
2、假设进程申请空间的大小为s，如果满足
，则将整个块分配给该内存，否则将块划分为两个大小相等的伙伴，大小为
3、一直划分下去直到产生大于或等于s的最小块
下面举一个相关的例子
假如现在系统可用的空间为1M
进程A申请100K的空间，然后根据伙伴算法，空间被分为四块，2个128K、1个256K、一个512K，将首个128K分配给A
然后进程B申请240K空间，这时将四个空闲块中的256K块分配给B
然后进程C申请64K的空间，这时将第2个128K又分为两个64K区块，将第一个64K区块分配给C。
释放机制同样参考该算法，如果释放后该区块有相邻的伙伴区块（大小相同），则合并为一个更大的区块。