Linux内核伙伴系统分析1
需积分: 0 184 浏览量
2022-08-03
13:17:32
上传
评论
收藏 821KB PDF 举报
Linux内核伙伴系统分析
①
薛 峰
(安徽师范大学数学计算机科学学院,芜湖241002)
摘 要:本文针对Linux内核实现的伙伴系统进行了抽象分析,并通过实例演示了算法的执行过程.分析了用于物
理地址空间管理的三级数据结构及其关系.在此基础上,详细描述了用于分配和回收页框的伙伴算法.对于待回收
的内存块而言,计算其伙伴的索引及合并内存块的索引是回收操作的关键,讨论了相关计算方法的几条结论并予以
证明.
关键词:Linux内核;内存管理;伙伴算法;伙伴系统
引用格式:薛峰.Linux内核伙伴系统分析.计算机系统应用,2018,27(1):174–179.http://www.c-s-a.org.cn/1003-3254/6177.html
Buddy System Analysis in Linux Kernel
XUEFeng
(SchoolofMathematics&ComputerScience,AnhuiNormalUniversity,Wuhu241002,China)
Abstract:ThebuddysystemimplementedintheLinuxkernelisstudied,andtheprocessofbuddyalgorithmis
demonstratedwithexamples.Therearethreelevelsofdatastructurededicatedtomanagepageframesinphysicaladdress
space.Firstly,thesedatastructuresandtheirrelationshipsarepresented.Then,thebuddyalgorithmusedtoallocateand
deallocatepageframesisdescribedindetail.Asfarasamemoryblocktobedeallocatedisconcerned,howtocalculate
theindexofitsbuddyandcoalescedmemoryblockisthekeypointofdeallocatingoperation.Severalconclusions
pertainingtothiscalculationaredealtwithandproved.
Key words:Linuxkernel;memorymanagement;buddyalgorithm;buddysystem
1引言
伙伴算法是一种动态存储分配算法,用于实现操
作系统内核空间和用户空间(如C语言库)的分配和
回收操作.Knowlton
[1]
和Knuth
[2]
最早系统地描述了用
于内存管理中的二分伙伴算法.之后,Hirschberg
[3]
和
Shen
[4]
先后提出斐波那契伙伴算法和加权伙伴算法,作
为伙伴算法的两种变体.为了适应不同的内存请求概
率分布,Peterson
[5]
又进一步提出泛化伙伴算法,针对不
同请求概率分布采取不同的分配策略.
实现伙伴算法的内存管理模块称为伙伴系统,是
固定分区和可变分区的一个合理折中方案
[6]
.然而,由
于存在内碎片和外碎片的问题,以及无法支持虚拟存
储器的缘故,在现代操作系统内核中单纯的伙伴系统
并没有得到广泛应用,而分页机制则成为内存管理的
主流技术.尽管如此,Linux内核成功地将分页机制与
伙伴系统系统结合起来,分页机制将逻辑地址空间映
射到物理地址空间,伙伴系统负责在物理地址空间中
分配和回收页框,因而内存块的尺寸被限定为页框尺
寸的倍数.为了追求时间效率,Linux内核选择实现了
二分伙伴算法,该算法的优点在于伙伴地址的计算更
加简便、高效.
目前,涉及Linux内核伙伴系统分析的文献很多,
计算机系统应用ISSN1003-3254,CODENCSAOBN E-mail:[email protected]
ComputerSystems&Applications,2018,27(1):174−179[doi:10.15888/j.cnki.csa.006177] http://www.c-s-a.org.cn
©中国科学院软件研究所版权所有. Tel:+86-10-62661041
①收稿时间:2017-04-16;修改时间:2017-05-02;采用时间:2017-05-16;csa在线出版时间:2017-12-22
174软件技术·算法SoftwareTechnique·Algorithm
资源评论
