[收藏夹] 计算机系统与组成原理

第一章、计算机系统概述

1.计算机发展历程

计算机硬件发展历程：电子管时代–>晶体管时代–>中小规模集成电路时代–>超大规模集成电路时代–>智能计算机–>生物计算机和量子计算机。 计算机的分类：专用计算机、通用计算机。 摩尔定律：当价格不变时，集成电路上可容纳的元器件的数目，约每隔18~24个月便会增加一倍，性能也将提升一倍。揭示了信息技术进步的速度。其他：操作系统直接影响计算机系统性能。

2.计算机系统层次结构

计算机系统=硬件+软件=（中央处理器、存储器和外部设备等）+（计算机的运行程序和相应的文档）

2.1 计算机硬件的基本组成

(1)存储器：分为主存储器（内存储器）和辅助存储器（外存储器）。主存储器存放重程序和数据，辅助存储器中的信息必须调入主存后才能被CPU访问。 (2)运算器：主要功能时进行算术运算和逻辑运算，核心是算数逻辑单元（ALU）。运算器包含若干通用寄存器。 (3)控制器：计算机的指挥中心。由程序计数器（PC）、指令寄存器（IR）和控制单元（CU）组成。 (4)输入设备。 (5)输出设备。

2.2 计算机软件的分类

（1）系统软件；（2）应用软件。

2.3 计算机编程语言分类

机器语言、汇编语言、高级语言。

2.4 编译程序与解释程序的区别

编译程序生成目标代码，而解释程序不生成；编译程序产生目标代码的执行速度比解释程序的执行速度快。

2.5 计算机的工作过程

不断地从存储器中逐条取出指令，然后送至控制器，经分析后由CPU发出各种操作命令，指挥各部件完成各种操作，直至程序中全部指令执行结束。

2.6 计算机系统的层次结构

(1)第1级。微程序机器级。微指令由硬件直接执行。 (2)第2级。传统机器级(机器语言)。用微程序解释指令系统。 (3)第3级。操作系统级。用机器语言解释作业控制语句； (4)第4级。汇编语言机器级。用汇编程序翻译成汇编语言程序； (5)第5级。高级语言机器级。用编译程序翻译成汇编程序或直接翻译成机器语言。

3.计算机性能指标

(1)吞吐量：单位时间内的数据处理量，主要取决于主存的存取周期； (2)响应时间：从提交作业到该作业得到CPU响应所经理的时间。响应时间越短，吞吐量越大。 (3)主频：机器内部主时钟的频率，衡量机器速度； (4)CPU周期：又称机器周期，指的是从内存读取一条指令字的最短时间。一个指令周期由若干个CPU周期构成； (5)CPU时钟周期：主频的倒数，是CPU中最小的时间单位。 (6)CPI、MIPS、FLOPS； (7)CPU执行时间：CPU对某特定程序的执行时间。

第三章、存储器层次结构

1. 存储器的分类

存储器=主存储器+高速缓冲存储器（Cache）+辅助存储器

(1)按照存储介质可分为： 1)半导体存储器：包括随机存储器和只读存储器两类（RAM和ROM）； 2)磁表面存储器：包括磁盘、磁带，使用顺序存取方式； 3)光盘存储器：也叫光存储器，一般指光盘； 4)磁心存储器：由各种磁心制成，目前已被半导体存储器取代。 (2)按存取方式可分为： 1)随机存取存储器（RAM）：可存可取，存取时间和存取位置没有关系。优点：读写方便，使用灵活；缺点：断电信息丢失。分为静态RAM（SRAM，常用作高速缓冲存储器）和动态RAM（DRAM常用作主存） 2)只读存储器（ROM）：只可取，一般把一些固定的、不变的程序存放在这里，其内容断电后仍可保留。 3)串行访问存储器：在对存储单元进行读写操作时，需要按照物理位置的先后顺序依次访问，主要包括顺序存取存储器（磁带）和直接存取存储器（磁盘，半串行，因为要先寻道）。 (3)按照在计算机中的作用可分为： 1）主存储器； 2)辅助存储器； 3)缓冲存储器。

2.存储器的性能指标

(1)存储容量=存储字数(表示存储器的地址空间大小即存储器的存储单元数目)*字长(存储字长，表示一次存取操作的数据量); (2)单位成本：每位价格=总成本/总容量； (3)存储速度：数据传输率=数据的宽度/存储周期（存储周期又称读写周期或访问周期，指连续两次独立地访问存储器操作之间所需的最小时间间隔）。

3.存储周期与存取时间的区别

存储周期又称读写周期或访问周期，指连续两次独立地访问存储器操作之间所需的最小时间间隔，而存取时间是指启动一次存储器操作到完成该操作所经历的时间，一般小于存储周期。

4.存储器的层次化结构

缓存-主存层次主要解决CPU和主存速度不匹配的问题。主存和缓存之间的数据交换是由硬件自动完成的，对程序员是透明的； 主存-辅存层次主要解决层次系统的容量问题。主存和辅存之间的数据交换是由硬件和操作系统共同完成的。

5. 半导体随机存取存储器

5.1 半导体存储芯片的基本结构

半导体存储芯片主要由存储矩阵、译码驱动电路和读/写电路组成。地址线是单向的，数据线是双向的，其余的属于控制线，包括读/写控制线（用来进行读/写操作）和片选线（用来选择存储芯片）。

5.2 半导体存储芯片的译码驱动方式

译码驱动：将地址线送来的地址信号转换成对应存储单元的选择信号。 (1)线选法（单译码）：矩阵有N行，则需要地址线$log_2N$根；矩阵每行有m位(也就是m列)，则需要m根数据线； (2)*重合法（双译码）：同时需要行和列的地址线。32($2^5$)行里选中1行需要5根地址线，32($2^5$)列选中一列也需要5根地址线，一共需要10根地址线。

5.3 静态RAM（SRAM）存储器

存储器的工作：保持存储信息、读数据和写数据

5.4 动态RAM（DRAM）存储器

存储器的工作：保持存储信息、读数据和写数据 DRAM存储器的刷新：采用电容式存储，按行刷新(因为存储体是矩阵形式)，由硬件支持，不由CPU指挥，占一个读/写周期。 3种刷新方式： 1)集中刷新：把刷新操作集中到一段时间内进行； 2)分散刷新：将刷新操作分散进行，周期性的进行； 3)异步刷新：是一个折中方案，有计划的刷新，时间分配十分合理。刷新的实质：读出后再按原样写入。

5.5 只读存储器（ROM）

可分为：掩膜型只读存储器(MROM)、可编程只读存储器(PROM)、可擦除可编程存储器(EPROM)、电可擦除可编程存储器(EEPROM)、快擦除读写存储器(Flash Memory，又叫闪存，集合了ROM和RAM的长处)。

5.6 对比ROM和RAM

存取方式一样，都是随机存取。不同的是，ROM只读，RAM可读可写。

5.7 存储器容量扩充

概念：将若干个存储芯片连接在一起组成足够容量的存储器。

补充求芯片数量的公式：若要求将容量为a*b（a为字线，连接地址线）的芯片组成容量为c*d的芯片，则协议的芯片数量n=(c*d)/a*b（整个存储器的容量除以单个芯片的容量）

3类扩充方法：

1)位扩充（增加a*b中的b）：增加存储字长，横向扩展，比如要将1K*4位的芯片组成1K*8位的存储器，过程如下：需要（1K*8）/（1K*4）=2片芯片，需要10根地址线（$2^{10}=1K$），需要8根数据线（1K*8中的8代表位数）；

2)字扩充（增加a*b中的a）：增加存储单元的个数，纵向扩展，比如要将1K*8位的芯片组成2K*8位的存储器，过程如下：需要（2K*8）/（1K*8）=2片芯片，需要11根地址线（$2^{11}=2K$），需要8根数据线（2K*8中的8代表位数）；

3）字位扩充（增加a*b中的a和b）：增加存储单元的个数和存储字长，纵向扩展，比如要将1K*4位的芯片组成4K*8位的存储器，过程如下：需要（4K*8）/（1K*4）=8片芯片，需要11根地址线（$2^{12}=4K$），需要8根数据线（2K*8中的8代表位数）；

6. 双口RAM

具有两组相互独立的地址线、数据线和读/写控制线。可以并行工作，是一种高速工作的存储器；有可能在同一时间两个端口同时操作存储器的同一个存储单元，因此设置了BUSY标志。

7. 多模块存储器（解决了CPU与I/O设备速度不匹配的问题，提高了存储器的工作速度）

不同于寻找更高速的元件和采用存储器层次结构，这种方法是通过调整主存的结构来提高访存速度，主要有两类：单体多字存储器、多体并行存储器

7.1 单体多字存储器

