计组-理论-虚拟存储系统
辅助存储器
区别于主存的存储设备，不直接与CPU交换数据
特点：容量大、价格低、非易失性、速度慢
磁记录方式
磁表面存储设备：磁介质+磁头
磁介质：通过磁头与介质的相对运动完成读写操作
写入操作：磁化过程。根据写入代码，确定写入驱动电流的方向，使磁表面被磁化的极性方向不同，以记录0和1
读出操作：感应过程。磁头相对磁化单元做切割磁力线运动，磁化单元的极性决定了感应电势的方向，以此区别0和1
编码方式
磁记录编码方式：怎么把一连串的二进制信息转换为磁层中一个序列的磁化反转状态，且可靠地使用电路实现这一转换过程
- 归零制RZ：正负脉冲电流
- 不归零制NRZ：正反向电流
- 曼彻斯特编码
- 调相制PM：磁化翻转方向，一般使用这种
- 调频制FM：磁化反转频率
曼彻斯特编码
调相制和调频制都是曼彻斯特编码，将01/10串转变为0/1的信息。每一位的中间有一次跳变。能够利用00和11识别出来确定每个位的开始和结束。
- 优点：跳变电平传输同步时钟信息，无需单独时钟同步信号，不含直流分量，具有很好的抗干扰能力，更适合于信道传输。
- 缺点：编码效率较低，数据传输率只有信号速率的 1/2。
如果曼彻斯特码数据流中只有1或0是不能得到正确的译码结果的，如果曼彻斯特编码数据流中出现00，则00前后的码元必定是1；如果曼彻斯特编码数据流中出现11，则00前后的码元必定是0，因此，我们可以将00与11作为曼彻斯特码译码的标志位。
在实际设计电路中，可以采用一个缓存器，保存上一个时钟采集到的信号和当前时钟采集到的信号，当缓存器的内容是01时，输出1；当缓存器的内容是10时，输出0；当缓存器的内容是00或11时，输出维持不变。
状态机的思想
编码性能
编码效率：记录一位信息的最大磁化翻转次数的倒数；FM与PM为2（50%），NRZ 为1（100%）
自同步能力：能否直接从读出的信号中提取同步信号；NRZ没有自同步能力，PM、FM 等都具备自同步能力
可靠性：归零制低，调相制高
硬磁盘
基本结构：磁盘控制器+磁盘驱动器（盘片）
磁盘控制器： 将主机发来的命令转化为对驱动器的控制命令，实现主机和驱动器之间的数据格式转化和传送，并控
制驱动器读写
磁盘驱动器（盘片）：存储和读写数据
磁盘结构与格式
数据结构：盘面（磁头： Head）、磁道（柱面： Cylinder）、扇区（ Sector）
每个磁道包含的扇区数相同，扇区容量为512 Bytes。能够访问的最小单位是扇区
扇区的地址表示：磁道-盘面-扇区，注意盘面在中间
在实际的扇区中，会加上其他的一些控制信号来提高读取的准确度，如同步信号等
磁盘的性能参数
记录密度：
- 道密度：磁盘沿半径方向单位长度的磁道数
- 位密度：单位长度磁道记录二进制的位数
存储容量：盘面数（磁头数）*每盘面的磁道数*每磁道的扇区数*扇区容量
访问时间（寻址时间）：
- 寻道时间：磁头从当前位置定位到目标磁道所需时间（平均值）
- 寻区时间：磁头定位到目标磁道后，等待目标扇区旋转到磁头下所需的时间（平均值）
数据传输率：单位时间内传输的数据位数（b/s）
磁盘
磁盘：软盘+硬盘（IDE+SCSI+SATA+SAS）
见课件相关内容
光盘
数据记录：凹凸点，凹点表示0，凸点表示1
虚拟存储器
在实际运行过程中，可能出现单程序或多程序（线程）对内存的需求之和多于计算机实际的内存容量。并且，主存的使用可能是碎片化的，无法找打一片连续的空间进行分配。进一步的，在实际的多核处理器中，会可能多个程序指向相同的地址，不同程序间读写相同的内容，导致数据污染或崩溃。
对于这样的关系，外部更大的空间就是磁盘，如何让磁盘存储部分不活跃的数据，即让主存充当数据的Cache，是对一种新的映射关系的需求来源。这种需求促进了虚拟存储器：一种把主存当做辅助存储器的高速缓存的技术，称为虚拟存储器（virtual memory）技术。
虚拟内存是一个间接容器。如果没有虚拟内存，程序地址直接映射到内存。假如内存为1G，程序A运行时占用了1GB，发现没有内存空间可以用，那么会导致崩溃。如果用虚拟内存，通过Map查找程序地址对应的物理内存地址，这个地址可能在主存中，也可能在外部磁盘中。
用户编程空间：用户编制程序时使用的地址称为虚地址或逻辑地址 ，其对应的存储空间称为虚存空间或逻辑地址空间。虚存空间的用户程序按照虚地址编程并存放在辅存中。
物理内存空间：计算机物理内存的访问地址称为实地址或物理地址 ，其对应的存储空间称为物理空间或主存空间。
- 当系统申请的内存不足时，系统把根据置换算法把暂时不用的内存置换到硬盘里，更新映射关系到硬盘上，再更新新申请的内存映射关系，让我们产生无限内存的错觉。
- 程序通过自身的映射表可以随意找到合适的物理内存，而不一定需要内存连续分配。
- 即使程序的地址相同，但是通过程序自己的映射表到不同的物理内存而不会互相产生干扰。有些内存是需要共享的。例如不同的程序会共享系统文件等，让程序实现共享的方法是地址指向相同的物理内存。
- 这个映射表就是页表，每个程序都有自己的页表
地址的管理方式：页和段
首先，虚拟存储器相当于把主存用作磁盘的Cache，这里所指的页相当于Cache概念中的块，只是为了区分称之为页。
页式调度：将虚存空间和物理地址空间都分成固定大小的页。主存按页顺序编号；每个独立编址的程序空间也按自己的页顺序编号。虚存空间和物理空间按页进行交换。
段式调度：把物理空间分成页；按程序的逻辑结构将程序空间划分为若干段，段的长度是随意的，虚存空间和物理空间按段进行交换。
段页式调度：上述两种方法的结合 。把物理空间分成页程序按模块先分段，每个段再分成与物理空间页同样大小的页面。虚存空间和物理空间按页进行交换。
段
段是一种更灵活的地址管理方式，因为段的大小是可变的，所以需要进行边界检查以确定偏移量是否在段内。段的地址由两部分组成：映射到物理地址的段号和段内偏移。
页
同样类似于Cache，页的数据也被分为页号和页偏移（用于在页内寻址字节），在实际地址和虚拟地址中，页偏移总是相同的，但页号可能不同，需要一种映射关系和处理这种映射关系的硬件，也就是下文提到的MMU和页号。
虚拟地址的页号一般显著大于物理页号，这样才能实现虚拟空间大于物理空间的效果。
当访问的页不在主存而在磁盘中时，称此时为缺页。缺页带来的访问磁盘的时间消耗是巨大的，为了降低缺页的可能性，通常允许存储器中的页以全相联的方式放置（依然在主存中，这里的全相联是类似于Cache的抽象概念，在主存中以Cache方式管理）。由于写的时间太长，在虚拟存储器中，写直达过于耗时，通常采用写回机制。
MMU
要使用虚拟存储器，就不能用指令给出的地址直接和内存沟通，因为程序给出的地址的位数显著多余内存芯片的地址位数。在虚拟存储器中要使用“虚拟地址”。首先，指令给出虚拟地址，然后虚拟地址会被送往一个被称为“内存管理单元”（即MMU）的地方，在MMU中虚拟地址会被转换为内存芯片能理解的物理地址。
页表
页表是一种数据结构，它用于计算机操作系统的虚拟内存系统，存储了虚拟地址到物理地址的映射。为了正确解读程序给出的虚拟地址，系统会维护一个映射表。
页表存储哪些东西？首先需要明确，页表并不是硬件，而是存储在主存中的一个数据结构，存储了映射关系的数据。硬件中有一个存储了指向页表地址的寄存器，称为页表寄存器。
处理器在宏观上的一种状态可以称为一种进程（不准确的定义），每个进程都有一个独立的页表，以进行不同的映射关系。OS会根据当前运行的进程改变页表寄存器，改变当前的地址映射关系。
页表的实现本质上就是数据，建立了一个虚拟页号-物理页号之间关系，虚拟页号可以通过自身的地址确定，故想要确定映射关系只需要存储物理页号，存储的也就是物理页号-有效位-脏位（页偏移虚拟物理是一致的，故不需要存储），虚页号决定了虚拟空间能有多少个页表。页表是存储在内存一片连续空间内的
由于页表的存在，每次的访存都至少需要两次：第一次访存（页表）获取物理地址，第二次访存（主存）获取数据。如果缺页（数据不在主存中）则需要花费更多时间。期间涉及了对TLB（页表Cache）和数据Cache的命中缺失问题。
页表对于一个程序而言非常重要，CPU在切换进程的时候需要保存进程现场和恢复进程现场，而所谓的“现场”就是由PC、通用寄存器和页表等内容组成。
多级页表
多级页表是页表的页表，把原先的页表进行了拆分。
单级页表虽然实现了地址转换，但是单级页表需要为每一个程序分配4MB的连续内存空间，在多程序并发的操作系统中，数十个乃至数百个单级页表会让内存苦不堪言——不仅因为这些页表会占用大量内存空间，而且其要求分配的内存是“连续的”，这相当于是要求内存为其分配连续的十个页框。
与此同时，大部分程序其实根本用不到那么多页，没有多少程序真的需要用完4GB的虚拟地址空间，因此页表中的绝大多数记录都是无效的，实际上并没有被使用，这样一来内存的使用效率就降低了。
为了解决单级页表效率低的问题，多级页表被提了出来。
如果一个页没有被使用，换句话说，如果有一段地址根本没有被使用过，其对应的页就不会真的存在在内存中，这一个信息被页表中的“有效位”记录，如果有效位标志为无效，就说明该页不存在与物理内存的映射关系，其也就不存在在内存中，这样就节约了内存空间。
现在我们要用同样的思想来节约页表的空间——如果有的页表记录根本就没有用，那么就不应该让它占据内存空间。
如果以4KB大小把单级页表的连续4MB划分开，或者说把1M项页表项划分成1K份，那么单级页表就被划分成1K个子块，每个子块的大小正好是一页。此时我们用一张顺序表记录这1K个子块的物理内存首地址，那么就可以像单级页表节约内存一样节约页表。
再进一步，如果用一整页来当作1K个子页表的索引表，那么在索引表中记录有效的子页表才该真实存在，别的记录无效的子页表实际上没有被程序使用，因此就不应该真实存在。通过这样的做法，我们成功节约了页表的空间，而且不再需要页表占用连续的内存空间。
所谓的子页表的索引表其实就是子页表的页表，我们把这里面的子页表称作第二级页表，把索引表称为第一级页表。
让我们用图来解说这个过程，在下图中第一级页表和每一张第二级页表都恰好占据一页，即4KB，因此第一级页表包含1K个记录，其中每个记录都记录一张第二级页表在内存中的首地址，每张第二级页表也包含1K个记录，其中记录了虚拟页号和物理页框号的映射关系。
假如此时第一级页表中的第1项记录无效，那就说明第1张第二级页表实际上不存在，那么我们就可以节省下一张第二级页表的存储空间，即省下了4KB，在很多程序中，第一级页表里的大部分记录都是无效的，因此我们省下了海量的内存空间。与此同时，第二级页表不再需要彼此连续，这样就让操作系统在分配内存的时候变得更灵活。
上面简单说明了二级页表的提出背景和原理，下面具体说说在二级页表下CPU该如何访问内存。
正如在单级页表下CPU把地址划分成虚拟页号和页内偏移两段，在二级页表下CPU要把地址划分成虚拟一级页号、虚拟二级页号和页内偏移三段，这三段分别占据32为地址的高中低三段。
进一步说，一级页表占据一页，包含1K个记录，因此需要10位地址来寻址；二级每个页表占据一页，包含1K个记录，因此也需要10位地址来寻址；根据物理内存地址寻址到每一页都是4KB大小，因此需要12位页内偏移地址来寻址。
高级页表访问的地址是高位的，越低的页表访问越低的地址进行访问数据。
到这里，CPU的访问过程就呼之欲出了，CPU访问数据时首先根据虚拟地址的对应高位访问第一级页表寄存器（记录第一级页表的物理内存首地址）和第一级虚拟页号查找第一级页表，然后根据第一级页表给出的物理内存地址和第二级虚拟页号查找第二级页表，然后根据第二级页表给出的物理内存地址和页内偏移查找内存中的数据。
在程序刚开始运行时，操作系统只会为程序分配第一级页表，当CPU开始寻址，操作系统就要逐步分配第二级页表，并修改第一级页表中的相关记录。每当第一级虚拟页号发生变化，就说明CPU要求访问一个新的第二级页表，此时操作系统要分配第二级页表。
假想一个理想场景，一个程序从头到尾只使用高10位地址为0的虚拟地址，即第一级虚拟页号固定为0，那么该程序就只需要一个第二级页表，这样一来我们就节省了其余第二级页表的空间。
在二级页表中，CPU要访问一次内存中的数据，实际上对应三次内存访问，第一次访问的是一级页表，第二次访问的是二级页表，第三次访问的才是真正的数据，由此看到二级页表让单次数据访问变得更加慢了，但是这为我们节省了内存空间。
在二级页表之上还可以建立页表，即多级页表，为什么又要建立更高级的页表？因为如果把最低级的子页表划分得更小，那么上级页表的记录就更多，如果上级页表的大小超过一页，那么就可以考虑用更高级的页表来节省中间级页表的空间，但与此同时CPU访问内存的速度将会进一步降低。我们应该力图让最高级的页表的大小小于一页，这样CPU在第一次访问内存的时候才能立刻得到子页表的地址。
缺页
当发生缺页时，处理器在主存中找不到所需页面，页面不在主存中，在磁盘中，需要停下处理器，先找到所需要的地址，再去寻找所需要的数据。
当缺页时，CPU会进入一个异常阶段，由特定的异常处理程序进行处理。一旦OS知道了引发缺页的EPC，会进行一下步骤：
- 使用虚拟地址查找页表项，在磁盘上找到被访问的页的位置
- 如果内存不空闲，则选择替换一个物理页；由于对页表采用写回策略，如果被替换的页是脏的，则需要在替换前进行写回
- 启动读操作，蒋被访问的页从磁盘上取回到所选择的物理页的位置。
调用“缺页中断处理程序”处理缺页，中断程序要访问磁盘，把磁盘中对应的盘块写到内存中，如果内存有空闲页则写进空闲页，如果没有空闲页则替换某一页，如果替换页被修改过，需要把替换页写回到磁盘。在把盘块调入内存之后还要修改页表。
TLB
通过前面的分析可以看出，页表存储在主存中，存储了地址的数据（映射关系）。当对主存的访问是频繁时，对页表的频繁查找会带来时间上的巨大消耗，于是想到建立一个页表的Cache，存储常用的映射关系，快速锁定地址，定位数据。
TLB一般采用全相连的模式：TLB的天然 命中率更高，不希望被轻易替换。相对Cache而言，由于TLB在处理器的关键路径上，因此TLB容量不能太大，通常包括32项或者64项，大小和具体物理实现有关。
说白了，TLB就是一个地址映射关系Cache，记录了最近使用地址的高速缓存，从而避免每次都要访问页表。最理想的情况就是访存时，TLB中有映射关系，得到物理地址，然后发现Cache中存有该数据，直接拿到数据，是最快的情况。
TLB的命中缺失
由于TLB页是Cache，也有命中缺失的情况：
TLB的数据存储为：有效位（虚页是否在主存中）-脏位（是否被修改）-标记（虚页号）-实际物理地址（实页号）组成。
TLB通常使用写回策略，毕竟同步页表的时间过于长，而且对页表的修改相较于对数据的修改不是那么频繁。
Cache和TLB优化
虚拟Cache
Cache分为
Cache的tag直接是虚拟页表号，节省查找页表获取物理地址的时间，如果不命中再访问TLB进行访问
虚拟-物理Cache
对Cache和TLB的访问时并行的，同时进行TLB的转换和虚拟Cache访问
获取组是虚拟的，tag是物理的
虚拟 index物理tag，为什么能用物理tag？
在访问Cache的同时获取了物理tag，需要物理虚拟index一样
