操作系统导论-空闲空间管理

第十七章:空闲空间管理

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

    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
    47
    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 ]

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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]的空闲可用空间。后面的运算以此类推

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

    1
    2
    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
    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
    47
    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开头的地址不会被复用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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的情况,因此只有搜索的次数变少,效率变快,其他差异不大。

    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)
  4. 三种不同的参数分别对应了以下三种不同的内存分配方式

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

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

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

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

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


操作系统导论-空闲空间管理
https://halc.top/p/3d85131
作者
HalcyonAzure
发布于
2022年5月7日
许可协议