OSTEP：内存碎片的管理

第十七章：空闲空间管理

1. 执行题目给出的参数可以得到以下内容

   answer

   seed 0
   size 100
   baseAddr 1000
   headerSize 0
   alignment -1
   policy BEST
   listOrder ADDRSORT
   coalesce False
   numOps 10
   range 10
   percentAlloc 50
   allocList
   compute True
   
   ptr[0] = Alloc(3) returned 1000 (searched 1 elements)
   Free List [ Size 1 ]: [ addr:1003 sz:97 ]
   
   Free(ptr[0])
   returned 0
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1003 sz:97 ]
   
   ptr[1] = Alloc(5) returned 1003 (searched 2 elements)
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1008 sz:92 ]
   
   Free(ptr[1])
   returned 0
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:92 ]
   
   ptr[2] = Alloc(8) returned 1008 (searched 3 elements)
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]
   
   Free(ptr[2])
   returned 0
   Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]
   
   ptr[3] = Alloc(8) returned 1008 (searched 4 elements)
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]
   
   Free(ptr[3])
   returned 0
   Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]
   
   ptr[4] = Alloc(2) returned 1000 (searched 4 elements)
   Free List [ Size 4 ]: [ addr:1002 sz:1 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]
   
   ptr[5] = Alloc(7) returned 1008 (searched 4 elements)
   Free List [ Size 4 ]: [ addr:1002 sz:1 ][ addr:1003 sz:5 ][ addr:1015 sz:1 ][ addr:1016 sz:84 ]

   这里以开头两段为例子分析，后面的算法相同

   ptr[0] = Alloc(3) returned 1000 (searched 1 elements)
   Free List [ Size 1 ]: [ addr:1003 sz:97 ]
   
   Free(ptr[0])
   returned 0
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1003 sz:97 ]
   
   ptr[1] = Alloc(5) returned 1003 (searched 2 elements)
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1008 sz:92 ]
   
   Free(ptr[1])
   returned 0
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:92 ]

   首先，根据开头参数可以知道目前分配方式不考虑Header头指针，并且不考虑内存合并

   ptr[0] = Alloc(3)会从1000开始分配大小为3的内存(此时空间足够，分配成功)，并返回1000的地址作为开头。此时空闲空间Free List只有一块，从1003开始，总大小为97

   之后的Free(ptr[0])则将刚刚分配的内存释放，释放后由于并未合并，因此出现了[3]->[97]的空闲空间表，之后再进行ptr[1] = Alloc(5)。由于第一个空闲空间为[3]不足以容纳[5]的分配，因此第二个空间是从1003作为内存开始的地址，并使用了5的内存空间

   然后再进行Free(ptr[1])的操作释放内存并且不合并，则有了[3]->[5]->[92]的空闲可用空间。后面的运算以此类推

   如果出现了在空闲的大内存中分配了新的小内存

   ptr[4] = Alloc(2) returned 1000 (searched 4 elements)
   Free List [ Size 4 ]: [ addr:1002 sz:1 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]

   则占用部分内存后，新的剩余内存将被作为新的内存段保留使用，并且已分配内存也会产生新的内存碎片

