《计算机系统基础》30’

一、处理器的时序电路

1、CPU中的时序电路

答：

CPU中的时序电路：通过RS触发器控制CPU的时序。

2、单周期处理器的设计

答：

CPU在处理指令时，一般需要经过以下几个步骤：

1）取指令（IF）

根据程序计数器PC中的指令地址，从存储器中取出一条指令，同时，根据指令字长度自动递增产生下一条指令所需要的指令地址，但遇到“地址转移”指令时，则控制器把“转移地址”送入PC，当然得到的“地址”需要做些变换才送入PC。

2）指令译码（ID）

对取指令操作中得到的指令进行分析并译码，确定这条指令需要完成的操作，从而产生相应的操作控制信号，用于驱动执行状态中的各种操作。

3）指令执行（EXE）

根据指令译码得到的操作控制信号，具体执行指令动作，然后转移到结果写回状态。

4）存储器访问（MEM）

所有需要访问存储器的操作都将在这个步骤中执行，该步骤给出的存储器的数据地址，把数据写入到存储器中数据地址所指定的存储单元或者从存储器中得到数据地址单元中的数据。

5）结果写回（WB）

指令执行的结果或者访问存储器中得到的数据写回相应的目的寄存器中。

单周期CPU，是在一个时钟周期内完成这五个阶段的处理。

3、流水线处理器的基本原理

答：

流水线（Pipeline）技术是指程序在执行时候多条指令重叠进行操作的一种准并行处理实现技术。通俗的讲将一个时序过程，分解成若干个子过程，每个过程都能有效的与其他子过程同时执行。旨在提高处理器处理效率，争取在一个时钟周期中完成一条指令。

将处理组织成阶段：取指、译码、执行、访存、写回。通常一条指令包含很多操作，可以将它们组织成一定的阶段序列，从而便于放入一个通用框架来进行流水线处理。

参考：

流水线处理器的基本原理：https://blog.csdn.net/pankul/article/details/8769979

4、Data Hazard的处理

答：

流水线给处理器带来了效率，当然也有问题。这些问题称之为流水线冒险（HaZard）。

1)结构冒险

由于处理器资源冲突，而无法实现某些指令或阶段的组合实现，就称之为处理器有结构冒险。

比如，早起的处理器中，程序和数据是存储在一起的，那么容易出现下面的情况：在第一个Cycle中，IF和MEM同时访问存储器导致有一个操作要等待，此时hazard就出现了。现在的处理器已经解决了该问题：指令存储在L1P cache中，数据存储在L1D cache中，单独访问，不会影响相互操作。

2）数据冒险

如果流水线中原来有先后顺序的指令同一时刻处理时，可能会导致出现访问了错误的数据的情况。

在汇编语句中，add R1,R2,R3将寄存器R2和R3的和赋予R1，改变R1的值；而紧接着下面的语句：add R4,R1,R5则会使用R1的值，可是R1必须在一条语句中的第5个cycle才能更新到寄存器中，语句二是在第4个cycle就要访问R1，也就是说第二条指令此时在使用错误的R1的值，这是数据hazard出现了。

解决方案：在两条指令中添加一条空指令：nop。但是会影响处理器的指令的执行效率。在现代处理器技术中，已经用forwarding的方式解决了。如下图（没图。。先放着吧？？？）如果处理器在检测到当前的源操作数正好在流水线的EX或者MEM阶段，直接将EX和MEM寄存器的值传递给ALU的输入，而不是再从寄存器堆中获取数据了。因此此时寄存器堆中的数据可能是没有被及时更新的。

3）控制冒险

**在流水线中的执行指令时，由于并行处理的关系，后面很多指令其实都在流水线中开始处理了，包括预取值和译码。那么，如果此时程序中出现一条跳转语句会怎么办呢？**因为程序已经跑到其他地址处执行，流水线中之前已经做好的预取值和译码动作都不能使用了。这些会被处理器的专有部件flush掉，重新开始新的流水线。此时我们可以称之为出现了控制冒险。这种情况对于程序和效率来水是存在很大的损失的。

