伙伴算法

‘壹’ linux内核物理内存管理有哪些常用算法 lru slab

采用伙伴算法分配内存时，每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理？如何在一个页面中分配小的内存区，小内存区的分配所产生的内碎片又如何解决？
Linux2.0采用的解决办法是建立了13个空闲区链表，它们的大小从32字节到132056字节。从Linux2.2开始，MM的开发者采用了一种叫做slab的分配模式，该模式早在1994年就被开发出来，用于Sun Microsystem Solaris 2.4操作系统中。Slab的提出主要是基于以下考虑：
· 内核对内存区的分配取决于所存放数据的类型。例如，当给用户态进程分配页面时，内核调用get_free_page()函数，并用0填充这个页面。 而给内核的数据结构分配页面时，事情没有这么简单，例如，要对数据结构所在的内存进行初始化、在不用时要收回它们所占用的内存。因此，Slab中引入了对象这个概念，所谓对象就是存放一组数据结构的内存区，其方法就是构造或析构函数，构造函数用于初始化数据结构所在的内存区，而析构函数收回相应的内存区。但为了便于理解，你也可以把对象直接看作内核的数据结构。为了避免重复初始化对象，Slab分配模式并不丢弃已分配的对象，而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时，就可以从内存获取而不用进行初始化，这是在Solaris 中引入Slab的基本思想。
实际上，Linux中对Slab分配模式有所改进，它对内存区的处理并不需要进行初始化或回收。出于效率的考虑，Linux并不调用对象的构造或析构函数，而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。
· 实际上，内核经常反复使用某一内存区。例如，只要内核创建一个新的进程，就要为该进程相关的数据结构（task_struct、打开文件对象等）分配内存区。当进程结束时，收回这些内存区。因为进程的创建和撤销非常频繁，因此，Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始，把那些频繁使用的页面保存在高速缓存中并重新使用。
· 可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区，可以创建一组特定大小的专用缓冲区进行处理，以避免内碎片的产生。对于较少使用的内存区，可以创建一组通用缓冲区（如Linux2.0中所使用的2的幂次方）来处理，即使这种处理模式产生碎片，也对整个系统的性能影响不大。
· 硬件高速缓存的使用，又为尽量减少对伙伴算法的调用提供了另一个理由，因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存，因此，这就增加了对内存的平均访问次数。
Slab分配模式把对象分组放进缓冲区（尽管英文中使用了Cache这个词，但实际上指的是内存中的区域，而不是指硬件高速缓存）。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关，因此，Slab缓冲区并非由各个对象直接构成，而是由一连串的“大块（Slab）”构成，而每个大块中则包含了若干个同种类型的对象，这些对象或已被分配，或空闲，如图6.12所示。一般而言，对象分两种，一种是大对象，一种是小对象。所谓小对象，是指在一个页面中可以容纳下好几个对象的那种。例如，一个inode结构大约占300多个字节，因此，一个页面中可以容纳8个以上的inode结构，因此，inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。

‘贰’ 基于伙伴堆算法的内存分配/释放的模拟实现

伙伴算法把所有的空闲页面分为10个块组，每组中块的大小是2的幂次方个页面，例如，第0组中块的大小都为20 （1个页面），第1组中块的大小为都为21（2个页面），第9组中块的大小都为29（512个页面）。也就是说，每一组中块的大小是相同的，且这同样大小的块形成一个链表。

我们通过一个简单的例子来说明该算法的工作原理。

假设要求分配的块其大小为128个页面（由多个页面组成的块我们就叫做页面块）。该算法先在块大小为128个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小为256个页面的链表中查找一个空闲块。如果存在这样的空闲块，内核就把这256个页面分为两等份，一份分配出去，另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页块，就继续找更大的块，即512个页面的块。如果存在这样的块，内核就从512个页面的块中分出128个页面满足请求，然后从384个页面中取出256个页面插入到块大小为256个页面的链表中。然后把剩余的128个页面插入到块大小为128个页面的链表中。如果512个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。

