操作系统之存储管理
存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和扩充。存储管理的目的是尽量提高内存的使用效率。
存储分配的四个算法
- 首次适应算法：把内存中的可用分区单独组成可用的分区表或可用分区自由链，按照起始地址递增的次序排列。每次按递增次序向后找，一旦找到大于或等于所要求内存长度的分区，则结束探索。从找到的分区中找出所要求的内存长度分配给用户，并把剩余的部分进行合并。
- 循环适应算法：上述首次适应算法经常利用的是低地址空间，后面经常是比较大的空白区，为了使内存所有线性地址空间尽可能轮流使用到，每重新分配一次，都在当前之后寻找。
- 最佳适应算法：是将输入作用放入主存中与它所需大小最接近的空白区中，使剩下的未用空间最小，该法要求空白区大小按从小到大次序组成空白区可用表或自由链。在进行分配时总是从最小的一个开始查询，因而找到的一个能满足要求的空白区就是最佳的一个。
- 最差适应算法：分配时把一个作业程序放入主存中最不合适它的空白区，即最大空白区（空闲区）。
考题：
（1）实存的存储分配算法用来决定输入的程序和数据放在主存的位置，采用“总是把程序装入主存中最大的空闲区域”的算法称为 _____ 。（最差适应算法）
段页式存储管理
1. 分页存储
分页存储的特点：
- 采用动态地址变换会增加计算机成本并降低处理机的速度
- 各种表格要占用一定容量的主存空间，而且还要花费一部分处理机时间用来建立和管理这些表格
- 虽然碎片消除，但每个作业的最后一页一般都有不能充分利用的空白区
- 存储扩充问题仍没有解决
页表：
页表列出了程序逻辑地址中的页号与主存中的物理地址块号之间的对应关系，其中包含若干个表目。
假设一个逻辑地址空间中的地址为A，页面的大小为L，则页号p和页内地址d可按照下面的式子求得：
ｐ＝ Int[A/L] 即Ａ除以Ｌ后取整（2500 / 1kB = 2）
ｄ＝ A mode L 即Ａ除以Ｌ的余数 (2500 % 1kB = 452)
然后根据页号查页表得到物理块号b，计算得到物理地址 B = b * l + d。
考题：
（1）页式存储系统的逻辑地址由页号和页内地址两个部分组成。假定页面的大小为4KB，地址变换过程如下图所示，其中逻辑地址用十进制表示。
图中有效地址经过变换后，十进制物理地址a应为 _____ 。（答案：33220 = 8 * 4KB + 452）
2. 分段存储
分段存储优点：
- 消除了碎片
- 信息的逻辑单位（提供了大容量的虚存）
- 各程序的修改互不影响（动态的装入和链接）
- 有利于信息共享
分段存储缺点：
- 存储管理地址变化需要花费处理机较多时间处理
- 存在抖动（后面介绍）
段页式存储管理
定义：它吸引了分段存储管理和分页存储管理各自的优点，在这种存储管理系统中处理机给出的有效地址被划分为3部分，即段号、页号和页内地址。
考题：
（1）当存储器采用段页式管理时，主存被划分为定长的 _____ ，程序按逻辑模块分成 _____ 。在某机器的多道程序环境下，每道程序还需要一个 _____ 作为用户标志号，每道程序都有对应的 _____ 。一个逻辑地址包括 _____ x、段号s、页号p和页内地址d这4部分。（页、段、基号、一个段表和一组页表、基号）
注：
每道程序可以有多个段，但只有一个段表，每个程序可以有多个页表
页面调度
如果选择的页面被频繁地装入和调出，这种现象称为“抖动”，应该减少和避免抖动现象。
为了解决抖动现在，聪明的人们想出了这么多的方法：
- 最优算法：选择不再使用或者最远的将来才会被使用的页，常用于淘汰算法的比较
- 随机算法：随机选择被淘汰的页，开销小，但是可以选中立即要访问的页
- 先进先出算法
- 最近最少使用
- 最不经常使用的页面先淘汰