解决方案：也就是在jump指令后面（不会被真正使用，但是会进入流水线）添加nop。在MIPS程序中，经常在jump指令后面添加nop语句。

在x86架构中，是通过硬件来实现flush，将无效的流水线排空，以保证正确运行流水线。这里会涉及到分支预测技术的使用。

在其他一些处理器中，用软件的方式来处理，添加nop。同时在编译器中通过乱序的思想用有效指令代替nop。这样也可以避免跳转带来的性能损失。

5、流水线设计中的其他问题

答：

1）每个阶段所用的硬件实际并不是互相独立的；增加的寄存器也会导致延迟增大；每阶段的周期划分也很难做到一致。

2）理想的流水线系统，每个阶段的时间都是相等的。实际上，各个阶段的时间是不等的。运行时钟是由最慢的阶段决定的。

3）另外流水线过深，寄存器的增加会造成延迟增大。当延迟增大到时钟周期的一定比例后，也会成为流水线吞吐量的一个制约因素。

二、优化程序性能

1、优化程序性能

答：

1）程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。这些优化不依赖于目标机器的任何具体属性。

2）程序优化的第二步，利用处理器提供的指令级并行能力，同时执行多条指令。

3）最后对大型程序的优化，使用代码剖析程序，代码剖析程序是测量程序各个部分性能的工具，这种分析能够帮助找到代码中低效率的地方，并且确定程序中应该着重优化的部分。

4）Amdahl定律，它量化了对系统某个部分进行优化所带来的整体效果。

2、优化编译器的能力和局限性以及表示程序性能

答：csapp chapter5 p325

优化编译器的能力：

现代编译器运用复杂精密的算法来去定一个程序中计算的是什么值，以及它们是被如何使用的。然后它们会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。

优化编译器的局限性：

编译器必须很小心地对程序只是用安全的优化，也就是对于程序可能遇到的所有可能的情况，在C语言标准提供的保证之下，优化后得到的程序和未优化的版本有一样的行为，限制编译器只进行安全的优化，消除了一些造成不希望的运行时行为的可能原因，但是这也意味着程序员必须花费更大的力气写出程序使编译器能够将之转换成有效机器代码，两个指针可能指向同一个存储器位置的情况称为存储器别名使用（memory aliasing）。这造成了一个主要的妨碍优化的因素，这也是可能严重限制编译器产生优化代码机会的程序的一个方面：如果编译器不能确定两个指针是否执行同一个位置，就必须假设什么情况都有可能，限制了可能的优化策略。

表示程序性能：

引入度量标准每元素的周期数（Cycles Per Element CPE），作为一种表示程序性能并指导我们改进代码的方法是用最小二乘拟合，得到一条形如y=mx+b的线，线性因子的系数m叫做每个元素的周期数CPE的有效数

3、特定体系结果或应用特性的性能优化

答：

1）简单地使用命令行选项，如‘-O1’就会进行一些基本的优化

2）消除循环的低效率：称作"代码移动"，这类优化包括识别要执行多次（例如在循环里）但是计算结果不会改变的计算，因而将计算移动到代码前面不会比多次求值的部分

3）减少过程调用：修改代码减少函数的调用，不过会危害一些程序的模块性

4）循环展开：通过增加每次迭代计算的元素的数量，减少循环的迭代次数。从而来个方面改程序的性能，首先它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。其次，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量

5）提高并行性：多个累计变量；重新结合变换

4、限制因素

1）寄存器溢出

循环并行性的好处收到描述计算的汇编代码的能力限制。特别地，IA32指令集只有很少量的寄存器来存放积累的值（IA32只有4个，x86-64可以12个）。如果我们的并行度p超过了可用的寄存器数量，那么编译器会诉诸溢出（spilling），将某些临时值存放到栈中。一旦出现这种情况，性能会急剧下降。

2）分支预测和预测错误触发

当分支预测逻辑不能正确预测一个分支是否要跳转的时候，条件分支可能会招致严重的预测错误处罚。

3）对于这个问题没有简单的答案，有一些通用原则

（1）不要过分关系可预测分支

（2）书写适合用条件传送实现的代码

5、确认和消除性能瓶颈

答：

处理大程序时连指导该优化什么地方都很困难

1）程序剖析

程序剖析包括运行程序的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间，这对于确认需要集中注意力优化的部分很有用，剖析一个有力指出在于可以在现实的基准数据上运行实际程序的同时，进行剖析（Unix系统提供了一个剖析程序GPROF）。通常，假设在有代表性的数据上运行程序，剖析能帮助我们对典型的情况进行优化，但是我们还应该确保对所有可能的情况，程序都有相当的性能。这主要包括避免得到糟糕的渐进性能的算法（例如插入算法）和坏的编程实例。

2）Amdahl定律(阿姆达尔定律)

其主要思想是当我们加快系统一部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少。

阿姆达尔曾致力于并行处理系统的研究。对于固定负载情况下描述并行处理效果的加速比s，阿姆达尔经过深入研究给出了如下公式：
S=1/(1-a+a/n)
其中，a为并行计算部分所占比例，n为并行处理结点个数。这样，当1-a=0时，(即没有串行，只有并行)最大加速比s=n；当a=0时（即只有串行，没有并行），最小加速比s=1；当n→∞时，极限加速比s→ 1/（1-a），这也就是加速比的上限。例如，若串行代码占整个代码的25%，则并行处理的总体性能不可能超过4。这一公式已被学术界所接受，并被称做“阿姆达尔定律”，也称为“安达尔定理”(Amdahl law)。

三、存储器结构及虚拟存储器

1、局部性

答：

一个编写良好的计算机程序通常具有良好的局部性。

引用临近于其他最近引用的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理。

局部性两种形式：

时间局部性：被引用过一次的内存位置很有可能在不远的将来再被多次引用（通常在循环里）。

空间局部性：一个内存位置被引用了一次，那么将来他附近的位置也会被引用。

局部性和性能的关系

1）有良好局部性的程序比局部性差的程序运行得更快。

2）局部性原理允许计算机设计者通过引入称为高速缓存存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。

3）重复引用相同变量的程序有良好的时间局部性

4）对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。

5）具有步长为I的引用模式的程序具有很好的空间局部性。

6）在内存中以大步长跳来跳去的程序空间局部性会很差。

7）对于取指令来说，循环有好的时间和空间局部性。

8）循环体越小，循环迭代次数越多，局部性越好。

2、存储器层次结构

答：

现在随着处理器和存储器在性能发展上的差异越来越大，存储器在容量尤其是访问延迟方面的性能增长越来越跟不上处理器性能发展的需要。为了缩小存储器和处理器两者之间在性能方面的差距，通常在计算机内部采用层次化的存储器体系结构。

可以看出，速度越快则容量越小、越靠近CPU。CPU可以直接访问内部存储器，而外部存储器的信息则要先取主存，然后才能被CPU访问。CPU执行指令时，需要的操作数大部分都来自寄存器；当需要从（向）存储器中取（存）数据时，先访问cache,如果不在cache中，则访问主存，如果不在主存中，则访问硬盘，此时，操作数从硬盘中读出送到主存，然后从主存送到cache，数据使用时一般只在相邻两层之间复制传送，而且总是从慢速存储器复制到快速存储器。传送的单位事一个定长块，因此需要确定定长块的大小，并在相邻两层间建立块之间的映射关系。

3、计算机高速缓存器原理

答：

加快CPU访问速度的主要方式之一是在CPU和主存之间增加高速缓冲存储器（简称高速缓存或者cache）。

