《操作系统导论》内存管理:地址空间

《操作系统导论》内存管理:地址空间

Tags
OS
Published
2022-12-25
Author
宿愿Cc
虚拟内存最主要的目标就是透明(transparency)。操作系统实现的虚拟内存,应该让程序看不见。程序以为它拥有私用的内存,从而让程序可以获得比实际物理内存更大的空间,但其实在幕后,操作系统(和硬件)做了很多工作,让它没有感知到内存被虚拟化的事实。
而实现虚拟内存的另一个目标是效率(efficiency)。操作系统应该追求虚拟化尽可能高效(efficient),包括时间(即不会使程序运行得更慢)上和空间(即不需要太多额外的内存来支持虚拟化)上。所以,在为了让虚拟化内存能够高效的工作,操作系统不得不需要硬件的支持,包括TLB这样的硬件功能
最后虚拟内存的第三个目标是保护(protetion)。操作系统应该确保进程受到保护,不会受到其它进程的影响,操作系统本身也不会收到进程的影响。一个进程中不应该以任何方式去影响其它进程的空间或者操作系统本身的内容。因此,保护让我们能够在进程之间提供隔离(isolation)的特性,每个进程都应该在自己独立的环境中运行,避免其它出错或恶意进程的影响。
 
notion image
实际上,作为程序员来说,我们所看到的所有内存地址都是虚拟地址(如C程序中打印指针的地址),只有操作系统通过精妙的虚拟化内存技术,才知道这些指令和数据所在的物理内存的位置。
 

内存操作API

 

malloc() 调用

malloc()调用需要传入申请堆空间的大小,分配成功的话,会返回一个指向新空间的指针,失败了就返回NULL。man手册中也可以看到malloc需要怎么做。
这里看到我们只需要包含 stdlib.h库,就可以使用malloc库了。但实际上我们甚至可以不这么做,因为C库是C程序默认链接的,其中就有malloc的代码,加上这个头文件只是让编译器检查你是否正确调用了malloc传参的数目及类型正确。
这个调用需要传入一个 size_t 类型的参数,这个参数是需要分配的内存大小,单位是字节,一般我们不会直接传入数字(比如10),这种方式是不推荐的。替代方式是使用各种函数和宏,如我们需要给一个双精度浮点数分配空间,只需要这样:
如果是为字符串声明空间,需要使用 malloc(strlen(s) + 1)+1是为了给结束符留下空间
 

free() 调用

free和malloc是成对使用的,free是用来释放不使用的内存的,这个函数接收一个参数,即一个有malloc返回的指针,知道何时释放内存是比分配内存是更困难的,如果要释放内存,只需如下:
这里我们也注意到了,free释放内存的时候是不需要传入内存的大小的,这是因为内存分配库它自己可以准确的追踪到需要释放多少内存。
通过调试器gdbvalgrind可以排查内存泄漏的问题
 

常见错误

在malloc和free的时候会出现一些常见的错误,后续的学习中我们可以看到,如分配内存时,没有空闲的内存可以分配了。
现在很多高级程序语言都支持自动内存管理(automatic memory management)。在这种语言中一般不会直接调用malloc(),会对其封装一层(通过用 new 或者类型的方式来创建一个新的对象),并且程序员也不需要关注何时释放它,因为垃圾收集器(garbage collector)会自动工作,找出不再引用的内存,替你释放它。
 

底层操作系统支持

我们刚刚在讨论malloc和free调用时,我们都没有提系统调用,原因很简单,它们并不是系统调用,它们只是库调用。malloc是建立在一些系统调用之上的,它会去使用brk系统调用,它可以改变程序分段的结束地址。
 

realloc调用:

void *realloc(void *ptr, size_t size);
可以重新分配一个空间(如数组)调整为新的空间大小。 如果 ptr 为NULL,则等价于 malloc(size)。 如果size为零,则等价于free(ptr)(前提是ptr不为NULL),它适合对数组扩容。
因为是对原有的空间进行调整,所以realloc也可以对原有的空间进行缩小,即通过size参数调整。如果要对原有的空间扩大的话,首先会先检查原内存段的后面空间是否足够,如果足够的话,则原地扩容,返回的依旧是原地址的指针。否则会重新找一块合适的内存,并将其地址指针返回。
 
Liunx中还有使用vmalloc和kmalloc,分别是虚拟地址空间连续和物理地址空间连续,物理地址空间连续的话,则虚拟地址空间也是连续的,对于需要进行DMA的设备来说很重要。
kmalloc最大可以分配 32 * PAGE_SIZE 的大小,一般PAGE_SIZE = 4KB,也就是kmalloc理论上最大可以分配128KB,但是这里需要再减去16KB,这是因为有16KB十倍页描述符结构使用了。
 

地址转换

为了让虚拟地址找到其对应的物理地址,我们可以通过采用两个硬件寄存器的方式来得到物理地址,基址(base)寄存器和界限(bound)寄存器,有时也被称为限制(limit)寄存器。通过这组寄存器,我们可以在编写程序的时候假设地址空间从零开始的,但是程序真正执行的时候,操作系统会通过加上基址寄存器的地址来获取真实的物理地址, 所有的内存访问都会转换成以下方式的物理地址。(它这个方式有点类似于,楼层+房间号)
早期还有软件的重定位方式,是通过一个加载程序(loader)的软件来接手要运行的可执行程序,将它的地址重写到物理内存中期望的偏移地址。 但是这种方式也有很多问题,首先是不提供访问保护,进程中错误的地址也可能会导致非法访问,一般来说,需要硬件支持来实现真正的真正的访问保护。
界限寄存器的作用就是用为了做访问保护的,当访问的内存地址超出这个界限时,进程则可能会被操作系统终止。
基址寄存器和界限寄存器是存在硬件结构芯片中的,它俩组合起来便可完成虚拟地址到真实地址的转换,因此它俩也被称为一个最基本的内存管理单元(Memory Management Unit, MMU)。它们会提供一些特殊的指令,使得操作系统能够修改它们的内容。
 
