[TOC]
内存介绍
虚拟化内存
设计目标
目标:
透明
, 这里指运行的程序感知不到内存被虚拟化的事实,相反,程序的行为就好像它拥有自己的私有物理内存。效率
这里依赖硬件。譬如TLB
, 主要消耗是虚拟地址转为实际物理地址。保护
即程序不能访问它的地址空间之外的任何内容。从而也实现了隔离。
用户看的内存地址都是虚拟地址。(这里指cpu运行在虚模式,而不是实模式下)。
用户程序地址空间分布示例:(这种放置方法只是一种约定)
内存种类
如上所见,有2个内存分配区域,堆和栈。
这是由内存的生命周期决定的。
在函数调用中,函数调用结束,内存就自动释放,所以也叫自动内存,被分配在栈上,都是临时使用的。
当无法确定内存的使用周期时,只能由程序员管理,由程序员来主动申请和释放,这种就分配到堆上。
内存分配库 提供malloc
和free
对应申请/释放内存。
操作系统提供的接口是brk
、sbrk
、mmap
。
内存申请,初始化,释放 管理需要很仔细。否则很容易出现运行时的段错误。这是C语言被认为难写的主要原因。
地址转换
由硬件+操作系统共同协作
- 硬件:将虚拟地址转换成实际的物理地址
- 操作系统:需要记录管理被占用和空闲的内存位置。
负责地址转换硬件设施又被称为内存管理单元(MMU)
基址寄存器+界限
硬件要求
硬件要求 | 解释 |
---|---|
特权模式 | 防止用户模式的进程执行特权指令 |
基址/界限寄存器 | 每个CPU需要一对寄存器来支持地址转换和越界检查 |
能够转换虚拟地址并检查它是否越界 | 电路来完成转换和检查界限 |
修改基址/界限寄存器的特权指令 | 在让用户程序运行前,操作系统必须能够设置这些值 |
注册异常处理程序的特权指令 | 操作系统必须告诉硬件,如果异常发生,那么执行哪些代码 |
能够触发异常 | 如果进程试图使用特权指令或越界的内存 |
操作系统的职责
操作系统的要求 | 解释 |
---|---|
内存管理 | 需要为新进程 从终止的内存回收内存 一般通过空闲列表来管理内存 |
基址/界限管理 | 必须在上下文切换时正确设置基址/界限寄存器 |
异常处理 | 当异常发生时执行的代码,可能的动作是终止犯错的进程 |
基址寄存器+界限 的方式实现简单,但有个以下问题:
- 由于是将进程的地址空间完整地加载到内存中,在堆和栈之中就大量的内存浪费。这叫内部碎片。
- 如果剩余物理空间无法提供连续区域来放置完整的地址空间,进程便无法运行
解决办法就是 把 进程的地址空间分开。
分段
最自然的分段就是 分成 代码段、堆段、栈段。
自然也就避免了 堆和栈之间的内存浪费。
这需要硬件的支持,原来是一个进程一对基址/界限对,现在需要每个段一对基址/界限对。
如何知道虚拟地址引用的哪个段?(从而正确引用相应的基址/界限对)
- 放在虚拟地址中,譬如前2个位 用于存段的标识。
- 隐式指明。地址由程序计数器产生,说明是代码段。基于栈或基址指针,说明是栈段。其他为堆段。
由于段和栈的增长方向不一样,检查方式也不一样,所以需要引入 增长方向的标识。
子进程和父进程代码段是一样的,完全可以共享,从而节省内存。于是可以进一步引入保护位。
段寄存器的值(有保护)
段 | 基址 | 大小 | 是否反向增长 | 保护 |
---|---|---|---|---|
代码 | 32KB | 2KB | 1 | 读-执行 |
堆 | 34KB | 2KB | 1 | 读-写 |
栈 | 28KB | 2KB | 0 | 读-写 |
简单分为代码/堆/栈 是种粗粒度的划分,还有种细粒度的划分,这需要进一步的硬件支持,并在内存中保存某种段表。
事实上,即便分段,也无法避免内存碎片。当无使用的内存空间小到无法放入 段时,便产生了外部碎片。
有2中方案处理:
- 内存紧凑法:就是重新放置内存,这需要复制和移动,很耗CPU
- 采用更好的算法,减小碎片: 最优匹配,最坏匹配,首次匹配,伙伴算法。都只能减小,不能避免。
空闲空间算法说明
如果管理的都是固定大小的内存块,算法简单而高效,切不会产生碎片。
如果管理的是不定长的内存块,问题复杂很多。
内存分配库 提供malloc
和free
对应申请/释放内存。
注意到malloc有个size_t
参数指明内存大小,但是free
只有一个指针,那么free怎么知道需要释放多大的内存呢?
实际上malloc申请的空间不只是size_t那么大小, 而是size_t + sizeof(header_t)
typedef struct header_t {
int size;
int magic;
} header_t;
在返回给用户的指针前还有个header_t 的内存,size指明了分配内存的大小。
于是通过(void*)ptr - sizeof(header_t)
获取真正的指针,通过size就可以知道需要释放的内存是多少了。
magic 是为了避免内存为覆盖的。。如果magic 值和预期的不符,就说明这块内存被异常覆盖了。
还有空闲空间管理有点类似,需要管理空间空间需要数据结构支持,这个数据结构也要存到内存里。
其结构大致如下:
typedef struct node_t {
int size; //剩余空间
struct node_t *next;//下一块空闲空间
} node_t;
也就是说100KB的剩余空间其实不能分配出去100KB,而是100KB- sizeof(node_t)。
空间的分隔与合并没啥好说的,很自然。
譬如有100KB剩余空间时,只申请30KB, 我当然是分隔成30KB+70KB, 然后只分配出去30KB, 这叫分隔。
当30KB释放时,如果和70KB相邻,我当然得合并,这样才能满足70~100KB的内存申请需求,这叫合并。
查找可用空间时,常规算法有:
- 最优匹配:就是遍历所有可用空间,看谁最小。优点:浪费的空间最小。缺点:需要遍历一次,同时分配后剩余的空间太小,容易产生碎片。
- 最差匹配:为了解决最优匹配的碎片问题。同样是遍历所有可用空间,看谁最大。优点:选的最大的,剩余空间仍然够大,不容易产生碎片。缺点:同样需要遍历,实际产生的碎片过多。
- 首次匹配:使用遍历时遇到的一个满足需求的块。优点:性能高。缺点:碎片集中在头部,因为都是从头开始遍历。
- 下次匹配:针对首次匹配的,不是从头开始遍历,而是记住上一次遍历完的位置,接着上次的位置开始遍历。和首次匹配性能差不多。
其他算法:
- 预分配:这个和memcache很像,先预分配256,512,1024等大小的内存块。当申请固定大小的内存块时,就用这些,否则就用常规的分配算法。
- 伙伴算法:只分配2的倍数的内存块。譬如有64kb, 需要申请7KB, 64->32->16->8, 64KB一直1分为2, 当分到8KB时,分配出去。当回收时,如果伙伴也是空闲的那么合并为16KB。其优点就是合并算法容易,一直递归上去就好了。
分页
如前所述,分段是把内存分成不定长的内存,不论用什么算法,都避免不了内存外部碎片。
而把内存分成固定大小的段,问题就简单多了。这就是分页。
分页带来了2个好处:
- 内存管理简单,不会产生外部碎片
- 更灵活。譬如不用再假设堆和栈的增长方向,以及他们如何使用。
相应地他也带来了虚拟地址转换的挑战。
譬如操作系统必须为每个进程存一个页表。
可以简单地把也变看成一个数组。
索引就是虚拟的页编号(VPN)
内容就是页表项,页表项就是一个字节。
譬如32位的字节,
其中前N为是实际的物理地址页编号。(PFN)
后面的位也有作用:
- 有效位: 表明是否已使用。如果未使用,就没必要分配实际的物理地址。也就是PFN是无效的
- 保护位:表明页是否可以读取、写入或执行。以错误的方式访问会陷入操作系统。
- 存在位:表示该页是在物理存储器还是在磁盘上。swap技术时使用
- 脏位:表明页面被带入内存后是否被修改过。如果被修改过,把页重新置入磁盘时需要写磁盘,否则没必要。
- 参考位/访问位:用于追踪页是否被访问,以及确定哪些页很受原因。用于置换页时参考。
譬如32位的机器上,有4GB的地址空间( $ 2^{32} $ ), 假设一页大小是4KB(
一个32位的地址,前20位为虚拟地址空间,后12位为偏移量。
从进程的页表里 找到对应的页表项,如果页表项有效,就提取PFN, 加上偏移量就得到了实际的物理地址。
从这里其实也看出了分页的问题:
- 太占内存。每个进程需要
(4MB)大小的页表项。在基址寄存器+界限中 只有1对。分段中只有3对,这里一下增长到了 。 - 计算慢。需要访问页表,然后根据虚拟地址计算VPN, 然后从页表中找到页表项,提取PFN, 再转换成实际物理地址。 访问页表本身也是一次内存访问。
关于计算慢,主要是每次指令读取/内存读写 都需要访问页面,而页表本身是存在内存的。
对比 分段 是用到的寄存器,自然就慢多了。
寄存器的读写速度远远大于内存访问。
所以优化方向就是避免内存访问,而这又是缓存发挥作用的时候,只是这个缓存是硬件来实现的。
他的名字是地址转换旁路缓冲存储器 ( translation-lookaside buffer,TLB)
支持分页的硬件TLB
tlb 成功的关键原因是 局部性规律。
- 时间局部性: 最近访问过的指令/数据项可能很快会再次访问。
- 空间局部性:当程序访问内存地址x时,可能很快会访问邻近x的内存。
既然是缓存,就一定有未命中的情况,谁负责处理呢?
- 1种可能是硬件,譬如CSIC指令集中。(Complex Instruction Set Computer)
- 1种可能是软件,即操作系统。譬如在RSIC指令集中(Reduced Instruction Set Computer)
通过操作处理未命中时有个细节, 在常规的陷入操作系统时,操作系统处理完后,进程继续执行下一个指令。
而在TLB为命中时,则是重试原来的指令。(这里也要注意未命中的无限递归问题)
TLB的内容 为 VPN | PFN | 其他位。
由于TLB缓存的内容只对当前进程有效,那么在进程切换时怎么办呢?
可能的策略是:
- 直接清空TLB。 这种其实不太好,切换回来TLB就未命中了。TLB命中率高不了
- 共享TLB。增加位来表示进程号。其名为ASID, 一般为8位。同时需要寄存器存下当前进程的ASID。
缓存还有一个问题,就是大小,超过缓存大小咋办?这时候需要置换了,写入新缓存时,要去掉老的缓存。
如何替换:
- 最近最少使用 (LRU)
- 随机选择
有了TLB, 在软件处理未命中时,显然也需要硬件提供指令 给 操作系统使用。
TLB解决了分页过慢的问题,但是没解决分页太占内存的问题。
分页之所以太占内存是线性结构问题。
譬如 32位,1页4kb的话,还有20位。而一个页表项4字节。那么有
显然问题是页表项过多。如何解决呢?
2个方向:
- 增加页的大小,
- 不用线性结构,换其他结构。
分页:较小的表
方案1: 更大的页
增加页大小确实能降低页表项,1页改成16Kb, 页表项变成
但是页太大了,容易产生内部碎片。仅适应数据库等特殊应用。
混合使用分段+分页
具体方案是 单个进程不再有完整的页表。
而是有3个段,代码段、堆、栈。然后每个段分配页表。
段的基址寄存器+界限 改为记录 物理页帧和也页表打小。
虚拟地址结构 改为 Seg | VPN | Offset。
这样我们就不用为未分配的内存 分配页表项了,从而大大减小了页表。
但分段本身的问题也还存在:
- 不够灵活,得假设地址空间的使用模式
- 如果堆是大二稀疏的,仍然会产生大量的外部碎片。会浪费页表项。
多级页表:最有效
线性结构是问题的根源,把线性结构分级不就可以了。
这就像原来一个目录里有
现在我们把目录改成多级目录。譬如2级目录。第一级目录有
如果某个目录项里的文件都是无效的。那么整个目录标识为无效,不再分配文件,于是就能节省
无效的目录项越多。节省的空间越多。
实际的设计目标是为了让 页表 的每一部分都能放入一个页。
举个例子:
有30为的虚拟地址空间,然后页大小为512字节。
那么虚拟地址为
如果采用二级结构,假设PTE为4字节,那么一页能存放 512/4 = 128 =
这样 就有
得再拆。
一级页目录 包含
二级页目录包含
三级页目录 包含
每一级刚好包含一页。
现在vpn的表示法是
1级页目录 | 二级页目录 | 三级页偏移 | offset
但是多级页表也是有代价的,他增加了TLB未命中时的复杂性,需要多次加载内存。。有几级就要加载几次。
反向页表。
原来之所以浪费空间是因为 有太多的页其实没有使用。
如果反过来。记录物理页帧->虚拟页 的映射。。也就是只记录分配了内存的页。是不是好很多呢?
这就是反向页表。由于索引是物理页帧,也就可以只存一个页表就够了。(而不是每个进程一个)
交换到磁盘
页表不咋访问时,不如交换到磁盘。降低内存压力。
超出物理内存
机制
为了支持更大的地址空间(大到可以超越物理内存),操作系统需要把当前没有在用的那部分地址空间找个地方存储起来,这个地方一般是硬盘,取名叫交换空间。
多道程序和易用性都需要操作系统支持比物理内存更大的地址空间。
交换空间:硬盘上开辟一部分空间专门用于物理页的移入和移除。他的大小决定了操作系统在某一刻能够使用的最大内存页数。
为了支持交换空间,PTE需要增加位 记住 硬盘地址。
当内存紧张时,可以
- 置换内存页 到硬盘上的交换空间。
- 大的二进制程序,可以按页加载。当内存紧张时,可以释放内存页,需要时再从二进制程序中读取。
更新内存访问流程
- 从虚拟内存中提取VPN
- 在TLB中通过VPN查找
- 命中,获取tlbEntry。能否访问?
- 不能访问。排除 保护异常。进程中断。End
- 能访问。访问内存。End
- 未命中。通过VPN计算PTE的内存地址并访问。PTE是否有效?
- 无效。抛出异常。End
- 有效。是否能访问?
- 不能访问。排除 保护异常。进程中断。End
- 能访问。是否在内存中?
- 不在,抛出页错误。End. 交给操作系统,从硬盘上加载物理页。然后回来重试指令。
- 在。插入TLB, 重试。End
- 命中,获取tlbEntry。能否访问?
为了保证有少量的空闲内存,大多数操作系统会设置2个值:
- 高水位线。HW
- 低水位线。LW
当可以物理内存页 低于LW时,交换物理内存到硬盘上,知道有HW页可用。
这个后台进程叫 交换守护进程(swap daemon) 或 页守护进程(page daemon)。
替换策略
没有空闲内存页可用时,需要踢出某个页到硬盘上,以空出内存页。选择踢哪个就叫替换策略。
虚拟内存 -> 实际内存 -> 物理硬盘。
从这个视角看,空闲内存页其实就是一个缓存系统。
那么替换策略就是为了提高命中率。(由于硬盘的读写速度远低于内存,所以哪怕提升一点命中率,性能提升也很明显)
常用的有:
- FIFO.实现最简单
- 随机替换
- LRU( 最近最少使用) 基本都是使用这个算法。
参考算法是 替换最远将来才会被访问的页。(最优策略,无法实现)
考虑到程序的局部性特征, LRU是最接近 最优策略的。但是LRU需要扫描所有页,这个消耗很大。
实际上 使用近似 LRU算法(又叫时钟算法:
- 在内存页载入时,使用位设置为1(使用位又叫引用位,可能在进程的页表中,也可能在某个数组中)
- 所有页组成一个环,然后操作系统扫描。遇到1时表示有使用,改成0.继续扫描。直到遇到第一个为0的页。选择他替换掉。
设置为0的目的是 避免重复扫描。这样最差的情况只需要扫描一次。
考虑到如果内存页在载入后如果被修改(脏位),那么替换出去时,就得写入硬盘,多了次I/O操作。
所以在扫描时优先扫描 没被访问且不脏的页替换掉。
在写入硬盘时,因为硬盘有磁头寻道的问题。。聚合写入性能更高,常常把多个写磁盘操作 聚合到一起写入。这样可以提高整体性能。