用户端内存管理¶
为什么选择用户端内存管理？¶
为什么要在操作系统课程中讨论用户土地内存管理？
毕竟，用户端内存管理几乎总是标准库或虚拟机的实现细节。
这很重要的原因是，操作系统将内存作为连续虚拟页的单位分配给用户程序。
页面的单位对于许多程序来说并不是很有用。大多数程序以结构化对象的形式工作，结构化对象由原始数据类型和指向其他结构化对象或原始数据类型的指针组成。
为什么选择用户端内存管理？¶
因为程序需要将机器视为页面以外的其他东西，所以我们可以将用户土地内存管理的主题视为系统提供的虚拟机的详细信息。
由于内存管理系统的细节根据语言需要而有所不同，因此该组件存在于操作系统实现中是不切实际的。
堆管理¶
《堆》¶
堆是进程内存的一部分，用于存储超出任何一个函数或方法的生命周期的数据。该数据的生存期由它何时被分配以及堆管理器何时显式删除它或垃圾收集它来定义。
像C或C++这样的语言通过Malloc、FREE、NEW、DELETE等显式语句手动分配内存块……
像C#或Java这样的语言通过使用垃圾收集器的new和de-alocate等语句来分配内存块
内存管理器¶
内存管理器的职责如下：
管理已分配的内存段列表
管理内存中的空闲区域列表
分配-当程序管理对象的内存时，内存管理器将找到至少与对象一样大的连续内存块。如果没有足够的连续内存可用，它会请求操作系统提供更多堆空间
释放-当程序释放堆内存时，内存管理器将释放的空间返回到空闲列表。在大多数实现中，内存通常不会返回给操作系统。
内存分配的特点¶
来自程序的对堆区块的请求通常大小不同
重新分配是不可预测的。在堆栈中，按照先入后出的顺序分配和释放内存。堆的情况并非如此。
因此，内存管理器必须准备好以不可预测的顺序处理不同大小的请求
大多数情况下，大多数请求都是对以字节或千字节为单位的小内存区域的请求。
内存分配的特点¶
虽然不是最优的，但分配器返回的内存区域大于请求的大小是可以接受的。
许多分配器会将堆分成不同块大小的桶。
因此，例如，分配器可以利用大小为32字节的存储器区域来服务对31字节存储器的请求
一个好的内存管理器的特点¶
空间效率-内存管理器应该最大限度地减少程序所需的总堆。这是通过最小化堆碎片来实现的。
程序效率-分配应安排在内存中，以保持局部性
低开销-内存分配/释放是程序中频繁的操作。因此，内存管理器的开销应该最小化。较小内存分配的效率应该优先于较大分配的效率，因为较小的分配发生得更频繁。
内存层次结构的更新者¶
内存类型/内存大小/访问时间
寄存器/32字/1 ns
一级缓存/16-64KB/5-10 ns
二级缓存/128KB-4MB/40-60 ns
物理内存/512MB-8 GB/100-150 ns
交换文件/512MB-8 GB/3-15毫秒
程序局部性¶
通常，程序包含许多从未执行过的指令。
使用可复用库构建的程序通常只使用这些库的一小部分功能。
程序通常将大部分时间花在执行最里面的循环和递归函数上。
实际上只执行了一小部分可以执行的代码。这意味着，在任何给定的方法中，都有专门用于异常和错误处理的基本代码块，这些代码块通常不会被调用。
碎片化¶
内部碎片-当响应内存请求时，内存区域大于请求的内存区域，则剩余的内存区域将被浪费。
外部碎片-不足以为请求提供服务的连续内存区域。
外部碎片=1-(最大可用区域/总可用内存)
之所以会出现碎片，是因为虽然可以决定堆分配的位置，但无法控制或预测它们最终释放的顺序。
减少堆的碎片¶
堆作为一个连续的空闲空间启动
当程序分配和释放内存时，可用空间将不再是连续的
一段时间后，可能会有一些空闲空间区域不够大，无法服务于内存分配请求。
如果可用空间变得足够零碎，那么即使有足够的总可用内存，请求更多内存也可能失败，因为没有足够大的连续空闲区域。
最佳匹配VS次匹配¶
最佳分配策略是将每个请求放入满足该请求的最小空闲内存区域
First-Fit分配策略是将每个请求放入将满足该请求的搜索中遇到的第一个空闲内存区域
总体而言，最佳策略在大多数情况下提供最佳性能。
最佳匹配策略的缺点是，它会导致更复杂的分配器，并且搜索最佳匹配空闲区域会有一些成本(尽管有一些方法可以绕过这一点)。
最合适的¶
为了避免为分配搜索最合适的空闲空间区域所带来的成本，最合适的分配器通常会将堆划分为不同的存储桶。
这些存储桶中的每个都将负责服务不同大小的请求。
在GNU标准C库中，有大小为8字节、16字节、24字节、...512字节。对于较大的分配，存在以对数方式分布的大小的额外存储桶(512,576,640，...)
为了服务分配请求，分配器将使用存储桶中的空闲列表，该列表是与请求大小相同或更大的最小存储桶。如果该桶为空，则使用下一个最大的桶。如果所有存储桶都已满，则分配器会向操作系统请求更多堆空间。
管理可用空间¶
管理可用空间有三种方法：
如果正在使用存储桶，则可以维护每个存储桶中哪些项目是空闲的位图。这相当直截了当。
边界标记--在每个数据块的最高端和最低端，我们保留一点信息，告诉我们该数据块是空闲的还是已分配的，以及该数据块有多大
双重链接的嵌入式空闲块-空闲块包含指向前一个空闲块和下一个空闲块的指针。通常会对这些列表进行排序，以帮助最佳匹配算法。
错误和显式分配器¶
对于像C这样的语言，当程序在显式分配的内存的已分配部分的边界之外写入时，这些覆盖可能会写入分配器使用的结构。
由于这种可能性，不同的分配器或多或少容易出现不同类型的错误。一般来说，边界标记和双向链接的嵌入自由列表很容易受到这些类型的错误的攻击。使用位图的存储桶分配器不太容易受到影响。
这一事实在调试过程中可能会有用。有些仅用于调试的分配器为每个分配返回超大的内存区域，并填充每个区域的前面和后面。在释放时，如果填充的值被更改，则分配器可以向控制台打印错误。
调试Malloc/Free¶
调试常见的Malloc/Free问题的一个很好的方法是使用dMalloc库。
该库可在http://dmalloc.com.上找到无需修改即可在现有应用中使用。
此库可帮助您发现：
未释放的对象最初分配到的位置。
其中，如果遇到任何缓冲区溢出，则为。
扩展堆¶
UNIX分配器有两种扩展堆的方式：
Sbrk-要求操作系统将数据段增加N个字节。
Mmap/mfree-来自操作系统的请求，要求分配单独的非连续内存区域。由于这些区域不是连续的，因此将它们返回到操作系统会更简单。Mmap/mfree的开销相当大。通常，mmap/mfree用于为不能放入存储桶(>1MB)的较大分配请求提供服务。
推荐读物¶
由GNU libc Malloc/realloc/Free-http://g.oswego.edu/dl/html/malloc.html的作者Doug Lea撰写的文章
手动取消分配的问题¶
手动内存取消分配可能会导致内存泄漏。内存泄漏被定义为已分配但未解除分配且在未来任何时候都不会被引用的内存。
只要有足够的可用内存，内存泄漏就不会导致程序不正确或崩溃。对于寿命较短的程序来说，这不是问题。对于寿命更长的程序来说，这是一个问题。
手动取消分配的问题¶
如果在释放后，指针指向释放的空间，并且程序在将来取消引用该指针，则手动内存释放可能会导致问题。这可能会导致修改分配给不同指针的内存或已释放给操作系统的内存。这可能会导致崩溃或程序行为不正确。
避免手动取消分配的问题¶
在设计应用程序时，请确保每个分配的对象都有一个定义的所有者。这可以是类的实例，也可以是函数。这适用于可以静态确定所有者的情况。
当无法静态确定所有者时，建议使用引用计数器。每当创建对对象的引用时，我们都会递增引用计数器。每当引用消失时，我们都会减少引用计数器。当计数器达到零时，我们重新分配对象。这在循环结构上遇到了麻烦。
一个简单的Malloc/Free实现(来自IBM Developer Works的示例)¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
#include <unistd.h>
int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;
struct mem_control_block {
int is_available;
int size;
};
void malloc_init()
{
last_valid_address = sbrk(0);
managed_memory_start = last_valid_address;
has_initialized = 1;
}
简单的Malloc/Free实现¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
void myfree(void *firstbyte) {
struct mem_control_block *mcb;
mcb = (struct mem_control_block*)
(firstbyte - sizeof(struct mem_control_block));
mcb->is_available = 1;
return;
}
简单的Malloc/Free实现¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
void *mymalloc(long numbytes) {
void *current_location;
struct mem_control_block *current_location_mcb;
void *memory_location;
if(! has_initialized) {
malloc_init();
}
numbytes = numbytes + sizeof(struct mem_control_block);
memory_location = 0;
current_location = managed_memory_start;
简单的Malloc/Free实现¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
while(current_location != last_valid_address)
{
current_location_mcb =
(struct mem_control_block *)current_location;
if(current_location_mcb->is_available)
{
if(current_location_mcb->size >= numbytes)
{
current_location_mcb->is_available = 0;
memory_location = current_location;
break;
}
}
current_location = current_location +
current_location_mcb->size;
}
简单的Malloc/Free实现¶
{LANGUAGE=C，BASIC STYLE=，INDENT=xleftMarch}
if(!memory_location)
{
sbrk(numbytes);
memory_location = last_valid_address;
last_valid_address = last_valid_address + numbytes;
current_location_mcb =
(struct mem_control_block*)memory_location;
current_location_mcb->is_available = 0;
current_location_mcb->size = numbytes;
}
memory_location = memory_location +
sizeof(struct mem_control_block);
return memory_location;
}
垃圾收集¶
垃圾收集¶
无法引用的数据被视为垃圾
显式分配器的一个问题是释放是错误的来源
一些运行时和编程语言提供了自动垃圾收集器。
第一个垃圾收集器实现是在1958年针对LISP编程语言的。
对垃圾收集器的要求¶
大多数垃圾回收器要求系统是类型安全的，以支持回收器。
大多数垃圾回收器要求引用/指针指向对象的开头，而不是位于中间的某个位置
通常，这些保证不能用于C程序。
C语言存在垃圾回收器，但程序员必须限制他们对C语言全部功能的使用
垃圾收集器的目标¶
收集的总体执行时间-垃圾收集器必须访问大量数据。他们越快越好
空间使用率-垃圾收集器必须将碎片保持在最低限度
等待时间-许多垃圾收集器要求程序在运行时暂时停止。因此，最好是最长等待时间较短。
像显式分配器一样，垃圾收集器可以通过从最近释放的区域分配内存来帮助保持局部性。
垃圾收集的缺点¶
垃圾收集器耗费处理时间来确定哪些对象是垃圾
垃圾收集器运行间隔不可预测。这可能会给以下方面带来麻烦：
垃圾收集器可能运行得太晚，导致太多垃圾堆积
垃圾收集器需要在某种程度上暂停执行。这可能会降低性能。
垃圾收集的缺点¶
垃圾收集器无法检测到何时出现物理内存不足的情况。对于手动释放，内存使用量应该始终是所需的最小值，但对于垃圾收集器，这可能是可变的。因此，垃圾回收器可能会鼓励过度使用物理内存或不必要的分页。
垃圾回收器无法删除所有可能的内存泄漏。垃圾收集员只能收集垃圾。
可达性¶
每个程序都有一个引用根集合的概念。根集是保存在每个执行线程的堆栈上的引用列表。
需要一些编程语言和编译器支持，以确保垃圾回收器可以使用此列表。
改变可达性的操作：
分配-分配新对象创建新的可访问对象
方法“out”参数和返回值-从方法内分配返回的值仍可由调用方访问
引用复制-将引用从一个引用变量复制到另一个引用变量。
方法返回-当方法返回时，堆栈上不是返回一部分的所有引用都会丢失。
引用计数垃圾收集器¶
引用计数垃圾回收器的工作原理是检测对象的引用计数何时为零，并在此时释放该对象。参考文献以下列方式增加和减少：
分配-新对象以引用计数1开始
参数传递-当将参数传递给方法时，其引用计数会递增
引用分配-如果创建了引用的副本，引用计数将增加1
方法返回--当一个方法返回时，该方法堆栈上的所有引用的计数都会减1
传递性-如果对象的引用计数达到0，则它还会递减它引用的每个对象的引用。
参考计数垃圾收集器的利弊¶
优点
其实现非常简单。
缺点
头顶上有很多簿记。每次调用和返回方法时，每个参数和堆栈变量都必须额外接触一次。
引用计数无法收集无法访问的循环数据结构。
标记和清除垃圾数据收集¶
标记和清除收集器的工作方式是停止程序的执行，并使用算法来确定哪些对象不可访问，并将这些不可访问的对象返回到空闲列表。
该算法通过维护四个集合来工作
空闲列表-空闲内存区域的列表
根集合-所有执行线程和全局变量堆栈上的所有引用的列表。
引用列表-引用的对象的列表。
未扫描列表-尚未找到要引用的已分配对象的列表。
然后，该算法对根集合中的所有项进行深度优先搜索。如果在扫描中到达某个项目，则将其从未扫描列表中删除到引用列表中。
扫描完成后，未扫描列表中剩余的项目将作为垃圾移动到空闲列表。
标记和紧凑垃圾收集¶
压缩垃圾收集器采取额外的步骤，在收集后在内存中移动对象，以使空闲空间连续，并使分配的对象在内存中更接近彼此。
这些收藏家中最受欢迎的是复制收藏家。
复制收集器通过对收集时留出的连续可用内存区域执行复制操作，而不是将对象添加到引用列表，来修改标记和清除收集器算法。然后，在收集完成后，先前的内存区变为空闲内存区。
有关更多细节，请参阅ACM类库中C.J.切尼的一篇论文中的“切尼算法”。
垃圾收集成本¶
标记和清除收集器的成本与可访问对象的数量有关
压缩(复制)收集器的成本与可访问对象的总大小相关。
增量垃圾收集¶
前面提到的垃圾收集器停止执行程序中的所有线程以运行。这可能会导致程序暂停很长时间。
为了使程序保持响应，需要增量垃圾收集。
增量垃圾收集器不是收集所有垃圾，而是只收集可能无法访问的对象，而不执行标记和清除算法。
然后，在后续的收集中，收集器将能够收集以前的收集变得无法访问的对象，以及任何新无法访问的对象。
增量垃圾收集¶
为什么增量式垃圾收集器通常工作得很好？
对于大多数程序来说，对象很快就会变成垃圾。这意味着程序中的大多数分配在分配后不久就变得没有引用。
通常，迅速成为垃圾的对象数量在80%-95%之间。这些对象通常很容易被增量垃圾回收器以高速度收集
缺点是，在第一轮增量收集中幸存下来的对象通常会存活不止一轮。在复制增量收集器时，这意味着它们也将被复制多次。
分代垃圾收集¶
分代垃圾收集器是实现复制增量垃圾收集器的一种特定方式。
世代收集器将堆划分为N个部分。第0节是最老的，1是次最老的，...
当段0变满时，然后调用收集器并将可到达的对象复制到段1中，从而使整个段0空闲。
当任何1...N段变满时，同样的算法也会发生。
有时，会针对介于1和N之间的某个值i运行垃圾回收，以释放段1...N中的对象。
这种类型的收集速度非常快，因为它倾向于扫描最有可能成为垃圾的年轻对象。
分代垃圾收集¶
代式垃圾收集器在许多平台上使用-
爪哇
.NET
Python
买家要当心¶
即使使用先进高效的垃圾收集算法，在理论上仍有可能“泄漏”内存。
对象生存期定义不明确或保持引用太长时间的程序可能会积累将来永远不会引用的对象。
这样的程序将慢慢耗尽内存，而不会创建任何垃圾以供收集器回收。
同样重要的是要记住，使用增量/世代收集器，并不是每次都会收集所有垃圾。此外，由于成本的原因，其中一些收集器永远不会回收大对象(大于8KB)。在这些系统中，可能会人为地耗尽内存。