‘叁’ 简述内存管理中buddy算法和slab机制的区别

1、Buddy算法
linux对空闲内存空间管理采取buddy算法，
Buddy算法：
把内存中所有页面按照2^n划分，其中n=0~5，每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成了大小不等的存储块，称为页面块，简称页块，包含一个页面的页块称为1页块，包含2个页面的称为2页块，依次类推。
每种页块按前后顺序两两结合成一对Buddy“伙伴”。系统按照Buddy关系把具有相同大小的空闲页面块组成页块组，即1页块组、2页块组……32页块组。 每个页块组用一个双向循环链表进行管理，共有6个链表，分别为1、2、4、8、16、32页块链表。分别挂到free_area[] 数组上。
位图数组
用于标记内存页面使用情况，第0组每一位表示单个页面使用情况，1表示使用，0表示空闲，第二组每一位表示比邻的两个页面使用情况，一次类推。默认为10个数组，当一对Buddy的两个页面中有一个事空闲的，而另一个全部或部分被占用时，该位置1.两个页面块都是空闲，对应位置0.
内存分配和释放过程
内存分配时，系统按照Buddy算法，根据请求的页面数在free_area[]对应的空闲页块组中搜索。 若请求页面数不是2的整数次幂，则按照稍大于请求数的2的整数次幂的值搜索相应的页面块组。
当相应页块组中没有可使用的空闲页面块时就查询更大一些的页块组，在找到可用的页块后分配所需要的页面。当某一空闲页面被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把他们加入到相应页面组中。
内存页面释放时，系统将其作为空闲页面看待，检查是否存在与这些页面相邻的其他空闲页块，若存在，则合为一个连续的空闲区按Buddy算法重新分组。

2、Slab算法
采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，不适合小内存区请求。如：几十个或者几百个字节。Linux2.0采用传统内存分区算法，按几何分布提供内存区大小，内存区以2的幂次方为单位。虽然减少了内碎片，但没有显着提高系统效率。
Linux2.4采用了slab分配器算法，该算法比传统的分配器算法有更好性能和内存利用率，最早在solaris2.4上使用。
Slab分配器思想
1）小对象的申请和释放通过slab分配器来管理。
2）slab分配器有一组高速缓存，每个高速缓存保存同一种对象类型，如i节点缓存、PCB缓存等。
3）内核从它们各自的缓存种分配和释放对象。
4）每种对象的缓存区由一连串slab构成，每个slab由一个或者多个连续的物理页面组成。这些页面种包含了已分配的缓存对象，也包含了空闲对象。

‘肆’ C#中buddy是什么意思

buddy算法是用来做内存管理的经典算法，目的是为了解决内存的外碎片。

‘伍’ buddy算法到底是10个链表还是11个链表

还是11个链表

‘陆’ BUDDY算法的C++实现

简介
http://www.csie.nctu.e.tw/~tcwu/doc/Linux/Kernel/chapter3/chapter3.htm
source
http://blog.csdn.net/VIV777/archive/2007/07/05/1680363.aspx
基本上用
Linux kernel memory management buddy system
或
MIPS memory management buddy system
作为关键字去搜寻就可以找到很多讯息

‘柒’ 操作系统一般对用户空间采用分页管理而对内核对象采用 slab 分配器，为什么

采用伙伴算法分配内存时，每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理？如何在一个页面中分配小的内存区，小内存区的分配所产生的内碎片又如何解决？ Linux2.0采用的解决办法是建立了13个空闲区链表，...

‘捌’ 操作系统对外存的管理能使用伙伴算法吗

