第四章、非连续式内存分配

非连续内存分配：

1.1、为什么需要非连续内存分配：

1.2 分段(Segmentation)：

程序的分段地址空间：

​ 逻辑地址空间是连续的，物理地址是离散的中间需要映射机制来建立联系。

通过硬件将内存中的不同区域划分，分别分开进行管理。如果用软件来实现就会涉及到拷贝，开销是很大的。

分段寻址方案：

一个段指一个 “内存块”，是一个逻辑地址空间。

方式一： 采用 段号(s) + 段内偏移(addr)的方式管理，也即是段寄存器+地址寄存器实现方案(x86是典型的例子)；

方式二： 是单地址实现方案，此时没有段表寄存器。 在分段管理的过程中，段长不是固定的。如果是单地址实现方案则更加简单，没有段表寄存器。直接拿逻辑地址中的段号去段表中查，其他步骤和上述一样

硬件实现方案：

段表中包含 段号(和逻辑地址中的段号相同)、段长(限制段的长度为合理范围)、段的基址(对应物理地址）；

段表是由操作系统提前建立好的，和硬件有着紧密的联系；

1.3 分页

分页和分段的最大区别就是 段的大小是可变的而页的大小是固定的

1.3.1 物理地址部分：页帧

桢(Frame):

对于一个物理地址，如果已知它的帧号和帧内偏移，就可以根据公式计算得出物理地址

地址计算实例：

每一帧的大小为 512byte，那么总共就由9位来表示帧的大小 S=9；

总共16位，剩余7位就用来表示帧号的大小，F=7；

---

1.3.2 逻辑地址部分：页

页(page)：

页内偏移大小 = 帧内偏移大小

页号大小 ! = 帧号大小

页内寻址方式：

首选虚拟地址包括了页号§和页内偏移地址(o)，cpu根据页号去页表
中查找对应的内容，页表中存放的是以页号为索引的帧号；查询出帧号后就能根据帧号去计算实际的物理地址了(因为帧的大小是固定的)。

页表也是由操作系统创建的。

页寻址机制：

页表结构：

页表项中包含的有标志位(Flags)，用于确定该处的物理物理页帧是否存在；帧号(f)，用于计算对应的物理地址

地址转换实例：

比如页号为4，那么找到页表中对应的为100，这里第二位为贮存位，为0则代表该处的物理页帧不存在，那么此时CPU会发出内存访问异常由操作系统进行处理。

如果页号为３，对应页表中为011，这里贮存位为1，那么找到对应的页帧号为00100 (4)，则物理地址为(4,1023)。

---

1.3.3 分页机制的性能问题：

分页机制的性能问题：

1.时间代价：访问一个内存单元需要2次内存访问

​ 一次用于获取页表项；

​ 一次用于访问数据；

2.空间代价：页表可能非常大

->访问一个内存单元需要2次内存访问：一次获取页表项；一次是访问数据。
->页表可能会非常大(页表的长度等于2^页号位数)
举例，64位机器，如果一页是1024KB，那么页表是多大？
假如页号是n位的，那么页表的长度等于2^ n，一页是1024KB，所以页内偏移是10位，一个逻辑地址的长度等于计算机位数，也就是64位，因此剩下的54位是留给页号的；因此页表的长度是2^54，明显CPU装不下。
一个程序一个页表，n个程序n个页表，就更大了。
CPU装不下，只能装在内存里；如果这样，需要访问2次内存，一次访问页表，一次访问程序。

3.解决方法：

  * 缓存caching
  * 间接访问 indrection

TLB（缓存）解决访问时间问题：

对于一些经常访问的页表，可以将其对应的页表项存放于TLB快表中，再次访问这些逻辑地址时就会很快，这样就避免了对页表的访问；

虽然速度快，但是TLB的容量有限，当发生访问缺失时会到页表中进行访问，然后将得到的帧号(f) 返回存储到TLB中；

TLB实际上是CPU的MMU内存管理单元保存的一段缓存，这段缓存保存的内容是 页表 的一部分，是经常访问到的那部分页表，其余不常用的页表内容保存在内存中。

TLB未命中，也叫TLB miss，这种情况比较少见，因为一页很大，32位系统一页是4K，如果采用局部性原理，那么访问4k次才会遇到一次TLB miss。对于x86这一类的操作系统，当miss后取表项存入TLB是完全由硬件完成的，操作系统不参与；但是对于MIPS另一类操作系统，是由软件(操作系统)来完成的。

解决访问空间的问题：

p1页表中存放的是p2的页号，p2页表中存放的是帧号；

逻辑地址中，页号部分分成了2部分，p1和p2。

p1存放着二级页表的起始地址，p2的作用就是之前的p。

p1找二级页表，p2找页，o找地址。

这里体现了二级页表的另一个好处，就是p1对应的位置是flags，假如说resident bit是0，那么整个二级页表都不用在内存中保存，这个是一级页表无法实现的！

---

1.3.4 反向页表

反向页表：

页表来表示物理地址(页帧)号，而不是之前的逻辑地址(页号)，不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应，能够减少页表尺寸，但是给映射关系的建立带来点困难。

传统页表的缺点：

(1)对于大地址空间，前向映射页表变得繁琐(例如64位系统采用5级页表)。

(2)逻辑地址空间增长速度快于物理地址空间，所以反向页表，也就是index是物理地址，value是逻辑地址，它的大小会小于传统页表。

基于页寄存器(page registers)的方案：

(1)每一帧和一个寄存器相关联，该寄存器包括：

• residence bit：此帧是否被占用；
• occupier：对应的页号p；
• protection bit：保护位；

(2)举个例子：

物理内存大小：4096 * 4096 KB = 16 MB
页面大小：4064 bytes = 4 KB
页帧数： 4K
页寄存器使用的空间(假设是8 bytes的register)：8 * 4096 = 32 KB
页寄存器的额外开销：32 KB / 16 MB = 0.2%
虚拟内存的大小：任意
可以看出内存开销很小。

（3）页寄存器的优缺点；

优点：

转换表的大小相对于物理内存来说很小；
转换表的大小跟逻辑地址空间的大小无关；

缺点：

需要的信息对调了，如何根据帧号找到页号呢；
需要在反向页表里去找想要的页号。

基于关联内存(associative memory)的方案：

如果帧数较少，页寄存器可以被放置在关联内存中；
在关联内存中查找逻辑页号，成功了，帧号就被提取出来；失败了，页错误异常page fault。
限制这种方案的因素包括，大量的关联内存非常昂贵(难以在单个时钟周期内完成；耗电)。

基于哈希(hash)查找的方案：

在查找时，将页号(page) + PID(运行程序的ID) 进行组合然后作为 input传入 哈希表，然后算出对应的帧号；

存在的问题：

  1. 由于是hash算法，因此一个input可能会对应多个output；

常page fault。

    限制这种方案的因素包括，大量的关联内存非常昂贵(难以在单个时钟周期内完成；耗电)。

基于哈希(hash)查找的方案：

[外链图片转存中…(img-G3rpktkZ-1601035537448)]

在查找时，将页号(page) + PID(运行程序的ID) 进行组合然后作为 input传入 哈希表，然后算出对应的帧号；

存在的问题：

  1. 由于是hash算法，因此一个input可能会对应多个output；
     2. 还是需要将整个反向页表放置到内存中，因此整个内存访问还是很大。