计算机系统原理2022年总结（八股文篇）

地址译码器的输入是什么？输出是什么？可寻址范围多少？ #

输入是地址，输出是地址驱动信号（只有一根地址驱动线被选中）。

直接存取存储器和相联存储器？ #

• 直接存取存储器根据地址就能定位到相应位置。
• 相联存储器的意思是其存放的位置和其内容有联系。根据其存储的内容即可定位到物理地址。（例如TLB）

常见的存储结构是用什么类型的存储器？ #

• BIOS采用闪存ROM（Flash ROM）
• Cache是SRAM
• 主存是DRAM

局部性产生的原因 #

• 程序代码、数据是连续存放的，且遵循一定的顺序（栈帧显然是一块连续空间）

时间、空间局部性例子 #

程序1：

int sumarrayrows(int a[M][N])
 {
    int i, j, sum=0;
        for  (i=0; i<M, i++)
	for (j=0; j<N, j++)  sum+=a[i][j];
        return sum;
 }

程序2：

 int sumarraycols(int a[M][N])
 {
     int i, j, sum=0;
          for  (j=0; j<N, j++)
	  for (i=0; i<M, i++)  sum+=a[i][j];
           return sum;
 }

**程序1比程序2快21.5倍。**因为二维数组访问的方法，前者的空间局部性好。

组相联映射向其他两种映射的转换 #

• 如果组群大小=1，那么所有块都可以看作是自己组群里的第一个块，且cache也只能分出一个组来，此时所有快都可以映射到cache的任意位置，所以是全相联映射。
• 如果cache的组大小=1，那么这是一个直接映射。因为内存组群中的所有块都只能映射到固定位置。

Cache的miss损失（miss penalty） #

• 即访问主存块所需要的时间。

关联度 #

• 即一个内存块可能映射到的Cache块的数量。
  • 直接映射：1
  • 全相联映射：Cache块数
  • N路组向量映射：路数
• 关联度越高，访存发生Cache miss的概率越低。

颠簸 #

• 如果使用LIFO或LRU替换算法，如果cache最近的块大小总是小于最近会访问的块的总数，就会出现颠簸。
• 即OS里面页面置换发生的抖动（因为虚存也是采用了Cache的思想，可以把内存看成是一个大Cache。）

Cache数据一致性问题 #

• 若多个CPU核心都带着各自的L1、L2 Cache对某段程序进行并行操作，那么其中一个核心修改了自己Cache里面对于某段内存空间的映射，而如果这几个线程都共享这一个内存空间，就会发生数据不一致的问题。
  • 因为在这个瞬间，只有修改Cache的那个核心带的Cache中是最新的数据。其他核心和原有内存单元中的数据都过时了。
• 若多个IO设备同时访存，CPU却不加以限制，就会导致内存被IO设备修改了，但是Cache 没跟上。或者CPU修改了Cache但是没有及时写回，IO设备就读出过时数据。

Cache写策略 #

• 如果发生写不命中，那好说；但是如果命中了Cache，那就写入Cache，从而需要对数据一致性进行保证。

• 因为这样就比较复杂，所以指令Cache比数据Cache更好设计。因为指令往往不需要写回去。

• 如果

  写命中
  

  
    - 写直达法
    	- 每次写Cache，也同时写入内存（效率大大降低，导致就算写命中也没什么效率提升）
    	- 改进：增加写缓冲。然后并不需要写入内存，而是写入缓冲。
    - 写回法（添加脏位）
    	- 添加一个脏位。如果需要被换出，看看脏位如果为1，就写入；否则丢弃。
  
  

• 如果

  写不命中
  

  
    - 写分配法
    	- 写，顺便把所在内存块换入Cache。（试图进一步利用局部性）
    - 非写分配法
    	- 只是直接往内存写，不考虑换入的问题。
  
  

Cache读策略 #

• 如果没命中，就从内存取。否则直接读。
• 可见，读策略相对于写策略及其简单。

分页管理和Cache的区别与联系 #

• 分页实际上是一个

  使用全相联映射

  的大Cache。

  • 因为全相联映射的命中率是三种映射中最高的。分页管理最重要的就是命中率，因为如果发生缺页中断，调入一页需要数百万个时钟周期，这相比其他操作都太慢了。

• 采用写回法的写策略，同样是为了减少磁盘IO。

• 缺页中断可以通过软件解决，因为它需要数百万个时钟周期，非常慢，所以硬件无法实现。

空洞页面 #

• 如果**虚拟地址空间中（即页表中）**有的项目没有任何信息（即没有确定页面编号和页面）

为什么使用链接 #

• 模块化
  • 因为可以把各种功能分配到不同的模块中单独实现，最后通过链接的方式合成
  • 可创建共享库，实现代码重用
• 效率高
  • 多核心下，可以并行编译不同模块
  • 可以只选择性链接执行所需要的代码

链接的本质和过程 #

把各可重定位目标文件中的节、相同的符号进行合并，同时完成静态重定位。

• 符号解析
  • 合并符号
