OSTEP Chapter 17 回顾
这里回顾第17章，本章介绍了空闲空间管理。
书籍介绍：
学习资料：
- https://pages.cs.wisc.edu/~remzi/OSTEP/
- https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/chinese
- https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES
第17 章 空闲空间管理
内容回顾
管理空闲空间的数据结构被称为空闲列表（free list）
两种碎片
- 外部碎片：物理内存充满了许多空闲空间的小洞，因而很难分配给新的段，或扩大已有的段。
- 内部碎片：分配程序给出的内存块超出请求的大小，在这种块中超出请求的空间（因此而未使用）就被认为是内部碎片。
底层机制：
分割与合并
追踪已分配空间的大小
使用头块
typedef struct header_t { int size; int magic; } header_t;当请求大小为$N$字节的内存，库实际上寻找的是$N$加头块大小的空闲块
嵌入空闲列表
typedef struct node_t { int size; struct node_t *next; } node_t; // mmap() returns a pointer to a chunk of free space node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); head->size = 4096 - sizeof(node_t); head->next = NULL;让堆增长
基本策略
- 最优匹配（best fit）
- 最差匹配（worst fit）
- 首次匹配（first fit）：找到第一个足够大的块
- 下次匹配（next fit）：从上次查找结束的位置开始
改进内存分配的方法
- 分离空闲列表（segregated list）：
- 如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象；其他大小的请求都给更通用的内存分配程序。
- 内核启动时，为可能频繁请求的内核对象创建一些对象缓存（objectcache）。
- 这些的对象缓存每个分离了特定大小的空闲列表。
- 如果某个缓存中的空闲空间快耗尽时，就向通用内存分配程序申请一些内存厚块（slab）（总量是页大小和对象大小的公倍数。
- 如果给定厚块中对象的引用计数变为0，通用的内存分配程序可以从专门的分配程序中回收这些空间。
- 如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，只管理这样大小的对象；其他大小的请求都给更通用的内存分配程序。
- 二分伙伴分配程序（binary buddy allocator）
- 空闲空间首先从概念上被看成大小为$2^N$的大空间。
- 当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再一分为二就无法满足）。
- 块被释放时，利用递归进行释放。
- 很容易确定某个块的伙伴。
- 分离空闲列表（segregated list）：
作业
1
λ python ./malloc.py flag -n 10 -H 0 -p BEST -s 0
seed 0
size 100
baseAddr 1000
headerSize 0
alignment -1
policy BEST
listOrder ADDRSORT
coalesce False
numOps 10
range 10
percentAlloc 50
allocList
compute False
ptr[0] = Alloc(3) returned ?
List?
Free(ptr[0])
returned ?
List?
ptr[1] = Alloc(5) returned ?
List?
Free(ptr[1])
returned ?
List?
ptr[2] = Alloc(8) returned ?
List?
Free(ptr[2])
returned ?
List?
ptr[3] = Alloc(8) returned ?
List?
Free(ptr[3])
returned ?
List?
ptr[4] = Alloc(2) returned ?
List?
ptr[5] = Alloc(7) returned ?
List? 计算：
ptr[0] = Alloc(3) returned 1000
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
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
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
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
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 1004
Free List [ Size 4 ]: [ addr:1002 sz:1 ] [ addr:1003 sz:5 ] [ addr:1015 sz:1 ][ addr:1016 sz:84 ] 答案：
λ python ./malloc.py flag -n 10 -H 0 -p BEST -s 0 -c
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 ]2
计算：
ptr[0] = Alloc(3) returned 1000
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
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
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
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
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
Free List [ Size 4 ]: [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:8 ] [ addr:1033 sz:67 ] 答案：
λ python ./malloc.py flag -n 10 -H 0 -p WORST -s 0 -c
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 ]3
在该场景下没有变化。
4
略过，直接实验即可。
5
python ./malloc.py flag -n 1000 -H 0 -p BEST -s 0 -C -c
python ./malloc.py flag -n 1000 -H 0 -p BEST -s 0 -c采用-C几乎没有碎片，但是用-c很多碎片。
6
python ./malloc.py flag -n 1000 -H 0 -p BEST -P 70 -s 0 -c经常失败。
python ./malloc.py flag -n 1000 -H 0 -p BEST -P 99 -s 0 -c很容易失败。
python ./malloc.py flag -n 1000 -H 0 -p BEST -P 1 -s 0 -c分配基本都成功。
7
python ./malloc.py flag -A "+50,-0,+25,+12,+6,-0,-1,-2" -H 0 -p BEST -s 0 -c先申请大的，然后释放，接着申请小的，不使用合并。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere