6.1非连续内存分配的需求背景
用户想要一块区域，而在内存当中又没有满足这个大小的连续区域，那这个分配就会失败，基于这种现状提出了一种需求，说我是否可以分配的内存空间不连续
非连续分配的设计目标
连续分配的缺点
分配给程序的物理内存必须连续
存在外碎片和内碎片
内存分配的动态修改困难
内存利用率较低
非连续分配的设计目标：提高内存利用效率和管理灵活性
非连续分配的设计目标：提高内存利用效率和管理灵活性
允许共享代码与数据
支持动态加载和动态链接
非连续内存分配的实现
■非连续分配需要解决的问题
·如何实现虚拟地址和物理地址的转换
软件实现（灵活，开销大）
硬件实现（够用，开销小）
■非连续分配的硬件辅助机制
·如何选择非连续分配中的内存分块大小
段式存储管理（segmentation）
段式存储分的块比较大，它以一个段作为一个基本的单位，在分配的时候，这一个段的内容必须在物理内存里是连续的，不同段之间是可以放到不同地方的
页式存储管理（paging）
把内存分成更小的块，这个块的名字叫做页，在分配的时候就是以页为单位来分配，页与页之间是不连续的
6.2段式存储管理 （segmentation）
段地址空间
■进程的段地址空间由多个段组成
主代码段
子模块代码段
公用库代码段
堆栈段(stack)
堆数据(heap)
初始化数据段
符号表等
■段式存储管理的目的
更细粒度和灵活的分离与共享
段式地址空间的不连续二维结构
段地址空间的逻辑视图
段访问机制
■段的概念
段表示访问方式和存储数据等属性相同的一段地址空间
对应一个连续的内存“块”
若干个段组成进程逻辑地址空间
■段访问：逻辑地址由二元组(s, addr)表示
s— 段号
addr— 段内偏移
段访问的硬件实现
段表，每个条目都有段基地址和段界限。段基地址包含该段在内存中的开始开始物理地址，而段界限指定该段的长度。
6.3页式存储管理（paging）
■页帧（帧、物理页面, Frame, Page Frame）
把物理地址空间划分为大小相同的基本分配单位（称为帧）
2的n次方，如512, 4096, 8192
■页面（页、逻辑页面, Page）
把逻辑地址空间也划分为相同大小的基本分配单位（称为页）
帧和页的大小必须是相同的
■页面到页帧
逻辑地址到物理地址的转换
页表
MMU（内存管理单元）/TLB（高速缓存）
注：frame和page之间的区别是在于，一个用来描述逻辑页面，一个用来描述物理页帧
帧(Frame)
■物理内存被划分成大小相等的帧
内存物理地址的表示：二元组(f, o)
f— 帧号(F位,共有2F个帧)
o— 帧内偏移(S位,每帧有2S字节)
物理地址= f * 2^S + o
概念：帧表：物理内存分配细节。每个条目对应着每一个帧，是空闲还是占用，被那个进程的哪个页所占用。
基于页帧的物理地址计算实例
页(Page)
进程逻辑地址空间被划分为大小相等的页
页内偏移=帧内偏移
通常：页号大小≠ 帧号大小
进程逻辑地址的表示：二元组(p, o)
p— 页号(P位, 2P个页)
o— 页内偏移(S位,每页有2S字节)
虚拟地址= p * 2^S + o
概念：采用分页技术不会产生外部碎片：每个帧都可以分配给需要它的进程。不过会产生内部碎片。
页式存储中的地址映射
页到帧的映射
逻辑地址中的页号是连续的
物理地址中的帧号是不连续的
不是所有的页都有对应的帧
页表
概念：保护
内存保护是通过与每个帧相关联的保护位来实现的。存在页表中。表示是可读写还是只读的。可以通过检查保护位来验证有没有读写的误操作。
6.4页表
页表结构
■每个进程都有一个页表
每个页面对应一个页表项
随进程运行状态而动态变化
页表基址寄存器(PTBR: Page Table Base Register)
页表地址转换实例
页式存储管理机制的性能问题
■内存访问性能问题
访问一个内存单元需要2次内存访问
第一次访问：获取页表项
第二次访问：访问数据
页表大小问题：
■页表可能非常大
64位机器如果每页1024字节，那么一个页表的大小会是多少？
2^64/2^13（1024字节对于的比特）
■如何处理?
缓存（Caching）
将数组的第一项得到的页表项缓存下来，要访问第二项的时候直接去缓存中去找相应的页
间接（Indirection）访问
页表很大，一个很长的表，切段，先找它在那个字表，再去字表内找
快表(Translation Look-aside Buffer, TLB)
快表实际上就是把近期访问过的页表项缓存到CPU里头。在CPU里面加上一组关联存储器，key是逻辑地址，value是物理地址（页帧号）。
TLB采用小但专用且快速的硬件缓冲，又称为转换表缓冲区，关联的快速内存。
■缓存近期访问的页表项
TLB使用关联存储(associative memory)实现，具备快速访问性能
如果TLB命中，物理页号可以很快被获取
如果TLB未命中，对应的表项被更新到TLB中
多级页表
对于整个列表中没有用的页表，可以通过各级页表当中的存在位把那些不存在的给省掉
■通过间接引用将页号分成k级
建立页表“树”
减少每级页表的长度
二级页表实例
大地址空间问题
■对于大地址空间(64-bits)系统，多级页表变得繁琐.
比如：5级页表
逻辑(虚拟)地址空间增长速度快于物理地址空间
■页寄存器和反置页面的思路
不让页表与逻辑地址空间的大小相对应
让页表与物理地址空间的大小相对应
页寄存器(Page Registers)
■每个帧与一个页寄存器(Page Register)关联，寄存器内容包括：
使用位(Residence bit):此帧是否被进程占用
占用页号(Occupier):对应的页号p（一个进程占用了这一页，它的逻辑页号是多少，把页号保存下来）
保护位(Protection bits)
页寄存器方案的特征
■优点:
页表大小相对于物理内存而言很小
页表大小与逻辑地址空间大小无关
■缺点:
页表信息对调后，需要依据帧号可找页号
在页寄存器中搜索逻辑地址中的页号
页寄存器中的地址转换
■CPU生成的逻辑地址如何找对应的物理地址?
对逻辑地址进行Hash映射，以减少搜索范围
需要解决可能的冲突
■用快表缓存页表项后的页寄存器搜索步骤
对逻辑地址进行Hash变换
在快表中查找对应页表项
有冲突时遍历冲突项链表
查找失败时，产生异常
■快表的限制
快表的容量限制
快表的功耗限制(StrongARM上快表功耗占27%)
反置页表
反置页表对于每个真正的内存或帧才有一个条目。每个条目保护保存在真正内存位置的页的虚拟地址以及拥有该页的进程信息。实现共享内存时存在困难
■基于Hash映射值查找对应页表项中的帧号
进程标识与页号的Hash值可能有冲突
页表项中包括保护位、修改位、访问位和存在位等标识
哈希页表
每个元素有3个域（1）虚拟页码，（2）所映射的帧号（3）指向链表的下一个元素的指针。
反置页表的Hash冲突
6.5段页式存储管理
段页式存储管理的需求
段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。
段式存储、页式存储能否结合？
由于段式存储，它分的块比较大，每一块里头的存储的内容是同一个段，这同一个段的访问方式和存储的数据都是相同的或者相类似的，做存储的保护是比较方便的，而另一种做法页式存储，它是由于分了很小的标准大小的块，那这样的话它在内存利用效率，内存和外存之间的存储的后备，这方面是会比较有优势。
段页式存储管理
首先是段号由进程的段基址找到相应的段表基址，找到相应的段表项，这个段表项里面有相应段的段长度和段基址，那这些加在一起得到一个相应段的页表的基址，这个再加上页号，就可以得到相应的页表项，页表项里头呢就有对应的物理页的页号、物理页帧号。这个页帧号和页内偏移加在一起就可以访问到实际的物理存储单元。
■在段式存储管理基础上，给每个段加一级页表
段页式存储管理中的内存共享
可以在段表的基址上加上一个共享段，指向相同的页表，那这两个段就共享了
■通过指向相同的页表基址，实现进程间的段共享
