操作系统学习之存储器层次结构
操作系统学习之存储器层次结构
存储器系统是一个具有不同容量，成本和访问时间的存储设备层次结构，如下图所示，CPU寄存器保存最常用数据，靠近CPU的小的、快速的高速缓存存储器(Cache)，然后是相对慢的主存(也就是常说的内存)，然后是本地存储(固态，磁盘)，也可能有远程存储(主要实现于分布式文件系统，Web服务器等)。
整个存储器系统，从上到下访问的时间越来越长，速度越来越慢，当然成本也越来越低。
- CPU寄存器的访问在零个周期就可以访问到，高速缓存(cache memory)在1 ~ 30个周期访问，主存(内存)在50 ~ 200个周期访问，本地磁盘大约需要几千万个周期，这里的周期指的是纳秒(ns)级别。
存储技术
不同层次的存储器实现的方式不同，价格也不同， 从而导致它们的存储大小受到限制。
随机访问存储器
随机访问存储器(RAM)，分为两类：静态和动态的，静态的比动态的更块，当然价格也更昂贵，因此一般用静态RAM(SRAM)来作为CPU和主存之间的高速缓存(Cache)，而动态RAM(DRAM)速度稍微慢一些，因此一般用作系统的主存(内存)。
静态RAM(SRAM)
SRAM是一种非常稳定的存储技术，确保只要有电，它就是稳定的，即使有干扰，也会在干扰过后，迅速保持稳定。
动态RAM(DRAM)
由于硬件原因，DRAM的稳定性和抗干扰能力不如SRAM，DRAM存储器单元对干扰特别敏感。因此对速度有影响。
DRAM的设计可以看作是一个二维表，当需要访问某个坐标中的数据时，假设需要访问(x,y)位置的数据，首先取出x的整行的数据，然后在取出y位置的数据，然后在舍弃整行数据、即使下一次访问的即使同一行数据，也会将该行丢弃，这是传统的DRAM的设计方式，以后增强版的DRAM有针对DRAM的缺陷的修改，例如快页模式DRAM就是对连续读取同一行的访问，不会每次都丢弃在获取，而是在第一次访问后存放在行缓冲区中，然后下次访问该行数据需要y匹配即可。
非易失性存储器
对于DRAM和SRAM来说，如果断电他们的数据就会丢失，因此称为易失性存储器，另一种是非易失性存储器，即使断电，信息仍然可以保存。**闪存就是一类非易失性存储器，**现在计算机中使用的固态硬盘就是一种新型的基于闪存实现的磁盘，它能提供比旋转磁盘更快，更强健和更低能耗的选择。
磁盘存储
磁盘是计算机中最大的存储单元，成本比较低，访问速度比较慢。
磁盘的构造
磁盘是由盘片构成的，每个盘片有两个面称为表面，盘片中央有一个可以旋转的主轴，它可以使得盘片以固定的旋转速率旋转，通常是5400 ~ 15 000转每分钟。盘片表面由一组称为磁道的同心圆组成，每个磁道被划分为一组扇区，每个扇区包含相同数量的数据位(通常为512字节)，扇区中间有一些间隙分隔开，间隙中不存储数据位，用来表示扇区的格式化位。
磁盘容量
一个磁盘上可以记录的最大位数称为最大容量，简称容量。
容量 = 扇区字节数 * 扇区数 * 磁道数 * 2(表面) * 盘片数 ==》 xxx字节 ， 1GB = 10^9字节。
磁盘操作
磁盘用读/写头 来读写存储在磁盘上的数据，而读写连接到一个传动臂的一端，通过沿着半径轴前后移动这个传动臂，驱动器就可以将读写投定位到盘面的任何磁道上，这个称为寻道，传动臂到磁道的高度0.1微米，因此如果磁道中落入灰尘，就会发生读/写头冲撞，所以磁盘总是密封包装。
访问时间
磁盘以扇区大小的块来读写数据，对扇区的访问时间包括：寻道时间，旋转时间，传送时间。
寻道时间
为了读取目标扇区的内容，传动臂首先将读/写头定位到包括目标扇区的磁道上，这个过程就成为寻道时间，寻道时间一般依赖于读/写头以前的位置和传动臂的旋转时间。
旋转时间
一旦读/写头定位到目标扇区的磁道中，就等待目标扇区的第一个位然后开始读写旋转，这一步依赖于当前读写头到达目标扇区的盘面的位置和磁盘旋转速度。其实就是一个圆面上，有可能寻道后刚好就是目标扇区的第一个位置，也可能刚好转过去了，是目标扇区最后一位的下一个位置，那就需要等待盘面旋转过来后在读/写。
传送时间
当目标扇区的第一个位位于读写头下时，驱动器就可以开始读或者写该扇区的内容了，一个扇区的传送时间取决于旋转速度和每条磁道扇区的数目。
逻辑磁盘块
由于现代的磁盘非常复杂，为了隐蔽这些复杂，对所有的扇区编号，将磁盘看作是一个由M个扇区块组成的序列，然后使用磁盘控制器进行维护逻辑块和实际物理扇区之间的映射关系。
当操作系统进行一次IO时，发送一条指令到磁盘控制器，然后控制器执行快速表查询，将指令翻译成(盘面，磁道，扇区)的三元组，这个三元组唯一标识了对应的物理扇区，然后读取数据。
固态硬盘
固态硬盘(SSD)是一种基于闪存实现的存储技术，一个SSD包由一个或者多个闪存芯片和闪存翻译层组成，闪存芯片实现磁盘中的机械旋转器，闪存翻译层实现的磁盘控制器的角色。将对逻辑块的请求翻译成对物理层的访问。如下图
访问主存
数据流通过总线在处理器和DRAM之间进行数据传输，CPU每次和主存之间数据传输都是由一系列步骤组成，称为总线事务。读事务：从主存传送数据到CPU，写事务：从CPU传送数据到主存。
总线是一组并行的导线，能携带地址，数据和控制信号，数据和地址信号可以共享统统一组导线，也可以各自分开使用，控制线携带的信号会同步事务，并表示当前正在被执行的事务的类型。
典型的连接CPU和主存的总线结构
I/O桥将进行系统总线的电子信号和存储器总线的电子总线之间的相互转换。
除了系统总线和存储器总线还有一个IO总线，像图像卡，键盘鼠标等都是通过IO总线连接到CPU和主存的，如下图。
访问磁盘
CPU使用一种称为存储器映射IO的技术来向IO设备发出命令。在一次磁盘读访问过程中CPU发送三条指令：指令1：告诉磁盘发起一个读操作；指令2：指明应该读的逻辑块号；指令3：指明应该存储磁盘扇区内容的主存地址。
然后读取该扇区的内容，读取的内容将直接传送给主存，不需要CPU干涉，设备自己可以执行读写总线事务，这个过程称为直接存储器访问(DMA)，这种数据传送称为DMA传送，传送完成后，磁盘控制器给CPU发送一个中断信号来通知CPU，然后CPU再继续处理。
局部性
在现代计算机设计中，大量使用到了局部性原理的思想，从而加快计算机的操作速度，因此了解局部性原理还是很有必要的。
所谓的局部性原理就是在程序运行期间，对数据或者指令的访问倾向于最近使用过的或者最近使用的数据的附近的数据。被分为时间局部性和空间局部性。
良好的时间局部性就是被引用过一次的存储器位置很可能在不远的将来再次被使用到。
良好的空间局部性就是一个存储器被引用一次，那么程序很可能在不远的将来引用到附近的一个存储器位置。
在硬件设备中，局部性原理允许计算机设计者通过引入高速缓存存储器的小而快速的存储器来保存最近被引用的指令和数据项，从而提高CPU对主存的访问速度。
在操作系统中，局部性原理允许操作系统使用主存作为虚拟地址空间来做最近被引用的块的高速缓存。系统也利用主存来缓存磁盘文件中最近被使用的磁盘块。
在Web浏览器中，最近被引用的网页缓存在本地或者是代理服务器上，等等都是利用局部性原理。
高速缓存存储器
高速缓冲是为了解决CPU和主存之间的差距而实现的，在现在计算机系统中，高速缓存成为了CPU访问主存的中间桥梁。并且为了提高效率，现代计算机中甚至由三级高速缓存，LI高速缓存 – L2高速缓存 – L3高速缓存，其各自访问周期分别是2 ~ 4周期，大约10周期和30 ~ 40周期。
高速缓存存储器的实现机制都是一样的，因此假设只有一级高速缓存来介绍高速缓存。
高速缓存存储器结构
在一个计算机系统中，其中每个存储器地址由m位，形成M= 2^ m 个不同的地址，那么这样一个机器的高速缓存存储器被组织成一个有S = 2^ s 个高速缓存组(cache set)的数组，每个Cache Set包含E个高速缓存行(Cache line)，每个行是由B = 2^b字节的数据快组成的，一个有效位指明这个行是否包含有意义的信息。还有t = m - (b + s)个标记位，它们唯一的标识存储在这个高速缓存行的块。
另外高速缓存结构将M个地址位划分为t个标记位，s个索引位和b个块偏移位，一般而言，高速缓存的结构可以用元组(S，E，B，m)来描述。高速缓存的大小指定是所有块的大小，不包括状态位和标记位，C = S * E * B。
那么缓存是如何工作的呢
当CPU发送一条指令时，假设时访问地址A，CPU将地址A发送给高速缓存，如果高速缓存中保存着这个地址，那么就地址对应的数据返回CPU，高速缓存的结构使得它能通过简单的检查地址位，找到请求的字。
因为高速缓存将地址划分为三部分，地址中的s段位用来索引地址所在的高速缓存数组中的对应的组E，组索引被解释为一个无符号整数，然后使用地址中的t段位来判断该组中哪一行包含这个字，标记位匹配成功以后，那么这个组中的这一行有这个数据，然后在根据地址中b段位的偏移值找到这个字。
直接映射高速缓存
据每组(E)中的高速缓存行的个数，高速缓存被分为不同的映射。每组(E)中只有一个Cache line，那么这样的高速缓存使用的映射就是直接映射。
直接映射高速缓存比较容易理解，因为每组只有一个高速缓存行。
直接映射高速缓存在处理不命中的行替换也比较简单，因为每组中只有一个行，所以直接替换策略就可以。
因为每个组中只有一个高速缓存行，因此对于这种来说可能就比较麻烦，因为映射到同一个高速缓存行的会有多个地址，那么直接映射高速缓存非常容易引起冲突不命中因此可能两块交替使用的地址刚好映射的是同一个高速缓存行，那么就需要不断的进行Cache替换，从而导致抖动。抖动就是高速缓存反复加载和驱逐相同的高速缓存块的组。
组相联高速缓存
因为直接映射高速缓存经常发生冲突不命中的问题， 而其问题正是因为每组只有一行。而组相联高速缓存就是将每个组实现成多余一个高速缓存行。通常称为E路组相联高速缓存。
组相联高速缓存中的组选择和直接映射高速缓存的组选择一样。
组相联高速缓存中的行匹配和字段选择比直接映射高速缓存更复杂，因为他必须检查整个组中的所有行的标记位和有效位，以确定请求是否在集合中。一个相联的存储器是一个(key value)对的数组，以key为输入，返回与输入的key相匹配的(key，value)对中的value的值，key就是标记位和有效位，而value就是块的内容。
对于组相联高速缓存来说，有一个重要的思想就是组中的任何一行都可以包含任何到映射到这个组的存储器块，所以高速缓存必须搜索组中的每一行，寻找一个有效的行，其标记与地址中的标记相匹配，如果命中，然后就偏移找到这个字。
组相联高速缓存存在不命中时的行替换
对于组相联高速缓存的行替换，是需要有一定的策略的，因为每组的由多个行，如果地址映射到该组，该组有空行就直接存入，如果没有空行就需要进行行替换。最简单的策略就是随机选择要替换的行 更复杂就是利用局部性原理，使得最近可能被使用的被替换的效率最下，例如使用LRU算法(最近最少使用算法)来替换最后一次访问时间最久远的哪一行。
全相联高速缓存
全相联高速缓存就是所有的行直接组成一个组。
全相联的策略地址中省略了组索引的s位，只有t标记位和d偏移位，全相联对于一次地址的匹配需要对整个组进行遍历，因此全相联只适合做小的高速缓存。
为什么要使用中间位来表示组索引
高速缓存使用中间位表示组索引是有原因的，如果使用高位做索引，那么一些连续的块就会被映射到相同的高速缓存组中，这样程序可能只能用到整个高速缓存的一个组，高速缓存的使用率比较低，而如果以中间位作为组索引，相邻的块会被映射到不同的高速缓存组中，这样对于高速缓存的使用率比较好。更好的发挥其作用。
有关高速缓存的写问题
CPU可能不只是对数据进行读操作，也可能对数据进行写操作，那么对于写操作的数据是需要回写的，高速缓存是如何实现回写的？
直写
在CPU对高速缓存的数据进行更新后，然后高速缓存立即将修改的数据回写到内存中，这种实现简单，但是会引起反复的总线流量。
回写
所谓回写就是推迟数据的更新，对于缓存中数据的修改不急于写到内存，而是等下当前的Cache line需要进行替换时，在将数据进行回写操作，当然这样可以减少总线流量，但是却增加复杂度，因为必须为每个Cahce line维护一个修改位，表明这个高速缓存是否被修改。
写不命中问题
对于写不命中，即当要写的地址不在Cache中，那么就出现写不命中，有两种解决办法。
写分配
所谓写分配就是加载相应的相应的低一级中的块到Cache中，然后更新这个Cache，写分配尸体利用写的空间局部性，因为这个位被写，其附近位也可能被写，但是缺点是每次不命中都需要从低一级中传送到高速缓存中。
非写分配
不经过高速缓存，直接将数据写到低一级中。
直写高速缓存通常就是非写分配，回写高速缓存通常就是写分配。
参考：《深入理解计算机系统》
第一次简总存储器层次以及高速缓存(Cache)，如有不足，请指正，谢谢！！！