linux伙伴系统

linux伙伴系统（精选四篇）

linux伙伴系统篇1

内存资源一直是计算机中最珍贵也最关键的资源, 内存管理的好坏, 直接关系到系统的速度和稳定性。内存处理不当, 就有可能导致系统崩溃。因此, 实现一个高效且稳定的内存管理策略成了大家不得不面对的问题。目前, 很多操作系统都有一套比较成熟的内存管理机制, 但无论是哪种管理机制, 都不可能做到内存资源利用效率和时耗二者兼顾。本文对Linux内核中伙伴算法进行了改进, 使其在内存管理方面更加适应于实验室的硬件平台。

1 伙伴算法原理

1.1 伙伴关系

定义:由一个母实体分成的两个各方面属性一致的两个子实体, 这两个子实体就处于伙伴关系。在操作系统分配内存的过程中, 一个内存块常常被分成两个大小相等的内存块, 这两个大小相等的内存块就处于伙伴关系。它满足3个条件: (1) 两个块具有相同大小记为2^K; (2) 它们的物理地址是连续的; (3) 从同一个大块中拆分出来。

1.2 伙伴算法的实现原理

为了便于页面的维护, 将多个页面组成内存块, 每个内存块都有2的方幂个页, 方幂的指数被称为阶 (order) 。在操作内存时, 经常将这些内存块分成大小相等的两个块, 我们称分成的两个内存块为伙伴块, 采用一位来表示它们的伙伴关系。当这个位为1, 表示其中一块在使用;当这个位为0, 表示两个页面快都空闲或者都在使用。系统根据该为为0或者为1来决定是否使用或者分配该页面块。系统每次分配和回收伙伴块时都要对它们的伙伴位跟1进行异或运算。所谓异或是指刚开始时, 两个伙伴块都空闲, 它们的伙伴位为0, 后来其中一块被使用了, 异或一下得1, 后来另一块也使用了异或一下得0, 后来前面一块回收了异或一下得1, 后来另一块也回收了异或一下得0。

2 伙伴算法在Linux内核中的应用

Linux内核为了尽量减少空间的浪费, 减少申请释放内存的消耗时间, 就采用基于伙伴算法的存储分配机制。

2.1 核心数据结构

Linux内核将内存空间划分到3个管理区中, 每个管理区都有一个free_area_t结构数组, 即free_area[MAX_ORDER]free_list链表将order相同的内存块连接在一起, map中的每一位表示伙伴位, 代表两个内存块。free_area_t结构示意图见图1。

2.2 内存分配机制

假定在系统初始阶段, 全是大小为2^8大小的块 (MAX_ORDER为10) , 每个块的起始页帧号分别为0, 256, 512等等, 并且表示伙伴关系的位全部都为0 (实际上操作系统代码要占去一部分空间, 这里只是为了举例) , 现在要分配一个2^4大小的页面, 要执行的步骤如下: (1) 从order为4的area的空闲链表开始搜索, 没找到就想order更高一级的area搜索, 依次类推, 按照假设条件会一直搜索到order为8的area, 找到了起始页帧号为0的2^8页块; (2) 把起始序号为0的2^8页块从order为8的area的空闲链表中摘除并用1与该area的map数组中的第0 (0>> (1+8) ) 项异或一下得1; (3) 把起始序号为0的2^8页块拆分成两个起始序号分别为0和128的2^7页块, 将前者放入order为7的area的空闲链表中, 并用1对该area的map数组的第0 (0>> (1+7) ) 项异或一下得1; (4) 把起始序号为128的2^7页块拆分成起始序号分别为128和192的2^6页块, 将前者放入order为6的area的空闲链表中, 并用1对该area的map数组的第1 (128>> (1+6) ) 项异或一下得1; (5) 把起始序号为192的2^6页块拆分成起始序号分别为192和224的2^5页块, 将前者放入order为5的area的空闲链表中, 并用1对该area的map数组的第3 (192>> (1+5) ) 项异或一下得1; (6) 把起始序号为224的2^5页块拆分成起始序号分别为224和240的2^4页块, 将前者放入order为4的area的空闲链表中, 并用1对该area的map数组的第7 (224>> (1+4) ) 项异或一下得1; (7) 起始序号为240的2^4页块就是所求的块。

2.3 内存回收

当回收序号为4的1页块时, 因为页块大小为1即2^0, 所以先找到order为0的area.把该页面块加入到该area的空闲链表中, 然后判断其伙伴块 (序号为5的1页块) 的状态, 读该area的map的第2位 (4>> (1+0) ) , 假设伙伴块被占, 则该位为0 (因为4和5两个页块曾经都忙, 用1异或了两次所以为0) , 现在4块空闲, 所以用1再异或一下得1, 因为5号页块忙, 所以不向上合并。