使用前提：指令和数据在主存内必须连续存放；原理：把存储器的存储字字长增加n倍，以存放n个指令字或数据字，于是单体多字存储器的最大带宽比单体单字存储器的最大带宽提高n倍。正常情况下不可能达到最大带宽，因为程序使用指令字和数据字存在随机性。；缺点：必须凑齐n个数据字之后才能作为一个存储字一次写入存储器，因此需要首先把属于一个存储字的n个数据字读入到数据寄存器中，等数据寄存器达到了一个存储字的长度，再将其写入存储器。

7.2 多体并行存储器

所谓多体并行存储器，就是采用多个模块组成的存储器，每个模块有着相同的容量和存取速度，各个模块都有独立的地址寄存器、数据寄存器、地址译码器和读/写电路，每个模块都可以看做一个独立的存储器。主要分为两种：高位交叉编址的多体并行存储器、低位交叉编址的多体并行存储器

7.2.1 高位交叉编址的多体并行存储器(竖着走，按列扫描)

高位地址表示体号，低位地址定位体内地址。由于每个模块内的体内地址顺序是连续的，因此又称顺序存储。这样，可以在同一时间使得不同的请求源同时访问不同的体，进而实现个体的并行工作。特点：相邻两个字在同一个存储体中，高位的变动才会产生交叉访问的效果。优点：非常有利于存储器的扩充，只需将存储单元的编号往后加即可。缺点：由于各个模块一个接一个的串行工作，因此存储器的带宽受到了限制。

7.2.2 低位交叉编址的多体并行存储器(横着走，按行扫描)

由于程序是存放在相邻的体中，因此又称交叉存储。低位为体号，高位定位体内地址。特点：连续地址分布在相邻的不同模块内，而同一个模块内的地址都是不连续的。

8. 高速缓冲存储器（Cache）–提高存储系统的工作速度

8.1 主存和Cache的编址

主存由一个个的字块组成，主存的地址分为两部分：高m位表示主存的块地址，低b位表示其块内的字或字节。同理，Cache的地址也应分为两部分：高ｃ位表示Cache的块号，低ｂ位表示其块内的字或字节数。 命中率：CPU要访问的的信息在Cache中的比例； 平均访问时间：假设命中率为$h$，$t_c$为命中时访问Cache的时间，$t_m$为未命中时的主存访问时间，则Cache-主存系统的平均访问时间$t_a$为$t_a=ht_c+(1-h)t_m$； Cache-主存系统效率：$e=t_c/t_a$ 。

Cache的命中率只与Cache的容量、Cache的字块长度有关。
主存与Cache之间传送数据的基本单位是块，而主存与CPU之间传送数据的基本单位是字（一个块包含多个字）。

8.2 Cache的基本结构

地址映射变换机构(将CPU送来的主存地址转换成Cache地址)；替换机构。

8.3 指令和数据是放在同一个Cache中吗？

一级Cache的指令和数据一般分开存放，而二级Cache的指令和数据放在一起，因此有L1 data Cache和L1 code Cache。

8.4 一些其他知识点

在CPU和主存之间增加Cache并不能增加计算机总存储量；程序员无需知道高速缓存的访问过程。

9. Cache和主存之间的映射方式(主存块号–>CPU块号)

(1)直接映射：每个缓存块可以和若干个主存块对应，每个主存块只能和一个缓存块对应。优点：实现简单。缺点：不够灵活(容易造成空闲Cache块的浪费)、冲突概率高(抖动)。应用场合：适合大容量Cache。 (2)全相联映射：主存中每一个字块可以映射到Cache中的任何一块。优点：Cache的命中率提高了、减小了块的冲突率(空位随便坐)进而提高了Cache的利用率。缺点：tag的位数增加了，访问Cache时主存字块标记需要和Cache的全部“标记”进行比较，才能判断所访问主存地址是否已在Cache内。应用场合：适用于小容量的Cache。 (3)组相联映射：按号分组，组内随意放(把Cache分成Q组，每组有R块)，这样，组间是直接映射，组内是全相联映射，虽没有直接相连的速度快，但电路实现简单(只需进行组间本比较，而无需对Cache的每一块进行比较[全相联是这样子的，它需要])，命中率高。

10.Cache中主存块的替换算法（针对全相联和组相联，至于直接映射只需直接替换就好了）

先进先出，近期最少使用(理想，预测性，难以实现)，最不经常使用，随机法。

11. Cache写操作策略（同步Cache块与主存块中的内容）

(1)写回法：当CPU写Cache命中时，只修改Cache的内容，而不立即写入主存，只有当此行被换出时才写回主存。这样减少了访存次数。Cache的每一行都设置一个修改位(脏位)，当某行被换出时，根据此行的修改位来决定将该行内容写回主存还是简单丢弃。

若未命中，则使用写分配法：加载主存中的块到Cache中，然后在Cache中更新，最后同步到主存。

(2)全写法：当写Cache命中时，Cache与主存同时发生写修改。

若未命中，则使用非写分配法：只写入主存而不调入Cache。

(3)写一次法：以上两种方法的折中，写命中与写未命中的处理方法与写回法基本一致，仅仅是第一次写命中时要同时写入主存。

12. 虚拟存储器

详见操作系统。

第四章、指令系统

1. 指令概述

构成机器语言的一条条语句就是一条条机器指令，全部机器指令的集合就是机器的指令系统。一条指令包括操作码和地址码两部分： 操作码：分为定长操作码和不定长操作码。告诉要做什么操作（比如，加减乘除）； 地址码：又称操作数字段，其任务是：指出操作数的地址、运算结果需存放的地址、下一条指令的地址。

2. 指令分类

(1)零地址指令：只给出操作码字段OP，适用于：1）不需要操作数的指令，比如停机指令、关中断指令等；2）堆栈计算机中的零地址运算类指令。 (2)一地址指令：地址码字段只有一个，适用于：1）单目运算，如求反，减一等；2）隐含约定目的地址的双操作数指令。假设指令字长32位，地址码字段24位，则寻址范围是$2^{24}=16M$ (3)二地址指令：有两个地址码字段，一个是源操作数地址，另一个是目的操作数地址，适用于各类加减乘除运算。假设指令字长32位，操作码8位，两个地址码字段各12位，则寻址范围是$2^{12}=4K$。 (4)三地址指令：有三个地址码字段。假设指令字长32位，操作码8位，三个地址码字段各8位，则寻址范围是$2^8=256$ (5)四地址指令：有四个地址码字段。若指令字长32位，操作码8位，4个地址码各6位，则直接寻址范围是$2^6==64$。

指令字长取决于操作码的长度、操作数地址的长度、操作数地址的个数。每一条指令指令都必须告诉CPU该指令如何做，因此必须指定操作码。

3.什么是指令字长

指令字长是指一条指令所占用存储空间的大小。指令字长一般为字节的整数倍。单字长指令：指令长度=机器字长；半字长指令：指令长度=0.5机器字长； 双字长指令：指令长度=2机器字长。

4.区分数据字和指令字

如果计算机中的某一个字表示的是一个数据，则此字称为数据字；如果计算机中的某一个字表示的是一条指令，则此字就称为指令字。

5. 定长操作码和不定长操作码

定长操作码：在指令字的最高位部分分配固定的若干位表示操作码。对于具有n位操作码字段的指令系统，最多能够表示$2^n$条指令。 不定长操作码：操作码的长度随地址码个数的减少而增加，不同的地址数的指令可以具有不同长度的操作码。这样子可以在满足需要的前提下有效的缩指令字长。需要注意的是：不允许较短的操作码是较长的操作码的前缀；各条指令的操作码一定不可以重复。

6.指令的寻址方式

定义：是指指令或操作数有效地址的寻找方式，主要分为数据寻址和指令寻址。寻址的原因：因为指令的地址码字段往往并不是操作数的真实地址，而是形式地址。

6.1 指令寻址和数据寻址的比较

确定指令存放位置的过程称为指令寻址方式，确定操作数存放位置的过程称为数据寻址方式，两者复杂度不一样。 指令寻址是指找到下一条将要执行的指令的地址，有两种方式：顺序执行(用指令计数器(PC)+1来得到下一条在指令的地址)和跳转执行(通过转移指令的寻址方式，计算出目标地址，送到PC中即可。目标转移地址的形成方式主要有3种：立即寻址(直接地址)、相对寻址(相对地址)、间接寻址(间接地址))。 数据寻址是指找到当前正在执行指令的数据地址。为了区分各种数据寻址方式，通常在指令字中设置一个字段，用来致命使用何种寻址方式，这样，数据指令字的结构变为{操作码，寻址特征，形式地址(A)}。

6.2常见的数据寻址方式

(1)立即寻址：立即给出操作数，不需要给出地址去其他地方找操作数。只需要在取指令时访问存储器，而在执行阶段不需要。但A的位数限制了立即寻址的范围。常用于对某寄存器或内存单元赋初值。

