Main memory
Background
首先提两个概念,这两个寄存器是由操作系统载入的：
- base register：存着最小的合法物理地址
- limit register：存着可用范围
- address binding：用户程序的相对地址被绑定到物理地址上，可以在编译期、加载期和运行期进行
- logical address：由CPU定义的，用户程序生成
- physical address：真实的物理地址
- memory-management unit(MMU)：负责将逻辑地址映射到物理地址
- dynamic loading：为了更好地管理内存，使得进程不受物理内存的限制
- dynamically linked libraries：通常是系统库，在执行前动态链接进来，避免占用太多内存
swapping
进程可以在内存和后台存储区（通常是磁盘）中交换。把需要的进程换进来，把暂时不用的进程替换出去
- swapping是非常耗时间的，因为在内存和外存之间的传输非常耗时间
contiguous memory allocation
通常而言，贮存会被分为两部分，一部分是给操作系统，另一部分给用户空间。
- 内存保护：limit register有一个地址空间范围，在进程被CPU执行时，这个范围会被加载进去，由操作系统进行验证；
- multiple-partition allocation：给每个进程分一个分区
- fixed partition（固定分区）
- 超过内存大小的进程无法进行
- 分区内部无法利用的内存变成内碎片，无法解决
- dynamic partition（动态分区）
- 在程序装载进内存时，系统将内存划分一块大小适合的连续区域给进程
- 操作系统自行管理已分配和空闲分区
- 为了减少碎片：可以通过紧缩和拼接的方法
- 三种分配算法：
- first fit：逐个寻找适合的分区
- best fit：选择剩下内存最小的适合分区
- worst fit：选择剩下内存最大的分区
- next fit：从上次查找结束并内存足够大的区域开始划分
paging
概念先行：
- frames：将物理内存分成帧
- pages：将逻辑地址分为页
- 每个地址被分为了page number(代表着页表的项数)和page offset（代表着页的大小）
- page number构成了page table的索引表，表中存着frame number，对应着内存中的frame
- 分页不会产生外部碎片，但有可能产生内部碎片，即每一页中的缺失
TLB
访问过程：
- 传统上需要访问物理内存两次，一次是访问获取页表的内容，另外一次是根据页表的指引去访问内存
- TLB是页表的一部分，只存有页表的部分条目，但不同于页表，TLB一般是存在cache，这样满足快速读取。
- 在进程被加载进来时，TLB会被填充，寻找frame时，CPU同时在TLB和page table中寻找。找到则返回frame，找不到则在page table中寻找
- 有效访问时间
- TLB访问时间a
- 内存页表访问时间b
- 命中率c
- 平均访问时间（有TLB）：(a+b)c + (b+b+a)(1-c)
- 没有TLB：2*b
- 页表有一个有效位，指示该页是否在内存中有映射，否则都需要到磁盘中去找
structure of the page table
Hierarchical Paging
假如有一个32位的系统，页表大小是4KB(212)，那么一个页表会含有1MB(220)条索引，如果一条索引4个字节，那么会产生4MB大小的页表
因此，我们可以使用二级页表，将页表分页。一个地址将会如下图所示：页目录是页表的索引，页表是进程物理空间本身的索引。
(P1是外部表的索引，P2是二级表的索引)
hashed page tables
超过32位地址空间通常是使用哈希页表
哈希页表的每一条目都包括一个链表的元素，每个元素有三个域：虚拟页码，物理帧号，指向下一个元素的指针。
通过页码途径哈希函数得到对应的条目，从而获得物理帧号。
inverted page tables
真正被使用的帧才会记录到在反向表的条目中。整个系统只有一张页表，对每个物理内存帧都只有一个条目，包括了逻辑地址和进程号。