过一段时间5号页块空闲, 同理, 先找到order为0的area, 把该页块加入到该area的空闲链表中, 读该area的map的第2位 (5>> (1+0) ) , 这时该位为1 (因为4块已回收) , 现在用1异或一下得0 (表示两块都空闲) , 这时向上合并, 把序号为4的1页块和序号为5的1页块从该area的空闲链表中摘除, 合并成起始序号为4的2^1页块, 将其放到order为1的area的空闲链表中。同理, 此时又要判断合并后的块的伙伴块 (序号为6的2^1页块) 的状态, 读该area的map的第1 (4>> (1+1) ) 位, 假设该伙伴块在此之前已被回收, 则该位为1 (表示忙) , 现用1异或一下得0, 并向上合并, 把序号为4的2^1页块和序号为6的2^1页块从order为1的area的空闲链表中摘除, 合并成序号为4的2^2页块, 并放入order为2的area的空闲链表中。然后再判断其伙伴块状态, 如此反复。

3 伙伴算法的不足及其改进

伙伴算法虽然是经典算法, 但也存在不足之处。

首先, 伙伴关系必须满足3个条件: (1) 大小相等; (2) 地址连续; (3) 从同一个大块中拆分出。这就限制了内存块的合并。如图2。

图中第1、2页面块空闲, 第0、3页面块忙, 但是1、2两块不能合并, 因为它们违背了伙伴关系的第3个条件所以不是伙伴关系, 本来连续的空间不能合并, 使得空间不能得到更好的利用。针对这种情况, 我们放宽对伙伴关系的限制, 在free_area_struct中增加一个二维数组tempbuddy[][2], tembuddy[x][0]和tembuddy[x][1] (x代表相邻页面块的个数) 代表与其相邻下一级area中相邻的两个空闲块的起始块号。正常情况下, 使用原来的伙伴位图。当内存紧张时, 就使用这两个不是buddy关系的空闲块。例如当所需要的2^n大小的页块不存在了, 就再它所在的tembuddy数组中临时查找两个相邻的空闲块。这样即没有破坏原来的伙伴位图, 又满足了内存需求。

其次, 该算法会产生内存浪费。因为伙伴算法是按2的幂次方申请空间的, 所以它申请到的空间都是2的幂次方个页面。假如你需要5个页面, 你就必须申请8 (2^3) 个页面, 这就造成3个页面的浪费。为了避免这个不必要的浪费, 我们在free_area_t中增加一个页面链表struct list_head free_temp_list。我们把后面5个页面 (假设是页块3) 分配出去, 前面3个页面从前往后依次分成2 (2^1) 个页面的页块1和1 (2^0) 个页面的页块2, 分别把这两个页块从order为3的空闲链表 (free_list) 中去除, 分别链入order为1和0的两个临时空闲链表 (free_temp_list) 。当回收页面时, 页块1先和页块2合并, 然后再合并页块3, 还原成原来的状态。该方法把一个大的内存块尽量细分, 在减少页面浪费的同时也增加了内存碎片。所以在分配较小的内存块时它比较合适。

再者, 该算法容易产生内存碎片。针对这个问题, 很多学者也都对其进行了改进, 比如fibonacci伙伴算法和weighted伙伴算法, 这两种算法对于页的申请一定程度上不局限于2的幂次方。但当算法增加页尺寸时, 系统就会增加新页尺寸的表项, 使得空闲链表增大。为了提供灵活多变的页尺寸, 而又不至于给系统增加太大的负担。我们对请求的页块大小进行再分配, 使得分配的几个页块还是2的幂次方个。比如系统请求15个页块, 我们可以先将15个页块分成8+4+2+1.然后分别从order为3、2、1、0的空闲链表中依次得到。不足之处在内存回收时增加了复杂度。为了不影响原来的伙伴位图, 便于内存回收页块, 应当将分成的几个页块标记起来。这种方法虽然增加了计算的复杂度, 但是内存资源非常宝贵的硬件上还是很有用处的。

4 结束语

本文首先介绍了Linux内核中伙伴算法相关的数据结构和算法实现原理, 在分析了该算法的不足之处, 并加以改进。虽然改进后的算法在效率上有了明显的提升, 但是也降低了精确性。但是该算法对于那些内存空间较小网速较快的硬件平台还是有较大的使用意义的。笔者在Linux 2.6.26内核基础上对该算法进行了改进, 并将其运行在实验室的NC (主要是上网功能, 内存只有256M) 机上, 大大提高了NC机的数据存储效率。