cache是一种小容量高速缓冲存储器，由快速的SRAM组成，直接制作在CPU芯片里，速度较快，几乎与CPU处于同一个量级。

在CPU和主存之间设置cache，总师把主存中被频繁访问的活跃程序块和数据块复制到cache中。由于程序访问的局部性，大多数情况下，CPU能直接从cache中取得指令和数据，而不必访问慢速的主存。

为便于cache和主存间交换信息，cache和主存空间都被划分为相等的区域。

例如，将主存按照每512字节划分成一个区域，同时把cache也划分成同样大小的区域，这样主存中的信息就可以按照512字节为单位送到cache中。

我们把主存中的区域称为块，也称为主存块，它是cache和主存之间的信息交换单位；cache中存放一个主存块的区域称为行或槽，也称为cache行。

4、高速缓存对性能的影响

答：

影响cache性能的因素决定系统访问性能的重要因素之一是cache命中率，它与许多因素有关。

1）命中率与关联度有关

关联度越高，命中率越高。关联度反映一个主存块对应的cache行的个数，显然，直接映射的关联度为1；2路组相联映射的关联度为2,4路组相联映射的关联度为4，全相联映射的关联度为cache行数。

2）命中率与cache容量有关

cache容量越大，命中率就越高。

3)命中率与主存块的大小有关

采用大的交换单位能很好地利用空间局部性，但是较大的主存块需要花费较多的时间来存取，因此，缺失损失会变大。由此可见，主存块的大小必须适中，不能太大，也不能大小。

此外，设计cache时还要考虑一下因素：

采用单级还是多级cache、数据cache和指令cache是分开还是合在一起、主存-总线-cache–CPI之间采用什么架构等甚至主存DRAM芯片的内部结构、存储器总线的总线事务类型等，也都与cache设计有关，都会影响系统总体性能。

下面对这些问题进行简单分析说明：

目前cache基本上都在CPU芯片内，且使用L1和L2cache，甚至L3cache,CPU的访问顺序为L1cache、L2cache和L3cache。

通常L1cache采用分离cache，即数据cache和指令cache分开设置，分别存放数据和指令。指令cache有时称为代码cache(code cache)。L2cache和L3cache为联合cache，即数据和指令放在一个cache中。

由于多级cache中各级cache所处的位置中，使得对它们的设计目标有所不同。例如假定是两级cache。那么，对于L1cache，通常更关注速度而不要求有很高的命中率，因为，即使不命中，还可以到L2cache，L2cache的速度比主存速度快的多；而对于L2cache，则要求尽量提高其命中率，因为若不命中，则必须到慢速的主存中访问，其缺失损失会很大而影响总体性能。

5、地址空间

答：

每个高级语言源程序经编译、汇编、链接等处理生成可执行的二进制目标代码时，都被映射到同样的虚拟地址空间，因此，所有进程的虚拟地址空间是一致的，这简化了链接器的设计和实现，也简化了程序的加载过程。

虚拟存储机制为程序提供了一个极大的虚拟地址空间（也称为逻辑地址空间），它是主存和磁盘存储器的抽象。虚存机制带来了一个假象，使得每个进程都好像都独占使用主存，并且主存空间极大。

这有三个好处：

1）每个进程具有一致的虚拟地址空间，从而可以简化存储管理

2）它把主存看成是磁盘存储器的一个缓存，在主存中仅保存当前活动的程序段和数据区，并根据需要在磁盘和主存之间进行信息交换，使有限的主存空间得到了有效利用

3）每个进程的虚拟地址空间是私有的，因此，可以保护各自进程不被其他进程破坏。

6、虚拟存储器

答：