(2)直接寻址：通过指令中的地址码字段找到真实地址(取货码取快递)，执行阶段需要访问一次存储器去取操作数。直接给出了操作数的有效地址，寻找操作数简单，但是寻址范围较小(操作数的有效地址仅由A决定，而A的位数一般都比较小，因此寻址范围比较小)。

(3)隐含寻址：指令字不明显的给出操作数的地址，其操作数地址隐含在操作码或者某个寄存器中。有利于缩短指令字长，但是需要增加存储操作数或隐含地址的硬件。

(4)间接寻址：解决了直接寻址的寻址范围小的问题。直接寻址直接给出了操作数的有效地址，而间接寻址给出的是操作数有效地址的地址。间接寻址又可以分为一次间接寻址和多次间接寻址。便于子程序返回和查表，但N次间接寻址需要在指令阶段还需要访问存储器N+1次(前N次找操作数的有效地址，最后一次找操作数)。

(5)寄存器寻址：和直接寻址类似，在直接寻址的指令字中，地址码字段给出的是主存地址，而在寄存器寻址的指令字中，地址码字段直接给出的是寄存器编号$R_i$，则操作数的有效地址为$EA=R_i$。 (6)寄存器间接寻址：和寄存器寻址不同之处在于，$R_i$中存放的不是操作数，而是操作数所在主存单元的地址号，有效地址$EA=(R_i)$。便于编制循环程序，但需要访问一次存储器去取操作数。

(7)基址寻址：设置一个基址寄存器(BR)，则其操作数的有效地址等于指令字中的形式地址A与基址寄存器中的内容(基地址)相加，即：$EA=A+(BR)$。扩大了操作数的寻址范围(因为基址寄存器的位数可以大于形式地址Ade位数)，便于解决多道程序问题。注意：基址寄存器的内容由操作系统确定，但用户有权知道使用了哪个寄存器作为基址寄存器。

(8)变址寻址：不同于基址寻址，在变址寻址中，变址寄存器中的内容由用户设定，在程序执行过程中其值可变，而指令字中的形式地址A是不可变的。也扩大了操作数的寻址范围，非常适合处理数组和循环问题。

(9)相对寻址：基于程序局部性原理，相对寻址的有效地址是将程序计数器(PC)的内容与指令字中的形式地址A相加而成，即：$EA=(PC)+A$。用于转移类指令，便与编制浮动程序。

7. CIRC和RISC的基本概念

7.1 CISC的主要特点

(1) 指令系统复杂庞大； (2)指令长度不固定，指令格式种类多，寻址方式种类多； (3)可以访存的指令不受限制(RISC只有取数/存数指令访问存储器)； (4)由于80%的程序只是用20%的指令，因此CISC各指令的使用频率差距太大； (5)各种指令执行时间相差很大，大多数指令需多个时钟周期才能完成； (6)控制器大多数采用微程序控制； (7)难以用优化编译生成高效的目标代码程序。

7.2 80-20定律

典型程序中80%的语句都是使用计算机中20%的指令，而这20%的指令都属于简单指令。

于是RISC出现了！

7.3 RISC的主要特点

(1)把复杂指令的功能用使用频率较高的简单指令实现； (2)指令长度固定，指令格式种类少，寻址方式种类少； (3)只有取数/存数指令访问存储器，其余的指令操作在寄存器中完成； (4)CPU中有多个通用寄存器(比CISC的多)； (5)一定采用流水线技术，大部分指令在一个时钟周期内完成； (6)控制器采用组合逻辑控制，不用微程序控制； (7)采用优化的编译程序。

7.4 对比RISC和CISC

RISC更能提高计算机的运算速度，更便于设计，可降低成本，提高可靠性，更有效支持高级语言程序。而CISC有专用指令来完成特定的更能，因此处理特殊任务比较高效。

第五章、中央处理器

1. 序言

CPU=运算器+控制器。运算器的功能是对数据进行加工；控制器的功能是负责协调并控制计算机各部件执行程序的指令序列，包括取指令、分析指令、执行指令、控制主机与I/O设备交换信息以及总线的管理，处理中断的能力。

2. CPU的功能

(1)控制器能自动形成指令的地址，并能发出取指令的命令，将对应此地址的指令取到控制器中，称为指令控制； (2)取到指令之后，应该产生完成每条指令所需要的控制命令，称为操作控制； (3)控制命令产生后，需要对各种控制命令加以时间上的控制，称为时间控制； (4)在执行的过程中，可能需要进行算术运算和逻辑运算，称为数据加工； (5)最后当然还有处理中断的能力，称为中断处理。

3. CPU的基本结构

控制单元(CU)：指令控制、操作控制、时间控制； 算数逻辑单元(ALU)：数据加工； 中断系统：中断处理； 寄存器。

4. CPU中的主要寄存器

可分为运算器中的寄存器和控制器中的寄存器

4.1 运算器中的寄存器

(1)暂存寄存器：暂存从主存读来的数据，对程序员透明(用户不可见)； (2)累加寄存器(ACC)：是一个通用寄存器，用户可见，暂时存放ALU运算的结果信息，至少要有一个； (3)通用寄存器组：存放操作数和各种地址信息，用户可见； (4)状态条件寄存器(PSW)：保存由算数指令和逻辑指令运行或测试的结果建立的各种条件码内容，用户可见。

4.2 控制器中的寄存器

(1)程序计数器(PC)：确定下一条指令的地址，具有寄存信息和计数两种功能； (2)指令寄存器(IR)：保存当前正在执行的指令，指令划分为操作码和地址码字段，由二进制数字组成； (3)存储器数据寄存器(MDR)：暂时存放由主存读出的一条指令或一个数据字，可作为CPU、内存和外部设备之间信息传送的中转站，并且补偿三者速度上的差别，此外在单累加结构的运算器中，存储器数据寄存器还可兼作操作数寄存器； (4)存储器地址寄存器(MAR)：保存当前CPU所访问的内存单元的地址。

5. 指令周期

定义：CPU每取出并执行一条指令所需的全部时间，即CPU完成一条指令的时间，称为指令周期。

一个指令周期=若干个机器周期一个机器周期=若干个时钟周期

一个完整的指令周期包括：取指周期(取指令)+间址周期(取地址)+执行周期(存取操作数或结果)+中断周期(存程序断点)

6. 指令的执行方案

【方案1】单指令周期：对所有的指令都选用相同的执行时间来完成，指令之间串行执行，效率低；【方案2】多指令周期：对不同类型的指令选用不同的执行步骤来完成，指令之间仍串行执行，但可以选用不同个数的时钟周期来完成不同指令的执行过程；【方案3】流水线方案：指令之间可以并行执行，力争在每个时钟脉冲周期完成一条指令的执行过程(理想情况下)。通过在每一个时钟周期启动一条指令，尽量让多条指令同时运行。

7. 信息流

信息流是根据指令要求访问的数据序列，在指令执行的不同阶段，要求访问的数据序列是不同的，而且对于不同的指令，它们的数据流往往也是不同的

8. 数据通路

数据在功能部件之间传送的路径称为数据通路，它的功能是实现CPU内部的运算器和寄存器，以及寄存器之间的数据交换。

8.1 数据通路的基本结构的两种方式

【方式1】CPU内部总线方式：将所有寄存器的输入端和输出端都连接到一条或多条公共的通路上。包括单总线结构(连接各部件的总线只有一条)和双总线结构和多总线结构(CPU中有两条或多条总线，此时数据的传递可以同时进行)。这种结构比较简单，但是数据传输存在较多的冲突现象，性能较低。【方式2】专用数据通路方式：根据指令执行过程中的数据和地址的流动安排连接线路。避免了使用共享的执行，性能较高，但硬件量较大。

8.2常见数据通路的数据传送

（1）寄存器之间的数据传送(by CPU内部总线)；（2）主存与CPU之间的数据传送(by CPU内部总线)；（3）执行算数或逻辑运算(算数逻辑单元ALU没有内部存储功能，因此执行算数逻辑运算时，要求ALU的两个输入端同时有效)。

9. 控制单元的功能

(1)从主存中取出一条指令，并指出下一条指令在主存中的位置； (2)对指令进行译码或测试，产生相应的操作控制信号，以便启动规定的动作； (3)指挥并控制CPU、主存、输入和输出设备之间的数据流动方向。

10. 控制器的控制方式

同步控制方式：整个系统的所有控制信号均来自一个统一的时钟信号

(1)采用完全统一节拍的机器周期(定长方式)； (2)采用不同节拍的机器周期(不定长方式)； (3)采用中央控制和局部控制相结合的方法。

异步控制方式：通过应答方式进行联络，不存在基准时标信号，一般用于主机与I/O设备之间的传送控制，使告诉的主机与慢速的I/O设备可以按照各自的需要设置时序系统。

