内存管理
虚拟内存
虚拟内存的基本思想
每个进程拥有自己的地址空间，这个空间被分割为多个块，每个块称作一页。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
虚拟内存的目的
是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
虚拟内存的三个重要功能
- 它在主存中自动缓存最近使用的存放磁盘上的虚拟地址空间的内容。
- 虚拟内存简化了内存管理，进而又简化了连接，在进程间共享数据、进程的内存分配以及程序加载。
- 虚拟内存通过在每条页表条目中加入保护位，从而简化了内存保护。
页式存储管理
页式存储管理的基本原理
页式存储管理是把主存储器划分成大小相等的若干区域，每个区域称为一块，并对它们加以顺序编号，如第 0 块、第 1 块等等。与此对应，用户程序的逻辑地址空间划分成大小相等的若干页，同样为它们加以顺序编号，从 0 开始，如第 0 页、第 1 页等。 页的大小与块的大小相等。
分页式存储管理的逻辑地址由两部分组成：页号和页内地址。其格式为：
在分页式存储管理系统中，允许将作业的每一页离散地存储在主存的物理块中，但系统必须能够保证作业的正确运行，即能在主存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。页表实现了从页号到主存块号的地址映射。作业中的所有页（0 ~ n）依次地在页表中记录了相应页在主存中对应的物理块号。页表的长度由进程或作业拥有的页面数决定。
页式存储管理的地址映射
调度程序在选择作业后，将选中作业的页表始址送入硬件设置的页表控制寄存器中。地址转换时，只要从页表寄存器中就可找到相应的页表。当作业执行时，分页地址变换机构会自动将逻辑地址分为页号和页内地址两部分，以页号位索引检索页表，如果页表中无此页号，则产生一个“地址错”的程序性中断事件；如果页表中有此页号，则可得到对应的主存块号，再按逻辑地址中的页内地址计算出欲访问的主存单元的物理地址。因为块的大小相等，所以块内地址等于页内地址。
$物理地址=块号×块长＋页内地址\hspace{50cm}$
页式存储管理的总结
减少分区管理的碎片，提高内存利用率。
段式存储管理
段式存储管理的基本原理
每个作业由若干个相对独立的段组成，每个段都有一个段名，为了实现简单，通常可用段号代替段名，段号从 0 开始，每一段的逻辑地址都从 0 开始编址，段内地址是连续的，而段与段之间的地址是不连续的。
其逻辑地址由段号和段内地址两部分所组成：
分段式存储管理是在可变分区存储管理方式的基础上发展而来的。在分段式存储管理方式中，以段为单位进行主存分配，每一个段在主存中占有一个连续空间，但各个段之间可以离散地存放在主存不同的区域中。为了使程序能正常运行，即能从主存中正确找出每个段所在的分区位置，系统为每个进程建立一张段映射表，简称段表。每个段在表中占有一个表项，记录该段在主存储器中的起始地址和长度。段表实现了从逻辑段到主存空间之间的映射。
段式存储管理的地址映射
从段表中找到段号对应的基址加上段内地址即为物理地址。
$物理地址=基址+段内地址$
空闲区的合并
如果在装入某段信息时找不到满足该段地址空间大小的空闲区，则可采用移动技术合并分散的空闲区，以利于大作业的装入。
当采用分段式存储管理的作业执行结束后，它所占据的主存空间将被回收，回收后的主存空间登记在空闲分区表中，可以用来装入新的作业。系统在回收空间时同样需要检查是否存在与回收区相邻的空闲分区，如果有，则将其合并成为一个新的空闲分区进行登记管理。
段表存放在主存储器中，在访问一个数据或指令时至少需要访问主存两次以上。为了提高对段表的存取速度，通常增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的段表项。
页式存储管理与段式存储管理的区别
| 页式存储管理 | 信息的物理单位 | 大小固定且由系统决定 | 地址空间是一维 |
|---|---|---|---|
| 段式存储管理 | 信息的逻辑单位 | 大小不等且由用户决定 | 地址空间是二维 |
- 页是信息的物理单位，是系统管理的需要而不是用户的需要；而段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段是为了更好地满足用户的需要。
- 页的大小固定且由系统决定，因而一个系统只能有一种大小的页面；而段的长度却不固定，由用户所编写的程序决定，通常由编译程序对源程序进行编译时根据信息的性质来划分。
- 分页式作业的地址空间是一维的，页间的逻辑地址是连续的；而分段式作业的地址空间则是二维的，段间的逻辑地址是不连续的。
段页式存储管理
段页式存储管理的基本原理
用户对作业采用分段组织，每段独立编程，在主存空间分配时，再把每段分成若干个页面，这样每段不必占据连续的主存空间，可把它按页存放在不连续的主存块中。
段页式存储管理的逻辑地址格式如下：
段页式存储管理为每一个装入主存的作业建立一张段表，且对每一段建立一张页表。段表的长度由作业分段的个数决定，段表中的每一个表目指出本段页表的始址和长度。页表的长度则由对应段所划分的页面数所决定，页表中的每一个表目指出本段的逻辑页号与主存物理块号之间的对应关系。
段页式存储管理的地址映射
逻辑地址—– >段号、段内页号、页内地址
段表寄存器— >段表始址
段号+段表始址—- >页表始址
页表始址+段内页号—–>存储块号
块号+页内地址——>物理地址
段页式存储管理的总结
- 先分为若干段，每一段分为若干页，再按页式管理，页间不要求连续。
- 用分段方法分配管理作业或进程，用分页方法分配管理内存。
- 兼有段式和页式管理的优点，系统复杂性和开销增大。
页面置换算法
在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
最佳页面置换算法（OPT, Optimal replacement algorithm）
所选择的被换出的页面将是最长时间内不再被访问的，通常可以保证获得最低的缺页率。
最佳页面置换算法是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
例子：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
1 | 1,3,4,3,5,6 |
| 访问页面 | 1 | 3 | 4 | 3 | 5 | 6 |
|---|---|---|---|---|---|---|
| 物理块 1 | 1 | 1 | 1 | 5 | 5 | |
| 物理块 2 | 3 | 3 | 3 | 3 | ||
| 物理块 3 | 4 | 4 | 6 | |||
| 缺页标记 | √ | √ | √ | √ | √ |
缺页次数为 5
缺页率为 $\frac{5}{6}$
最近最久未使用页面置换算法（LRU, Least Recently Used）
虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
LRU 性能较好，但需要寄存器和栈的硬件支持。
例子：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
1 | 1,3,4,3,5,6 |
| 访问页面 | 1 | 3 | 4 | 3 | 5 | 6 |
|---|---|---|---|---|---|---|
| 物理块 1 | 1 | 1 | 1 | 5 | 5 | |
| 物理块 2 | 3 | 3 | 3 | 3 | ||
| 物理块 3 | 4 | 4 | 6 | |||
| 缺页标记 | √ | √ | √ | √ | √ |
缺页次数为 5
缺页率为 $\frac{5}{6}$
先进先出置换算法（FIFO, First In First Out）
当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。
内存的页面中驻留主存时间最长的页面，会被新的页面直接覆盖，而不是驻留主存时间最长的页面先出队，然后新的网页从队尾入队。
例子：一个系统为某进程分配了三个物理块，并有如下页面引用序列：
1 | 1,3,4,3,5,6 |
| 访问页面 | 1 | 3 | 4 | 3 | 5 | 6 |
|---|---|---|---|---|---|---|
| 物理块 1 | 1 | 1 | 1 | 5 | 5 | |
| 物理块 2 | 3 | 3 | 3 | 6 | ||
| 物理块 3 | 4 | 4 | 4 | |||
| 缺页标记 | √ | √ | √ | √ | √ |
缺页次数为 5
缺页率为 $\frac{5}{6}$