一个系统中的进程是与其他进程共享CPU和主存资源的，然而，共享主存会形成一些特殊的情况，如果太多的进程需要太多的存储器，那么他们中的一些就根本无法运行。当一个程序没有空间可用的时候，那就是他运气不好。存储器还容易被迫害，如果一个进程不小心写了另外一个进程使用的存储器，它就可能失去原先的逻辑。为了更有效的管理存储器，现在系统引入了一种对主存的抽象概念，叫做虚拟存储器。

目前，在服务器、台式机和笔记本等各类通用计算机系统中都采用虚拟存储技术。在采用虚拟存储技术的计算机中，指令执行时，通过存储器管理部件（Memory Management Unit,简称MMU）将指令中的逻辑地址（也称虚拟地址或虚地址，简写为VA）转化为主存的物理地址（也称主存地址或实地址，简写为PA）。在地址转换过程中由硬件检查是否发生了访问信息不在主存或地址越界或访问越权，则由操作系统进行相应的异常处理。由此可以看出，虚拟存储技术既解决了编程空间受限的问题，又解决了多道程序共享主存带来的安全问题。

下图是具有虚拟存储机制的CPU与主存的连接示意图，从图中可知，CPU执行指令时所给出的是指令或操作数的虚拟地址，需要通过MMU将虚拟地址转换为主存的物理地址才能访问主存，MMU包含在CPU芯片中。图中显示MMU将一个虚拟地址转换为物理地址4，从而将第4、5、6、7这4个单元的数据组成4字节数据送到CPU。下图仅是一个简单的示意图，其中没有考虑cache等情况。

7、虚拟内存的管理

答：

1）请求分页存储管理

每次访问仅将当前需要的页面调入主存，而进程中其他不活跃的页面放在磁盘上。当访问某个信息所在页不在主存时发生缺页异常，此时，硬件将调出OS内核中的缺页处理程序，将缺失页面从磁盘调入主存。

与主存块大小相比，虚拟页的大小要大得多。因为DRAM比SRAM大约慢10~100倍，而磁盘比DRAM大约慢100000多倍，所以进行缺页处理所花的代价要比cache缺失大得多。

而且，根据磁盘的特性，磁盘扇区定位所用的时间要比磁盘读写一个数据的时间长大约100000倍，也即对扇区第一个数据的读写比随后数据的读写要慢100000倍。考虑到缺页代价的巨大和磁盘访问第一个数据的开销，通常将主存和磁盘之间交换的页的大小设定得比较大，典型的有4KB和8KB等，而且有越来越大的趋势。

因为缺页处理代价较大，所以提高命中率是关键，因此，在主存页框和虚拟页之间采用全相联映射方式。此外，当进行写操作时，由于磁盘访问速度很慢，所以，不能每次写操作都同时写DRAM和磁盘，因而，在处理一致性问题时，采用回写方式，而不用全写方式。

2）请求分段存储管理

根据程序的模块化性质，可按程序的逻辑结构划分成多个相对独立的部分，例如，过程、数据表、数据阵列等。这些相对独立的部分被称为端，它们作为独立的逻辑单位可以被其他程序段调用，形成段间连接，从而产生规模较大的程序。段通常有段名、段起点、段长等。段名可用用户名、数据结构名或段号标识，以便于程序的编写、编译器的优化和操作系统的调度管理等。

可以把段作为基本信息单位在主存-辅存之间传送和定位。分段方式下，将主存控件ain按实际程序中的段来划分，每个段在主存中的位置记录在段表中，段的长度可变，所以段表中需有长度指示，即段长。每个进程有一个段表，每个段在段表中有一个段表项，用来指明对应段在主存中的位置、段长、访问权限、使用和装入情况等。段表本身也是一个可再定位段，可以存在外存中，需要时调入主存，但一般驻留在主存中。

在分段式虚拟存储器中，虚拟地址由段号和段内地址组成。通过段表把虚拟地址转换成主存物理地址，分段式管理系统的优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享；某些类型的段（如堆、栈、队列等）具有动态可变长度，允许自由调度以便有效利用主存空间。但是，由于段的长度各不相同，段的起点和终点不定，给主存空间分配带来麻烦，而且容易在主存中留下许多空白的零碎空间，造成浪费。

