OSTEP:内存碎片的管理
第十七章:空闲空间管理
执行题目给出的参数可以得到以下内容
answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47seed 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 ]这里以开头两段为例子分析,后面的算法相同
1
2
3
4
5
6
7
8
9
10
11
12
13ptr[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]
的空闲可用空间。后面的运算以此类推如果出现了在空闲的大内存中分配了新的小内存
1
2ptr[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 ]则占用部分内存后,新的剩余内存将被作为新的内存段保留使用,并且已分配内存也会产生新的内存碎片
使用最差匹配有如下输出
answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47seed 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
开头的地址不会被复用1
2
3
4
5
6
7
8
9
10
11Free(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 ]在使用
FIRST
进行匹配的情况下,空间分配的情况与BEST
无异,在本例题示范当中,由于FIRST
是找到可以用的内容后直接进行匹配,而示例当中恰好所有可用空间最小的情况匹配了FIRST
的情况,因此只有搜索的次数变少,效率变快,其他差异不大。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15+ 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)三种不同的参数分别对应了以下三种不同的内存分配方式
ADDSORT
: 空闲的地址在搜索的时候是按地址的顺序进行排序搜索SIZESORT-
: 空闲的地址在搜索的时候按地址块的大小,先搜索大的,后搜索小的SIZESORT+
: 空闲的地址在搜索的时候按地址快的大小,先搜索小的,后搜索大的
由于
BEST
和WORSE
分配的方法都需要把所有内存段全部搜索后再分配,因此在根据这两种不同的调度之后产生的内存碎片的数量是相同的。在三种不同的调度中采取FIRST
控制空闲变量则将会造成比较大的影响。对于SIZESORT-
的情况来说,由于未分配的大块内存一直在最前面,因此很容易在反复删除小内存段的过程中不断积累内存碎片;优点是每次直接扫描的第一个就将是可以直接使用的内存,搜索的次数明显减少。采用SIZESORT+
的情况下,由于小碎片都积累在前面,因此如果此时遇到比较大块的内存需要分配时,则会增加需要搜索的内存段数量,时间会增加;优点是每次分配的时候都尽量先匹配比较小的内存段,对于多次分配小内存的情况来说,不会那么容易产生浪费。首先,如果对内存段不采用合并处理的话,随着时间推移,内存碎片将会越来越多,并且后面能够成功分配内存需要的搜索次数以及成功概率都会升高。其次,由于内存合并是在地址连续的基础上才会进行合并,因此如果采用了
SIZESORT
的分配方法,打乱了地址的顺序,虽然依旧有成功合并的可能,但是效率还是要低于以ADDRSORT
方法对空闲内存段进行排序。如果
-P
设置的太高,模拟的则是在平时写程序的过程中一直不对申请的内存空间进行Free
释放,则会导致空间过早的就被使用完毕,后续无法再继续分配,设置的低的情况下则代表了内存每次使用分配完毕以后都立即释放,这样就能够一直有空闲的内存等待分配。如果要生成高度碎片化的空间,只要让空闲的空间碎片始终不被合并,并且分配的时候根据上述中第四题得到的规律增加搜索次数,让即使被
Free
的内存块也无法被使用或增加使用次数即可。