非连续式内存分配

本文中的图片均来自B站清华大学的操作系统课程

为什么提出了非连续式内存分配：

1.连续式内存分配的缺点

（1）分配给一个程序的物理内存是连续的

（2）内存利用率低

（3）有外碎片/内碎片的问题

2.非连续内存分配的优点

（1）能够分配一个程序的物理内存是不连续的

（2）能够更好进行内存的利用和管理

（3）能够实现数据以及代码的共享

（4）能够支持动态加载和动态链接

3.非连续式内存分配的缺点

（1）如何 建立虚拟地址和物理地址之间的转换

（2）实行软件方案（开销大）

分段：更好的分离和共享

程序的分段地址空间

逻辑地址空间是连续的，物理地址是离散的。

分段寻址的方案：

以上的开销大，如何用硬件实现

(1)段访问机制：一个段指一个内存块，是一个逻辑地址空间

程序根据段访问机会访问内存地址需要一个二维的二元组（S段号，addr端内偏移）

左图就是：段寄存器+地址寄存器实现方案           右图就是：单地址实现方案

（2）段访问机制的硬件实现方案：

 非连续式内存分配：分页

物理地址部分：页帧

（1）页帧：物理内存被分割为大小相等的帧（物理地址部分）

一个内存的物理地址是一个二元组(f,o)，f:帧号(它是F位的，因此意味着一共2F个帧)；o：帧内偏移(它是S位的，因此意味着每帧有2S字节)；物理地址=2^S x f + o。

 （2）举个实例

 逻辑地址部分：页

(1)页：一个程序的逻辑地址空间被划分为大小相等的页(逻辑地址部分)
(逻辑地址的)页内偏移量=(物理地址的)帧内偏移量
(逻辑地址的)页号大小可能不等于(物理地址的)帧号大小

 （2）页寻址机制的实现

页表实际上就是一个大的数组/hash表。它的index是页号，对应的value是页帧号，首先根据逻辑地址计算得到一个页号，也就是index，再在页表上找到对应的页帧号，最后根据页帧号计算得到物理地址。

 非连续内存分配：页表-TLB

页表概述

（1）通过标志位来判断当前页号的性质

(2)举个实例。逻辑地址空间是16位64kB，物理地址空间是15位32kB，并不是对等的，但是一页和一帧的大小是一样的，都是10位1kB。

逻辑地址(4,0),页号4对应的二进制是100，它的位置对应着flags。根据上图，可知它的dirty bit是1，resident bit是0，clock/reference是0；因此可以知道逻辑地址(4,0)在物理地址中实际是不存在的。如果CPU访问这个逻辑地址会抛出一个内存访问异常；
逻辑地址(3,1034),页号3对应的二进制是011，它的位置(也就是页号的位置)对应着flags。根据上图，可知它的dirty bit是0，resident bit是1，clock/reference是1；因此可以知道逻辑地址(3,1034)在物理地址中存在。再复习一下，页表里存放的是什么。因为由于逻辑地址的页内偏移和物理地址的帧内偏移是一样的，所以页表不需要保存偏移。根据页表，页号3对应的页帧号是4，再加上它们的偏移量相等，所以逻辑地址(3,1034)对应的物理地址是(4,1023)。
这个页表是由操作系统维护。

 (3)分页机制的缺点

要付出空间代价和时间代价

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

缓存caching

间接访问indirection

快表TLB

优化页表的时间开销问题最好的解决办法是缓存。

TLB实际上是CPU的MMU内存管理单元保存的一段缓存，这段缓存保存的内容是 页表 的一部分，是经常访问到的那部分页表，其余不常用的页表内容保存在内存中。
TLB未命中，也叫TLB miss，这种情况比较少见，因为一页很大，32位系统一页是4K，如果采用局部性原理，那么访问4k次才会遇到一次TLB miss。

 页表-二级/多级页表

介绍如何优化页表的空间开销问题，解决方法是多级页表。

虽然增加了内存访问次数和开销，但是节省了保存页表的空间（时间换空间，然后在通过TLB来减少时间消耗）

（1）二级页表

逻辑地址中，页号部分分成了2部分，p1和p2。
p1存放着二级页表的起始地址，p2的作用就是之前的p。
p1找二级页表，p2找页，o找地址。
这里体现了二级页表的另一个好处，就是p1对应的位置是flags，假如说resident bit是0，那么整个二级页表都不用在内存中保存，这个是一级页表无法实现的！

（2）多级页表

例如64位系统采用5级页表