我们来看一个小例子,假设一个进程拥有4KB大小的地址空间,它被加载到物理内存16KB开始的位置。一些地址转换的结果如下
虚拟地址
物理地址
0
16KB
1KB
17KB
3000
19384
4400
错误(越界)
空闲列表 操作系统会记录内存中未被使用的内存块,用来给新进程进来时分配内存,有多种数据结构可以来实现这个功能,其中最简单的就是空闲列表(free list),它就是一个列表,用来记录没有被使用的物理内存范围。
 
下图展示了大多数硬件和操作系统的交互
notion image
但是基址寄存器和界限寄存器同时会带来一些问题,即预先需要给程序分配一个内存,即使程序目前刚启动,可能还用不了这么大的内存,但是依旧需要先分配好。
 

分段

分段的出现就是为了解决程序还未使用那么大的空间,但是需要预先分配这些空间,如下图所示,堆和栈之间有大量的空闲空间
notion image
注意看下图左侧是虚拟内存,右侧是物理内存,在物理内存中将程序分为 代码段,栈段,堆段,同时MMU(内存管理单元)一共需要3组基址和界限寄存器来提供支持,在图最下方有所体现
notion image
我们可以看到段寄存器的值,代码段的基址地址处于物理内存32KB的位置,大小是2KB,堆的基址是34KB,大小是2KB,栈的基址位于28KB,大小也是2KB
如果我们需要对虚拟地址100进行引用(100处于代码段),那么则会将100+32KB(100+32768) = 32868得到地址是32868,这个地址没有超出代码段的范围,则会对这个地址发起内存引用。
再来看一个例子,如果我们对一个虚拟内存4400(堆地址)发出内存访问,因为堆的虚拟地址是从4096开始的,那么4400-4096=304,得到这个地址位于堆地址的304,再用物理地址的基址加上它304+34KB(34816)=35120,这个地址也没有超出堆的界限。
段错误 有一个经典的错误就是段错误,在x86-64中,这个错误是11号错误,这个错误是指在支持分段的机器上发生了非法的内存访问。但现在很多不支持分段的机器依旧有保留这个术语
 

如何区分引用的是哪个段

有一种显式(explicit)方式,采用地址的开头几位来标识不同的段,如一个14位的地址,通过开头两位来区分,如果开头是00,那么引用的是代码段,如果开头是01,则表示引用的是堆段
notion image
如堆地址 4200,对应的2进制是01000001101000,开头前两位是01,则表示引用的是堆段
notion image
 

栈如何区分

栈有些不太一样,栈是反向增长的,在我们的例子中,它是从28KB的位置增长到26KB的,所以硬件还需要知道段的增长方向,因此需要增加一个字段来标识。
段寄存器的值(支持反向增长)
基址
大小
是否反向增长
代码
32KB
2KB
1
34KB
2KB
1
28KB
2KB
0
假设要访问虚拟内存15KB,可以这样换算,16KB-15KB=1KB,28KB-1KB=27KB,所以对应到物理地址应该是出于27KB的位置。
还有一种方式可以换算,15KB对应的二进制是11 1100 0000 0000,舍去前2位(前两位是用来确定段的),那么 1100 0000 0000转换到10进制就是3072也就是3KB,而1111 1111 1111转换到10进制是4096,然后3072-4096 = -1024, 28KB + -1024 = 27KB (28672 + -1024 = 27645)
 

支持共享

随着分段机制的不断改进,系统设计人员很快意识到,通过增加一点硬件支持,就可以实现新的效率提升,尤其是代码共享很常见,今天的系统任然在用。
为了支持共享,需要一些额外的硬件支持,这就是保护位(protection bit),每个段都增加了一个保护位,标识程序是否有权限能够读写该段。
段寄存器的值(有保护位)
基址
大小
是否反向增长
保护
代码
32KB
2KB
1
读-执行
34KB
2KB
1
读-写
28KB
2KB
0
读-写
有了保护位之后,硬件算法除了要判断虚拟地址是否越界外,还要检查特定访问是否运行。
 

操作系统支持

分段也带来了一些问题,第一个问题就是操作系统在上下文切换的时候,各个段寄存器的值都必须保存和恢复。
第二个问题更重要,即管理物理内存的空闲空间,操作系统运行的越来越久后,会产生大量的外部内存碎片(external framentation)。
虽然内存中依旧还有很多的空间,但是没有合适的空间能够进行分配,因为都是碎片化的。如下左图中需要分配一个20KB的的段,明明还有24KB的空闲空间,但是就是没办法分配出来。
notion image
或者可以通过一些方式让内存变成紧凑(compact)的内存,即操作系统先终止运行的进程,将它们的数据复制到连续的内存区域去,然后修改段寄存器的值,指向新的物理地址。但是让碎片内存变成紧凑内存的话是需要消耗大量CPU资源的。
还有更简单的做法是利用空闲列表管理算法,相关的算法可能有成百上千种,
如最优匹配(best-fit, 从空闲链接中找最接近需要分配空间的空闲块), 最坏匹配(worst-fit)、 首次匹配(fist-fit) 以及像伙伴算法(buddy algorithm)这样更复杂的算法。
但是这些算法都无法完全消除内存碎片,因此,好的算法也只是试图减小它。
当有一千种解决方案的时候,那就没有最好的解决方案 当一个问题有很多种解决方案的话,那就说明没有特别好的解决方案,最好的解决方案就是,完全避免这个问题,永远不要分配不同大小的内存块。