计算机储存系统和缓存

计算机采用分级存储体系的主要目的是为了 解决存储容量 、成本和速度之间的矛盾问题
两级存储： Cache-主存 、主存-辅存（虚拟存 储体系）

寄存器 （cpu，64位比特位），Cache（SRAM相联存储器）， 内存（主存，DRAM，RAM，ROM（掉电不会丢失）），外存（辅存）

cache缓存

高速缓存cache

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

cache

由控制部分和存储器组成， 存储器存储数据， 控制部分判断CPU要访问 的数据是否在Cache中， 在则命中， 不在则依据一定的算法从主存中替换，设置多级高速缓存Cache可以提高命中率（访问主存的效率）

使用Cache改善性能的依据是程序的局部性原理

时间局部性：被引用过一次的存储位置可能在未来会被多次引用 （for循环）

空间局部性：如果一个存储器的位置被引用，那么将来它附近的位置也会被引用 （顺序执行过程）

地址映射

在CPU工作时， 送出的是主存单元的地址， 而应从Cache存储器中 读／写信息 。这就需要将主存地址转换为Cache存储器地址， 这种地址的转换称为地址映射， 由硬件自动完成映射，Cache与主存的地址映射（主存与外存的地址映射是由软件和硬件结合完成的）

1、直接映射： 将Cache存储器等分成块， 主存也等分成块并编号，二者块号相同才能命中

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

3、组组相连映射： 前面两种方式的结合，组间采用直接映像， 即主 存中组号与Cache中组号相同的组才能命 中， 但是组内全相联映像， 也即组号相同 的两个组内的所有块可以任意调换

地址映像方法	描述	优点	缺点
直接相联映像	主存的块与Cache的块的关系是固定的	硬件电路设计，地址变换简单	冲突率较高，灵活性较差
全相联映像	主存与Cache均分大小相同的块，允许主存的任何一块可以调入Cache存储器的任何一块	冲突率较低，主存的块调入Cache的位置不受限制，十分灵活	电路难于设计和实现，只适用于小容量的Cache，无法从主存块号直接获得Cache块号，变换比较复杂，速度较慢
组相联映像	将Cache中的块再分组，组采用直接相联，块采用全相联	折中	折中

替换算法

替换算法的目标就是使Cache获得尽可能高的命中率，当发生冲突时，需要进行页面淘汰
1、随机替换算法 （RAND）。就是用随机数发生器产生一个要替换的块号， 将该块替换出去 。
2、先进先出算法 （FIFO）。就是将最先进入Cache的信息块替换出去 。
3、近期最少使用算法（LRU） 。这种方法是将近期最少使用的Cache中 的信息块替换出去 。
4、优化替换算法 。这种方法必须先执行一次程序， 统计Cache的替换情况 。有了这样的先验信息， 在第二次执行该程序时便可以 用最有效的方式来替换

5、最不频繁使用算法（LFU），计数器，统计使用次数，计数器位数比较多，实现困难

cache读写过程

写直达：同时写Cache和内存

写回：只写cache，淘汰页面时写回内存

标记法：只写入内存，并将标志位清零，若用到此数据，只需要再次调取

cache命中率

设读取一次Cache时间为1ns， 若 CPU访问的数据不在Cache中， 则需要从内存中读取， 设读取一次内 存的时间为1000ns， 若在CPU多次读取数据过程中， 有90％命中
Cache， 则CPU读取一次的平均时间为（ 90％＊ 1＋10％＊ 1000） ns

存储磁盘

磁盘

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

磁头首先要寻找到对应的磁道， 然后等待磁盘进行周期旋转， 旋转到指定的扇区 ， 才能读取到对应的数据，

所以一般先进行移臂调度，切换不同磁道，再进行旋转调度，旋转到指定扇区

因此， 会产生寻道时间和等待时间 。公式为： 存取时间 = 寻道时间＋等待时间（平均定位时间 ＋转动延迟） 。
注意： 寻道时间是指磁头移动到磁道所需的时间； 等待时间为等待读写的扇区转到磁头下方所用的时间 。

磁盘调度算法

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