• 重定位
  • 修改程序代码所在地址
  • 根据符号定义的地址去修改符号引用的地址
• 合并成段
  • 把访问属性相同的节合并成段

链接然后装入 #

• 把.init，.text（代码）,.rodata（只读数据）装入到只读区，也就是常说的代码段；（其中，.init是链接后才出现的。在连接前不存在这个节。）
• 把.data（全局变量），.bss(未初始化全局变量)装入到可读写区，也就是常说的数据段。
• 其他的节在运行时，都不需要装入到内存中。
• 于是，可执行文件中就有这两个段了。
• 装入时，把这两个段原封不动装入内存中。

栈段、堆段、共享库区域 #

• 栈和堆是处于系统空间的特定位置，他们两个对着头进行生长。在其中间的空闲区域，还有一部分是给了共享库区域。
• 因为位置可预测，所以才会出现缓冲区溢出攻击这种方式。

共享库 #

• 在被装入时或运行时动态链接
• 在Linux下称为共享库（.so,shared .o文件），在Windows下称为dll。

目标文件格式 #

• COM格式
  • DOS下使用，只具备固定装入的能力。（即只能通过覆盖的方式切换程序，见OS）
• COFF格式
  • 严格地利用数据结构定义了其中的代码、数据等节，早期System V使用
• PE格式
  • COFF升级版，在WIndows下使用
• ELF格式
  • COFF升级版，在Linux下使用

分节（以下面的程序为例） #

int x=100; //.data
int y; //.bss
void prn(int n)//.text
{
   printf(“%d\n”,n);//.text
}

void main()//.text
{
    static int a=1;//.data
    static int b;//.bss
    int i=200,j;//.text
    prn(x+a+i);//.text
} 

链接后，ELF文件发生的变化 #

• e_entry字段指出了程序的第一条指令的地址（原来是0）
• 地址都被重定位到了正确的地址（注意都是虚拟地址）
• 多了个init节
• 少了rel节（因为该节负责重定位）

三种符号——全局符号，局部符号，外部符号 #

//swap.c
extern int buf[]; //外部符号
 
int *bufp0 = &buf[0]; //全局符号
static int *bufp1; //局部符号

void swap() //全局符号
{
  int temp;//非符号

  bufp1 = &buf[1];
  temp = *bufp0;
  *bufp0 = *bufp1;
  *bufp1 = temp;
}
//main.c
int buf[2] = {1, 2};
extern void swap();

int main() 
{
  swap();
  return 0;
} 

• 全局符号：在一个模块中被定义，并且允许其他模块能够访问的，例如模块中的全局变量

• 局部符号：上述符号，但是加了static。另外还包括函数中的static变量。

• 外部符号：在一个模块中引用其他模块中的

  全局符号

  。即加了extern的那些。

  • 例如，上述buf在main中属于全局符号，但是在swap中属于外部符号。链接的符号链接作用就是把他们联系起来。

注意，符号可以是变量，可以是函数，可以是文件，可以是节。

注意，符号可不仅仅包括变量哦。

符号表.symtab #

• 其中给出了每个符号的其名称（标识符）、所在节、相对所在节的偏移量、大小、对应的类型（变量，函数，文件，节）、对应的符号类型（全局、局部、外部）。

强符号和弱符号 #

• 已初始化的全局变量是强符号，未初始化的是弱符号。
• 如果一个强符号被在多个文件中定义，会出现已定义错误。
• 但是如果只在其中一个文件中对该符号进行强定义，而在其他文件中都是弱定义，就不会报错，但该符号被编译为强符号及其初始值和位置，而弱符号被忽略，且地址就是强符号的。
• 如果没有强定义，且多个文件出现了对于该符号的弱定义，则任选一个为准，且地址就是被选中的那个弱符号的。
• 为什么要把上面地址的问题进行加粗？考虑如下问题：

//main.c
1  int d=100;
2  int x=200;
3  int main() 
4  {  
5    p1();
6    printf (“d=%d, x=%d\n”, d, x );
7    return 0;
8  }

//p1.c
1  double d;
2 
3  void p1() 
4  {
5    d=1.0;
6  }

则输出是：

d=0，x=1 072 693 248

• 因为弱符号使用了强符号的地址作为自己的地址（因为链接是把相同的符号连接起来，所以它只是这一个符号而已，所以地址当然是一样的），而且符号对于数据类型的关注粒度只能到“他是函数名，还是数据名”的程度，并不能对具体数据类型给出区分（不会进行类型检查！），**所以这个时候d就变成了一个类似于**共用体的存在！！！
• 因为double是8字节，所以把后面的x也给占用了。

因此，如何优雅而安全地使用全局变量？应当遵循以下原则。 #

• 尽量加static
  • 防止被外界引用而产生意想不到的后果
• 一定要赋值
  • 保证是强定义的，避免出现上面例子里的问题
• 外部全局变量应当使用extern
  • 保证是强定义的，避免出现上面例子里的问题

由于全局变量引发的问题一般是几乎不可能debug出来的。

