开发者社区> auqbllxiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

内存都没了,还能运行程序?(三)

简介: Java建设者
+关注继续查看
  • 堆(heap):

可读可写

存储的是程序运行期间动态分配的 malloc/realloc 的空间

堆的生存期随进程持续性,从 malloc/realloc 到 free 一直存在

下面是我们用 Borland C++ 编译过后的结果

_TEXT    segment dword public use32 'CODE'
_TEXT    ends
_DATA    segment dword public use32 'DATA'
_DATA    ends
_BSS    segment dword public use32 'BSS'
_BSS    ends

段定义( segment ) 是用来区分或者划分范围区域的意思。汇编语言的 segment 伪指令表示段定义的起始,ends 伪指令表示段定义的结束。段定义是一段连续的内存空间


所以内存针对自动增长的区域,会有三种处理方式

  • 如果一个进程与空闲区相邻,那么可把该空闲区分配给进程以供其增大。
  • 如果进程相邻的是另一个进程,就会有两种处理方式:要么把需要增长的进程移动到一个内存中空闲区足够大的区域,要么把一个或多个进程交换出去,已变成生成一个大的空闲区。
  • 如果一个进程在内存中不能增长,而且磁盘上的交换区也满了,那么这个进程只有挂起一些空闲空间(或者可以结束该进程)

40.jpg

上面只针对单个或者一小部分需要增长的进程采用的方式,如果大部分进程都要在运行时增长,为了减少因内存区域不够而引起的进程交换和移动所产生的开销,一种可用的方法是,在换入或移动进程时为它分配一些额外的内存。然而,当进程被换出到磁盘上时,应该只交换实际上使用的内存,将额外的内存交换也是一种浪费,下面是一种为两个进程分配了增长空间的内存配置。

41.jpg

如果进程有两个可增长的段,例如,供变量动态分配和释放的作为堆(全局变量)使用的一个数据段(data segment),以及存放局部变量与返回地址的一个堆栈段(stack segment),就如图 b 所示。在图中可以看到所示进程的堆栈段在进程所占内存的顶端向下增长,紧接着在程序段后的数据段向上增长。当增长预留的内存区域不够了,处理方式就如上面的流程图(data segment 自动增长的三种处理方式)一样了。


空闲内存管理


在进行内存动态分配时,操作系统必须对其进行管理。大致上说,有两种监控内存使用的方式

  • 位图(bitmap)
  • 空闲列表(free lists)

下面我们就来探讨一下这两种使用方式

使用位图的存储管理

使用位图方法时,内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位,0 表示空闲, 1 表示占用(或者相反)。一块内存区域和其对应的位图如下

42.jpg

图 a 表示一段有 5 个进程和 3 个空闲区的内存,刻度为内存分配单元,阴影区表示空闲(在位图中用 0 表示);图 b 表示对应的位图;图 c 表示用链表表示同样的信息

分配单元的大小是一个重要的设计因素,分配单位越小,位图越大。然而,即使只有 4 字节的分配单元,32 位的内存也仅仅只需要位图中的 1 位。32n 位的内存需要 n 位的位图,所以1 个位图只占用了 1/32 的内存。如果选择更大的内存单元,位图应该要更小。如果进程的大小不是分配单元的整数倍,那么在最后一个分配单元中会有大量的内存被浪费。

位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况,因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题是,当决定把具有 k 个分配单元的进程放入内存时,内容管理器(memory manager) 必须搜索位图,在位图中找出能够运行 k 个连续 0 位的串。在位图中找出制定长度的连续 0 串是一个很耗时的操作,这是位图的缺点。(可以简单理解为在杂乱无章的数组中,找出具有一大长串空闲的数组单元)


使用链表进行管理


另一种记录内存使用情况的方法是,维护一个记录已分配内存段和空闲内存段的链表,段会包含进程或者是两个进程的空闲区域。可用上面的图 c 来表示内存的使用情况。链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志,长度和下一个链表项的位置。

在这个例子中,段链表(segment list)是按照地址排序的。这种方式的优点是,当进程终止或被交换时,更新列表很简单。一个终止进程通常有两个邻居(除了内存的顶部和底部外)。相邻的可能是进程也可能是空闲区,它们有四种组合方式。

43.jpg

当按照地址顺序在链表中存放进程和空闲区时,有几种算法可以为创建的进程(或者从磁盘中换入的进程)分配内存。我们先假设内存管理器知道应该分配多少内存,最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描,直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样,否则将空闲区分为两部分,一部分供进程使用;一部分生成新的空闲区。首次适配算法是一种速度很快的算法,因为它会尽可能的搜索链表。

