操作系统 三（存储管理）

一、 存储系统的“金字塔”层次结构

1. 设计原理：

cpu自身运算速度很快。内存、外存的访问速度受到限制

2. 各层次存储器的特点：

1）主存储器（主存/内存/可执行存储器）

保存进程运行时的程序和数据，内存的访问速度远低于cpu执行指令的速度。

2）寄存器

cpu内部一些小型存储区域，暂时存放参与运算的指令、数据和运算结果等。

寄存器与处理机相同速度，完全与cpu协调工作，容量不大。

3）高速缓存

介于寄存器和内存之间，主要用于备份内存中较常用的数据，减少处理机对内存的访问次数。容量远大于寄存器，比内存小两个到三个数量级。为了缓和内存与处理机速度之间的矛盾。

4）磁盘缓存

缓和磁盘的I/O速度远低于内存的访问速度，主要用于暂时存放频繁使用的一部分磁盘数据，减少访问磁盘的次数。本身不实际存在，利用内存中的部分存储空间，暂时存放从磁盘中读出（写入）的信息。

3. 结构的优点：

二、 装入、链接

1. 装入

1）绝对装入

单道程序环境。编译后，产生绝对地址的目标代码。逻辑地址与实际地址完全相同。

2）可重定位装入

根据内存的具体情况，将装入模块装入内存的适当位置。所有逻辑地址与实际装入内存的物理地址不同。

把装入时对目标程序中指令和数据的逻辑地址变换为物理地址，称为重定位。

不允许程序运行时在内存中移动位置。

3）动态运行时装入

一个进程可能被多次换出、换入，换入后位置通常不同。

在装入模块装入内存后，不会立即把装入模块中的相对地址变换为绝对地址，程序真正要执行时才进行地址变换。“动态重定位”

2. 链接

1. 静态链接

在程序运行之前，将各目标模块及所需库函数链接成一个完整的装配模块，不再拆开。

装配成一个装入模块时：①修改相对地址②变换外部调用符号

2. 装入时动态链接

将用户源程序编译后所得一组目标模块，边装入边链接。

优点：

①便于修改和更新

②便于实现对目标模块的共享

3. 运行时动态链接

在执行过程中，发现一个“被调用模块”还未被装入内存时，立即由os找到该模块，装入内存并链接到装入模块。

1. 三、 动态分区分配算法（论述分析、计算）

1. 首次适应算法

空闲分区链从链首开始顺序查找，大小满足就划分。

保留了高址部分的大空闲分区，低址部分不断被划分，留下很多碎片。

2. 循环首次适应算法

从上次找到的空闲分区的下一个空闲分区开始查找，直至找到。若链尾空闲分区的大小不满足要求，应返回第一个空闲分区比较大小。

减少了查找空闲分区时的开销，使大的空闲分区较缺乏。

3. 最佳适应算法

将所有的空闲分区按容量以从小到大的顺序排好，第一次找到能满足要求的空闲分区即是最佳。

存储器中会留下许多难以利用的碎片。

4. 最坏适应算法

将空闲分区从大到小排好，挑选最大的空闲区，缺乏大的空闲分区。

产生碎片概率小，查找效率很高。

5. 四、 重定位、对换

6. 五、 分页存储 （综合应用）

系统为每个进程建立一个页表，给出“逻辑页号”和具体“内存块号”的对应关系，实现从页号到物理块号的地址映射。

设置页表始址寄存器、页表长度寄存器

优点：实现简单、易于共享、内碎片小、不存在外碎片----->改进：多级页表

缺点：页表长度过大、程序运行中不是所有页面都要装入内存

多级页表：页表也进行分页，内存仅存放当前使用的页表，不用的放在磁盘上。为小页表建一张页目录表。

逻辑地址：页目录、页表页、位移。

内存有效访问时间：

EAT=2t

引入快表后：EAT=a×λ+（1-a）×（t+λ）+t

t：一次内存访问时间 λ：查找快表所需时间 a：命中率

7. 六、 段式存储

段表寄存器：段表起始地址、段表长度

8. 七、 分段和分页区别

同：

都采用离散分配方式；

都通过地址映射机构实现地址变换

异：

①页是信息的物理单位。分页是系统管理的需要，对用户不可见。

段是信息的逻辑单位。通常包含一组意义相对完整的信息。

②页的大小固定，由系统决定。段的长度不固定，取决于用户所编写的程序。

③分页的用户程序地址空间是一样的，用户程序地址属于单一的线性地址空间。分段是用户的行为，分段系统中，用户程序的地址空间是二维的，标志一个地址时需给出段名，段内地址。

9. 八、 虚拟存储

10. 定义

当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。

11. 页表（与分页对比）

12. 缺页中断

需要访问的页面不在内存中，产生缺页中断。os接到信号后，根据页表中给出的外存地址，将该页调入内存。

内存中有空闲块，则直接分配一页，修改页表。

内存中没有空闲块，淘汰某页，若被修改过则写回外存。

13. 页面淘汰算法

①最佳页面置换算法（OPT）

将以后永不使用或(未来）最长时间内不会被访问的页面淘汰。

保证最低缺页率。

②先进先出（FIFO）

淘汰在内存中驻留时间最长的页面。

③最近最久未使用（LRU）

淘汰最后一次访问时间距离当前时间最长的一页。

需要记录各个页的最后使用时间。

④最少使用（LFU）

淘汰最近一段时间未使用过的一页。

缺页率：缺页中断次数/总页面访问次数

14. 抖动、工作集

抖动：进程频繁的将页面换进和换出

进程未获得足够的物理页面，缺页率非常高，导致较低的cpu利用率。

工作集：某段时间内进程访问的页面集合