主存

约 3491 个字 16 张图片预计阅读时间 12 分钟

背景

此处不区分主存和内存这两个称呼

内存发展史

略，只需要知道DRAM、SRAM和ROM分别是什么，以及内存的发展速度赶不上处理器

内存的作用

程序必须被加载到内存，放入进程才能执行，进程本质是active的内存
主存和寄存器只能够被CPU直接访问
访问寄存器只需要一个时钟周期（或者更少），访问主存需要多个时钟周期，所以主存和寄存器之间存在Cache
内存需要被保护来确保操作正确

编译与执行

以C这种纯粹的编译型语言为例，编译的过程如下：

源代码(.c)编译为目标文件(.obj)，对于高级语言来说一般包含两个过程
源代码被编译为目标平台的汇编(.asm)
汇编语言被编译为二进制目标文件
链接器将不同目标文件链接起来得到可执行文件(.exe)
运行时目标文件被加载器装入内存

涉及如下软件：

编译器(compiler)是一个计算机程序，它能够将源代码转化为另一种计算机语言（往往是二进制形式，称作目标代码）
链接器(linker)是一个程序，它能够加载一个或多个由编译器生成的目标，把它们整合进一个可执行文件
装载器(loader)加载可执行文件到内存中执行

存在三种地址：

符号地址(Symbolic Address)：源程序中的地址通常是符号地址，比如变量名
可重定位地址(Relocatable Address)：编译器通常绑定它们的符号地址到可重定位地址（比如距离这个模块开头14byte）
绝对地址(Absolute Address)：链接器或者装载器将可重定位地址绑定到绝对地址（比如0x1000）

代码和数据绑定到内存地址可以在三个不同阶段发生：

编译时刻(Compile time)：编译出来的代码已经是绝对地址，如果地址变化必须重新编译
装入时刻(Load time)：如果在编译时刻代码地址未知，必须生成可重定位代码
执行时刻(Execution time)：绑定被推迟到了执行时，绑定的地址可以在执行时变动，需要硬件的支持

逻辑地址和物理地址

基址(base)寄存器和限长(limit)寄存器定义了逻辑地址空间：

逻辑地址空间指的是CPU生成的空间
物理地址空间指的是MMU能看到的地址

逻辑地址和物理地址对于编译时和装载时绑定是相同的，对于执行时绑定是不同的。

MMU

MMU(Memoey Management Unit)是负责映射虚拟地址到物理地址的硬件设备，在MMU机制下，在访问内存前，可重定位寄存器的值会被添加到每个由用户进程生成的地址上（这是最简单的虚拟内存机制）

用户进程只能处理逻辑地址，它永远不可能看见真实的物理地址。

动态装载/链接

动态装载是指程序只有在被调用时才会被装载，这样可以更好利用内存，不使用的程序不会被装载，在有大量代码低频出现的场景下非常有用，并且不需要操作系统特别支持。

动态链接是指链接延迟到了执行时，一小份代码（称作stub）被用来装载 memory-resident library routine，本质是将stub的地址替换为了routine的地址，从而去执行routine。动态链接的好处有：

节省主存空间
减少可执行文件大小
不需要重新链接到新库

动态链接和共享库需要操作系统的支持，共享库在Windows中是dll文件，所以绝对不能随便删除dll文件

内存管理

内存保护

主存通常被两部分使用，即OS和用户进程，可以将OS放在低地址或者高地址，很多OS，包括Windows和Linux选择放在高地址。需要防止进程访问它不拥有的地址，重定位寄存器被用来保护用户进程相互之间不干扰，以及不能改变OS的代码和数据。

重定位寄存器中包含了最小物理地址
限长寄存器包含了逻辑地址的范围，所有逻辑地址都小于限长寄存器的值
MMU通过改变重定位寄存器中的值动态映射逻辑地址

为什么不用软件实现limit reg和relocation reg？

因为访问内存是非常普遍的操作，使用软件效率太低，而且软件不够安全。

连续分配

连续内存分配(Contiguous memory allocation)：每个进程都被包含在了单一内存段中，紧邻的内存段包含的是下一个进程。具体分为：