摘要：伙伴算法是内存管理的比较常用的算法之一。以Linux内存管理为基础, 阐述了Linux内核中关于伙伴算法的应用。同时也指出了伙伴算法在内存管理方面的不足之处, 针对具体的情况提出了具体的改进方法, 使得该算法在具体的条件下更加高效。

关键词：伙伴算法,内存管理,Linux内核

参考文献

[1][爱尔兰]MEL GORMAN.深入理解Linux虚拟内存管理[M].白洛, 李俊奎, 刘森林, 译.北京:北京航空航天大学出版社, 2006.

[2]毛德操, 胡希明.Linux内核源代码情景分析 (上册) [M].杭州:浙江大学出版社, 2001.

[3]W REISIG, PetriNets:An Introduction[M].Berlin, Heidelberg:Spring-Verlag, 1985.

linux伙伴系统篇2

大家都知道windows系统有一个自动更新，那么，linux系统又应该怎样更新呢?下面，就以比较常用的linux版本CentOS为例，来教大家具体的操作方法，

方法一：利用终端命令更新

1、启动CentOS系统，进入到桌面。

2、在桌面上右击鼠标，选择“在终端中打开”。

3、登陆root帐户(CentOS系统的方法是键入 su，回车，再输入密码。注意，密码在屏幕上不显示)。

4、再键入 yum update(这是CentOS的系统更新命令)，回车，

这时，系统会检测是否有可升级的程序，如果有，则会列出详细的升级项，并询问你是否升级，你只需输入 y 回车即可。

方法二：利用系统自带的系统更新界面更新

1、点击菜单“系统”-“管理”-“软件更新”。

2、这时，系统会自动扫描是否有可用的更新。如果有，则会在屏幕上列出。

3、此时，点击“安装更新”，会弹出提示框要求输入root用户密码。在此，我们输入密码，点击“授权”。

4、随后，系统便开始下载并安装更新了。

Linux:自由的操作系统篇3

近十年来，Linux作为操作系统世界里冉冉升起的新星，继承了Unix操作系统的良好基础，以开放源代码的特性吸引了全世界电脑爱好者，受到了包括IBM、HP、Intel和Oracle在内的一些计算机业巨头的技术支持，从而在技术方面得到了迅速的发展，已成为能够与Unix、Windows和Mac OS抗衡的操作系统。

了解Linux

说到Linux，不能不提Unix操作系统。Unix操作系统诞生于1969年，是一个分时、多用户、多任务、具有网络功能、通信功能和可移植性的操作系统，广泛应用于各种机型，是影响范围最大、最为稳定的操作系统之一。但是，Unix系统比较庞大，大部分安装在小型机上，价格也很昂贵。在Linux出现之前，使用Unix系统对于个人用户是一个可望而不可及的梦想，但正是Linux使这种梦想变成了现实。

Linux是Unix操作系统的克隆。Linux系统的创始人—芬兰的赫尔辛基大学学生Linus Torvalds对Unix操作系统相当感兴趣，考虑将它移植到个人计算机 (Intel X86 架构)上。他潜心研究 Unix 的核心，并且去除较为繁复的核心程序，1991年在386的计算机上开发出了Linux 第一个0.01版的内核，首次在Internet上公布。之后，在Linus的带领下，通过互联网，一个世界范围内的开发组对Linux进行坚持不懈的开发，到了 1994 年正式发布了内核为1.0的Linux操作系统，同时作为Linux的吉祥图案的一只可爱的胖企鹅Tux诞生了。在短短的十年里Linux的内核已发布了数十种版本(http://www.kernel.org)，目前内核已升至2.6.8.1。

Linux发展的初期与Windows明显不同的是，它的安装比较麻烦、图形界面的友好度比较低，这也导致Linux在桌面领域普及缓慢。值得庆幸的是，随着时间的推移，开发者们越来越意识到图形界面的重要性，在开发过程中融入了其他图形化操作系统的优点，包括微软的Windows系统和Unix的CDE等。目前在Linux上已实现多个图形管理程序，可变换不同的桌面图案或功能菜单，这点是Windows操作系统的单一图形接口也望尘莫及的。Linux应用最普遍的图形用户界面KDE和GNOME(见图1)，不但能够给用户提供一个完整的图形界面，同时还给软件开发提供了一条捷径。事实上已涌现出越来越多的针对KDE和GNOME的应用程序。

Linux的发行版本

Linux这个词本身只表示Linux内核，对于需要更完整功能的操作系统来说，毕竟还不够完备。可能还需要一些软件开发工具、数据库、Web服务器（例如Apache 服务器)、桌面环境（比如KDE和GNOME）和办公套件（如Openoffice）等等。由于Linux免费的内核及良好的稳定性，并可以在便宜的x86 架构下的计算机平台运作，所以吸引了很多的套件商与自由软件的开发团队，在这个 Linux 的核心上开发相关的软件。他们将 Linux 内核、内核工具与相关的软件，包括一些GNU软件（如gcc、cc、C++、Tcl/Tk、Perl、Fortran77等）集合起来，并加入自己公司或团队的系统管理模块与工具，制作出一套可以完整安装的操作系统。这个完整的Linux 操作系统，我们就称为“Linux Distribution”，或者是中文所谓的安装套件。

