操作系统之内存管理

在多道程序中，需要从磁盘中同时读入多个进程到内存，我们需要对内存进行管理，使得能够有条理地执行进程。
通常指令先要从内存中读入，进行解码，还要从内存中读取操作数，再将结果返回给内存。内存看到的只是地址。
一个进程占了一块内存，跨度是一串连续的地址，我们用base register和limit register来限定进程访问的范围。
CPU只能访问的存储器是内存和CPU的寄存器，所以如果有指令要访问数据，必须要提前导入到内存。下面会讲到交换方法，和动态载入。
Cache：因为访问CPU寄存器必访问内存速度快了很多，所以我们不能老是访问内存，所以要有Cache。访问内存可能会导致CPU暂停。
进程访问的地址的限定通过硬件实现：即通过base和limit寄存器的比较实现。
OS可以改limit和base的值。
磁盘有一个输入队列，存放准备导入内存的进程。
代码里我们通常用一个变量代表地址，我们可以将变量绑定到可重定位地址，加载程序再将重定位地址绑定成绝对地址。
绑定的情况：
1.编译时：如果在编译时就知道内存的地址，那么直接绑定绝对地址。
2.加载时：在编译时生成可重定位代码，在加载时才生成绝对代码。
3.执行时：如果执行时还要将进程从一个内存块移到另一个内存块，则只有执行时才绑定。
CPU生成的逻辑地址，内存的地址是物理地址。
程序生成的地址空间称为逻辑地址空间。
运行时虚拟地址到物理地址通过MMU映射。通过CPU的逻辑地址+base register就得到物理地址。用户是不知道物理地址的。

动态加载：如果一个程序必须全部加载入内存，那么必须限制程序的大小，所以动态加载是将一个大程序分成多个子程序，每次将某个子程序调入内存，如果一个子程序需要调入另一个子程序，则再加载，加强内存空间的使用率。

动态链接：通过在程序内部存放一个存根引用语言库，可以不必复制多个语言库副本，并且如果版本号不同，可以在内存中存放多个不同版本的库。
--------
如果CPU要执行的进程不再内存中，而在备份存储器中，则需要换入和换出，即交换。
当就进程换出后再次换入时，需要考虑位置问题：
1.当在加载时就绑定到物理地址，则换入到同一个位置。
2.在运行时绑定，则可以换入到任意位置。
交换的时间分为：转移时间，磁盘磁头寻址时间。
换出的进程选择方面需要注意不能选在I/O等待队列中的进程。
因此有一个修正的交换方式，可以在内存吃紧的情况下交换，但是在CPU使用率降低到一定时停止交换。

为了管理内存，需要为每个进程分配连续的内存。
内存映射需要将CPU的逻辑地址先与limit register比较，再加上base register。
当操作系统的一部分不常用时，可以先将它换出到备份存储，这块空间就可以腾给用户进程使用。

内存分配最简单的是将内存分成多个固定大小的分区，每个分区容纳一个进程。
可变分区是OS保存一个表，记录哪些内存可用，哪些内存已占用。
空闲的内存区域称为孔。
当一个进程从输入队列进入内存，有几种选取孔的方案：
1.最佳适应：遍历一遍，找到合适的最小孔。
2.首次适应。
3.最差适应。（真不知道要这个干嘛。。）
在第一第二中方法时，会存在外部碎片问题。
外部碎片问题：进程入孔后，还多出一点小空间，但不能放进程了。
内部碎片问题：分配内存时按块分配，比如一个进程3K，一个孔4K，则直接将4K分给进程，4-3=1K就是内部碎片。
解决外部碎片的方法是紧缩，将进程都挤一块。但是当绑定在加载时，则不能紧缩。
还有一种方法是重点，即可以将内存分配为非连续。
50%规则：在可分配的内存中，有50%的空间是碎片。

分页：将CPU的逻辑地址分成页，而将物理内存地址分成帧。备份存储也分成大小一样的块。先通过页号找到页表对应的帧，再加上页偏移找到内存的位置。
将CPU逻辑地址分成页号和页偏移方法：先将CPU逻辑地址的大小变成2^m,m就是逻辑地址的位数，设2^n为一页的大小，那么n则为页偏移。
m-n就为页号长度。
分页会导致内部碎片。因为帧大小固定，一次分配就是一帧的整数倍。
进程由几页组成，每个页对应一个帧。因此进程的内容就不一定要连续，每个进程对应一个页表。OS还持有每个进程页表的副本。
帧表：包括全部的帧以及他们是空闲还是被占用。
一开始页表放在PCB的寄存器中，因为速度快。但是随着页表的变大，必须把页表放在内存，而PCB只需保留一个页表基寄存器（PTBR），指向页表的头部。得到帧号再加上页偏移后再次访问内存。因此要2次访问。
由于上述方案需要2次内存访问，延迟大，所以产生了（TLB）快表（感觉就像cache），保留页表的一小部分，可以同时访问TLB的每个元素，速度快。如果TLB中没有，则按常规访问，并且将这个页表添加入TLB（局部性原理）。TLB的结构是键为页号，值为帧号。
有时TLB中还会有ASID，地址空间标识符（ASID）：唯一标识一个进程，一定要ASID匹配并且页号匹配才算匹配。
如果没有提供ASID时，则TLB保存一个进程的页表，每次进程切换，则TLB被flush。

TLB的命中率：访问TLB能找到的概率。

我们可以为每个帧授予权限，只读，可读写，可执行等。
页表的保护方式是通过在页表中提供一位称为“有效无效位”，即v或i。代表该页号是否合法。因为可能一个程序只有1-5的页号，所以页号为6以后的都被置为i。当然还可以通过PTLR(页表长度寄存器)来限制页表大小。
分页可以共享公共代码，但是这些公共代码是不能修改的。想象一下为什么能共享，因为进程只需要存放独有的页表，页表对应的帧在内存中，所以只需要一个程序即可，但是需要独立的数据，因此数据不能共享。
组织页表有几种方法：
1.多级页表。向前映射页表：从外级页表逐步映射到地址。想到了多级索引。【页表划分出题】

由来：因为我们的地址空间越来越大，所以页表也越来越大，因此到了我们都不能连续存放页表的地步，所以出现了多级页表。
2.hash页表。逻辑地址的页号通过hash后找到hash表对应位置，hash表每个元素对应一个链表，一个元素由虚拟页码、帧号、next组成。
群集页表适用于64位地址空间，hash页表的每个条目存储多个物理页帧的映射。
3.反向页表。通常一个进程有一个页表，但是占用内存大，因此整个系统只有一个反向页表，一个反向页表条目为<pid,page_number>，虚拟地址空间的一个条目为<pid,page_number,offset>，但是缺点为遍历时间长，但是可以结合前面提到的技术,如先TLB，再hash，再反向页表。但是反向页表不能共享内存。

分段是考虑到了用户对于内存的视角来构造的。将程序看成是一个段，没有顺序，用户通过<段号，段偏移>确定地址。
类似于页表，分段通过段表来实现地址映射，段表一个元素对应base register和limit register。