面试经验5-4

介绍一下linux的内存管理

内存管理的目标：

1. 提升内存读写的速度（Cache）。

2. 保护OS，防止用户进程去读写OS的内存空间。

3. 包含用户进程：用户进程之间不能随意的存取对方的内存空间。

4. 操作正确：地址转换，内存的分配以及回收。

内存的分段和分片。

​ a. 碎片问题。碎片有两种：分页内部碎片（固定分区）与分段外部碎片（可变分区）。

​ b. 物理地址与逻辑地址的映射关系。让程序员不用管物理内存，只需要操作逻辑内存。

​ 为了解决这两个问题，有两种方案。

分段：把一个program分成data，code，stack这种。并且把他们叫segment，每一段的逻辑地址都从0开始。逻辑地址就是2byte的段号+14byte的段内偏移。

​ segment是离散的存放在内存中的：空间利用率提升了。坏处：额外的空间：段表，包括了段的起始地址+段的限长。

分页：按照物理内存，切成frame。逻辑地址：page。这样也可以实现离散的存放。额外的空间是页表：page->frrame。逻辑地址：页号+页内偏移。如何换成物理地址呢？把page号换成frame号就可以。

​ 页面的大小，页面大小\(2^n\)，逻辑地址长度m bits。页内位移占n bits，页号占用m-n bits。x86_64的linux pagesize是4096 Bytes。可以算出n是12（页内偏移占的比特数）。m是52个比特（理论上，实际上是48个bit）。

​ 页表：每一个进程都有一个页表。页表是用来将逻辑地址翻译为物理地址的。实际上这也是CPU调度器（dispathcer）在把进程安排到CPU上跑的时候才会使用，具体的用途是定义物理页表。内存的paging其实会增加context swtich的时间。页表是放在内存中的，也会占用内存的空间。为了解决页表的连续储存问题，现代内存管理器采用的方案是多级页表。x86_64采用的页表是4级页表，多级页表的作用就是让页表不要连续分布，并且有的级别页表可以不创建或者不放在内存中。

https://www.zhihu.com/question/63375062

​ 页表硬件：页表是存储在主存中，有一个page-table base register指向了页表。对于进程切换来说，只需要切换这个页表基寄存器就可以了。为了加速页表存取，使用了TLB来进行加速。TLB中有相应的逻辑地址，那就直接转换。

​ 基于页的保护和共享：基于分页的方案下，设置一些标志位。设置为valid-invalid，只读，读写，可执行等等。将多个program的相同部分，text，data等等放在同样一个物理块的frame里。

​ 虚拟内存的概念：虚拟内存是一种允许执行的进程不完全装入内存的技术。好处就是，逻辑内存可以比物理内存大，并且将物理内存抽象为了一个超大的，一致的存储。

​ 请求调页：进程的页不一定全部在内存中，查page table，其中的标志位显示这个page没在内存中那就要请求调页。如果是从未调用过的页不会被加载进内存。存在物理内存中的页叫内存主流（resident）。请求调页会产生一个segment fault（缺页中断），然后将数据从磁盘中调进内存。缺页中断对效率影响很大，所以决定哪些程序的页到物理的frame算法就很重要。算法有FIFO，Optimimal（无法达到），LSU，clock等。

​ 系统抖动（thrashing）：由于一直swap in，swap out那些必要的页。那就会一直调页，这就是进程开多了就会卡的原因。可以根据PFF动态调节进程分得的页框（frame）数量。

介绍一下链接器（Linker）做了什么？

​ 为什么要链接？linker需要做的是把多个文件捏成一个，具体的做法就是将elf相同的段合并在一起，避免内存的浪费（如果只是将elf首尾相接，由于每一个段都要进行内存空间进行，这是很浪费的）。这就需要对文件中的符号进行重新解析和重定位。

​ 链接做的事：1.空间和地址的分配。2.符号的解析和重定位。

​ 第一件事是对空间和地址进行分配。获取所有目标文件的段长度，合并，计算输出文件中各个段长度与位置。第二件事：使用第一步收集到的信息，读取输入文件中段的数据、重定位信息，进行符号解析和重定位。链接所用的地址是虚拟地址。64位linux虚拟的地址都是从0x400000开始分配的。

​ 前置知识：将函数和和变量称为符号。符号的类型：定义在本目标文件中的全局符号，外部符号是本目标文件中引用的全局符号。段名，该段的起始地址。局部符号是只在编译内部可见，其他目标文件不可见的符号。符号修饰。为了避免和库文件中的符号冲突，C加“_”。c++由于有类的多态，所以符号修饰更复杂。比如要有函数名，参数类型，类别名，名称空间（namespace）。