2. 使用最差匹配有如下输出

   answer

   seed 0
   size 100
   baseAddr 1000
   headerSize 0
   alignment -1
   policy WORST
   listOrder ADDRSORT
   coalesce False
   numOps 10
   range 10
   percentAlloc 50
   allocList
   compute True
   
   ptr[0] = Alloc(3) returned 1000 (searched 1 elements)
   Free List [ Size 1 ]: [ addr:1003 sz:97 ]
   
   Free(ptr[0])
   returned 0
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1003 sz:97 ]
   
   ptr[1] = Alloc(5) returned 1003 (searched 2 elements)
   Free List [ Size 2 ]: [ addr:1000 sz:3 ][ addr:1008 sz:92 ]
   
   Free(ptr[1])
   returned 0
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:92 ]
   
   ptr[2] = Alloc(8) returned 1008 (searched 3 elements)
   Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]
   
   Free(ptr[2])
   returned 0
   Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]
   
   ptr[3] = Alloc(8) returned 1016 (searched 4 elements)
   Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1024 sz:76 ]
   
   Free(ptr[3])
   returned 0
   Free List [ Size 5 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:8 ][ addr:1024 sz:76 ]
   
   ptr[4] = Alloc(2) returned 1024 (searched 5 elements)
   Free List [ Size 5 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:8 ][ addr:1026 sz:74 ]
   
   ptr[5] = Alloc(7) returned 1026 (searched 5 elements)
   Free List [ Size 5 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:8 ][ addr:1033 sz:67 ]

   比对可以发现，在最差匹配的情况下，第二次重复分配8大小的空间时不会重复利用本身空闲的长度为8的空间，而是依旧从后面的最大空闲空间中分配8大小的空间出来，此时地址从1024开始分配，并且1008开头的地址不会被复用

   Free(ptr[2])
   returned 0
   Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1016 sz:84 ]
   
   --- BEST
   - ptr[3] = Alloc(8) returned 1008 (searched 4 elements)
   - Free List [ Size 3 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1016 sz:84 ]
   
   +++ WORSE
   + ptr[3] = Alloc(8) returned 1016 (searched 4 elements)
   + Free List [ Size 4 ]: [ addr:1000 sz:3 ][ addr:1003 sz:5 ][ addr:1008 sz:8 ][ addr:1024 sz:76 ]

3. 在使用FIRST进行匹配的情况下，空间分配的情况与BEST无异，在本例题示范当中，由于FIRST是找到可以用的内容后直接进行匹配，而示例当中恰好所有可用空间最小的情况匹配了FIRST的情况，因此只有搜索的次数变少，效率变快，其他差异不大。

   + policy FIRST
   ---
   - policy BEST
   
   + ptr[3] = Alloc(8) returned 1008 (searched 3 elements)
   ---
   - ptr[3] = Alloc(8) returned 1008 (searched 4 elements)
   
   + ptr[4] = Alloc(2) returned 1000 (searched 1 elements)
   ---
   - ptr[4] = Alloc(2) returned 1000 (searched 4 elements)
   
   + ptr[5] = Alloc(7) returned 1008 (searched 3 elements)
   ---
   - ptr[5] = Alloc(7) returned 1008 (searched 4 elements)

4. 三种不同的参数分别对应了以下三种不同的内存分配方式

   • ADDSORT: 空闲的地址在搜索的时候是按地址的顺序进行排序搜索
   • SIZESORT-: 空闲的地址在搜索的时候按地址块的大小，先搜索大的，后搜索小的
   • SIZESORT+: 空闲的地址在搜索的时候按地址快的大小，先搜索小的，后搜索大的

   由于BEST和WORSE分配的方法都需要把所有内存段全部搜索后再分配，因此在根据这两种不同的调度之后产生的内存碎片的数量是相同的。在三种不同的调度中采取FIRST控制空闲变量则将会造成比较大的影响。对于SIZESORT-的情况来说，由于未分配的大块内存一直在最前面，因此很容易在反复删除小内存段的过程中不断积累内存碎片；优点是每次直接扫描的第一个就将是可以直接使用的内存，搜索的次数明显减少。采用SIZESORT+的情况下，由于小碎片都积累在前面，因此如果此时遇到比较大块的内存需要分配时，则会增加需要搜索的内存段数量，时间会增加；优点是每次分配的时候都尽量先匹配比较小的内存段，对于多次分配小内存的情况来说，不会那么容易产生浪费。

5. 首先，如果对内存段不采用合并处理的话，随着时间推移，内存碎片将会越来越多，并且后面能够成功分配内存需要的搜索次数以及成功概率都会升高。其次，由于内存合并是在地址连续的基础上才会进行合并，因此如果采用了SIZESORT的分配方法，打乱了地址的顺序，虽然依旧有成功合并的可能，但是效率还是要低于以ADDRSORT方法对空闲内存段进行排序。

6. 如果-P设置的太高，模拟的则是在平时写程序的过程中一直不对申请的内存空间进行Free释放，则会导致空间过早的就被使用完毕，后续无法再继续分配，设置的低的情况下则代表了内存每次使用分配完毕以后都立即释放，这样就能够一直有空闲的内存等待分配。

7. 如果要生成高度碎片化的空间，只要让空闲的空间碎片始终不被合并，并且分配的时候根据上述中第四题得到的规律增加搜索次数，让即使被Free的内存块也无法被使用或增加使用次数即可。