本周末前往北京腾讯实习，开贴记录一下生活

一些往年题和资料，有的网上有，有的不知道有没有，反正我把自己知道的做了整理
操作系统往年题（6 套，现在考试有变化，但是考试明显有很多往年题的影子）： XJTU-COMP400627-OS/期末 at main · DANNHIROAKI/XJTU-COMP400627-OS (github.com)
计算机组成作业答案：https://pan.quark.cn/s/c2f5dec0b408
计算机组成往年题（2 套）： MISC-3-1-XJTU/计组实验/计组考试题 at master · RuqinF/MISC-3-1-XJTU (github.com)
形式语言与编译往年题、部分作业答案（2 套）：https://pan.quark.cn/s/e68b0830bd69

“去年有个同学是个什么竞赛队的主席，好像还挺厉害的，跑去实习了，回来复习一周考个 43”
场景：计试班，大三挂科 t 出计试😆

分享一些个人在学习过程中的笔记。

参考资料：

• https://speech.ee.ntu.edu.tw/~hylee/ml/2022-spring.php
• https://speech.ee.ntu.edu.tw/~hylee/ml/2023-spring.php
• https://github.com/mli/paper-reading
• 《动手学深度学习》

# 编译与链接 考虑用下面这条指令来构建 a.cpp 的可执行文件 ``` gcc a.c -o a ``` 这句话执行的时候做了四件事：预处理，编译，汇编，链接；这四个阶段分别对应了预处理器，编译器，汇编器，链接器四种工具。

预处理

1. 展开所有宏定义，条件宏定义
2. 将#include 包含的头文件插入到指定位置
3. 删除注释，添加文件名和行号（用于报错）

编译

编译过程可分为 6 步：词法分析，语法分析，语义分析，源代码优化，代码生成，目标代码优化
前 4 步属于编译器前端，后 2 步属于编译器后端，按照中间语言生成的前后来划分。
具体来说，词法分析将代码分割为 token，语法分析通过 token 产生抽象语法树，语义分析对抽象语法树进一步处理，检查程序是否符合语义规则，源代码优化将整个抽象语法树转换为中间代码。

汇编

汇编器将 a.s 翻译成机器语言指令，并将这些指令打包为可重定位目标文件（也就是.o 文件）。

链接

可重定位目标文件

其格式和内容如下：

----------------------
|     ELF Head       |    ELF 头，描述目标文件的基本信息
----------------------
|      .text         |    机器代码
----------------------
|      .rodata       |    只读数据
----------------------
|      .data         |    已初始化的全局变量和静态变量
----------------------
|       .bss         |    未初始化的全局变量和静态变量（实际上不占用空间，只需要运行时赋初值）
----------------------
|     .symtab        |    符号表，存储定义和引用的所有函数和全局变量
----------------------
|     .rel.text      |    代码重定位表，调用外部函数的指令需要重定位
----------------------
|     .rel.data      |    数据重定位表，引用外部全局变量和外部函数的全局变量需要重定位
----------------------
|      .debug        |
----------------------
|       .line        |
----------------------
|      .strtab       |
----------------------
|section header table|
----------------------

静态链接

• 链接器获取各个目标文件的符号表，并将之合并为一个全局符号表。
• 链接器获取各个目标文件的各个段的长度，计算出每个合并后段的长度与位置。
• 每个段的起始位置都默认是 0，加载时通过段起始地址 + 段内偏移量访问字段。

1. 符号解析
   每个可重定位目标文件中都有三类符号：
   a. 被当前模块定义且不能被其他模块引用的符号（static 函数和全局变量）
   b. 被当前模块定义且能被其他模块引用的符号（不带 static 的函数和全局变量）
   c. 被当前模块引用但在其他模块内定义的符号（其他模块定义的不带 static 的函数和全局变量）
   将每一个符号引用指向其对应的符号定义，就是符号解析，符号解析的规则如下：
   强符号是给定初值且定义的符号，弱符号是声明但未定义的符号。
   a. 只能有一个强符号。
   b. 一个强符号和多个弱符号，选择强符号为符号定义。
   c. 多个若符号，没有强符号，选择任意一个弱符号为符号定义。
2. 重定位
   上述生成的文件中，各个段的起始位置都默认是 0，链接器需要把符号定义和内存对应，这一对应的过程就是重定位。
   a. 链接器首先把各个段合并，生成聚合段作为可执行目标文件的段
   b. 计算出每个段的长度和起始位置
   c. 根据每个段的起始位置，给每个段内的代码/符号引用赋以运行时地址（也即段内偏移量）
   3.静态链接的优缺点

静态链接优缺点

缺点：浪费空间，因为每个可执行程序中对所有需要的目标文件都要有一份副本；更新困难，每次修改库函数代码，就需要重新编译链接。
优点：在可执行程序中具备了执行程序需要的任何东西，执行时运行速度快。

动态链接

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在运行时完成链接。

假设现在有两个程序 program1.o 和 program2.o，这两者共用同一个库 lib.o，假设首先运行程序 program1，系统首先加载 program1.o，当系统发现 program1.o 中用到了 lib.o，即 program1.o 依赖于 lib.o，那么系统接着加载 lib.o，如果 program1.o 和 lib.o 还依赖于其他目标文件，则依次全部加载到内存中。当 program2 运行时，同样的加载 program2.o，然后发现 program2.o 依赖于 lib.o，但是此时 lib.o 已经存在于内存中，这个时候就不再进行重新加载，而是将内存中已经存在的 lib.o 映射到 program2 的虚拟地址空间中，从而进行链接（这个链接过程和静态链接类似）形成可执行程序。

动态链接的加载时重定位

1. 重定位.so 的文本和数据到某个内存段。
2. 重定位可执行文件中所有对.so 文件的引用。

这里涉及到一个有趣的细节，在 ics 课编码 linker 的时候，引用动态链接库中的符号会在第一次引用时多次跳转指针找到对应符号的内存段，并记录下来具体的位置，而在第二次引用时，则使用第一次记录下来的具体位置直接访问。

动态链接优缺点

优点：即使需要每个程序都依赖同一个库，也不会像静态链接那样在内存中存在多个副本，而是这多个程序在执行时共享同一份副本；更新方便，只需要替换原来的库文件，而无需将所有的程序重新链接。
缺点：链接推迟到了运行时，损失性能。

加载

通过加载器将可执行文件的代码和数据从磁盘中复制到内存中，然后 PC 跳转到程序的第一条指令或入口点。

秋招了，写点计算机八股笔记，方便自己背诵和复习
欢迎门友补充、提问，或者在楼中写下自己认为的重要八股知识