单一连续分配(Single Cotinous Allocation)：内存分为系统区和用户区，用户区每次只调入一道程序运行，也就是说没有并发
多分区分配(Multiple-partition allocation)：将内存划分为若干个连续区域，称为分区，每个分区只能存放一个进程：
固定分区(fixed partition)
动态分区(dynamic partition)

固定分区就是把每个分区的大小提前划分好

动态分区是在程序装入内存时把可用内存“切出”一个连续的区域分配给该进程，且分区大小正好适合进程的需要（不一定是刚刚好，一般会多分配点）：

空洞(hole)：可用的内存区块，不同大小的空洞散布在内存中
当有进程抵达时，它会被分配足够容纳它的内存
OS维护已分配的分区和空闲分区(hole)的信息

上面说了hole是散布在内存中的，所以需要选择一块合适的分配给进程，一般情况OS维护的空洞信息可以看做是一个线性表，有三种选择算法（在ads装箱问题中学过，此处不赘述）：

First-fit
Best-fit
Worst-fit

此外，还可以选择优化所维护空洞信息的数据结构：

快速适应算法：将空闲分区按大小进行分类，设置索引表项，每一类型对应一项，挂成链（把原来的一根变成多根），分配时查找索引，取出适合类的第一块进行分配。
伙伴系统（buddy system）：每个空闲分区必须是2的$n$次幂字节，对进程占用的空间$n$计算一个$i$值使$2^i>n $，从剩余空闲分区找最适合的，若无则逐层拆分，释放时则逐层合并。lab4 中给出了伙伴系统的实现。
哈希算法：根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，根据所需空间大小计算得到哈希表的位置。

碎片

内存中可能都存在一些细小的空洞，无法分配给任何进程，这造成了内存的浪费：

外部碎片：存在于不同的分区间，这些碎片的总和可能可以满足一个请求，但是不连续
内部碎片：分配的内存可能比请求的内存稍大，多出来的那部分有实际可能未被使用

减少外部碎片可以通过整合(compaction)，将所有碎片集中至一处，比如将所有进程移动至内存空间的一侧，空洞移动至另一侧，整合只有在执行时刻绑定地址才适用。此外，移动进程的地址会导致I/O问题，可以选择锁住正在进行I/O的进程，也可以选择仅在OS buffer中进行I/O

分页

思想

分页显然不是凭空造出来的方案，它是基于：

非连续分配：分配给一个进程的内存可以物理上不连续，以此来减少外部碎片，提高内存利用率
虚拟内存：进程看到的内存最好是连续的，这样可以简化进程执行的逻辑，于是选择将不连续的物理地址映射为连续的逻辑地址
查找效率：访问的逻辑地址一定需要被翻译成物理地址，如果映射非常随机，那么翻译的开销会很大，所以一次要映射一小段连续内存(一页)

这里将物理内存划分为帧(frame)，大小是2的幂次，逻辑内存也划分为相同大小，不过称作页(page)，不过都称为页也可以。

跟踪所有的空闲帧，在运行一个大小为n页的程序时，分配n帧来加载程序
建立一个页表(page table)来将逻辑地址翻译为物理地址
仍有内部碎片

页表

如何找到页表

页表在内存中，有自己的逻辑地址，而访问逻辑地址需要先访问页表，那要怎么找到页表呢？答案是MMU会用物理地址找，根页表的物理地址会以某种方式存在内存/寄存器中。

由CPU生成的逻辑地址被划分为了两部分：

页号(page number)：用作在页表中的索引，包含了每一页在物理内存中的基地址
页偏移(page fault)：与基址组合以确定实际物理地址

实现分页的硬件如下：

页表驻留在主存中
页表基址寄存器(page-table base register)指向页表
页表长度寄存器(page-table length register)指示页表的大小
访问数据/指令需要两次内存访问，一次访问页表，另一次才是访问数据/指令

TLB

为了减少访问时间，引入一种特殊的fast-lookup hardware cache，称作TLB(translation look-aside buffer)，某些TLB在每个Entry中存储了ASID(address-space identifier)用于唯一标识每个进程来为进程提供地址空间保护。TLB 支持并发查找，如果没在TLB中找到才去页表中找。

在引入TLB后的地址翻译硬件如下：