联合控制方式：折中方案，这种方式对各种不同的指令的微操作大部分采用同步控制方式，小部分采用异步控制方式。

11. 控制单元(CU)的设计

11.1 两种设计方式的对比

组合逻辑控制(硬布线逻辑控制)：控制器处理速度块，但电路庞杂导致难以扩展，制造周期长，不灵活，可维护性差。
微程序控制:仿照程序设计的方法编制每个机器指令对应的微程序，每个微程序由若干条微指令构成，各微指令包含若干条微命令。扩展单元设计简单，指令添加容易(灵活)，可维护性好，但速度较慢。

11.2 微程序设计

11.2.1 微程序设计的概念

将一条机器指令编写成一个微程序，每一个微程序包含若干条微指令，每一条微指令对应一个或几个微操作命令。然后把这些微程序存到一个控制存储器中，用寻找用户程序的方法来寻找每个微程序中的微指令。所以逐条执行每一条微指令，也就相应地完成了一条机器指令的全部操作。每一条机器指令都与一个以操作性质命名的微程序对应。

11.2.2 微程序控制的相关概念

微命令与微操作一条机器指令可以分解成一个微操作序列(不可再分)。微命令是由控制部件向执行部件发出的各种控制命令，是构成控制序列的最小单位。微命令和微操作一一对应，微命令是微操作的控制信号，微操作是微命令的执行过程。
微指令与微周期 微指令是若干微命令的集合，包含操作控制字段和顺序控制字段。微周期指从控制存储器中读取一条微指令并执行相应的微操作所需的时间。
主存储器和控制存储器 主存储器用于存放程序和数据，在CPU外部，用RAM实现；**控制存储器(CM)**用于存放微操作，在CPU内部，用ROM实现。
程序与微程序程序是指令的有序集合，用于完成特定的功能；微程序是微指令的有序集合，一条指令的功能由一段微程序来实现。

11.2.3 微程序控制单元的基本组成

控制存储器：这是微程序控制单元的核心部件，用来存放全部微程序，包含控制地址寄存器(CMAR，存放欲读出的微指令地址)和控制数据寄存器(CMDR,存放从控存中读出的微指令)； 顺序逻辑：用来控制微指令序列。

11.2.4 微指令的基本格式

操作控制字段：发出各种控制信号； 顺序控制字段:可指出下地址，以控制微指令序列的执行。

11.2.5 微指令的编码方式

(1)直接编码(直接控制)方式：在微指令的微命令字段中每一位都代表一个微命令，不需要译码，因此简单、直观，执行速度快，操作并行性好。但微指令字长过长，造成控制存储器容量极大。

(2)字段直接编码方式：将微指令的微命令字段分成若干小字段，把互斥性微命令组合在同一字段中，把相容性微命令组合在不同字段中。缩短了微指令字长，但是要通过译码电路后再发出微命令，比较慢。

注：微指令周期是指读出微指令的时间+执行该条微指令的时间。

(3)字段间接编码方式：一个字段的某些微命令需由另一个字段中的某些微命令来解释，而不是靠字段直接译码发出微命令。可以进一步缩短微指令字长，但削弱了微指令的并行能力。

(4)混合编码方式

11.2.5 微指令格式

水平型微指令：一次能定义并执行多个并行操作。

优点：微程序短，执行速度快；

缺点：微指令长，编写微程序较麻烦。

垂直型微指令：类似机器指令操作码的方式，由微操作码字段规定微指令的功能。

优点：微指令短，简单、规整，便于编写微程序；

缺点：微程序长，执行速度慢，工作效率低。

混合型微指令

12. 指令流水线

12.1 指令流水线的优缺点

优点：缩短了程序的执行时间各功能部件的利用率明显提高；

缺点：需付出较大的硬件开销，控制过程相比顺序执行也更为复杂。

12.2 影响流水线的因素

(1)资源相关：多条指令进入流水线后在同一机器时钟周期使用了同一个功能部件所发生的冲突。

(2)数据相关：后一条指令必须等待前一条指令执行完毕才能执行。

(3)控制相关：当执行转移指令时，依据转移条件的产生结果，可能顺序执行下一条指令，也可能转移到新的目标地址取指令，从而使流水线断流。

第六章、总线

6.1 总线的基本概念

定义：总线是一组能为多个部件分时共享的公共信息传送线路(物理线路)。

特点：分时+共享。

特性：机械特性(尺寸、形状)+电气特性(传输方向和有效的电平范围)+功能特性(每根传输线的功能)+时间特性(哪根线在什么时候有效)。

总线的传输周期：指CPU通过总线对存储器或I/O端口进行一次访问所需的时间。

总线宽度：举例，高速公路有16条车道，则宽度就是16。

6.2 总线的分类

按照数据传送方式，可分为并行传输总线和串行传输总线.

按照总线的使用范围，可分为计算机总线和测控总线.

按照连接部件的不同，可分为片内总线，系统总线和通信总线.

注：片内总线就是芯片内部的总线，系统总线是连接五大不见之间的信息传输线，包括数据总线、地址总线和控制总线。

6.3 总线的组成

一组控制线、一组数据线和一组地址线。

6.4 总线的性能指标

总线宽度：通常是指数据总线的根数。

总线带宽：单位时间内总线上传输数据的位数。

总线复用：地址总线和数据总线共用一组线。

信号线数：地址总线、数据总线和控制总线3种总线数的总和。

6.5 总线的结构

(1)单总线结构：将CPU、主存和I/O设备都连接在一组总线上，允许它们之间直接交换信息。结构简单，容易扩充外部设备，但不允许两个以上的部件同时向总线传输信息。特点：主存和I/O设备统一编址，CPU可以像访问内存一样访问外部设备。

(2)双总线结构：将速度较低的I/O 设备从总线中分离出来，形成主存总线与I/O 总线分开的结构。

(3)三总线结构：在I/O高速设备与主存之间增加了一条DMA总线。

6.6 总线仲裁（确定哪个设备可以使用总线）

6.6.1 集中仲裁方式

(1)链式查询方式：总线上的所有部件公用一根总线请求线，当由部件请求使用总线时，均需经此线发送请求信息到总线控制器，若总线不忙，则允许请求，否则等待。

优先级判别方式：离总线控制器越近的部件，其优先级越高。

优点：结构简答，易扩充；

缺点：对设备电路的故障敏感，对低优先级的部件不公平。

(2)计数器查询方式：采用一个计数器控制总线的使用权。

优先级判别方式：当总线控制器接收到总线请求信号判断总线不忙时，计数器开始计数，计数值通过一组地址线发向各个部件。当地址线上的计数值与请求使用总线设备的地址一致时，该设备获得总线控制权。同时，终止计数器的计数及查询工作。

优点：各设备优先级顺序可以改变，而且对电路故障不敏感；<br。缺点：增加了控制线数，控制较为复杂。

(3)独立请求方式：每一个设备均有一对总线请求信号和总线同意信号。

优先级判别方式：在总线控制器中排队，等待批准。

优点：响应时间很快(以增加控制线为代价)，对优先级顺序的控制相当灵活；

缺点：总线控制更复杂。

6.6.2 分布仲裁方式

不需要中央仲裁器，每个主模块都有自己的仲裁号和仲裁器，多个仲裁器竞争使用总线。

7. 总线周期

完成一次总线操作的时间称为总线周期。

包括申请分配阶段+寻址阶段+传送数据阶段+结束阶段。

8. 总线定时

8.1 同步定时方式

系统采用一个统一的时钟信号来协调发送和接受双方的传送定时关系。时钟信号通常由中央处理器的总线控制器发出，然后送到总线上的所有部件。

优点：传送给速度快，具有较高的传输速率，总线控制逻辑简单。

缺点：主从设备之间属于强制性同步，不能及时进行数据通信的有效性检验，可靠性较差。

适用范围：总线长度较短，总线所接部件的存取时间应该比较接近。

8.2 异步定时方式

