计组理论重点与易错点

Cache

1.时间局部性：最近的未来要用到的信息，很可能是现在正在使用的数据，因为程序中存在循环和需要多次重复执行的子程序段，以及对数组的存储和访问操作。

空间局部性：最近的未来要用到的信息，很可能与现在正在使用的信息在存储空间上是邻近的，因为指令通常是顺序存放、执行指令的，数据也一般是以向量、数组等形式簇聚地存储的。

2.Cache与主存间按数据块为单位进行数据交换，Cache与CPU之间以字为单位进行数据交换。

3.CPU与Cache间数据交换以字为单位，而Cache与主存间的数据交换以Cache块为单位。

4.当集中访问的存储区超过Cache组的大小时，命中率可能变得很低，这种现象被称为抖动。

5.Cache一致性问题：主要针对写操作。

一、写命中：

1）.全写法/直写法：CPU对Cache写命中时，必须将数据同时写入Cache和主存，实现简单，能够随时保持主存数据的正确性。但增加了访存次数。改进：写缓冲，CPU写命中时同时写入Cache和写缓冲（位于Cache和主存之间的一个FIFO队列）中，其可解决速度不匹配问题，但若出现频繁写会使写缓冲饱和溢出。

2）.回写法：CPU写命中时，只将数据写入Cache，不立即写入主存，只有当此块被替换时才写回主存，减少访存次数，但存在数据不一致的隐患。

二、写不命中：

1）.写分配法：更新主存单元，后将该主存块调入Cache，试图利用程序的空间局部性，但每次写不命中都需要从主存中读一个块到Cache中。

2）.非写分配法：只更新主存单元，不把主存块调入Cache中。

注意：通常非写分配法同全写法合用，写分配法同回写法合用。

6.在Cache与主存的映射关系实现中，“比较器”用于并行地比较分组中所有Cache行的Tag标记位与要访问物理地址的Tag标记位，则比较器的个数就是分组中的Cache行数即块数，比较器位数即为Tag标记位数。

7.==主存地址空间代表的是地址的总位数，也就是所有主存总共的地址数，其中按字节编址和按字编址的区别在于，前者的一条主存地址代表的是一个字节内存的地址，而后者的一条主存地址代表的是一个字内存的地址，而由于Cache的存在，将主存地址空间根据Cache块的大小分为若干块，因此计算每一条地址对应的块号，需要先从主存的具体大小得到其对应的地址再除去每一主存块储存的大小再除以组相联对应的组数（若为全相联则无需此步），或者也可以通过将首地址加上偏移量（注意：此处的偏移量一定要是同编址方式一致即一条地址对应的内存大小要一致）再通过主存地址格式得到相应的块号，注意：一定要认真计算，切记想当然==

8.一些Cache的简述题：32位主存地址，按字节编址，采用直写写策略和LRU替换算法，Tag为20位，Index为6位，offset为6位，初始时Cache为空。若CPU一开始的访问操做是读取主存单元00010003中的指令，简要说明从Cache中访问该指令的过程，包括Cache缺失处理。

00010003H根据主存地址格式可得，组号为0，因此该地址所在主存块映射到指令Cache的第0组，又因为Cache初始为空，则所有Cache行的有效位均为0，则Cache访问缺失，此时，将该主存块取出后存入指令Cache的第0组中的任意一行，并将主存地址高20位填入该行的标记字段，设置有效位，修改LRU位，最后再根据块内地址从该行中读出相应的内容。

虚拟存储器

1.虚拟存储器的实际容量小于主存+辅存。

2.虚拟存储器在处理一致性问题时，只能使用回写法+写分配

3.每个进程有一个页表，这里是由OS维护的内存中的页表，其中每一个页表项由实页号、装入位、修改位和替换控制位等，注意同TLB的页表项做区分，没有Tag位。

4.虚页偏移位==实页偏移位。

5.一个页表项代表一个虚页，页大小是指内存划分的单元大小，一般以字节为单位，是一个页能存储数据的大小；而页表项二进制位数是指存储映射关系和控制信息的二进制位数，以比特为单位。