静态库 #

• .a文件，意思是.archive。
• 由很多.o文件打包而成。即：你可以把很多.o文件连接成可执行文件，也可以打包成静态库.a文件。
• 支持增量更新：如果.a文件中的一些符号发生改变，则下次打包只需要更新改变的部分。
• 链接过程
  • 按命令行输入的从左到右的顺序遍历所有的.o，把当前遍历到的未能解析的符号记录下来，并利用当前遍历到的符号去试图解析之前所记下来的符号。
  • 于是，就能保证：只有库中的那些需要用到的符号才被链接；且因为函数名称等也都是符号，所以能节约大量空间。
  • 但是，需要注意，命令行的输入顺序是有讲究的。从左到右，应该构成一个依赖的拓扑序列。
    • 例如，你的MC依赖libsoil，但是却把MC放在libsoil之后，那么扫描libsoil时，就把那些可以用来解析MC中调用libsoil的那些符号给扔掉了。扫描到了MC才把他们加入未解析符号表中，但是之后不会再有库可以解析他们了，因为libsoil已经被遍历过了。

动态链接共享库 #

• 在Linux下，称为动态共享对象（Dynamic Shared Object，.so）
• 好处
  • 更新方便：不至于库文件已更新，使用它的所有软件都得发起一次更新，这个规模可以非常宏大，因为存在迭代性。
  • 节约内存：因为运行时，so被保存在了系统堆空间和栈空间之间，所有进程都共享它，所以即便是很多进程都需要用到它，也只需保存一份so在内存中（这就要求它必须是可重入的）。
    • 设想，因为c标准库就是一个共享库，如果他是静态库，那么执行多少个程序就有多少份c库的副本在内存中跑，这非常没有意义。所以动态库就非常重要。
    • 所谓“配置某种语言的执行环境”，就是把动态库配置好。
  • 节约磁盘空间：编译生成的文件小了。
• 分为两种动态链接方式
  • 装入时动态链接
    • 编译后，只是部分链接的可执行文件，但是它可执行。
    • so文件和部分链接可执行文件中都有.interp节，可执行文件中的该节指出了需要的动态共享库的路径。在装入时，也把该共享库装入，就可以在内存中完成最后的链接，在内存中执行最终链接的可执行对象。
    • 即：外存中——部分链接，但是可执行的文件；内存中——完全连接的可执行对象。
  • 运行时动态链接
    • 通过系统调用的方式，在运行过程中请求动态地加载库文件。
    • 然后，通过指针的方式访问库的符号。

PIC代码（位置无关代码，Position Independent Code） #

• 动态库里面的代码都是位置无关代码。
• 他能保证其中任意一段代码改变了其原有位置，都能正常执行。甚至是从中删去一些无关的部分导致长度改变，仍能正常执行。
• 特点：代码可加载到任意内存地址即可执行。
• 难点：保证模块外对其的正常访问。

异常控制流（叫中断控制流更好理解） #

• CPU正常顺序执行指令，叫做控制流。如果此时发生中断，打断了正常控制流，转而执行服务程序，这其中的控制称为中断控制流。
• 以下方式会导致中断控制流：
  • 外中断（由硬件导致）
  • 内中断（由OS、硬件导致）
  • 进程调度（OS导致）
  • 发信号（OS导致）

“异常”的分类 #

• 故障（fault）
  • 非自愿
• 自陷（trap）
  • 自愿
• 终止（abort）
  • 出现严重错误，必须结束执行

MIPS特有的纯软件中断控制流 #

• 出现异常时，把异常信息放到一个寄存器里（即哪个cause寄存器），OS查询该寄存器从而做出反应。
• 而在x86中，采用的是中断隐指令。

带缓冲的IO #

• 输出缓冲略
• 输入缓冲：每次都往缓冲区里面读，读满了就不读了。
• stderr是无缓冲的，所以直接输出。
• stdout和stderr的比较：前者带有缓冲区，所以1024字节后才会输出，这样能减少系统调用的次数，提升性能；**但是后者能够**更及时地输出。

南桥和北桥 #

• 北桥芯片负责连接控制CPU前端总线（所谓CPU前端总线就是CPU接出来的，负责与其他设备进行交互的总线）、存储器总线、显卡总线、南桥芯片。
  • 可见，北桥芯片负责与电脑的至关重要的快速部件进行连接。并且把与其他慢速设备的通信交给了南桥芯片。
• 南桥芯片负责和其他慢速设备进行连接，包括PCIE总线（主板扩展槽，例如固态硬盘、磁盘SATA）、USB、网卡等。
  • 然后，把这些数据传递给北桥芯片，从而才能到达CPU等核心设备。因此，南桥和北桥是互联的。

IO体系结构（如何连接一个鼠标？） #

• CPU-前端总线-北桥-南桥-设备控制器-鼠标。
• 可见，设备控制器是连接在南桥上的，例如USB。

外设控制器的一般实现结构 #

• 数据缓冲寄存器
• 状态、控制寄存器
• 设备控制逻辑