分段式和分页式存储管理各有优缺点，因此可以采用两者结合的段页式存储管理方式。

3）请求段页式存储管理

在段页式虚拟存储器中，程序按模块分段，段内再分页，用段表和页表（每段一个页表）进行两级定位管理。段表中每个表项对应一个段，每个段表项中包含一个指向该段页表起始位置的指针，以及该段其他的控制和存储保护信息，由页表指明该段各页在主存中的位置以及是否装入、修改等状态信息。

程序的调入调出按页进行，但它又可以按段实现共享和保护。因此，它兼有分页式和分段式存储管理的优点。它的缺点是在地址映射过程需要多次查表。

8、翻译和映射

答：

9、后备转换缓冲器TLB

答：

地址转换过程中，访存时首先要到主存查页表，然后才能根据转换得到的物理地址再访问主存以存储指令或数据。如果缺页，则还要进行页面替换、页面修改等，访问主存的次数就更多。因此，采用虚拟存储机制后，使得访存次数增加了。为了减少访存次数，往往把页表中最活跃的几个页表项复制到高速缓存中，这种在告诉缓存中的页表项组成的页表称为后备转换缓冲器（Translation Lookaside Buffer,TLB）,通常称为快表，相应地称主存中的页表为慢表。

10、动态存储器分配和垃圾收集

答：

我们可以通过mmap和munmap来创建和删除虚拟存储器区域，但对开发来说使用起来并不方便，况且没有很好的移植性，所以提出了是使用动态存储分配器来管理进程空间中的堆区域。动态存储分配器维护着一个进程的虚拟存储器区域，称为堆。堆事从低位地址向高位向上增长的，对于每个进程，内核维护着一个brk，它指向堆的顶部。

分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟存储器片，要么是已分配的，要么是空闲的。已分配的显式地保留为供应应用程序使用。空闲块可用来分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是存储器隐式执行的，它们都是显式的来分配存储块的，不同之处在于由哪个实体来负责释放已分配的块。

• 显式分配器

要求显式的释放已分配的块。如C标准库中的malloc和free，C++中的new和delete操作符。

• 隐式分配器

要求分配器检测一个已分配的块何时不再被程序使用，那么就释放这个块。隐式分配器也叫做垃圾收集器（Garbage collector），如java语言就依赖类似分配器。

下面我们看下malloc和free的实现是如何管理一个C程序的16字的小堆的。每个方框代表一个4字节的字。粗线标出的矩形对应于已分配块（有阴影）和空闲块（无阴影），初始时，堆都是一个大小为16个字的、双字对齐的、空闲块组成的。

• a)程序请求一个4字的块，malloc的响应是：从空闲块的前部切出一个4字的块，并返回一个指向这个块的第一个字的指针p1
• b)程序请求一个5字的块，malloc的响应是：从空闲块的前部分分配一个6字的块，返回指针p2，填充的一个额外字是为了保持空闲块是双字边界对齐的。
• c)程序请求一个6字的块，而malloc就从空闲块的前部切出一个6字的块。返回指针p3
• d)程序释放在b中分配的那6字的块。需要注意的是，在调用free返回之后，指针p2仍然指向被释放的块，在它被一个新的malloc调用重新初始化之前不能在程序中再使用p2
• e)程序请求一个2字的块。在这种情况下，malloc分配在前一步中释放了的块的一部分，并返回指向新块的指针p4

**垃圾收集器是一种动态存储器分配器，它自动释放程序不再需要的已分配块。这些块称为垃圾。自动回收堆存储的过程叫做垃圾收集。**在java虚拟机中就使用了类似的机制，应用显式分配堆块，但是从不显式地释放他们。垃圾收集器定时识别垃圾块，并相应地调用free，将这些块放回到空闲链表中。

