怎样看网站是谁做的,网站备案网站要有内容吗,工商网站查询个人信息,网站建设定制通常情况下#xff0c;一个高级操作系统必须要给进程提供基本的、能够在任意时刻申请和释放任意大小内存的功能#xff0c;就像malloc 函数那样#xff0c;然而#xff0c;实现malloc 函数并不简单#xff0c;由于进程申请内存的大小是任意的#xff0c;如果操作系统对ma…通常情况下一个高级操作系统必须要给进程提供基本的、能够在任意时刻申请和释放任意大小内存的功能就像malloc 函数那样然而实现malloc 函数并不简单由于进程申请内存的大小是任意的如果操作系统对malloc 函数的实现方法不对将直接导致一个不可避免的问题那就是内存碎片。
内存碎片就是内存被分割成很小很小的一些块这些块虽然是空闲的但是却小到无法使用。随着申请和释放次数的增加内存将变得越来越不连续。最后整个内存将只剩下碎片即使有足够的空闲页框可以满足请求但要分配一个大块的连续页框就可能无法满足所以减少内存浪费的核心就是尽量避免产生内存碎片。
针对这样的问题有很多行之有效的解决方法其中伙伴算法被证明是非常行之有效的一套内存管理方法因此也被相当多的操作系统所采用。
伙伴算法简而言之就是将内存分成若干块然后尽可能以最适合的方式满足程序内存需求的一种内存管理算法伙伴算法的一大优势是它能够完全避免外部碎片的产生。什么是外部碎片以及内部碎片前面博文slab分配器后面已有介绍。申请时伙伴算法会给程序分配一个较大的内存空间即保证所有大块内存都能得到满足。很明显分配比需求还大的内存空间会产生内部碎片。所以伙伴算法虽然能够完全避免外部碎片的产生但这恰恰是以产生内部碎片为代价的。
Linux 便是采用这著名的伙伴系统算法来解决外部碎片的问题。把所有的空闲页框分组为 11 块链表每一块链表分别包含大小为1248163264128256512 和 1024 个连续的页框。对1024 个页框的最大请求对应着 4MB 大小的连续RAM 块。每一块的第一个页框的物理地址是该块大小的整数倍。例如大小为 16个页框的块其起始地址是 16 * 2^12 2^12 4096这是一个常规页的大小的倍数。
下面通过一个简单的例子来说明该算法的工作原理
假设要请求一个256129~256个页框的块。算法先在256个页框的链表中检查是否有一个空闲块。如果没有这样的块算法会查找下一个更大的页块也就是在512个页框的链表中找一个空闲块。如果存在这样的块内核就把512的页框分成两等分一般用作满足需求另一半则插入到256个页框的链表中。如果在512个页框的块链表中也没找到空闲块就继续找更大的块——1024个页框的块。如果这样的块存在内核就把1024个页框块的256个页框用作请求然后剩余的768个页框中拿512个插入到512个页框的链表中再把最后的256个插入到256个页框的链表中。如果1024个页框的链表还是空的算法就放弃并发出错误信号。
简而言之就是在分配内存时首先从空闲的内存中搜索比申请的内存大的最小的内存块。如果这样的内存块存在则将这块内存标记为“已用”同时将该内存分配给应用程序。如果这样的内存不存在则操作系统将寻找更大块的空闲内存然后将这块内存平分成两部分一部分返回给程序使用另一部分作为空闲的内存块等待下一次被分配。
以上过程的逆过程就是页框块的释放过程也是该算法名字的由来。内核试图把大小为 b 的一对空闲伙伴块合并为一个大小为 2b 的单独块。满足以下条件的两个块称为伙伴 两个块具有相同的大小记作 b它们的物理地址是连续的第一块的第一个页框的物理地址是 2 * b * 2^12 的倍数该算法是迭代的如果它成功合并所释放的块它会试图合并 2b 的块以再次试图形成更大的块。 下面通过一个例子来深入地理解一下伙伴算法的真正内涵下面这个例子并不严格表示Linux 内核中的实现是阐述伙伴算法的实现思想
假设系统中有 1MB 大小的内存需要动态管理按照伙伴算法的要求需要将这1M大小的内存进行划分。这里我们将这1M的内存分为 64K、64K、128K、256K、和512K 共五个部分如下图 a 所示 1.此时如果有一个程序A想要申请一块45K大小的内存则系统会将第一块64K的内存块分配给该程序产生内部碎片为代价如图b所示
2.然后程序B向系统申请一块68K大小的内存系统会将128K内存分配给该程序如图c所示
3.接下来程序C要申请一块大小为35K的内存。系统将空闲的64K内存分配给该程序如图d所示
4.之后程序D需要一块大小为90K的内存。当程序提出申请时系统本该分配给程序D一块128K大小的内存但此时内存中已经没有空闲的128K内存块了于是根据伙伴算法的原理系统会将256K大小的内存块平分将其中一块分配给程序D另一块作为空闲内存块保留等待以后使用如图e所示
5.紧接着程序C释放了它申请的64K内存。在内存释放的同时系统还负责检查与之相邻并且同样大小的内存是否也空闲由于此时程序A并没有释放它的内存所以系统只会将程序C的64K内存回收如图f所示
6.然后程序A也释放掉由它申请的64K内存系统随机发现与之相邻且大小相同的一段内存块恰好也处于空闲状态。于是将两者合并成128K内存如图g所示
7.之后程序B释放掉它的128k系统也将这块内存与相邻的128K内存合并成256K的空闲内存如图h所示
8.最后程序D也释放掉它的内存经过三次合并后系统得到了一块1024K的完整内存如图i所示。
https://blog.csdn.net/wenqian1991/article/details/27968779