首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同,只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置,以便下次寻找空闲区时从上次结束的地方开始搜索,而不是像首次匹配算法那样每次都会从头开始搜索。Bays(1997) 证明了下次算法的性能略低于首次匹配算法。

另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表,找出能够容纳进程的最小空闲区。最佳适配算法会试图找出最接近实际需要的空闲区,以最好的匹配请求和可用空闲区,而不是先一次拆分一个以后可能会用到的大的空闲区。比如现在我们需要一个大小为 2 的块,那么首次匹配算法会把这个块分配在位置 5 的空闲区,而最佳适配算法会把该块分配在位置为 18 的空闲区,如下

44.jpg

那么最佳适配算法的性能如何呢?最佳适配会遍历整个链表,所以最佳适配算法的性能要比首次匹配算法差。但是令人想不到的是,最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存,因为它会产生大量无用的小缓冲区,首次匹配算法生成的空闲区会更大一些。

最佳适配的空闲区会分裂出很多非常小的缓冲区,为了避免这一问题,可以考虑使用 最差适配(worst fit) 算法。即总是分配最大的内存区域(所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧),使新分配的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。

如果为进程和空闲区维护各自独立的链表,那么这四个算法的速度都能得到提高。这样,这四种算法的目标都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度,因为必须将一个回收的段从进程链表中删除并插入空闲链表区。

如果进程和空闲区使用不同的链表,那么可以按照大小对空闲区链表排序,以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时,只要找到一个合适的空闲区,则这个空闲区就是能容纳这个作业的最小空闲区,因此是最佳匹配。因为空闲区链表以单链表形式组织,所以不需要进一步搜索。空闲区链表按大小排序时,首次适配算法与最佳适配算法一样快,而下次适配算法在这里毫无意义。

另一种分配算法是 快速适配(quick fit) 算法,它为那些常用大小的空闲区维护单独的链表。例如,有一个 n 项的表,该表的第一项是指向大小为 4 KB 的空闲区链表表头指针,第二项是指向大小为 8 KB 的空闲区链表表头指针,第三项是指向大小为 12 KB 的空闲区链表表头指针,以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中,也可以放在一个专门存放大小比较特别的空闲区链表中。

快速匹配算法寻找一个指定代销的空闲区也是十分快速的,但它和所有将空闲区按大小排序的方案一样,都有一个共同的缺点,即在一个进程终止或被换出时,寻找它的相邻块并查看是否可以合并的过程都是非常耗时的。如果不进行合并,内存将会很快分裂出大量进程无法利用的小空闲区。


            </div>

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
程序员需要了解的硬核知识之内存(三)
我们都知道,计算机是处理数据的设备,而数据的主要存储位置就是磁盘和内存,并且对于程序员来讲,CPU 和内存是我们必须了解的两个物理结构,它是你通向高阶程序员很重要的桥梁,那么本篇文章我们就来介绍一下基本的内存知识。
8 0
程序员需要了解的硬核知识之内存(三)
我们都知道,计算机是处理数据的设备,而数据的主要存储位置就是磁盘和内存,并且对于程序员来讲,CPU 和内存是我们必须了解的两个物理结构,它是你通向高阶程序员很重要的桥梁,那么本篇文章我们就来介绍一下基本的内存知识。
9 0
程序员需要了解的硬核知识之内存(三)
我们都知道,计算机是处理数据的设备,而数据的主要存储位置就是磁盘和内存,并且对于程序员来讲,CPU 和内存是我们必须了解的两个物理结构,它是你通向高阶程序员很重要的桥梁,那么本篇文章我们就来介绍一下基本的内存知识。
14 0
程序内存分区
程序内存分区
42 0
程序员需要了解的硬核知识之内存(三)
我们都知道,计算机是处理数据的设备,而数据的主要存储位置就是磁盘和内存,并且对于程序员来讲,CPU 和内存是我们必须了解的两个物理结构,它是你通向高阶程序员很重要的桥梁,那么本篇文章我们就来介绍一下基本的内存知识。
35 0
理解程序内存
内存对很多人来说感觉是个很熟悉的东西,因为我们在用VC调试程序时,很多时候都会察看内存中变量的值。但是,很多时候我们的思维也就因此局限在有源码的模块,当遇到一些跨模块或是没有源代码的Bug,我们还是无从下手。
835 0
+关注
3110
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载