操作系统概念——内存管理

第八章 内存管理
8.1 相关背景
从硬件角度来看,首先需要解决主存读取速度问题.
访问内存比寄存器等指令慢很多,所以会造成瓶颈,主要通过cache来缓解,另外还有超线程调度等手段.
其次硬件要解决地址保护问题,防止用户进程访问到内核或其他进程等非法地址.
一个简单的办法是通过设置base和limit寄存器来限定用户态访问范围,好处是简单快速.
而内核态代码运行在特权级别下,一般是没有访问地址限制的. base和limit也只能由内核设置.
如果发生了访问违规,硬件会产生一个中断提交给操作系统做错误处理.

动态地址绑定:
程序加载为进程时,一般可以加载到内存的任意地址.
进程的实际运行地址的绑定可以在编译、加载(链接)、运行时指定.
为了避免重新编译、链接和加载,一般是运行时动态绑定地址(运行过程中可变).
运行时地址绑定即逻辑地址(虚拟地址)到物理地址的映射,一般通过MMU硬件进行.

动态加载:
即在需要的时候才加载到内存执行,目的是节省内存.
如大量很少访问的异常处理代码/数据.
一般不需要操作系统的特殊支持.

动态链接和共享库:
运行时才做符号地址解析(链接),目的是节省磁盘和内存(共享),以及更新共享库更方便.
更新共享库不用重新链接;更新的共享库和调用方可以指定版本tag,因此多版本可以共存.
共享库系统一般需要操作系统的支持,因为需要跨进程共享和装载等特权行为.

8.2 Swapping
Swapping将空闲的进程换出到外存,腾出内存,使得进程总物理内存可以超过系统物理内存大小.
标准的Swap模型以进程整体为单位,内存占用较大时切换开销会比较高.
如果进程有Pending IO操作,则一般不参与换出防止IO写入地址错乱,或者让内核先接着,
换入时再copy一次数据到用户空间,但这样引入了双重拷贝的开销.
实际操作系统一般实现的是标准Swap的变体,比如剩余内存较低时才启动Swap,或者只Swap出进程一部分.
一般Swap机制与虚拟内存机制一起工作.

移动设备操作系统一般不直接实现Swap,原因是闪存空间比较小,内存和闪存之间数据吞吐也较低,
以及闪存设备一般有最大可写次数的限制;当内存较低时,也有其他类似机制替代Swap.
IOS会尝试让进程主动释放一些内存,只读数据如代码空间会被释放掉(而非换出),后面需要时再重新加载.
如果进程释放的空间不够IOS可能会将其终止.
Android系统与IOS类似,但在终止之前会保存一些状态到闪存方便其快速重启.
所以移动设备开发需要更加注重内存的使用.

8.3 连续内存分配
即进程占用的内存是连续的,系统按整体分配内存.
早期一些采用将内存切成固定大小的块整体分给进程,整体归还,则并发能力为分块数.
另一种方法是变长块分配,即经典的动态内存分配,first-fit/best-fit/worst-fit等方案.
从空间利用率上看first-fit和best-fit要比worst-fit好,而first-fit比best-fit更快.
动态分配有外部碎片和内部碎片的问题:
外部碎片指所有空间块总量足够大,但因为分散不连续,可能无法利用上;
研究表明即使做了优化外部碎片也可能达到总量的1/3.
内部碎片指系统是按最小blocksize分配,因此内部会有部分剩余空间是无用的.
碎片问题在存储管理等其他方面也经常遇到.
解决内部外部碎片的一个方法是定期做内存整理,但开销较大.
另一个方案是允许进程占用不连续的空间,如分段/分页管理.

8.4 分段
从开发者视角将代码、数据等对象按段为单位组织,段内是连续空间,
每个对象相对段的起始位置有一个偏移d,段与段之间逻辑上没有顺序关系,可以不连续.
因此一个对象的逻辑地址可以表示为<段号,段内偏移>二元组.
硬件基于段表将逻辑地址翻译为物理地址:
segmentation_mappming
段表内容是(base,limit)二元组,前者对于段物理起始地址,后者对应段的长度.
翻译时段号s作为段表下标查询,检查d小于limit,最后将base+d作为对象的物理地址.
分段允许进程空间不连续,但没有解决外部碎片问题,因为段内空间依然是要求连续分配的.