​ 番外：extern是为了解决c/c++符号解析的时候，符号修饰不同的问题。c++中有一个关键字来声明或者定义C符号extern “C”。c++编译器会在编译c++文件的时候定义一个宏来兼容c的头文件。

​ 强符号与弱符号：为了解决多个目标文件中有相同全局符号的定义。引入了强弱符号的定义：初始化了的全局变量和函数为强符号，未初始化的全局变量为弱符号。多个强符号报错，强符号与弱符号选强符号。多个弱符号选占用空间大的那一个。这个地方很容易出问题，因为不会报错，而且你不知道全局符号是哪一个。

​ 符号解析：linker逐个解析目标文件，并且维护三个集合。E维护可重定位目标文件，在链接完成的时候，这个集合的文件会被合起来形成可执行文件。U维护引用了但是未定义的文件，D用来存放输入文件已经定义的符号。每次解析一个文件，都会先判单是目标文件还是库文件。目标文件直接更新E和D。未定义的符号放到U。如果是.a文件则扫描库文件，找到U中的定义就加入库文件中的目标文件。U去掉一个未定义符号，D加入定义了U中符号的目标文件中定义的符号。注意libc.a会被隐式的加入这个过程。最后，如果U是非空就报错。

​ 重定位：汇编器遇到最终位置未知的目标引用，它就会生成一个重定位条目。告诉目标文件合成未可执行文件如何修改这个引用。存放在.relo.text中和.relo.data中。过程，对每一个重定位条目

\(refptr = s + r.offset\) refptr指向的是要被重定位的引用。

如果r.type是相对引用

\(refaddr=ADDR(s)+r.offset\)

\(*refptr=(unsigned)(ADDR(r.symbol) + *refptr - refaddr)\).

如果r.type是绝对引用

\(*refaddr=(unsigned)(ADDR(r.symbol)+*refptr)\)

注意*refptr常常被初始化为-4(32位系统，相对引用)。原因是：PC指向的是下一条指令的地址，我们想从当前位置直接跳到符号的地址，用PC值+偏移，其实是多加了一部分（PC指向的是当前指令的下一条），那我们把它拽回来。

​ 简单介绍一下动态链接：为了解决很多常用的代码每次都复制造成的空间浪费，还有动态库会更新的问题。所以就有了动态链接这种东西（其实动态库还是有一些不方便的，因为linux不同的发行版动态库的位置都不一样）。链接器只是拷贝了一些重定位与符号表的信息，代码和数据节其实并没有拷贝。

​ 编译器是如何实现对全局变量的PIC引用的呢？首先，代码段中任何指令与数据段中任何一个变量之间的距离都是以一个运行时常量。所以动态链接库中，编译器在数据段开始的地方创建了一个表叫global offset table。GOT包括每个被这个目标模块引用的全局数据目标的条目。编译器还未GOT中每个表目生成一个重定位记录。动态加载的时候，就是使用GOT中的每一个条目，使它包含正确的绝对地址。每个用到全局数据的目标模块都有自己的一个GOT。

​ ELF编译技术使用了一种叫延迟绑定的方法。使用GOT和PLT来实现。GOT是.data节的一部分，PLT是.text节中的一部分。具体的过程就是：当函数第一次被调用的时候，控制传递到PLT对应表目中的第一条指令，通过GOT相应表目执行一个间接跳转回到自己的第二条指令将符号的ID压入栈中。最后一条指令回到PLT[0]，从GOT[1]中将另一个标识信息压入栈，通过GOT[2]间接跳转到动态链接器中，动态链接器用两个栈顶层信息来确定函数位置，用这个覆盖GOT表项。下一次调用就可以指通过将控制传递给PLT，然后通过GOT的记录间接跳转就可以了。

https://blog.csdn.net/weixin_48953972/article/details/125729543

介绍一下函数加载器是怎么工作的。

Unix每一个程序都运行在一个进程上下文中，这个进程上下文都有自己的虚拟地址空间。当shell运行一个程序的时候，父shell进程生成一个进程上下文。它是父进程的一个复制品，子进程通过execve系统调用启动加载器。加载器删除子进程已经有的虚拟存储段，创建一个新的代码，数据，堆和堆栈。新的栈和堆段被初始化为0。通过将虚拟地址空间中的页映射到可执行文件的页大小的chunk。新的代码和数据段被初始化为可执行文件的内容。最后，加载器跳转到_start地址，调用main函数，除了一些头部信息，加载的过程中没有任何从磁盘到存储器的数据拷贝。CPU引用一个被映射的虚拟页才会进行拷贝。这个时候，操作系统利用页面调度机制自动将页面从磁盘传送到存储器。