允许各模块的速度不一致，没有公共的时钟标准，不要求所有部件严格地统一操作时间，而是采用应答方式(需要在主从模块之间增加两条应答线）。有不互锁、半互锁和全互锁3种方式。

优点：总线周期长度可以改变，能保证两个工作速度相差较大的部件或设备之间可靠地进行信息交换，自动适应时间的配合；

缺点：比同步控制方式稍微复杂一些，速度比同步定时方式慢。

一、考纲

1、浮点数的规格化表示

原码的尾数，规格化表示应该是 ×.1×……×
补码的尾数，规格化表示应该是 0.1×……× 或 1.0×……× ，即符号位(MS)和最高有效位(M1)相异。

2、数制之间的转换

3、浮点数的加法

例题：解：[X]浮 = 00，001 11.0110101 [Y]浮 = 11，110 00.1100101
- （1）对阶 ΔE=EX-EY=[EX]补+[-EY]补 = 00，001+00，010 = 00，011 ΔE=3>0，将MY右移3位，EY加3： [Y]浮 = 00，001 00.0001100 （101）
- （2）尾数相加： [MZ]补 = 11.1000001（101）
- （3）结果规格化：左规一位，无溢出： [MZ]补 = 11.0000011（01） [EZ]补 = 00，001 + 11，111= 00，000
- （4）舍入：按照0舍1入法，尾数多余位舍去结果为：[Z]浮 = 0，000 1.0000011

4、微程序的流程图

例：ADD 和 JMP 指令：

- 看指令有几个字节，就看有多少个 PC+1

5、程序代码所在地址的计算，和跳转程序的偏移量的计算。

指令寻址：
- 顺序寻址方式：PC + 1，自动取下一条指令。
- 跳跃寻址方式：由该条转移指令的地址码字段得到新指令地址，然后将其置入PC中。
数据寻址：
- 指令的地址码字段，通常都不代表操作数的真实地址，把它称作形式地址，记为A。操作数的真实地址称为有效地址，记作EA，它是由寻址方式和形式地址共同来确定的。

- 立即寻址：操作数在指令的地址码字段，即： DATA＝A

- 直接寻址：操作数位于存储器中，操作数所在的存储器单元的地址存放在指令的地址字段A中，即： DATA＝（EA） EA=A

- 间接寻址：操作数位于存储器中，操作数所在的存储器单元地址也存放在存储器中，该存储器地址则存放在指令的地址字段中，即： DATA＝（EA） EA=（A）

- 寄存器寻址：操作数位于寄存器中，操作数所在的寄存器编号存放在指令的地址字段A中，即： DATA＝（Ri）

- 寄存器间接寻址：操作数位于存储器中，操作数所在的存储器地址存放在寄存器中，而该寄存器编号存放在指令的地址字段A中，即： DATA＝（EA） EA＝（Ri）

- 变址寻址：操作数位于存储器中，操作数所在的存储器地址EA由变址寄存器RI和指令的地址字段A指出： DATA＝（EA） EA＝（RI）＋A

- 基址寻址：操作数位于存储器中，操作数所在的存储器地址EA由基址寄存器Rb和指令的地址字段A指出： DATA＝（EA） EA＝（Rb）＋A

- 基址变址寻址：
- 相对寻址：
- 堆栈寻址：

6、根据模型机的指令格式，写出某条指令编码的二进制代码。

7、结合指令的格式，根据内存中存放的内容，写出内存中的各条指令。

8、根据模型机的结构，写出微程序各个字段的值和控存的容量。

令微指令的字长为n，下址字段为 a 位，则控存容量为 2^a * n 位。

9、控制器的组成和功能。

程序计数器 PC：①当指令顺序执行时，由PC+1产生下一条指令的地址；②当遇到转移指令时，转移地址 -> PC作为下一条指令的地址。
指令寄存器 IR：
地址寄存器 AR：
数据寄存器 DR：
指令译码器：
操作控制信号形成部件：①采用硬布线设计的操作控制信号形成部件；② 采用微程序设计的操作控制信号形成部件。
时序信号产生器：

10、计算二级存储体系的命中率和访问时间，以及访问效率。

在一个程序执行期间，设Nc表示Cache完成存取的总次数，Nm表示主存完成存取的总次数，则命中率：h = Nc / ( Nc + Nm)
若tc表示Cache的访问时间，tm表示主存的访问时间，则Cache/主存系统的平均访问时间ta为：ta = htc + ( 1 - h ) * ( tm + tc ) 或 ta = htc + ( 1- h ) * tm
Cache/主存系统的访问效率e：e = tc / ta

11、组相联方式下各个字段的位数，以及某个地址位于那一组。

主存字块标记 t+r 位，组地址 c-r 位，块内地址 b 位。
j = ( i mod 2^(c -r) ) * 2^r + k , 0 <= k <= 2^r - 1

12、在主存采用多体交叉方式时，计算访问时间。

每个存储体的字长都等于数据总线宽度，存储体存取一个字的存储周期为T，总线传送周期为τ，存储器的交叉存储体数为M，为了实现流水线方式存取，应当满足 T=Mτ
T/τ称为交叉存取度，当交叉存储体数大于或等于T/τ时，可以保证启动某模块后经Mτ时间再次启动该模块时，它的上次存取操作已经完成。这样，连续读取M个字所需的时间为t=T+（M-1）τ

13、计算汉字的内码和字形码占用的字节数。

汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表示。
机内码等于汉字国标码加上8080H。即两个字节的最高位均设为“1”。
英文字符的机内代码是七位的ASCII码，当用一个字节表示时，最高位为“0”。
汉字字形码是将汉字字形经过点阵数字化后形成的一串二进制数，用于汉字的显示和打印。根据汉字输出的要求不同，点阵有以下几种：
- 简易型汉字：16×16， 32字节/汉字
- 普通型汉字：24×24， 72字节/汉字
- 提高型汉字：32×32，128字节/汉字。
- 即汉字的字形码的字节数等于字节的点阵大小的平方 / 8。

14、深入了解MIPS处理器的结构图。

15、看懂MIPS书写的条件循环控制程序。

16、将 MIPS I 型指令扩展到 IO 设备输入输出的情况。

扩展前：

扩展后：

17、操作码的分配原则。

操作码的扩展

- 4位操作码,15条三地址指令

- 8位操作码,15条二地址指令

- 12位操作码,15条一地址指令

- 16位操作码

18、集中式刷新刷新一遍的时间的计算。

例：64K×1位DRAM芯片中，存储电路由4个独立的128×128的存储矩阵组成。设存储器存储周期为500ns，单元刷新间隔是2ms。
则在2ms单元刷新间隔时间内，集中对128行刷新一遍，所需时间128×500ns=64μs，其余时间则用于访问操作。
在内部刷新时间（64μs）内，不允许访存，这段时间被称为死时间。
集中式刷新缺点：访问访存“死区”的时间比较长，降低了计算机系统的效率。

19、存储器的地址分配和连接。

位扩展
- 扩展前容量为：1K × 4 位
- 扩展后容量为：1K × 8 位

字扩展
- 扩展前容量为：1K×８位
- 扩展后容量为：2K × 8 位

二、知识点总结

1、CISC和RISC的优缺点：

CISC：
- 优点：指令越多功能越强，强调代码效率，容易和高级语言接轨。可以对存储器直接操作，实现从存储器到存储器的数据转移，可加入DSP指令。
- 缺点：指令太多不易记忆；CPU内部结构复杂造成频率不高；指令执行速度慢。
RISC：
- 优点：指令少容易记忆，尽量将操作码和操作数用1个16位数或32位数表示，指令整齐。CPU时钟频率可以做得很高，指令执行速度快。
- 缺点：同样功能的程序，产生的代码量比较大；不能对存储器直接访问，不能实现存储器到存储器的数据转移。

2、存储器分类：

按存储介质分：
- 半导体存储器
- 磁存储器
- 纸带存储器
- 光存储器
按存取方式分：
- 随机读写存储器（RAM）：断电不保存。-> 主存储器
- 只读存储器（ROM）：断电保存。有掩膜式只读存储器（MROM）、可编程只读存储器（PROM）、可擦除可编程只读存储器（EPROM）、电可擦除可编程只读存储器（EEPROM）、闪存（Flash）。
- 相联存储器（CAM）：在这种存储器中访问一个字是通过它的部分内容而不是地址进行检索的。
- 顺序存储器（SAS）：存取时间和存储单元的物理位置有关。 -> 磁带
- 直接存取存储器（DAS）：先根据部分地址信息找到大致范围，再在此范围内顺序检索，找到目标。 -> 磁盘、磁鼓存储器等大容量的辅助存储器。
按信息的可保存性分：
- 永久记忆存储器 -> 磁盘、光盘、U盘
- 非永久记忆存储器 -> RAM
按在计算机系统中的作用分：
- 寄存器
- 主存储器
- 辅助存储器
- 高速缓冲存储器（Cache）

3、微程序控制器和硬布线控制的划分依据：

根据微操作控制信号的产生方式（也可以说是根据操作控制信号形成部件的电路结构）区分的，微程序控制器中，微操作控制信号从控制存储器读出，而硬布线控制器由组合逻辑电路即时产生。

4、微程序控制器和硬布线控制的优缺点：

微程序控制器中，指令的修改和扩充比较容易；

硬布线控制器的执行速度比较快。

5、主存与Cache的地址映射方式：

直接映射：
- 高位标记 t 位，字块位置 c 位，块内地址 b 位。
- Cache中的行号 j 和主存的块号 i 间的函数关系： j = i mod 2^c

全相联映射：
- 高位位置 m 位，块内地址 b 位。

组相联映射：
- 主存字块标记 t+r 位，组地址 c-r 位，块内地址 b 位。
- j = ( i mod 2^(c -r) ) * 2^r + k , 0 <= k <= 2^r - 1

6、单周期MIPS的R、I、J三种类型指令的格式、意义和执行过程：

指令格式：

在R型指令中：
- OP：操作码
- rs：第一个源操作数寄存器
- rt：第二个源操作数寄存器（单目源数据）
- rd：结果寄存器
- shamt：移位操作时的位移量，非移位操作时为0
- func：功能码
- 例：R[rd] ← R[rs] + R[rt]
在I型指令（立即数型指令）中：
- rs：源操作数寄存器
- rt：结果寄存器
- 例：R[rt] ← R[rs]
在J型指令（无条件转移指令）中：
- address：直接地址

三、重点题型

操作系统

（一）操作系统概述

1、操作系统的概念、特征、功能和提供的服务

【操作系统的概念】

用户观点：根据用户所使用计算机的不同而设计不同类型的操作系统系统观点：操作系统是计算机系统的资源管理程序进程观点：操作系统由若干个可以独立运行的程序和一个对这些程序进行协调的核心所组成虚拟机观点：也称机器扩充，操作系统为用户使用计算机提供了许多服务功能和良好的工作环境

【操作系统的特征】

并发性：两个或多个事件在在同一时间间隔内发生（而并行性是指两个或多个事件在同一时刻发生）共享性：系统中的硬件和软件资源不再为某个程序所独占，而是供多个用户共同使用（包括互斥共享（如打印机，某些变量，队列等一段时间只能供一个作业使用的资源）和同时访问（如可重入代码，磁盘等），后者作业访问资源的顺序不会影响访问的结果）虚拟性：把一个物理上的实体变为若干个逻辑上的对应物异步性：在多道程序环境中，由于资源等因素的限制，程序走走停停，以不可预知的速度向前推进

【操作系统的功能】

处理器管理：对处理器的分配和和运行（以进程为单位）实施有效的管理，包括进程控制（负责进程的创建，撤销以及状态转换），进程同步（对并发执行的进程进行协调），进程通信（负责进程间的信息交流），进程调度（按一定算法进行处理器分配） 存储器管理：对内存进行分配，保护和扩充，包括内存分配（按一定策略为每道程序分配内存），内存保护（保证各程序在自己的内存区域内运行而不相互干扰），内存扩充（为允许大型最作业或多作业的运行，必须借助虚拟存储技术去获得增加内存的效果） 设备管理：对计算机系统内的所有设备进行管理。包括设备分配（根据一定的设备分配原则对设备进行分配），设备传输控制（实现物理的输入输出操作），设备独立性（用户程序中的设备与实际使用的物理设备无关) 文件管理：操作系统中负责信息管理的部分称为文件系统，文件管理的主要任务包括文件存储空间的管理（存储空间的分配与回收），目录管理（提供按名存取的功能），文件操作管理（负责完成数据的读写），文件保护 用户接口：方便用户使用操作系统，包括命令接口（包括联机命令接口和脱机命令接口），程序接口（也称系统调用），图形接口