6.TLB一个页表项由有效位、脏位、使用位、TLB与Cache映射关系下的Tag标记位、实页号组成。

7.TLB、Cache和Page缺失

TLB、Cache和Page缺失

其中，TLB和Cache任一个缺失都要访问一次主存，Page缺失需要访问磁盘。Cache缺失处理由硬件完成、缺页缺失由软件完成，OS通过“缺页异常处理程序”实现。TLB缺失既可由硬件也可由软件。

8.Cache全由硬件实现，对所有程序员透明；虚拟存储器由OS和硬件共同实现，对系统程序员透明，对应用程序员不透明。

9.虚拟存储器运用了局部性原理，因此所运行程序应具有局部性原理才可充分发挥其作用。

10.只能由OS和硬件访问页表。

11.缺页中断：在请求分页系统中，当要访问的页面不在内存时，就会产生缺页中断。当查找页表发现状态位为0，则产生缺页中断，将缺页的进程阻塞，如果有空闲块，则要调入的页直接装入，并修改相应的页表项，若无空闲块，则根据替换算法淘汰某页后再装入，最后恢复CPU环境，返回缺页的进程继续执行程序。

12.虚拟地址空间并不是总大于物理地址空间。可能相等也可能小于。

主存储器

1.闪存本质上是带电可擦除可编程ROM

2.半导体存储器分类，SRAM一般用作Cache、DRAM一般用作主存。

半导体存储器

3.DRAM刷新的原因：1.内部保持二进制信息”1”即高电平的情况下，内部的Cs电容的电荷会发生泄漏，状态不能长久保持，为了保持数据性质不变，需要进行电荷的补充即刷新，对所有数据进行行刷新。2.读出是破坏性的，即会破坏内部的数据性质，只进行被破坏数据的再生。

4.DRAM芯片封装的特殊性：由于行列地址管脚复用，行列地址线位数一般均分总字位数。

5.存取时间不等于存取周期，存取周期等于存取时间加上恢复时间（恢复内部状态的复原时间），对于破坏性读出的存储器，存取周期往往比存取时间大很多，由于存储器中的信息读出后需要马上进行再生。

6.Cache-主存层主要解决CPU和主存速度不匹配的问题，数据调动由硬件自动完成，对所有程序员透明。主存-辅存层解决存储系统的容量问题，数据调动由硬件和OS共同完成，对应用程序员透明。

7.按存取方式的存储器：

1）.随机存储器（RAM）：主要用作主存或Cache，分为SRAM和DRAM

2）.只读存储器（ROM）：可与RAM共同作为主存的一部分，统一构成主存的地址域。由其派生出的存储器包含可反复重写的类型，存取方式为随机存取。广义上的只读存储器有可通过电擦除等方式进行写入的，虽不是“只读”，但是保留了断电内容保留、随机读取特性

3）.串行访问存储器：对存储单元进行读/写操作时，需按其物理位置的先后顺序进行寻址，包含顺序存取存储器（磁带）和直接存取存储器（磁盘、光盘（CD-ROM是只读光盘不算是只读存储器ROM，是直接存取存储器）。前者内容只能按某种顺序执行，存取速度慢。后者存取信息时通常先寻找整个存储器中的某个小区域，再在小区域内顺序查找。速度介于随机存储器和顺序存取存储器之间。

8.Cache与主存访问类型问题，除非题目中有说明同时访问Cache和主存（此时不命中时间为访问主存的时间），否则应为访问Cache和主存的时间之和。

9.DRAM集成度高、位价低、功耗低，存取速度比SRAM慢，须定时刷新和读后再生，一般用于大容量的主存系统。

10.刷新以行为单位，对同一行进行相邻两次刷新的时间间隔称为刷新周期，通常取2ms，常用刷新方式：

1）.集中刷新：一个刷新周期内，用一段固定时间依次对存储器的所有行进行逐一再生即刷新，此期间停止对存储器的读/写操做，即死时间/访存死区。

2）.分散刷新：将存储器系统工作周期分为两部分：前半部分用于正常读/写，后半部分刷新，该方式增加了系统存取周期。

