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