Linux教程

操作系统笔记(3)

本文主要是介绍操作系统笔记(3),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

伙伴系统

固定分区和动态分区方案都是存在缺陷。

固定分区方案限制了活动进程的数量,并且若可用分区的大小与进程大小很不匹配,则内存空间的利用率就会非常低。
动态分区的维护非常复杂,并且会引入进行压缩的额外开销。

由此,就像是对于查看和修改复杂度这种一般,这种情况下也出现了一种很具有吸引力的这种方案:伙伴系统

伙伴系统中可用内存块的大小为\(2^K\)个字,L≤K≤U,其中\(2^L\)表示分配的最小块的尺寸,\(2^U\)表示分配的最大块的尺寸,\(2^U\)表示可供分配的整个内存的大小

而分配的流程如下:

最初,整个可供分配的空间被视为一个大小为\(2^U\)的块。若请求的大小s满足\(2^{U-1}\)<s≤\(2^U\),那么整个空间将都会被分配。
否则的话,这个块分裂为两个大小相等伙伴,大小均为\(2^{U-1}\)。如果存在\(2^{U-2}\)<s≤\(2^{U-1}\),则给请求分配两个伙伴中的一个;
否则,其中的一个伙伴又被分成两半。
持续这一过程,直到产生≥s的最小块,并分配给该请求。
在任何时候,伙伴系统中为所有大小为\(2^i\)的“空洞”维护一个列表。空洞可通过对半分裂从i+1列表中移除,并在i列表中产生两个大小为\(2^i\)的伙伴
当i列表中一对伙伴都变成未分裂的块时,将它们从i列表中移除,合并为i+1的列表中的一个块。

请求大小为k的块,并且k满足\(2^{i-1}\)<k≤\(2^i\),下面是一个寻找大小为\(2^i\)空间的算法例子

void get_hole(int i)
{
  if(i==(U+1)) <failure>;
  if(<i_list empty>)
  {
    get_hole(i+1);
    <split hole into buddies>;
    <put buddies on i_list>;
  }
  <take first hole on i_list>;
}
这篇关于操作系统笔记(3)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!