虚拟内存.docx
《虚拟内存.docx》由会员分享，可在线阅读，更多相关《虚拟内存.docx（32页珍藏版）》请在冰点文库上搜索。
虚拟内存
内存管理内幕
JonathanBartlett（johnnyb@）,技术总监,NewMediaWorx
2004年11月29日
本文将对Linux™程序员可以使用的内存管理技术进行概述，虽然关注的重点是C语言，但同样也适用于其他语言。
文中将为您提供如何管理内存的细节，然后将进一步展示如何手工管理内存，如何使用引用计数或者内存池来半手工地管理内存，以及如何使用垃圾收集自动管理内存。
为什么必须管理内存
内存管理是计算机编程最为基本的领域之一。
在很多脚本语言中，您不必担心内存是如何管理的，这并不能使得内存管理的重要性有一点点降低。
对实际编程来说，理解您的内存管理器的能力与局限性至关重要。
在大部分系统语言中，比如C和C++，您必须进行内存管理。
本文将介绍手工的、半手工的以及自动的内存管理实践的基本概念。
追溯到在AppleII上进行汇编语言编程的时代，那时内存管理还不是个大问题。
您实际上在运行整个系统。
系统有多少内存，您就有多少内存。
您甚至不必费心思去弄明白它有多少内存，因为每一台机器的内存数量都相同。
所以，如果内存需要非常固定，那么您只需要选择一个内存范围并使用它即可。
不过，即使是在这样一个简单的计算机中，您也会有问题，尤其是当您不知道程序的每个部分将需要多少内存时。
如果您的空间有限，而内存需求是变化的，那么您需要一些方法来满足这些需求：
o确定您是否有足够的内存来处理数据。
o从可用的内存中获取一部分内存。
o向可用内存池（pool）中返回部分内存，以使其可以由程序的其他部分或者其他程序使用。
实现这些需求的程序库称为分配程序（allocators），因为它们负责分配和回收内存。
程序的动态性越强，内存管理就越重要，您的内存分配程序的选择也就更重要。
让我们来了解可用于内存管理的不同方法，它们的好处与不足，以及它们最适用的情形。
回页首
C风格的内存分配程序
C编程语言提供了两个函数来满足我们的三个需求：
omalloc：
该函数分配给定的字节数，并返回一个指向它们的指针。
如果没有足够的可用内存，那么它返回一个空指针。
ofree：
该函数获得指向由malloc分配的内存片段的指针，并将其释放，以便以后的程序或操作系统使用（实际上，一些malloc实现只能将内存归还给程序，而无法将内存归还给操作系统）。
物理内存和虚拟内存
要理解内存在程序中是如何分配的，首先需要理解如何将内存从操作系统分配给程序。
计算机上的每一个进程都认为自己可以访问所有的物理内存。
显然，由于同时在运行多个程序，所以每个进程不可能拥有全部内存。
实际上，这些进程使用的是虚拟内存。
只是作为一个例子，让我们假定您的程序正在访问地址为629的内存。
不过，虚拟内存系统不需要将其存储在位置为629的RAM中。
实际上，它甚至可以不在RAM中——如果物理RAM已经满了，它甚至可能已经被转移到硬盘上！
由于这类地址不必反映内存所在的物理位置，所以它们被称为虚拟内存。
操作系统维持着一个虚拟地址到物理地址的转换的表，以便计算机硬件可以正确地响应地址请求。
并且，如果地址在硬盘上而不是在RAM中，那么操作系统将暂时停止您的进程，将其他内存转存到硬盘中，从硬盘上加载被请求的内存，然后再重新启动您的进程。
这样，每个进程都获得了自己可以使用的地址空间，可以访问比您物理上安装的内存更多的内存。
（个人理解：
进程取决于系统中断点的初始内存分配只分配了进程运行所需的一部分内存，另一部分也被分配了内存地址但是却不在内存中，被分配的的内存地址根据转换表转换为对应的硬盘地址，也就是说另一部分本来应该加载在对应内存地址中的数据被加载在了经过转换的硬盘地址中，当进程需要存储在硬盘地址中的数据时就把硬盘空间当成内存进行加载。
）
在32-位x86系统上，每一个进程可以访问4GB内存。
现在，大部分人的系统上并没有4GB内存，即使您将swap也算上，每个进程所使用的内存也肯定少于4GB。
因此，当加载一个进程时，它会得到一个取决于某个称为系统中断点（systembreak）的特定地址的初始内存分配。
该地址之后是未被映射的内存——用于在RAM或者硬盘中没有分配相应物理位置的内存。
因此，如果一个进程运行超出了它初始分配的内存，那么它必须请求操作系统“映射进来（mapin）”更多的内存。
（映射是一个表示一一对应关系的数学术语——当内存的虚拟地址有一个对应的物理地址来存储内存内容时，该内存将被映射。
）
基于UNIX的系统有两个可映射到附加内存中的基本系统调用：
obrk：
brk（）是一个非常简单的系统调用。
还记得系统中断点吗？
该位置是进程映射的内存边界。
brk（）只是简单地将这个位置向前或者向后移动，就可以向进程添加内存或者从进程取走内存。
ommap：
mmap（），或者说是“内存映像”，类似于brk（），但是更为灵活。
首先，它可以映射任何位置的内存，而不单单只局限于进程。
其次，它不仅可以将虚拟地址映射到物理的RAM或者swap，它还可以将它们映射到文件和文件位置，这样，读写内存将对文件中的数据进行读写。
不过，在这里，我们只关心mmap向进程添加被映射的内存的能力。
munmap（）所做的事情与mmap（）相反。
如您所见，brk（）或者mmap（）都可以用来向我们的进程添加额外的虚拟内存。
在我们的例子中将使用brk（），因为它更简单，更通用。
实现一个简单的分配程序
如果您曾经编写过很多C程序，那么您可能曾多次使用过malloc（）和free（）。
不过，您可能没有用一些时间去思考它们在您的操作系统中是如何实现的。
本节将向您展示malloc和free的一个最简化实现的代码，来帮助说明管理内存时都涉及到了哪些事情。
要试着运行这些示例，需要先复制本代码清单，并将其粘贴到一个名为malloc.c的文件中。
接下来，我将一次一个部分地对该清单进行解释。
在大部分操作系统中，内存分配由以下两个简单的函数来处理：
ovoid*malloc（longnumbytes）：
该函数负责分配numbytes大小的内存，并返回指向第一个字节的指针。
ovoidfree（void*firstbyte）：
如果给定一个由先前的malloc返回的指针，那么该函数会将分配的空间归还给进程的“空闲空间”。
malloc_init将是初始化内存分配程序的函数。
它要完成以下三件事：
将分配程序标识为已经初始化，找到系统中最后一个有效内存地址，然后建立起指向我们管理的内存的指针。
这三个变量都是全局变量：
清单1.我们的简单分配程序的全局变量
inthas_initialized=0;
void*managed_memory_start;
void*last_valid_address;
如前所述，被映射的内存的边界（最后一个有效地址）常被称为系统中断点或者当前中断点。
在很多UNIX®系统中，为了指出当前系统中断点，必须使用sbrk（0）函数。
sbrk根据参数中给出的字节数移动当前系统中断点，然后返回新的系统中断点。
使用参数0只是返回当前中断点。
这里是我们的malloc初始化代码，它将找到当前中断点并初始化我们的变量：
清单2.分配程序初始化函数
/*Includethesbrkfunction*/
#include
voidmalloc_init（）
{
/*grabthelastvalidaddressfromtheOS*/
last_valid_address=sbrk（0）;
/*wedon'thaveanymemorytomanageyet,so
*justsetthebeginningtobelast_valid_address
*/
managed_memory_start=last_valid_address;
/*Okay,we'reinitializedandreadytogo*/
has_initialized=1;
}
现在，为了完全地管理内存，我们需要能够追踪要分配和回收哪些内存。
在对内存块进行了free调用之后，我们需要做的是诸如将它们标记为未被使用的等事情，并且，在调用malloc时，我们要能够定位未被使用的内存块。
因此，malloc返回的每块内存的起始处首先要有这个结构：
清单3.内存控制块结构定义
structmem_control_block{
intis_available;
intsize;
};
现在，您可能会认为当程序调用malloc时这会引发问题——它们如何知道这个结构？
答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。
这使得返回的指针指向没有用于任何其他用途的内存。
那样，从调用程序的角度来看，它们所得到的全部是空闲的、开放的内存。
然后，当通过free（）将该指针传递回来时，我们只需要倒退几个内存字节就可以再次找到这个结构。
在讨论分配内存之前，我们将先讨论释放，因为它更简单。
为了释放内存，我们必须要做的惟一一件事情就是，获得我们给出的指针，回退sizeof（structmem_control_block）个字节，并将其标记为可用的。
这里是对应的代码：
清单4.解除分配函数
voidfree（void*firstbyte）{
structmem_control_block*mcb;
/*Backupfromthegivenpointertofindthe
*mem_control_block
*/
mcb=firstbyte-sizeof（structmem_control_block）;
/*Marktheblockasbeingavailable*/
mcb->is_available=1;
/*That'sIt!
We'redone.*/
return;
}
如您所见，在这个分配程序中，内存的释放使用了一个非常简单的机制，在固定时间内完成内存释放。
分配内存稍微困难一些。
以下是该算法的略述：
清单5.主分配程序的伪代码
1.Ifourallocatorhasnotbeeninitialized,initializeit.
2.Addsizeof（structmem_control_block）tothesizerequested.
3.startatmanaged_memory_start.
4.Areweatlast_validaddress?
5.Ifweare:
A.Wedidn'tfindanyexistingspacethatwaslargeenough
--asktheoperatingsystemformoreandreturnthat.
6.Otherwise:
A.Isthecurrentspaceavailable（checkis_availablefrom
themem_control_block）?
B.Ifitis:
i）Isitlargeenough（check"size"fromthe
mem_control_block）?
ii）Ifso:
a.Markitasunavailable
b.Movepastmem_control_blockandreturnthe
pointer
iii）Otherwise:
a.Moveforward"size"bytes
b.Gobackgostep4
C.Otherwise:
i）Moveforward"size"bytes
ii）Gobacktostep4
我们主要使用连接的指针遍历内存来寻找开放的内存块。
这里是代码：
清单6.主分配程序
void*malloc（longnumbytes）{
/*Holdswherewearelookinginmemory*/
void*current_location;
/*Thisisthesameascurrent_location,butcasttoa
*memory_control_block
*/
structmem_control_block*current_location_mcb;
/*Thisisthememorylocationwewillreturn.Itwill
*besetto0untilwefindsomethingsuitable
*/
void*memory_location;
/*Initializeifwehaven'talreadydoneso*/
if（!
has_initialized）{
malloc_init（）;
}
/*Thememorywesearchforhastoincludethememory
*controlblock,buttheusersofmallocdon'tneed
*toknowthis,sowe'lljustadditinforthem.
*/
numbytes=numbytes+sizeof（structmem_control_block）;
/*Setmemory_locationto0untilwefindasuitable
*location
*/
memory_location=0;
/*Beginsearchingatthestartofmanagedmemory*/
current_location=managed_memory_start;
/*Keepgoinguntilwehavesearchedallallocatedspace*/
while（current_location!
=last_valid_address）
{
/*current_locationandcurrent_location_mcbpoint
*tothesameaddress.However,current_location_mcb
*isofthecorrecttype,sowecanuseitasastruct.
*current_locationisavoidpointersowecanuseit
*tocalculateaddresses.
*/
current_location_mcb=
（structmem_control_block*）current_location;
if（current_location_mcb->is_available）
{
if（current_location_mcb->size>=numbytes）
{
/*Woohoo!
We'vefoundanopen,
*appropriately-sizelocation.
*/
/*Itisnolongeravailable*/
current_location_mcb->is_available=0;
/*Weownit*/
memory_location=current_location;
/*Leavetheloop*/
break;
}
}
/*Ifwemadeithere,it'sbecausetheCurrentmemory
*blocknotsuitable;movetothenextone
*/
current_location=current_location+
current_location_mcb->size;
}
/*Ifwestilldon'thaveavalidlocation,we'll
*havetoasktheoperatingsystemformorememory
*/
if（!
memory_location）
{
/*Movetheprogrambreaknumbytesfurther*/
sbrk（numbytes）;
/*Thenewmemorywillbewherethelastvalid
*addressleftoff
*/
memory_location=last_valid_address;
/*We'llmovethelastvalidaddressforward
*numbytes
*/
last_valid_address=last_valid_address+numbytes;
/*Weneedtoinitializethemem_control_block*/
current_location_mcb=memory_location;
current_location_mcb->is_available=0;
current_location_mcb->size=numbytes;
}
/*Now,nomatterwhat（well,exceptforerrorconditions）,
*memory_locationhastheaddressofthememory,including
*themem_control_block
*/
/*Movethepointerpastthemem_control_block*/
memory_location=memory_location+sizeof（structmem_control_block）;
/*Returnthepointer*/
returnmemory_location;
}
这就是我们的内存管理器。
现在，我们只需要构建它，并在程序中使用它即可。
运行下面的命令来构建malloc兼容的分配程序（实际上，我们忽略了realloc（）等一些函数，不过，malloc（）和free（）才是最主要的函数）：
清单7.编译分配程序
gcc-shared-fpicmalloc.c-omalloc.so
该程序将生成一个名为malloc.so的文件，它是一个包含有我们的代码的共享库。
在UNIX系统中，现在您可以用您的分配程序来取代系统的malloc（），做法如下：
清单8.替换您的标准的malloc
LD_PRELOAD=/path/to/malloc.so
exportLD_PRELOAD
LD_PRELOAD环境变量使动态链接器在加载任何可执行程序之前，先加载给定的共享库的符号。
它还为特定库中的符号赋予优先权。
因此，从现在起，该会话中的任何应用程序都将使用我们的malloc（），而不是只有系统的应用程序能够使用。
有一些应用程序不使用malloc（），不过它们是例外。
其他使用realloc（）等其他内存管理函数的应用程序，或者错误地假定malloc（）内部行为的那些应用程序，很可能会崩溃。
ashshell似乎可以使用我们的新malloc（）很好地工作。
如果您想确保malloc（）正在被使用，那么您应该通过向函数的入口点添加write（）调用来进行测试。
我们的内存管理器在很多方面都还存在欠缺，但它可以有效地展示内存管理需要做什么事情。
它的某些缺点包括：
o由于它对系统中断点（一个全局变量）进行操作，所以它不能与其他分配程序或者mmap一起使用。
o当分配内存时，在最坏的情形下，它将不得不遍历全部进程内存；其中可能包括位于硬盘上的很多内存，这意味着操作系统将不得不花时间去向硬盘移入数据和从硬盘中移出数据。
o没有很好的内存不足处理方案（malloc只假定内存分配是成功的）。
o它没有实现很多其他的内存函数，比如realloc（）。
o由于sbrk（）可能会交回比我们请求的更多的内存，所以在堆（heap）的末端会遗漏一些内存。
o虽然is_available标记只包含一位信息，但它要使用完整的4-字节的字。
o分配程序不是线程安全的。
o分配程序不能将空闲空间拼合为更大的内存块。
o分配程序的过于简单的匹配算法会导致产生很多潜在的内存碎片。
o我确信还有很多其他问题。
这就是为什么它只是一个例子!
其他malloc实现
malloc（）的实现有很多，这些实现各有优点与缺点。
在设计一个分配程序时，要面临许多需要折衷的选择，其中包括：
o分配的速度。
o回收的速度。
o有线程的环境的行为。
o内存将要被用光时的行为。
o局部缓存。
o簿记（Bookkeeping）内存开销。
o虚拟内存环境中的行为。
o小的或者大的对象。
o实时保证。
每一个实现都有其自身的优缺点集合。
在我们的简单的分配程序中，分配非常慢，而回收非常快。
另外，由于它在使用虚拟内存系统方面较差，所以它最适于处理大的对象。
还有其他许多分配程序可以使用。
其中包括：
oDougLeaMalloc：
DougLeaMalloc实际上是完整的一组分配程序，其中包括DougLea的原始分配程序，GNUlibc分配程序和ptmalloc。
DougLea的分配程序有着与我们的版本非常类似的基本结构，但是它加入了索引，这使得搜索速度更快，并且可以将多个没有被使用的块组合为一个大的块。
它还支持缓存，以便更快地再次使用最近释放的内存。
ptmalloc是DougLeaMalloc的一个扩展版本，支持多线程。
在本文后面的参考资料部分中，有一篇描述DougLea的Malloc实现的文章。
oBSDMalloc：
BSDMalloc是随4.2BSD发行的实现，包含在FreeBSD之中，这个分配程序可以
升级会员 