3）.异步刷新：将刷新周期除以行数，得相邻两行间刷新的时间间隔t，每隔t产生一次刷新请求，分散“死时间”。

刷新不依赖外部访问。

11.MDR的位数与数据线的位数相同，MAR的位数与地址线的位数相同。

12.数据总线的位数与工作频率的乘积正比于数据传输速率。

13.若存储器容量为32K*16位，则32K = 2^15^，因此一共需要15根地址线，行列地址线的总和，此外还需要16根数据线。对于SRAM，地址引脚总和为15；而对于DRAM，由于地址引脚复用，只需要8根地址引脚。

14.按信息的可保存性分类：RAM为易失性存储器，而ROM、磁表面存储器和光存储器为非易失性存储器。

15.SRAM依靠双稳态电路的两个稳定状态分别存储0和1.

16.U盘采用Flash存储器计术，是在E^2^PROM的基础上发展起来的，属于ROM的一种，由于擦写速度和性价比可观，常用作辅存。

17.计算机OS保存在硬盘上，需要BIOS的引导程序将OS引导到主存（RAM）中，而引导程序固化在ROM中。

18.动态半导体存储器的特点：1.每隔一段时间，需根据原存内容重新写入。2.一次完整的刷新过程只需要占用一个存储周期。

19.DRAM的刷新也是一个读取的过程，根据读出内容对相应单元进行重写，会和CPU的访存冲突，有访存“死时间”，且刷新是每隔一段时间向栅极电容补充一次电荷，以行为单位。

20.在主存中，地址存储器MAR用来存放当前CPU访问的内存单元地址，或存放CPU写入内存的内存单元地址。数据存储器MDR用来存放由内存中读出的信息或写入内存的信息。且MAR的位数通常决定了主存地址空间的大小，MDR位数由存储字长决定。

21.DRAM依据栅极电容原理存储信息，SRAM依据双稳态触发器原理存储信息。

22.刷新地址计数器提供刷新地址(按行刷新)，位数同行地址相同。

重点

==存储器的扩展==、==DRAM的刷新==

指令系统与MIPS汇编

1.定长指令：操作码长度固定不变，硬件设计简单、指令译码时间开销小、指令空间利用率低。（MIPS）

变长指令：设计复杂、开销大、利用率高。（x86）

2.形式地址：指令中直接给出的地址编码；

有效地址：根据形式地址和寻址方式计算出的操作数在内存单元中的地址。；

常用寻址方式：立即寻址、寄存器直接寻址、基址寻址、相对寻址、堆栈寻址；

寻址方式的确定分为操作码直接确定寻址方式和指令代码包含寻址方式字段，前者无需寻址方式字段。

立即寻址：操作数直接在指令代码中给出，只能作为双操作数指令的源操作数。

寄存器直接寻址：操作数在寄存器中，指令地址字段给出寄存器的地址（了解）

基址寻址：操作数在存储器中，指令地址字段给出基址寄存器和形式地址，基址寄存器的值+形式地址为有效地址（load/store指令），可使较短形式地址长度实现较大存储空间的寻址。

相对寻址：基址寻址的特例，下一条PC+偏移量为有效地址，即PC计数器即为基址寄存器（如分支跳转指令）。

3.MIPS架构中每种指令只有唯一寻址方式，无需寻址方式编码，对Load/Store指令只有一种基址寻址的方式。其中j类型的跳转的寻址方式称为伪直接寻址，I类型指令的寻址方式为立即寻址，ALU运算指令的寻址方式为寄存器直接寻址。

4.数据伪指令：.BYTE，在内存中以8位字节存储数值；.HALF，在内存中以16位半字存储数值，分配时需要满足分配地址半字对齐的条件，即地址值要是2的倍数；.WORD，在内存中以32位字存储数值，分配时需要满足分配地址字对齐的条件，即地址值是4的倍数。.FLOAT和.DOUBLE同理，前者存储单精度后者存储双精度。