垃圾收集器将存储器视为一张有向可达图，改图的节点被分成一组根节点和一组堆节点。每个堆节点对应于堆中一个已分配块。有向边p->q意味着块中的某个位置指向块q中的某个位置。根节点对应于这样一种不再堆中的位置，他们中包含指向堆中指针。这些位置可以是寄存器、堆里的变量，或者是虚拟存储器中读取数据区域内的全部变量。

当存在一条从任意根节点出发并到达p的有向路径时，我们说节点p是可达的。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的。垃圾收集器的角色就是维护可达图的某种表示，并通过释放不可达节点将它们返回给空闲链表，来定期回收它们。

四、链接、进程及并发编程

1、静态链接

答：

1）将可重定位的文件和命令行完全链接的、可加载、可运行的目标文件；

2）可重定位目标文件由各代码和数据节组成；

完成静态链接，链接器要完成以下两个工作：

1）符号解析，将每一个符号引用正好和一个符号定义关联起来；

2）重定位：可重定位的目标文件地址都是从零开始的，连接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使得他们指向这个内存位置。

2、目标文件

答：

分类：可重定位目标文件；可执行目标文件；共享目标文件；

可重定位目标文件：

包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。

可执行目标文件：

包含二进制代码和数据，其形式可以被直接复制到内存并执行。

共享目标文件：

一个特殊类型的可重定位目标文件，可以在加载或者运行时被动态的加载进内存并链接。

3、符号和符号表

答：

定义：符号表记录了目标模块定义的符号和引用的符号信息。

三种符号类型：

1）由模块m定义并能被其他模块引用的全局符号，非静态的C函数和全部变量；

2）由其他模块定义并被模块m引用的全局变量；

3）由目标模块定义和引用的局部符号，表现为静态全局变量和函数；

符号解析：链接符号引用与符号定义

1)全局符号的多种定义问题

强符号：已被初始化的全部变量和函数

弱符号：未被初始化的全部变量

2）规则

（1）不允许有多个同名的强符号

（2）如果有一个强符号和多个弱符号同名，选强符号

（3）如果有多个弱符号同名，从其中任意选一个

3）符号的地址由链接器确定，但符号的大小以及其类型在编译器就已经确定了，链接只负责解析和重定位符号确认符号的地址，同名符号有且仅有一个地址

4）静态链接可选方式

（1）一组可重定位目标文件

（2）所有相关的目标模块打包成一个单独文件-静态库（存档文件）

5）使用静态库来解析符号

过程：

符号解析时，链接器从左到右按照他们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件和存档文件（如.c .o）。

链接器维护三个集合：所有目标模块集合E；未定义的集合U；定义的集合D；

扫描开始，链接器来判断输入f是什么，若是目标文件，f添加到E，修改U/D来反应f中的符号定义和引用；若f是存档文件，链接器就尝试匹配U中未解析的符号和由存档文件成员定义的符号，若存档文件成员m中有已定义的符号，m放E，修改U/D；如果链接器完成扫描后，U非空，则链接器输出错误并终止，否则他会合并和重定位E中的目标文件

4、重定位和加载

答：

1）重定位（可结合静态链接的两个步骤作答）

需要的术语：

（1）重定位节和符号定义：聚合所有目标文件的相同节，链接器开始将运行时内存地址赋给每一个节和每一个符号☆☆☆

（2）重定位节中的符号引用，链接器修改代码节和数据节中的每个符号引用，使得他们执行正确的运行时地址。

2）过程：

（1）一个概念，当汇编器遇到未知的符号引用，就会生成一个重定位条目，代码的重定位条目存放在.rel.text中，已初始化数据的重定位条目放在.rel.data中

重定位结构的数据结构：

typedef struct

{

?	long offset;

?	long type:32; //符号相对节的偏移

?	symbol:32;

?	long addend;

}EIf64_Rela