【操作系统提供的服务】

程序执行，I/O操作，文件操作，资源分配与保护，错误检测与排除

2、操作系统的发展与分类

【操作系统的发展】

无操作系统阶段：用户独占资源，资源利用率低，CPU等待人工操作，手工操作的慢速CPU运算的高速矛盾（引入了脱机输入/输出技术）单道批处理系统：自动性，顺序性，单道性多道批处理系统：多道，宏观上并行，微观上串行

【操作系统的分类】

批处理操作系统：运行过程无需用户干预，大大提高了系统资源利用率和系统吞吐量，但无交互性，使用不便

分时操作系统：在操作系统中采用分时技术（把处理器的运行时间分成很短的时间片，按时间片轮流把处理器为分配给各联机作业使用）而得,特征是多路性，交互性，独占性，及时性

实时操作系统：提供及时响应和高可靠性

嵌入式操作系统

集群系统：将两个或多个独立的系统耦合起来，共同完成一项任务

网络操作系统

分布式操作系统

（二）进程管理

1、进程与线程的基本概念

【进程的定义】

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

【进程的组成】

程序段：进程中能被进程调度程序调度到CPU上执行的代码段

数据段：进程对应的程序加工处理的原始数据或者程序执行时产生的中间或结果数据

PCB：既能标识进程存在，又能刻画执行瞬间的数据结构

【进程的特征】

动态性：进程是程序的一次执行过程，是动态地产生，变化和消亡的

并发性：内存中有多个进程实体，各进程可并发执行

独立性：进程是能独立运行，独立获得资源，独立接受调度的基本单位

异步性：各进程按各自独立的，不可预知的速度向前推进

结构性：每个进程都会配置一个PCB，结构上看，进程由数据段，程序段，PCB组成

【进程与程序的关系】

进程是动态的，程序是静态的

进程是暂时的，进程是永久的

进程与程序的组成不同

通过多次执行，一个程序可以产生多个不同的进程；通过调用关系，一个进程可以执行多个程序。进程可以创建其他进程，而程序不能形成新的程序

进程具有并行特性，而程序没有

【进程与作业的关系】

作业是用户向计算机提交任务的任务实体，而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位

一个作业可由一个或多个进程组成，但一个进程不能构成多个作业

作业的概念主要用在批处理系统中，而进程的概念则几乎用在所有的多道程序系统中

【为什么PCB是进程存在的唯一标志？】

在系统调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据

进程在执行过程中，当需要和与之合作的进程实现同步，通信或访问文件时，也都需要访问PCB

当程序由于某种原因暂停执行时，又需要将其断点的处理机环境保存在PCB中

【导致进程创建的事件有哪些？】

用户登录。在分时系统中，用户在终端输入登录信息，系统检测通过后就为该终端用户建立新进程并插入到就绪队列

作业调度。在批处理系统中，当作业调度程序按照一定的算法调度到某个作业时，将该作业装入内存，并为其分配资源并创建进程，并插入到就绪队列

请求服务。基于进程的需要，由其自身创建一个新进程并完成特定任务

【创建进程时，操作系统需要完成的主要工作是什么？】

先向系统申请一个空闲PCB，并指定唯一的进程标识符（PID）

为新进程分配必要的资源

将新进程的PCB初始化。为新进程的PCB填入进程名，家族信息，程序数据地址，优先级等信息

将新进程的PCB插入到就绪队列

【导致进程撤销的事件有哪些？】

进程正常结束，进程异常结束以及外界干预等

【撤销一个进程时，操作系统主要完成的工作是什么？】

先从PCB集合中找到被撤销进程的PCB

若被撤销进程正处于执行状态，则应立即停止该进程的执行，设置重新调度标识，以便进程重新后将处理器分配给其他进程

对后一种撤销策略，若被撤销进程有子孙进程，还应将该进程的子孙进程撤销

回收被撤销进程所占有的资源，或者归还给父进程，或者归还给系统。最后，回收其PCB

【阻塞一个进程时，操作系统主要完成的工作是什么？】

首先停止当前进程的运行。因该进程正处于执行状态，故应中断处理器

保存该进程的CPU现场以便之后可以重新调用该进程并从中断点开始执行

停止运行该进程，将进程状态由执行状态改为阻塞状态，然后将该进程插入到相应事件的等待队列中

转到进程调度程序，从就绪队列中选择一个新的进程投入运行

【唤醒一个进程时，操作系统主要完成的工作是什么？】

将被唤醒进程从相应的等待队列中移出

将状态改为就绪并插入相应的就绪队列

【简述进程上下文切换的过程】==【切换进程时，操作系统主要完成的工作是什么？】

保存处理及上下文，包括程序计数器和其他寄存器

更新PCB信息

把进程的PCB移入相应队列，如就绪，某事件的阻塞队列

选择另一个进程执行，更新其PCB

更新内存管理的数据结构

恢复处理器上下文

【线程的定义】

线程是进程内一个相对独立的，可调度的执行单元

【线程的实现】

内核级线程：依赖于内核，由操作系统内核完成创建和撤销工作的线程

用户级线程：不依赖于操作系统核心，由应用进程利用线程库提供创建，同步，调度和管理线程的函数来控制的线程

组合方式：同时提供内核线程控制机制和用户线程库

【多线程模型】

【线程与进程的比较】

调度。引入线程后，线程是独立调度的基本单位，进程是拥有资源的基本单位；在同一进程中，线程的切换不会引起进程切换；在不同进程中进行线程切换，将引起进程切换

拥有资源。进程始终是拥有资源的基本单位，线程可以访问其隶属进程的系统资源

并发性。引入进程的操作系统中，不仅进程之间可以并发执行，而且同一进程内的多个线程之间也可以并发执行，这使得操作系统具有更好的并发性，大大提高了系统的资源吞吐量