字符串伪指令：.ASCII，为一个字符串分配字节序列，且不以NULL结尾；.ASCIIZ以NULL结尾。.SPACE为数据段n个未初始化字节分配空间。

5.时钟周期Tc >= Tctq（一个寄存器从输入到输出的时间，可以理解为在一个寄存器里经过的时间) + Tcd（组合逻辑电路的最长延时） + Tsetup(输出稳定下来的时间) + 时钟偏移

6.哈佛体系结构：使用指令存储区（IM）和数据存储区（DM）分别保存指令和数据。

7.普林斯顿结构：指令和数据使用同一存储器。

8.规格化浮点数是为了增加浮点数的表示精度。

8.==jr和JALR==指令是R型指令。

9.根据指令集的复杂程度，可以将指令集架构(ISA)分为CISC和RISC。

外存与IO

1.扇区的地址表示：从左至右：柱面（磁道）号、磁头号、扇区号。只考虑CAV，即恒定角速度的磁盘存储结构。

2.CPU响应中断、程序断点(PC)入栈、关中断、获取中断向量->PC等由中断隐指令硬件实现。中断服务子程序通过软件实现。

3.在独立请求方式下，若要支持N个设备，则需要N个总线请求信号和N个总线响应信号。建立完全的一对一的请求响应关系。

4.RAID（独立冗余磁盘阵列），多个物理盘组成，被OS当成一个逻辑磁盘，数据分布在不同的物理磁盘上，冗余磁盘用于保存数据校验信息，校验信息保证在出现磁盘损坏时能有效的恢复数据。

六种模式：

RAID0：无差错控制的带区组，完全没冗余，数据条带化分布在不同的物理盘上。

RAID1：镜像结构，成本太高，即完全复制一份物理盘，读操作性能改善，写操作性能不高。

RAID2：带海明检验，并行访问技术，磁盘任何时刻都并行地相应I/O请求。根据磁盘数据计算错误校验码，校验码按位分布在冗余磁盘对应位置。

RAID3：带奇偶校验码的并行传送，校验码是简单的奇偶校验码，保存在独立的冗余磁盘对应位置上。

RAID4：带奇偶校验码的独立磁盘结构，数据按较大的条带分布在不同的磁盘上，校验码也为奇偶校验码，保存在独立的冗余磁盘对应位置上。

RAID5：分布式奇偶校验码的独立磁盘结构，与RAID4区别在于校验信息的保存位置，数据校验码作为条带的一部分保存在磁盘组不同的磁盘中，有效避免了RAID4的校验盘写入瓶颈。

5.按信息交换的单位划分，I/O设备可以分为字符设备和块设备。

6.DMA方式和中断方式之间的差别：

1）.后者是程序的切换，需要保护和恢复现场；但前者除了预处理和后处理，其他时候不占用CPU的任何资源。

2）.对中断请求的响应只能发生在每条指令执行完毕时（即指令的执行周期后）；而对DMA请求的响应可发生在每个机器周期结束时（取指、间址和执行周期之后均可），只要CPU不占用总线就可被响应。

3）.中断传送过程需要CPU的干预，但DMA传送过程不需要CPU干预。

4）.DMA请求的优先级高于中断请求。

5）.中断方式具有对异常事件的处理能力，但DMA仅局限于传送数据块的I/O操作。

6）.从数据传送看，后者靠程序传送，前者靠硬件传送。

7.I/O总线分为三类：数据线、地址线和控制线。数据缓冲寄存器和命令/状态寄存器中的内容都是通过数据线来传送的，如I/O接口中的命令字和状态字；地址线用以传送与CPU交换数据的端口地址；而控制线用于给I/O端口发送读/写信号，仅用于对端口进行读/写控制。

8.I/O接口即为I/O控制器，功能为接收主机发送的I/O控制信号，并实现主机和外设间的信息交换。磁盘驱动器是由磁头、磁盘和读/写电路等组成的，即日常所说的磁盘本身。可编程中断控制器也为I/O接口。

9.外部中断是指CPU执行指令以外的事件产生的中断，通常指来自CPU与内存以外的中断，如键盘输入。

