Linux的页面分配为何采用链表与位图相结合的方法?这两种结构对于分配和释放各起什么作用?

admin2016-05-14  27

问题 Linux的页面分配为何采用链表与位图相结合的方法?这两种结构对于分配和释放各起什么作用?

选项

答案Linux的页面分配时采用链表与位图相结合的方法。在分配内存时,根据申请内存的大小在free_area[i]所管理的大小为2i的内存块的链表中分配,这样只需要O(1)的执行时间就能完成分配。当然还要在对应的位图中进行标注,这也仅需要O(1)的执行时间。 在释放内存块时,在相应的位图中进行标注,并判断是否其伙伴也是空闲的,如空闲,则加以合并,一般也只需O(1)的执行时间。但如递归地影响上一级管理更大内存块的位图,要递归地在上一级位图上进行标注和合并,在位图上递归地标注和合并时,最坏情况时间复杂度为O(log2N),即ree_area中的表项数。同样这也需要在相应的链表中进行处理,需要执行插入一个空闲节点操作的时间复杂度为O(1),但当需要合并时的时间复杂度正比于有关链表的长度。 只有在位图中需要合并时才在链表中进行合并这种操作,如果单采用链表的管理方案,不管最终需要或不需要合并,每次都要在有关的链表中进行查找和判断,就需占用较多的执行时间。 所以总地来说,链表主要是为了提高分配速度的,而位图是为了提高释放和合并内存的效率的。

解析
转载请注明原文地址:https://kaotiyun.com/show/kONx777K
本试题收录于: 操作系统题库理工类分类
0

最新回复(0)