系统开销。引入线程后，线程之间的切换开销很小，而且由于同一进程内的多个线程共享进程的地址空间，因此多线程之间的同步与通信容易实现

2、进程调度的基本概念、调度方式、调度算法

【操作系统中的3级调度】

高级调度，又称作业调度，按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程，发生频率最低

中级调度，又称内存调度，按照某种规则，从挂起队列中选择合适的进程将其数据调回内存，发生频率中等

低级调度，又称进程调度，按照某种规则，从就绪队列中选择一个进程为其分配处理机，发生频率最高

【进程调度的概念】

系统按照一定的策略动态地把处理器分配给就绪队列中的某个进程，以便使之执行

【进程调度的功能】

用PCB记录系统中所有进程的有关情况以及状态特征

选择获得处理器的进程

处理器分配

【引起进程调度的原因】

当前进程运行结束，包括任务完成而正常结束或者因出现错误而异常结束

当前运行进程因某种原因，如I/O请求，P操作，阻塞原语等从运行态变为阻塞态

执行完系统调用等系统程序后返回用户进程，这时可以看作系统进程执行完毕，从而可以调度一个新的用户进程

在采用抢占式调度方式的系统中，更高优先级的进程要求使用处理器，则使当前运行进程进入就绪队列

在分时系统中，分配给该进程的时间片已用完

【不能进行进程调度的情况】

处理中断的过程中。处理中断过程复杂，很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理器资源

在操作系统内核程序临界区中。进程进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放

在其他需要完全屏蔽中断的原子操作过程中。原子操作不可再分，不能进行进程切换

【进程调度的方式】==【CPU调度算法中抢占式调度和非抢占式调度有何区别？】

抢占方式，当一个进程正在处理器上运行时，若有更高优先级的进程进入就绪队列，则立即暂停执行当前进程，将处理器分配给新进程。可优先处理紧急进程，也可实现让各进程按时间片轮流执行，适用于分时操作系统，实时操作系统

非抢占方式，当一个进程正在处理器上运行时，即使有更高优先级的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或者因发生某种事件而进入完成或者阻塞状态时，才把处理器分配个新进程。实现简单，开销小，但无法处理紧急任务，适用于早期批处理系统

【调度算法】

先来先服务

短作业优先

优先级调度，分为抢占式和非抢占式，优先级相同时，通常按照先来先服务或者短作业优先的顺序执行

时间片轮转

高响应比优先，响应比=（等待时间+运行时间）/运行时间

多级反馈队列调度

3、进程同步的基本概念、临界区、信号量、经典同步问题

【两种形式的制约关系】

间接相互制约关系（互斥）

直接相互制约关系（同步）

【临界资源与临界区】

临界资源：同时仅允许一个进程使用的资源

临界区：进程中用于访问临界资源的代码，又称临界段

【互斥的要求】

空闲让进：当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区

忙则等待：当已有进程进入临界区时，其他师徒进入的进程必须等待

有限等待：对要求访问临界区的进程，应在有限的时间内进入自己的临界区

让权等待：当一个进程因为某些已有无法进入自己的临界区时，应释放处理器给其他进程

【信号量】

(1)整型信号量：未遵循让权等待

(2)记录型信号量（资源信号量），P&V 操作主要用这个

【经典同步问题】

生产者-消费者读者写者问题（读优先，读写公平，写优先）哲学家进餐理发师

【PV操作的框架细节】

根据实际进程类型来判断是否添加while循环代码用cobegin和coend表示进程之间的并发执行

4、死锁的基本概念、处理策略、死锁预防和死锁避免的算法、死锁检测

【死锁的定义】

当多个进程因竞争系统资源或相互通信而处于永久阻塞状态时，若无外力作用，这些进程都将无法向前推进，均无限期地等待此组进程中某个其他进程占有的，自己永远无法得到的资源，这种现象称之为死锁

【可剥夺资源与不可剥夺资源的区别】

可剥夺资源是指虽然资源占有者进程需要使用该资源，但另一个进程可以强行把该资源剥夺来归自己使用

不可剥夺资源是指除占有者进程不再需要使用该资源而主动释放资源，其他进程不可在资源占有者使用资源过程中强行剥夺

【死锁产生的原因】

系统资源不足（根本原因）

进程推进顺序不当

信号量的使用不当
简而言之，对不可剥夺资源的不合理分配，可能导致死锁

【死锁产生的必要条件】

互斥条件：进程要求对所分配的资源进行排他性控制，即在一段时间内某种资源仅为一个进程所占有

不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由获得该资源的进程主动释放

请求和保持条件：也成部分分配条件，是指进程已经保持了至少一个资源，但又提出了新的资源请求，而在等待新的资源被分配的同时，又对已有资源保持占有

循环等待条件：存在一种资源的循环等待链，而链中每一个进程已获得的资源同时被链中的下一个进程所请求

【处理死锁的基本方法】

鸵鸟算法：视死锁不见

预防死锁：破坏死锁产生的4个必要条件中的一个或多个

避免死锁：在资源的动态分配过程中

检测及解除死锁

【死锁的预防】

破坏互斥条件：允许多个进程同时访问资源，可行性不高

破坏不剥夺条件：对于一个已经获得了某些资源的进程，若新的资源请求不能立即得到满足，则它必须释放所拥有的全部资源，以后需要时再重新申请，实现复杂，可能导致部分工作失效，导致系统开销增大，导致饥饿

破坏请求和保持条件：运行之前一次行分配好所需要的全部资源，简单安全，但资源利用率低，可能导致饥饿

破坏循环等待条件：给资源编号，必须按照编号从小到大的顺序申请资源，不方便增加新设备，会造成资源浪费，用户编程麻烦

【死锁的避免】

银行家算法

【死锁定理】

系统状态为死锁的条件是：当且仅当g该状态下的资源分配图是不可完全简化的

【死锁的检测】

死锁检测算法

【死锁的解除】

资源剥夺法：从其他进程中抢占足够的资源给死锁的进程以解除其死锁状态

撤销进程法：撤销一些进程，直到有足够的资源分配给其他进程，进程死锁状态

进程回退法：让一个或多个进程回退到足以避免死锁的地步，进程回退时资源释放资源而不是被剥夺，要求系统保持进程的历史信息，设置还原点

（三）内存管理

1、内存管理基本概念

【内存管理的功能】

内存的分配与回收

地址变换

内存扩充

存储保护

【链接的3种方式】

静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开

动态链接：将应用程序编译后所得到一组目标模块装入内存时采用边装入边链接的动态链接方式

运行时动态链接：在程序执行中需要该目标模块时，才对这些模块进行链接，便于修改和更新，便于实现对目标模块的共享

【程序装入的3种方式】

绝对装入：编译时就知道程序将要驻留在内存中的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计

可重定位装入：又称静态重定位，根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，适用于早期的多道批处理操作系统，容易实现，无需增加硬件地址变换机构，但要求为每个程序分配一个连续的存储区，而且在程序执行期间不能移动，不能再申请内存空间，难以做到程序和数据的共享

动态运行时装入：又称动态重定位，允许程序运行时在内存中移动位置，把地址变换推迟到程序真正要执行时才进行，需要一个重定位寄存器的支持：物理地址=基址寄存器内容+逻辑地址

【内存保护的方法】

界限寄存器方法，包括上、下界寄存器方法和基址和限长寄存器方法

存储保护键方法,给每个存储块分配一个单独的保护键

2、内存交换及分页、分段、段页式内存分配管理

【内存空间的扩充】

覆盖

交换

【连续分配管理方式】

单一连续分配

固定分区分配

动态分区分配

【动态分区分配算法】

首次适应算法

最佳适应算法

最坏适应算法

邻近适应算法

【基本分页存储管理方式的优缺点】

优点：内存利用率高，实现了离散分配，便于存储访问控制，无外部碎片

缺点：需要硬件支持（尤其是快表），内存访问效率下降，共享困难，有内部碎片

【基本分段存储管理方式的优缺点】

优点：便于程序模块化处理和处理变换的数据结构，便于动态链接和共享，无内部碎片

缺点：与分页类似，需要硬件支持；为满足分段的动态增长和减少外部碎片，要采用拼接技术；分段的最大尺寸受到主存可用空间的限制；有外部碎片

【分段与分页的区别】

页是信息的物理单位，段是信息的逻辑单位；

分页的目的是系统管理所需，为了提高内存利用率；分段的目的是为了更好的满足用户的需要

页的大小固定且由系统决定；段的长度不固定，段长由用户编写的程序决定

分页的地址空间是一维的，而分段的地址空间是二维的；

分页有内部碎片，无外部碎片；分段有外部碎片，无内部碎片

【页式存储管理方式中设置快表的作用】