8.5 分页
页模型下,进程的逻辑地址空间被切位等大小的地址块称为页(page),同时物理内存也按此大小切分为帧(frame),
进程执行时,其页被映射加载到任意可用的帧上. 同时底层存储如磁盘也按页大小切为块管理,方便swap等活动.
页模型的好处是逻辑地址和物理地址完全独立,进程空间视图变得统一.
页表(page table)维护地址映射的相关信息,其每项内容是某页对应的的帧地址(序号).
在简单分页模型下,逻辑地址分为页编号和页内偏移地址两部分,前者作为页表的下标查找到帧后加上偏移称为实际物理地址.
通过利用空闲的帧可以解决外部碎片问题,但平均会产生半个页大小的内部碎片.
因此页的大小越小内部碎片也越小,但会增大页表. pagesize总体上是增大的趋势.
通过增大页号范围,分页还可以用来支持比实际物理内存更大的寻址空间.
操作系统负责对帧的管理(frame table),记录哪些帧被什么进程占用.
页表是进程上下文的一部分,需要参与上下文切换过程. 有些系统通过共用页表降低开销.

硬件上如何组织:
页表项较少时(<256),可以用寄存器实现;但现代系统页表一般较大,会放在主存里,由PTBR寄存器存储其地址, 这样切换页表仅需修改寄存器内容;但是每此都去内存查询页表代价太大,因此一般会有专门的高速缓存来加速查找, 即translation look-aside buffer(TLB). TLB是内置在cpu指令流水线中的一部分,因此不会产生额外的开销,但也因此大小收到限制,当前一般<1024个条目. 系统可以区分指令TLB和数据TLB,以及引入多级TLB来保证命中率. 一些TLB支持带ASID查找,即进程的标示也参与匹配,否则可能每次切换用户进程要刷新TLB. TLB的硬件特性对系统性能有较大影响,操作系统一般需要配合参照其设计. 示意图: paging_hardware_with_tlb

内存保护:
一般页表项中有一些bit位用于内存保护,如指定可读、可写、可执行等权限.
违规访问会给系统提交一个异常中断,一般会导致进程终止.
另一个bit是valid表示位,表示该进程是否拥有该页内存(是否已分配).
但由于内部碎片的问题可能产生实际未分配的碎片区域.
一般的进程只需要很少的页表项,因此判断时可以先用PTLR长度寄存器来过滤范围.

内存共享:
以页为单位可以实现内存共享,如可重入的纯逻辑代码.
好处是节省内存或者用于进程间通信.
一般需要操作系统设置管理响应的权限位.

8.6 页表组织架构
1)多级页表
即将页表本身组织为页的内容,多级索引串联起来:
hierarchical_paging

好处是从第一级开始,大量没分配的页不会有记录,降低了存储大小. (但还是会存在一些invalid项)
缺点是地址空间很大时,需要的级数较多,TLB miss下访问内存的次数也会变多.

2)哈希页表
以页编号为key,帧地址为value的哈希表,并考虑冲突情况:
hashed_page_table
其实多级页表本质上也是一类多级哈希方式,只是每层桶数都足够使得没有冲突.

3)倒排页表
一般地每个进程都有一个页表,每个页表使用有序的虚拟地址正常查找.
倒排页表按物理地址有序来组织逆向查找,表内容是对应该物理地址上分配的进程和页信息:
inverted_page_table
好处是系统只需要维护一份页表, 表项总数不超过内存帧数,一般比所有进程的总页数要少.
缺点是翻译时可能需要遍历查找,并且不方便支持内存共享.

SPARK上Solaris系统页表组织举例:
使用了两个哈希页表,内核和所有用户空间各用一个.
每个表项代表若干连续的页空间,而非单个页,更加高效.
除了TLB外系统带有一个TSB缓存有最近访问的页.
翻译地址时,先从TLB查找,如果miss则从TSB查找,找到后更新TLB.
如果TSB也没找到则产生中断去查找哈希表,创建cache并更新到TSB和TLB,最终返回MMU完成翻译.

8.7 Intel 32位和64位架构举例
IA32同时支持分段和分页:逻辑地址->线性地址->物理地址
两个映射分别由段映射和页映射完成,两者组合构成MMU.
IA32支持4K和4M两种页大小,4K页采用二级页表管理,4M页使用单级页表.
为了提高内存使用率,IA32允许页表被换出到磁盘,由invalid位标识.
IA32的PAE(page-address extension)技术可以寻址36位内存空间(64G).
主要区别是多引入了一层总页表,以及增大表项大小到8字节以便表示更大的页编号范围(20bits到24bits).
这里的Extension主要是针对虚拟地址空间(单个进程利用>4G的物理内存);PAE需要操作系统额外支持.

x86-64目前支持48位大小的虚拟地址范围,使用四层页表结构.
使用PAE可以支持最大52位内存的寻址.
PAE一般对32位机器更有用,但目前64位机器已经普及了.

8.8 ARM架构
32位ARM是目前移动设备上主要硬件,由ARM公司设计,苹果等公司授权自行生产.
ARM32支持4K、16K、1M、16M等多种页大小, 前2总采用2级页表,后2种使用单级页表.
采用2级TLB设计,micro TLB和main TLB. 前者对数据和指令寻址各有1个.

发表评论

电子邮件地址不会被公开。