一、单项选择题(每题1分，共20分) 1.操作系统的发展过程是( C ) C、管理程序，原始操作系统，操作系统 2.用户程序中的输入、输出操作实际上是由(B、操作系统 )完成。 3.进程调度的对象和任务分别是( C )。 C、进程，从就绪队列中按一定的调度策略选择一个进程占用CPU 4.支持程序浮动的地址转换机制是( A、动态重定位 ) 5.在可变分区存储管理中，最优适应分配算法要求对空闲区表项按(C、尺寸从小到大)进行排列。 6.设计批处理多道系统时，首先要考虑的是( 系统效率和吞吐量 )。 7.当进程因时间片用完而让出处理机时，该进程应转变为( b )状态。 A、等待 B、就绪 C、运行 D、完成 8.文件的保密是指防止文件被( c )。 A、篡改 B、破坏 C、窃取 D、删除 9.若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区是由( d ) 临界区构成。 A、2个 B、3个 C、4个 D、5个 10.按逻辑结构划分，文件主要有两类：(记录式文件 )和流式文件。 A、记录式文件 B、网状文件 C、索引文件 D、流式文件 11.UNIX中的文件系统采用(、流式文件 )。 A、网状文件 B、记录式文件 C、索引文件 D、流式文件 12.文件系统的主要目的是(A、实现对文件的按名存取 )。 13.文件系统中用( D、目录 )管理文件。 14.为了允许不同用户的文件具有相同的文件名，通常在文件系统中采用(B、多级目 录 )。 15.在多进程的并发系统中，肯定不会因竞争(C、CPU )而产生死锁。 16.一种既有利于短小作业又兼顾到长作业的作业调度算法是( C、最高响应比优先 )。17.两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消息，或 者建立某个条件后再向前执行，这种制约性合作关系被称为进程的( B、同步 )。18.当每类资源只有一个个体时，下列说法中不正确的是( )。 A、有环必死锁 B、死锁必有环 C、有环不一定死锁 D、被锁者一定全在环中 19.数据文件存放在到存储介质上时，采用的逻辑组织形式是与(A、文件逻辑结构 ) 有关的。 20.在单处理器的多进程系统中，进程什么时候占用处理器和能占用多长时间，取决于(B、进程自身和进程调度策略 )。 二、填空题(每空2分，共20分) 1.若信号量S的初值定义为10，则在S上调用了16次P操作和15次V操作后S的值应 该为( 9 )。 2.进程调度的方式通常有(抢占 )和(非抢占)两种方式。 3.每个索引文件都必须有一张( 索引结点 )表，其中的地址登记项用来指出文件在外存 上的位置信息。 4.在一请求分页系统中，假如一个作业的页面走向为：4、3、2、1、4、3、5、4、3、2、1、 5，当分配给该作业的物理块数为4时(开始时没有装入页面)，采用LRU页面淘汰算法将产生( 8 )次缺页中断。 5.信号量被广泛用于三个目的是( 同步 )、( 互斥 )和描述前趋关系。 6.程序并发执行时的特征是( 间断性 )、( 失去了封闭性 )、( 不可再现性 )和独立性。 三、判断题(每题1分，共10分) ( T )1.文件系统中分配存储空间的基本单位不是记录。 ( F )2.具有多道功能的操作系统一定是多用户操作系统。 ( T )3.虚拟存储器是由操作系统提供的一个假想的特大存储器，它并不是实际的内存，其大小可比内存空间大得多。 ( T )4.批处理系统的(主要优点)是系统的吞吐量大、资源利用率高、系统的开销较小。 ( F )5.文件系统中源程序是有结构的记录式文件。 ( F )6.即使在多道程序环境下，普通用户也能设计用内存物理地址直接访问内存的程序。 ( F )7.顺序文件适合建立在顺序存储设备上，而不适合建立在磁盘上。 ( T )8.SPOOLing系统实现设备管理的虚拟技术，即：将独占设备改造为共享设备。它由专门负责I/O的常驻内存进程以及输入、输出井组成。 ( F )9.系统调用是操作系统与外界程序之间的接口，它属于核心程序。在层次结构设计中，它最靠近硬件。 ( F )10.若系统中存在一个循环等待的进程集合，则必定会死锁。 四、程序与算法(共10分) 设有一缓冲池P，P中含有20个可用缓冲区，一个输入进程将外部数据读入P，另有一 个输出进程将P中数据取出并输出。若讲程每次操作均以一个缓冲区为单位，试用记录型信号量写出两个进程的同步算法,要求写出信号量的初值。 解： semaphore mutex=1; semaphore empty=20; semaphore full=0; int in,out = 0; item p [20]; void Procer(){ while(ture){ procer an item in nextp; wait(empty); wait(mutex); p[in] := nextp; in := (in+1) mod 20; signal(mutex); signal(full); } } void Consumer(){ while(ture){ wait(full); wait(mutex); nextc := p[out]; out := (out+1) mod 20; signal(mutex); signal(empty); } } 五、问答题(共16分) 某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。系统对这四类资源的拥有量为:A类3个、B类14个、C类12个、D类12个。进程对资源的需求和分配 情况如下： 按银行家算法回答下列问题： (1)现在系统中的各类资源还剩余多少?(4分) (2)现在系统是否处于安全状态?为什么?(6分) (3)如果现在进程P2提出需要A类资源0个、B类资源4个、C类资源2个和D类资源0个，系统能否去满足它的请求?请说明原因。(6) (1)A：1;B：5;C：2;D：0 (2)need矩阵为：P1 0 0 0 0 P2 0 7 5 0 P3 1 0 0 2 P4 0 0 2 0 P5 0 6 4 2 存在安全序列，如P1，P3 ，P4，P5，P2，所以安全 (3)能，因为试探分配后，可用资源为1，1，0，0。可找到安全序列，所以可分配。六、计算题(第1题6分;第2题10分;第3题8分;共24分) 1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下： 则逻辑地址0A5D(H)所对应的物理地址是什么?(6分) 0A5D(H)=0000 1010 0101 1101 2号页对应4号块，所以物理地址是0001 0010 0101 1101 即125D(H)。 2、设有三道作业，它们的提交时间及执行时间由下表给出: 作业号 提交时间 执行时间 1 8.5 2.0 2 9.2 1.6 3 9.4 0.5 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间 (时间单位:小时，以十进制进行计算;要求写出计算过程)(10分) FCFS: 作业号 提交时间 执行时间 开始时间 完成时间 周转时间 1 8.5 2.0 8.5 10.5 2.0 2 9.2 1.6 10.5 12.1 2.9 3 9.4 0.5 12.1 12.6 3.2 平均周转时间=(2.0+2.9+3.2)/3=2.7(小时) SJF: 作业号 提交时间 执行时间 开始时间 完成时间 周转时间 1 8.5 2.0 8.5 10.5 2.0 2 9.2 1.6 11.0 12.6 3.4 3 9.4 0.5 10.5 11.0 1.6 平均周转时间=(2.0+3.4+1.6)/3=2.3(小时) 3、假定当前磁头位于100号磁道，进程对磁道的请求序列依次为55，58，39，18，90，160，150，38，180。当采用先来先服务和最短寻道时间优先算法时，总的移动的磁道数分别是多少?(请给出寻道次序和每步移动磁道数)(8分) FCFS: 服务序列依次为:55，58，39，18，90，160，150，38，180 移动的磁道数分别是: 45, 3, 19, 21, 72, 70, 10, 112,142 总的移动的磁道数是:494 SSTF: 服务序列依次为:90，58，55，39，38，18，150，160，180 移动的磁道数分别是: 10, 32, 3, 16, 1, 20, 132, 10, 20 总的移动的磁道数是:244

‘玖’ Linux采用什么算法来解决内存碎片问题、make内编译的文件为

一、Linux采用了“伙伴系统”，http://ke..com/view/4935190.htm
二、关于make的问题，参考http://ke..com/view/974566.htm
内部有例子，如果不懂，给我留言。

‘拾’ linux内核管理内存中，伙伴算法是基于什么问题提出来的

你说的应该不是内核，一般的linux内核大小也就是几兆，比如一个linux发行版的光盘映像，里面应用程序占了绝大多数存储空间，内核只是很小的一部分。