目前世界上已有百种以上不同的Linux安装套件组合，但不论这些套件的名称或开发厂商是谁，它们都是同属于 Linux 的大家庭。由于各个 Distribution 都是架构在 Linux内核下发展属于自己公司的风格，因此大家都遵守 Linux Standard Base ( LSB ) 的规范，也就是说，各个 Distribution 其实都是差不多的，只是里面所使用的各套件可能并不完全相同而已。各家公司所发行的光盘套件是可以在网络上面自由下载的。不过，如果想要有较佳的服务，那么购买该公司发行的光盘也是不错的选择。

几个主要的 Linux 发行公司的网址：

Red Hat: http://www.redhat.com

Turbolinux: http://www.turbolinux.com

FreeBSD: http://www.freebsd.org

Debian: http://www.debian.org

Mandrake: http://www.linux-mandrake.com/en/

Slackware: http://www.slackware.com/

SuSE: http://www.suse.com/index_us.html

Fedora: http://fedora.redhat.com

……

了解更多信息，您可以查阅Linux Distributions 的网站： http://www.linuxiso.org 或http://www.fokus.gmd.de/linux/linux-distrib.html。

近年来，Linux 在我国取得了可喜的发展，涌现出不少颇具实力的中文Linux 发行商。

Redflag Linux： http://www.redflag-linux.com

Xteam linux: http://www.xteamlinux.com.cn

Linux的优势

Linux已成为最近几年来最受瞩目的操作系统之一，主要原因是它的免费，以及系统的开放性，可以随时取得程序的原代码，这对于程序开发人员是很重要的。除了这些它还具有以下的优势：

1．跨平台的硬件支持

由于Linux的内核大部分是用C 语言编写的，并采用了可移植的Unix标准应用程序接口，所以它支持如i386、Alpha、AMD和Sparc等系统平台，以及从个人电脑到大型主机，甚至包括嵌入式系统在内的各种硬件设备。

2．丰富的软件支持

与其他的操作系统不同的是，安装了Linux系统后，用户常用的一些办公软件、图形处理工具、多媒体播放软件和网络工具等都已无需安装。而对于程序开发人员来说，Linux更是一个很好的操作平台，在Linux的软件包中，包含了多种程序语言与开发工具，如gcc、cc、C++、Tcl/Tk、Perl、Fortran77等。

3．多用户多任务

和Unix系统一样，Linux是一个真正的多用户多任务的操作系统。多个用户可以各自拥有和使用系统资源，即每个用户对自己的资源（例如：文件、设备）有特定的权限，互不影响，同时多个用户可以在同一时间以网络联机的方式使用计算机系统。多任务是现代计算机的最主要的一个特点，由于Linux系统调度每一个进程是平等地访问处理器的，所以它能同时执行多个程序，而且各个程序的运行是互相独立的。

4．可靠的安全性

Linux是一个具有先天病毒免疫能力的操作系统，很少受到病毒攻击。

对于一个开放式系统而言，在方便用户的同时，很可能存在安全隐患。不过，利用Linux自带防火墙、入侵检测和安全认证等工具，及时修补系统的漏洞，就能大大提高Linux系统的安全性，让黑客们无机可乘。

5．良好的稳定性

Linux内核的源代码是以标准规范的32位（在64位CPU上是64位）的计算机来做的最佳化设计，可确保其系统的稳定性。正因为Linux的稳定，才使得一些安装 Linux 的主机像Unix机一样常年不关而不曾宕机。

6．完善的网络功能

Linux 内置了很丰富的免费网络服务器软件、数据库和网页的开发工具，如Apache、Sendmail、VSFtp、SSH、MySQL、PHP和JSP等。近年来，越来越多的企业看到了Linux的这些强大的功能，利用Linux担任全方位的网络服务器。