10.中断处理过程为：1.关中断；2.保存断点；3.识别中断源，即引出中断服务程序（形成中断服务程序入口地址并送给PC）；（这三步都是由中断隐指令完成的，由硬件实现）4.保存现场和屏蔽字（现场信息指用户可见的工作寄存器的内容，存放程序执行到断点处的现行值），例如保存通用寄存器的内容；5.开中断，允许更高级中断请求得到响应，以实现中断嵌套（单重中断没有该步）；6.执行中断服务程序；7.关中断，保证在下一步执行过程中不被中断（单重中断没有该步）；8.恢复现场和屏蔽字；9.开中断、中断返回。第4-9步由中断服务程序（软件）实现。

11.中断I/O方式申请使用的是CPU处理时间，它不适合高速外设，外设通过中断控制器向CPU发送中断请求信号，CPU响应中断请求后开始执行中断服务程序，中断服务程序执行完后CPU自行返回，无需外设发送中断结束信号；而DMA方式申请的是总线的使用权，除了适合快速外设，多路型DMA控制器也适合同时为多个慢速外设服务，DMA传送结束后的处理由中断服务程序完成。采用周期挪用法时，DMA控制器挪用一个或几个主存周期来访问主存，传送完一个数据字（即总线位宽）后释放总线，是一种单字传送方式，每个字传送完后CPU可以访问主存。

计算机性能指标

1.机器字长：

即字长，指计算机进行一次整数运算（即定点整数运算）所能处理的二进制数据的位数，通常与CPU的寄存器位数、ALU有关，其一般等于通用寄存器的位数或ALU的宽度，字长越长，数表示的范围越大，计算精度越高。

2.数据通路带宽

数据总线一次所能并行传送信息的位数，该数据通路带宽指的是外部数据总线的宽度，与CPU内部的数据总线宽度可能有所不同。

数据通路：各个子系统通过数据总线连接形成的数据传送路径。

3.主存容量

指主存储器所能存储信息的最大容量，通常以字节衡量。其中，MAR的位数反映了存储单元的个数，MDR的位数反映了存储单元的字长。

4.运算速度

1）吞吐量与响应时间

吞吐量：系统在单位时间内处理请求的数量，主要取决于主存的存取周期。

响应时间：从用户向计算机发送一个请求，到系统对该请求做出响应并获得所需结果的等待时间，包含CPU时间(运行一个程序所需的时间)与等待时间(用于磁盘访问、存储器访问、I/O操作、OS开销等的时间)。

2）主频和CPU时钟周期

主频（CPU时钟频率）：时钟周期的倒数。

CPU时钟周期：机器内部主时钟脉冲信号的宽度。时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成。时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定，也以指令流水线的每个流水段的最大延迟时间确定。

3）CPI

执行一条指令所需的时钟周期数。

一般指的是该程序或机器指令集中所有指令执行所需的平均时钟周期数，是一个平均值。

IPS = 主频/平均CPI

4）CPU执行时间

CPU执行时间 = CPU时钟周期数 / 主频 = （指令条数 * CPI） / 主频。

5）MIPS

每秒执行多少百万条指令，（Million Instructions Per Second）

MIPS = 指令条数 / （执行时间 * 10^6^）= 主频 / （CPI * 10^6^）

6)FLOPS

每秒执行多少次浮点运算。

MFLOPS：每秒执行多少百万次浮点运算；

GFLOPS: ……十亿（10^9^）……；

TFLOPS: ……万亿（10^12^）……；

PFLOPS: ……千万亿（10^15^）……；

EFLOPS: ……百京（10^18^）……；

ZFLOPS: ……十万京（10^21^）……；

注意

描述存储容量、文件大小时，K、M、G、T通常用2的幂次表示。描述速率、频率等时，k，M，G，T通常用10的幂次表示。

浮点数运算的三个基本操作是阶码运算、尾数运算和结果规格化。浮点数阶码和尾数都为0时认为是0；阶码为255，尾数为0时表示无穷大，由符号位决定正负。

5.反码

