存在的问题
如何把多个进程的地址空间映射到物理地址空间中，合理分配使用内存
地址重定位
进程中的地址不是进程的最终物理地址，因为其在运行之前没有被加载到物理内存中，所以不能确定其最终的物理地址。因此需要地址重定位将进程中的地址空间中的逻辑地址转化成运行时可以直接寻址的物理地址。
静态重定位
当程序加载到内存中时，一次行实现逻辑地址到物理地址的转换，这样在执行过程中可以直接去内存中寻址相应的数据。
动态重定位
程序加载到内存中时不改变逻辑地址，在程序执行时逐条指令完成地址转换。
动态重定位实现
物理内存
内存划分
- 等长划分：把物理内存划分成大小相等的区域
- 不等长划分：物理内存被分配成大小不相等的内存区域
内存管理方法
- 位图：对于等长划分，每个分配单元对应位图中的一位
- 空闲区表、已分配区表：对于不等长分配，表中每一项记录空闲区(或已分配区)的起始地址、长度、标志
- 空闲区链表
内存分配算法
- 首次适配：在空闲区表中找到第一个满足进程要求的空闲区
- 下次适配：从下次找到的空闲区处接着查找
- 最佳适配：查找整个空闲表，找到能够满足进程要求的最小空闲区
- 最差适配：查找整个空闲表，找到能够满足进程要求的最大空闲区，将该空闲区分成两部分,一部分分配给该进程使用，另一个部分作为一个新的空闲区
内存回收算法
当某一块内存归还之后，前后空闲区合并并修改空闲区表
- 上相邻
- 下相邻
- 上下相邻
- 上下都不相邻
伙伴系统
一种经典的内存分配方案
主要思想
将内存按照2的幂次进行划分，组成若干空闲块链表，查找该链表找到能满足的最佳匹配块
算法
- 将整个可用内存空间看做一块：2^U
- 假设进程申请的空间大小为s,如果满足2^(U-1)< s < 2^U,则分配整个块，否则，将块划分为两个大小相等的伙伴，大小为2^(U-1)
- 一直划分下去，直到产生大于或等于s的最小块
例子
基本内存管理方案
单一连续区域
一段时间内只有一个进程在内存中
优点
- 简单
缺点
- 内存利用率低
固定分区
- 把内存空间分成若干区域，称为分区
- 每个分区大小可以相同也可以不同
- 分区大小确定后固定不变
- 每个分区装且只装一个进程
例子
可变分区
根据进程的需要把内存空闲空间分割出一个分区，分配给该进程，剩余部分成为新的空闲区域。
缺点
- 出现外碎片，大致内存利用率下降 紧缩技术：将所有小的空闲区合并为较大的空闲区，但是需要考虑系统开销和移动的时机
以上三种方式都是进程整个进入内存中的连续内存区域，下面三种方式是进程进入内存的若干区域并且不连续的。
页式存储管理方案
设计思想
- 用户地址空间被划分成大小相等的部分，称为页
- 物理地址空间按照相同的大小被划分成大小相等的区域，被称为页帧
逻辑地址划分
内存分配
以页为单位进行分配，按照进程需要的页数来分配
- 页表记录了逻辑页号与页框号的对应关系
- 每个进程一个页表，存放在内存中
地址转换
CPU取到逻辑地址，硬件自动划分为页号和页面地址，用页号查找页表得到页框号，再与页内偏移拼接成物理地址。
缺点
- 可能引起内碎片问题
段式管理方案
设计思想
- 用户地址空间按照程序自身逻辑关系划分为若干个程序段，每个程序段都有一个段名
- 内存地址空间被动态划分成若干长度不相同的区域，被称为物理段
内存分配
以段为单位进行分配，每段在内存中占据连续空间，各端之间可以不相邻
逻辑地址划分
由段号和段内地址组成，但是段号不是自动划分的，需要显示给出。
内存分配
- 段表记录了段号、段首地址和段长度之间关系
- 每个进程一个段表存放在内存中
地址转换
CPU取到逻辑地址，用段号查段表，得到该段在内存的起始地址，再与段内偏移计算成物理地址。
交换技术
解决在较小的内存空间中运行较大的进程问题。
- 内存紧缩技术
- 覆盖技术
- 交换技术
- 虚拟存储技术
覆盖技术
- 按照自身逻辑结构，不会同时执行的程序段共享同一块内存区域
- 程序各个模块之间有明确的调用结构，同一进程里的几个独立的程序段进行相互覆盖
交换技术
内存紧张时，系统将进程中某些进程暂时移到外存中，把外存中某些进程换进内存中，占据之前所占用的区域，交换技术是以进程为单位，若进程所需内存大于系统内存 ，则此进程无法进行，是不同的程序里的程序段进行交换
存在的问题
- 交换的内容：运行时创建或者修改的内容：堆、栈，其他在可执行程序中都存在
- 交换到磁盘上的位置：系统指定一块特殊的磁盘区，不经过文件系统，由操作系统使用底层的读写操作对其进行高效访问
- 何时发生交换：进程很少使用或者不用；内存空间不够用
- 交换的进程：不应换出处于等待I/O状态的进程
虚拟存储技术
当进程运行时，先将其一部分装入内存，另一部分留在磁盘中，当要执行的指令或者访问的数据不在内存时，有操作系统将其加载到内存中。而虚拟存储是以页或段为单位，是把进程再分为页或段对内存进行分化，若进程所需内存大于系统内存，进程也可以运行，因为该进程的一部分可换到外存上
地址保护
- 确保每个地址有独立的地址空间
- 确保进程访问合法的地址空间
- 将地址与
基地址寄存器和界限寄存器进行比较判断是否越界，该寄存器的值通过操作系统特殊指令加载
- 将地址与
- 确保进程操作是合法的
- 主要是判断访问权限的问题:只有读权限的地址空间内不可以写数据
虚拟页式管理
基本思想
- 程序开始运行之前不装入全部页面，而是装入一个或者0个页面
- 根据程序需要，动态装入其他的页面
- 内存空间已满，新的页面需要装入内存，根据置换算法加载新的页面
页表以及页表项设计
页表项组成
每个进程一张页表，页表由页表项组成
- 页框号：表示虚页表对应的页框号(物理页面)
- 有效位：表示该页是在内存还是在磁盘上
- 访问位：表示该页面是否被使用或者访问
- 修改位：表示该页面在内存被修改
- 保护位：表示该页面的读写操作
二级页表
为了解决页表太大的问题，引入多级页表
反转页表
由于每个进程一张页表，而页表又有可能非常大空间，因此尝试引入反转页表，整个系统建立一张页表，页表项记录进程i的虚拟地址与页框号的映射关系
问题
- 根据虚拟地址查物理地址时需要查找整个页表
- 将虚拟地址的页号部分映射到散列值，将散列值指向一个反转页表
地址转换
快表
引入快表原因
- 访问内存至少两次
- CPU执行指令快于内存执行指令，CPU性能得不到发挥
利用程序访问的局部性原理，引入快表
快表
在CPU中引入的高速缓存，可以匹配CPU的处理速率和内存的访问速度，其按照内容进行并行查找
加入快表转换过程
页错误
地址转换过程中硬件产生的异常
- 缺页异常：虚拟页面没有调入物理内存
- 页面访问违反异常
- 错误访问地址
置换算法
最佳页面置换算法
设计思想
置换以后不再需要的或最远的将来才会用到的页面
实现
基于进程的走向来实现，更多的是作为一种标准来衡量其他算法的性能
先进先出置换算法
设计思想
选择在内存中驻留时间最长的页并置换它
实现
页面链表法
第二次机会算法
设计思想
在先进先出算法的基础上进行该机而来的，此算法按照先进先出算法选择某一页面，检查其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置零，并将其从链头取下放到链尾。
问题
在第二次机会算法中当给某个页面第二次机会的时候，将其访问位置零，然后将其挂到链尾，这都是需要开销的，于是我们改进为时钟算法。
时钟算法
设计思想
维持一个保存所有页面的环形链表，一个指针指向最老页面，发生缺页中断时，检查指针指向页面，若R=0，则更新它，若R=1,清除R位，指针前移，继续搜索
最近未使用算法
设计思想
找到最久没有使用的页面置换出去，页面被访问时设置R位，修改时设置M位，R位定期清0；
把页面分四类
- 0类.未被访问，未被修改的R=M=0
- 1类未被访问，被修改R=0,M=1
- 2类被访问，未被修改R=1,M=0
- 3类被访问，被修改R=1，M=1
系统从类类编号最小的非空类随机挑选一个置换
最近最少使用（LRU）
设计思想
找到最久没有使用过的置换之
实现
为每个页框维护一个时间戳（或者一个栈），需要扫描所有的时间戳，开销大
最不经常使用
设计思想
选择访问次数最少的页面置换掉
实现
- 软件计数器，一页一个，初值为零
- 每次时钟中断时，计数器加R
- 发生缺页中断时，选择计数器值最小的一页置换。
老化算法
设计思想
计数器在加R前先右移一位，R位加到计数器的最左端，这样如果R值为零，则计数器没有影响，如果值为1，则会变得很大，于是如果一个页面长久不被访问，则计数器值就会越来越小。最后选择值最小的置换出去。
BELADY现象
例子：系统给某进程分配m个页框，初始为空页面访问顺序为
1 2 3 4 1 2 5 1 2 3 4 5，采用FIFO算法，计算当m=3和m=4时的缺页中断次数。
结论：m=3时，缺页中断九次；m=4时，缺页中断十次。注意：FIFO页面置换算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。
工作集算法
影响缺页次数的因素
- 页面置换算法的不同
- 页面本身的大小
- 程序的编制方法
- 分配给进程的页框数量
缺页越多，系统的性能越差，这称为颠簸（抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。
页面尺寸问题
- 确定页面大小对分页的硬件设计非常重要，而对操作系统是个可选的参数
- 要考虑的因素
- 内部碎片
- 页表长度
- 辅存的物理特性
- 多种页面尺寸：为了有效使用TLB带来灵活性，但给操作系统带来复杂性
程序编制方法对缺页次数的影响
例子：
分配了一个页框，页面大小为128个整数，矩阵A(128 x 128)按行存放。
可以看到左边是按列赋值，右边是按行赋值。按列编制就是首先读入第一页（一行，因为矩阵是按行存放的），然后给第0个位置赋值，每次读入一行，直到将第0列赋值完，读完之后再给第1列赋值，这样会产生128*128次缺页异常；而按行赋值，第一次读入一页，给第0行的所有元素赋值，这样会产生128次缺页异常。于是可以看到程序的编制方法对缺页次数是有很大影响的。
分配给进程的页框数与缺页率的关系
可以看到页框数越多那么缺页率越低，但是我们不可能给出所有的页框，于是需要找到一个平衡点W，超过这个点之后页框数的增加对缺页率的降低有限，这也是工作集算法的出发点。
工作集模型
基本思想
根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使得该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数，这是由Denning提出的。
工作集
一个进程当前正在使用的页框集合
例子：
设计思想
找出一个不在工作集的页面并置换它
- 每个页表项中有一个字段：记录该页面最后一次被访问的时间
- 设置一个时间值T
- 判断：根据一个页面的访问时间是否落在“当前时间 - T”之前或之中决定其在工作集之外还是之内
实现
扫描所有页表项，执行操作
- 如果一个页面的R位是1，则将该页面的最后一次访问时间设为当前时间，将R位清零
- 如果一个页面的R位为0，则检查该页面的访问时间是否在“当前时间 - T”之前，如果是，则该页面是需要被置换的页面；否则，记录当前所有被扫描过页面的最后访问时间里面最小值。扫描下一个页面并重复上述操作。
