存储系统

分级存储体系

两级存储：Cache-主存、主存-辅存（虚拟存储体系）

计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。

局部性原理

在 CPU 运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：

• 时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能被再次访问，即在 相邻的时间里会访问同一个数据项。
• 空间局部性原理：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即 相邻的空间地址会被连续访问

Cache

高速缓存 Cache 用来存储当前最活跃的程序和数据，直接与 CPU 交互，位于CPU和主存之间，容量小，速度为内存的 5-10 倍，由半导体材料构成。其内容是主存内容的拷贝副本，对于程序员来说是透明的。

Cache 由控制部分和存储器组成，存储器存储数据，控制部分判断 CPU 要访问的数据是否在 Cache 中，在则命中，不在则依据一定的算法从主存中替换。

命中率和平均时间

Cache 有一个命中率的概念，即 当 CPU 所访问的数据在 Cache 中时，命中，直接从 Cache 中读取数据，设读取一次 Cache 的时间为 1ns，若 CPU 访问的数据 不在 Cache 中，则需要从内存中读取，设读取一次内存的时间为 1000ns，若在 CPU 多次读取数据过程中，有 90% 命中 Cache，则 CPU 读取一次的平均时间为 $(90\% \times 1 + 10\% \times 1000)ns$

Cache 的替换算法

为了便于 CPU 访问，要把主存中经常访问的内容调入 Cache 中去。当 Cache 满了之后，就需要替换掉不常用的块。

替换算法的目标就是使Cache 获得尽可能高的命中率。常用的替换算法有如下几种。

1. 随机替换算法：就是用随机数发生器产生一个要替换的块号，将该块替换出去。
2. 先进先出算法：就是将最先进入 Cache 的信息块替换出去。
3. 最近最少使用算法（最常用）：这种方法是将近期最少使用的 Cache 中的信息块替换出去。
4. 优化替换算法：这种方法必须先执行一次程序，统计 Cache 的替换情况。有了这样的先验信息，在第二次执行该程序时就可以用最有效的方法来替换。

地址映像

在 CPU 工作时，送出的是主存单元的地址，而应从 Cache 存储器中读/写信息。这就需要 将主存地址转换为 Cache 存储器地址，这种地址转换称为地址映像，由硬件自动完成，分为下列三种方法：

直接映像

将Cache存储器等分成块，主存也等分成块并编号。主存中的块与 Cache 中的块的对应关系是固定的，也即 两者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。

先按 Cache 的区域将内存分成区，每个区分成不同块，可以是不同区的块号相同才能命中。

全相联映像

提示

这里的主存没有分区

同样都等分成块并编号。主存中任意一块都与 Cache 中的任意一块对应。因此 可以随意调入 Cache 任意位置，但地址变换复杂，速度较慢。因为主存可以随意调入 Cache 任意块，只有当 Cache 满了才会发生块冲突，是最不容易发生块冲突的映像方式。

组组相连映像

前面两种方式的结合，将 Cache 存储器先分块再分组，主存也同样先分块再分组，组间采用直接相连映像，即主存中组号与 Cache 中组号相同才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。

磁盘的结构和参数

磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。

磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，因此，会产生 寻道时间和等待时间。

存取时间 = 寻道时间 + 等待时间(平均定位时间+转动延迟)

提示

寻道时间是指磁头移动到磁道所需要的时间；等待时间为等待读写的扇区转动到磁头下方所用的时间。

磁盘调度算法

磁盘数据的读取时间分为寻道时间+旋转时间，其中寻道时间耗时最久，需要重点调度，有如下调度算法：

• 先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。
• 最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生饥饿现象，有的进程可能永远无法访问。
• 扫描算法 SCAN：又称为 ”电梯算法“，磁头在磁道上双向移动，磁头永远是从里向外或者从外向里一直移动完才掉头，与电梯类似。
• 单向扫描算法 CSCAN：与 SCAN 不同的是，只做单向移动，即只能从里向外或者从外向里。