符号位为0的数反码与原码相同；符号位为1的数反码是符号位不变，原码剩下位取反；也就是反码的正数取反就得到相应的负数。

计算机系统层次结构

1.硬件系统和软件系统共同构成了一个完整的计算机系统。

2.计算机硬件：

1）.冯诺依曼机：“存储程序”的思想：1.计算机硬件系统由运算器、存储器、控制器、输入输出设备组成；2.指令和数据同等地位存储在存储器中，且均由二进制代码给出。冯诺依曼机的基本工作方式是控制流驱动方式，按照指令的执行序列，依次读取指令，后根据指令的控制信息，调用数据信息进行处理。因此工作过程中始终以控制信息流为重，数据信息流只是被动的被调用而已。

2）.功能部件：IO、存储器（主存和辅存，主存采用按地址存取方式进行存取）、运算器（包含若干通用寄存器，用于暂存操作数和中间结果，如累加器、乘商寄存器、操作数寄存器等，还有程序状态寄存器（PSW))、控制器（**程序计数器(PC，存放当前的指令地址，有自加1的功能，“1”指指令长度，可自动形成下一条指令地址)、指令寄存器(IR，存放当前指令，内容来自主存的MDR)、控制单元(CU)**）

运算器和控制器集成在同一芯片上，称为CPU。CPU和主存共同构成主机，CPU和主存间通过地址、控制、数据组成的总线连接，主机外的其他硬件设备称为外部设备，即外设。

3.地址译码器是主存的构成部分，不属于CPU，地址寄存器(MAR)虽属于主存，但现代计算机绝大多数CPU内集成了地址寄存器，并未集成到运算器和控制器中。

4.编译程序是先完整编译后运行的程序，如C、C++等；解释程序是逐句翻译且边翻译边执行的程序，如JavaScript、Python等，因此一般速度较编译程序慢。

C语言编译过程：源程序(.c)——（编译器，编译）—->汇编源程序 ——-(汇编)——-> 目标程序 ——–(链接程序) ——–>可执行程序

5.相联存储器既可以按地址寻址又可以按内容（通常是某些字段）寻址。

6.翻译程序是指高级语言源程序转换为机器语言程序的软件，分为两种：1.编译程序，将源程序一次全部翻译成目标程序，并生成目标代码文件。2.解释程序，将源程序的一条语句翻译成机器目标代码，并立即执行，翻一条执行一条，并不会产生目标代码文件。3.汇编程序，将汇编语言源程序翻译为机器语言程序

7.指令计数器（PC）：保存指令所在存储单元地址。指令寄存器（IR）：保存指令二进制代码。 指令译码器（ID）：解释指令。

总线

1.仲裁方式

1.链式查询方式

总线控制器收到总线申请BR,BG逐个下传，遇到某接口有总线申请，停止下传，该接口获得总线使用权，建立总线忙信号BS。

2.计数器定时查询方式

总线控制器收到总线申请BR，计数器开始计数，当某个有总线申请的设备地址与计数器一致，其获得总线使用权，建立BS，若每次计数从上一次计数的终止点开始，则可以实现每个设备使用总线的机会相等。

3.独立请求方式

每个设备都有独立的请求信号和总线同意信号。总线控制器根据设备的优先级决定将总线的使用权交给谁。

2.可屏蔽中断和不可屏蔽中断

通过INTR线发出的是可屏蔽中断，通过NMT线发出的是不可屏蔽中断。前者优先级最低，在关中断模式下不被响应，后者用于处理紧急和重要事件，优先级最高，内部异常在中间。

中断响应判优通常是通过硬件排队器（或中断查询程序）实现的。

中断优先级分为响应优先级和处理优先级，前者由硬件线路或查询程序的查询顺序决定，不可动态改变；后者可利用中断屏蔽计术动态调整，来实现多重中断，如屏蔽字。如不使用中断屏蔽技术，则这两者相同，每个中断源都有一个屏蔽触发器，1表示屏蔽该中断源的请求，0反之。所有屏蔽触发器组合在一起便能构成一个屏蔽字寄存器，内容为屏蔽字。