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

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

admin2016-05-14  73
问题 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)