快表，又称联想寄存器(TLB)，时一种访问速度比内存快很多的高速缓存，用来存放最近访问过的页表项的副本，若快表命中，则只要访问一次高速缓存以及一次主存即可，这样就可以加速地址变换的速度，从而提高了查找的速度和指令执行效率

3、虚拟内存

（1）虚拟内存的基本概念

【虚拟内存的特征】

离散性：程序在内存中离散存储

多次性：一个作业可以分成多次调入内存

对换性：又称交换性，指作业在运行过程中可以换入换出

虚拟性：从逻辑上扩充内存容量，用户可以使用的空间远大于实际内存容量

【局部性原理】

时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短的时期内

空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据，都集中在一个较小的区域内

【请求分页存储管理原理】

在分页存储管理系统的基础上，通过增加请求调页功能，页面置换功能所形成的一种虚拟存储系统;在资源运行之前，装入部分页面便可投入运行，运行时若缺页则调页，同时还可以通过页面置换功能将暂时用不到的页面调出到外存

【请求分页管理方式的优缺点】

优点：可以离散存储程序，降低了碎片数量；提供虚拟存储器，提高了主存利用率，有利于多道程序运行，方便用户

缺点：必须有硬件支持；有些情况下会产生抖动现象；程序最后一页仍存在未被利用的部分空间

（2）页面置换算法

【页面置换算法】

最佳置换算法（OPT)

先进先出算法(FIFO)

最近最少使用算法(LRU)

时钟置换算法（CLOCK）

改进型时钟置换算法

【抖动现象】

刚刚换出的页面，过后不久又要访问，并且调入不久后又被调出，如此反复，使得系统把大部分的时间用在了页面的调入调出上，而几乎不能有效的工作

（3）页面分配策略

【工作集】

定义：最近n次内存访问的页面集合，数字n被称作工作集窗口，也就是工作集的大小

【页面分配策略】

固定分配全局置换

可变分配全局置换

可变分配局部置换

【页面调入策略】==【何时调入页面】

请求调页策略，实现简单，但容易产生缺页中断，时间开销大，容易产生抖动现象

预调页策略，将之后可能用到的页面一次全部调入内存

【从何处调入页面】

系统拥有足够的对换区空间，则全部从对换区调入所需页面，以提高调页速度

系统缺少足够的对换区空间，凡是不会被修改的文件都从文件区调入，置换出这些页面时，由于他们没有被修改而不必再将它们换出，右后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，就应调换到对换区，以后需要时再从对换区调入

UNIX方式：进程运行前，相关数据全放在文件区，故未使用过的页面都可以从文件区调入；若被使用过的页面需要换出时，则写回对换区，下次需要时从调换区调入

（四）文件管理

1、文件系统基础

（1）文件概念

【文件的定义】

文件是具有文件名的一组相关元素的集合，在文件系统中是一个最大的数据单位，它描述了一个对象集，每个文件都有一个文件名，用户通过文件名来访问文件

【文件的组成结构】

数据项，文件系统中最低级的数据组织形式，包括基本数据项(用于描述一个对象是的某种特性的一个值)和组合数据项(由多个数据项组合而成)

记录，是指一组相关的数据项的集合，用于描述一个对象在某一方面的属性

文件，是指由创建者所定义的一组相关数据的集合，逻辑上可分为有结构文件和无结构文件

【文件的属性】

名称。文件名唯一，以容易读取的形式保存

标识符。系统内文件的唯一标签，对用户透明

文件类型。被支持不同类型的文件系统使用

文件位置。指向文件的指针

文件的大小，建立时间，用户标识

（2）文件的逻辑结构：顺序文件、索引文件和索引顺序文件

【3种有结构文件】

顺序文件：定长记录的顺序文件，若物理上采用顺序存储则可以实现随机存取，若再能保证记录的顺序结构，则可实现快速检索，但因为文件存储要求连续的存储空间，所以会产生碎片，同时也不利于文件的动态扩充

索引文件：可以进行随机访问，易于文件的增删，但索引表的使用增加了存储空间的开销，并且索引表的查找策略对文件系统的影响很大

索引顺序文件：大大提高了了顺序存取速度，但仍需配置一个索引表，增加了存储开销

（3）目录结构

【目录的功能】

实现按名存取

提高检索速度

允许文件同名

允许文件共享

文件目录：FCB的有序集合，一个FCB称为一个文件目录项

目录文件：为了实现文件目录的管理，通常将文件目录以文件的形式保存在外存空间，这个文件就称为目录文件（它是长度固定的记录式文件)

【文件控制块FCB】

文件控制块是用于保存文件属性信息的数据结构，至少包含以下信息：文件名，文件的结构（有结构的记录式文件or无格式的流式文件），文件的物理位置，存取控制信息，管理信息

【索引结点】

FCB的改进，把除了文件名之外的其他文件描述信息都放到索引结点（i结点），文件目录中的每个目录项仅由文件名和指向该文件i节点的指针构成；

存放在磁盘上的使用节点称为磁盘索引节点，每个文件都有唯一的磁盘索引节点，主要包括以下内容：文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度，文件链接计数，文件存取时间；

存放在内存中的索引节点称为内存索引节点，主要包括以下内容：索引节点编号，状态，访问计数，逻辑设备号，链接指针

【文件的目录结构】

单级目录结构，在整个文件系统中只建立一张目录表，每个文件占据其中的一个表目，易于实现，管理简单，但不允许文件重名，文件查找速度慢

二级目录结构，将文件目录分为主文件目录和用户文件目录，允许文件重名，可获得较高的查找速度，但缺乏灵活性，用户不能对自己的文件进行分类

多级目录结构，又称树形目录结构，，使用路径名来唯一标识文件，便于对文件分类，层次结构清晰，能更有效的进行文件的管理与保护，但查找文件时需按照路径名逐级访问中间节点，增加了磁盘访问次数，进而影响了查询速度

无环图目录结构，实现了文件的共享，但使得系统的管理变得复杂

（4）文件的访问类型及访问控制

【访问类型】

读，写，执行，添加，删除，列表清单

【访问控制】

对不同的用户访问同一个文件采取不同的访问类型，访问控制通常有四种方法：

访问控制矩阵，访问控制表和用户权限表都是采用某种数据结构来记录用户或用户组对每个文件的操作权限，而口令和密码是另一种访问控制方法，口令直接存储在系统内部，不够安全，密码方法的保密性强，节省存储空间，但编码和译码要花费一定时间

2、文件系统实现

（1）文件系统层次结构

【文件的层次结构】

用户接口

文件目录系统

存取控制验证

逻辑文件系统与文件信息缓冲区

物理文件系统

（2）目录实现

【目录的实现】

线性表

散列表

（3）文件实现

【外存分配方式】

静态分配：在文件建立时一次性分配所需的全部空间

动态分配：根据动态增长的文件长度进行分配

【连续分配】

最简单的磁盘空间分配策略，为文件分配连续的磁盘区域，保证了逻辑文件中的记录顺序与存储器中文件占用盘块顺序一致；优点是查找速度快（只需起始块号和文件大小），目录中关于文件物理存储位置的信息也比较简单，缺点是不方便文件拓展，容易产生碎片，需要定期进行存储空间的紧缩

【链接分配】

分为隐式链接和显式链接。

隐式链接（默认）：目录项中有指向索引顺序文件的第一块盘块和最后一块盘块的指针，此外每个盘块中都含有指向下一个盘块的指针；缺点是不支持随机访问，访问效率低下，并且由于其中任何一个盘块的指针错误都会导致后面的盘块的位置丢失；另外，指向下一个盘块的指针也需要耗费少量的存储空间；优点是方便文件拓展，不会有碎片问题，外存利用率高

显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，称为文件分配表(FAT)，一个磁盘仅设置一张FAT并且在开机时就将其读入内存且常驻内存；优点是既支持顺序访问，又支持随机访问，块号转换过程无需访问磁盘，因此访问速度较快；缺点是FAT需要占用一定的存储空间

【索引分配】

系统为每个文件分配一个索引块，索引块中存放索引表，索引表的每个表项对应分配给该文件的一个物理块；优点是支持随机访问，无外部碎片，便于文件拓展，缺点是访存次数增加导致文件的存取速度降低（可以通过提前将索引表调入内存来解决），索引表本身需占用一定的存储空间

【文件的存储空间管理】

空闲文件表空闲块链表位示图，保存在主存中

成组链接法(UNIX的文件存储空间管理方法)，适用于大型文件系统

3、磁盘组织与管理

（1）磁盘的结构

引导控制块

分区控制块

目录结构

文件控制块

（2）磁盘的调度算法

先来先服务(FCFS)

最短寻道时间优先(SSTF)

扫描算法（电梯调度算法）(SCAN)

循环扫描算法(C-SCAN)