计算机系统大作业：程序人生—Hello‘s P2P

4.5 本章小结

本章首先介绍了汇编的概念和作用，接着通过实操，对hello.s文件进行汇编，生成ELF可重定位目标文件hello.o，接着使用readelf工具，通过设置不同参数，查看了hello.o的ELF头、节头表、可重定位信息和符号表等，通过分析理解可重定位目标文件的内容。最后将其与hello.s比较，分析不同，并说明机器语言与汇编语言的一一对应关系。

第5章 编译

5.1 链接的概念与作用

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程（在本章中，链接即是指将可重定向目标文件 hello.o与其他一些文件组合成为可执行目标文件hello），这个文件可被加载到内存并执行。在现代系统中，链接是由链接器进行的。

链接可以实现分离编译。我们可以借助链接的优势将大型的应用程序分解成更小、更加易于管理的模块，使得各模块之间的修改都和编译相互独立。这样当我们需要修改某一模块时只需要重新编译经过修改的模块并重新链接即可，不需要重新编译其他文件。

5.2 在Ubuntu下链接的命令

命令如下：ld -ohello-dynamic-linker /lib64/ld-linux-x86-64.so.2/usr/lib/x86_64-linux-gnu/crt1.o/usr/lib/x86_64-linux-gnu/crti.ohello.o /usr/lib/x86_64-linux-gnu/libc.so/usr/lib/x86_64-linux-gnu/crtn.o

5.3 可执行目标文件hello的格式

5.3.1 ELF头

命令如下：readelf -h hello

可执行目标文件hello与可重定位文件hello.o稍有不同：前者ELF头中字段e_entry给出执行程序时的第一条指令的地址，而后者的此字段为0。且前者比后者多了一个程序头表，也成为段头表，是一个结构数组；还多了一个.init节，用于定义init函数，该函数用来执行可执行目标文件开始执行时的初始化工作。因为可执行目标文件不需要重定位，所以比后者少了两个.rel节。

查看hello的ELF头，发现hello的ELF头中Type处显示的是EXEC，表示是可执行目标文件，这与hello.o不同。hello中的节的数量为30个。

5.3.2 节头表

命令如下：readelf -S hello

与.o的节头不同的是，在这里每一节都有了实际地址，说明重定向已经完成:

发现刚才提到的30个节的具体信息，在hello文件节头表中都有显示，包括大小Size，偏移量Offset，其中Address是程序被载入虚址地址的起始地址。

5.3.3 程序头表

命令如下：readelf -l hello

查看hello的程序头表，首先显示这是一格可执行目标文件，共有12个表项，其中有4个可装入段（Type=LOAD），VirtAddr和PhysAddr分别是虚拟地址和物理地址，值相同。Align是对齐方式，这里4个可装入段都是4K字节对齐。以第一个可装入段为例，表示第0x00000~0x005f0字节，映射到虚拟地址0x400000开头的长度为0x5f0字节的区域，按照0x1000=4KB对齐，具有只读（Flags=R）权限，是只读代码段。

5.3.4重定位节

命令如下：readelf -r hello

5.3.5符号表

命令如下：readelf -s hello

5.4 hello的虚拟地址空间

从5.3.3的程序头表看，LOAD可加载的程序段第一段的地址为0x400000，那么虚拟内存地址从由0x401000开始，使用edb加载hello如下图所示：

由图5.3.2可以知道，.inerp段的起始地址为04002e0，用edb查看.inerp段的信息，如下图所示：

同理，.text段的起始地址为0x4010f0，用edb查看.text段的信息，如下图所示：

同理，.rodata段的起始地址为0x402000，用edb查看.rodata段的信息，如下图所示：

5.5 链接的重定位过程分析

首先，使用objdump -d -r hello对hello进行反汇编，结果如下：

hello的反汇编代码多了很多节，并且发现每条数据和指令都已经确定好了虚拟地址，不再是hello.o中的偏移量。通过链接之后，也含有了库函数的代码标识信息。

接着，我们具体比较分析一下hello和hello.o的反汇编结果，下面两个图分别为hello.o和hello的反汇编的部分截图，其余同理。

可以看出，在hello.o中跳转指令和call指令后为绝对地址，而在hello中已经是重定位之后的虚拟地址。

接下来，以0x401148出的call指令为例，说明链接过程。先用readelf -r hello.o查看hello.o的重定位信息：

由图可知，此处应该绑定第0x5个符号，同时链接器知道这里是相对寻址，接着查看hello.o的符号表，找到第5个符号puts，此处绑定puts的地址。

在hello中找到puts的地址为0x401090。

当前PC的值为call指令的下一条指令的地址，也就是0x40114d。而我们要跳转到的地方为0x401090，差0x16b，因此PC需要减去0x16b，也就是加上0xff ff fe 95，由于是小端法，因此重定位目标处应该填入95 fe ff ff。

5.6 hello的执行流程

使用edb单步调试运行程序，观察其调用的函数，这里可以发现在调用main之前主要进行了初始化的工作调用了_init，在这个函数之后动态链接的重定位工作已经完成，我们可以看到在这个函数的调用之后是一系列在这个程序中所用到的库函数（printf，exit，atoi等等），这些函数实际上在代码段并不占用实际的空间只是一个占位的符号，实际上他们的内容在共享区（高地址）处。之后调用了_start这个就是起始的地址，准备开始执行main的内容，main函数内部所调用的函数在第三章已经进行了分析，这里略过。main内部的函数，在执行main之后还会执行__libc_csu_init 、__libc_csu_fini 、_fini，最终这个程序才结束。

下面的表格列出了在使用edb执行hello时，从加载hello到_start，到call main，以及程序终止的过程中调用与跳转的各个子程序名或程序地址：

5.7 Hello的动态链接分析

动态链接器使用过程链接表PLT和全局偏移量表GOT实现函数的动态链接。通过hello节头表查询PLT和GOT的位置：

查阅节头可以得知，.got.plt起始位置为0x404000，在调用之后该处的信息发生了变化，如下图所示：

通过以上两张图的对比，可以得知，对于变量而言，我们利用代码段和数据段的相对位置不变的原则计算正确地址。对于库函数而言，需要plt、got合作，plt初始存的是一批代码，它们跳转到got所指示的位置，然后调用链接器。初始时got里面存的都是plt的第二条指令，随后链接器修改got，下一次再调用plt时，指向的就是正确的内存地址。plt就能跳转到正确的区域。

5.8 本章小结

本章着重介绍了可重定位目标文件 hello.o 经过链接生成可执行目标文件 hello的过程。首先详细介绍并分析了链接的概念、作用及具体工作。随后验证了 hello的虚拟地址空间与节头部表信息的对应关系，分析了hello的执行流程。最后对hello程序进行了动态链接分析。通过本章的实验操作，我更加深刻地理解了链接和重定位的相关概念，复习了课程第七章链接的相关知识，也了解了动态链接的过程及作用。

第6章 hello进程管理

6.1 进程的概念与作用

6.1.1 进程的概念

进程是指计算机中运行的程序，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

6.1.2 进程的作用

每次运行程序时，shell创建一新进程，在这个进程的上下文切换中运行这个可执行目标文件。应用程序也能够创建新进程，并且在新进程的上下文中运行它 们自己的代码或其他应用程序。

进程提供给应用程序的关键抽象：一个独立的逻辑控制流，如同程序独占处理器；一个私有的地址空间，如同程序独占内存系统。

6.2 简述壳Shell-bash的作用与处理流程

6.2.1 Shell-bash的作用

Shell-bash是一个交互型应用级程序，代表用户运行其他程序。它是系统的用户界面，提供了用户与内核进行交互操作的一种接口。它接收用户输入的命令并把它送入内核去执行。

6.2.2 Shell-bash的处理流程

Shell首先检查命令是否是内部命令，若不是，再检查是否是一个应用程序（比如Linux自身的应用程序，如ls和rm，也可以是应用商店的应用程序，如xv）。随后shell在搜索路径里寻找这些应用程序（搜索路径就是一个能找到可执行程序的目录列表）。如果键入的命令不是一个内部命令并且在路径里没有找到这个可执行文件，将会显示一条错误信息。如果能够成功找到命令，该内部命令或应用程序将被分解为系统调用并传给Linux内核。处理流程如下所示：

①从终端读入输入的命令；

②将输入字符串切分获得所有的参数；

③如果是内置命令则立即执行；

④若不是则调用相应的程序执行；

⑤shell应该随时接受键盘输入信号，并对这些信号进行相应处理。

6.3 Hello的fork进程创建过程

当在shell上输入./hello命令时，命令行会首先判断是否为内置命令，如果是内置命令则立即对其进行解释。否则会调用fork创建一个新进程并在其中执行。 根据shell的处理流程推断，输入命令执行hello后，shell会对我们输入的命令进行解析，认为该命令是执行当前目录下的可执行文件hello，因此shell会调用fork()创建一个子进程。子进程与父进程近似，并得到一份与父进程用户级虚拟空间相同且独立的副本——包括数据段、代码、共享库、堆和用户栈。父进程打开的文件，子进程也可读写。二者之间最大的不同在于PID的不同。fork函数只会被调用一次，但会返回两次，在父进程中，fork返回子进程的PID，在子进程中，fork返回0。

6.4 Hello的execve过程

execve函数加载并运行可执行目标文件Hello，且带参数列表argv和环境变量列表envp。该函数的作用就是在当前进程的上下文中加载并运行一个新的程序。只有当出现错误时，例如找不到filename，execve才会返回到调用程序，调用成功不会返回。与fork不同，fork一次调用两次返回，execve一次调用从不返回。

在execve加载了Hello之后，它调用启动代码。启动代码设置栈，并将控制传递给新程序的主函数，该主函数有如下的原型：

int main(intargc , char **argv , char *envp);

结合虚拟内存和内存映射过程，可以更详细地说明exceve函数实际上是如何加载和执行程序Hello：

①删除已存在的用户区域（自父进程独立）。

②映射私有区：为Hello的代码、数据、.bss和栈区域创建新的区域结构，所有这些区域都是私有的、写时才复制的。

③映射共享区：比如Hello程序与标准C库libc.so链接，这些对象都是动态链接到Hello的，然后再用户虚拟地址空间中的共享区域内。

④设置PC：exceve做的最后一件事就是设置当前进程的上下文中的程序计数器，使之指向代码区域的入口点。

6.5 Hello的进程执行

6.5.1 进程上下文信息

进程上下文信息是指内核重新启动一个被抢占的进程所需要恢复的原来的状态，由寄存器、程序计数器、用户栈、内核栈和内核数据结构等对象的值构成。

在内核调度了一个新的进程运行时，它就抢占当前进程，并使用一种上下文切换的机制来控制转移到新的进程。具体过程为：①保存当前进程的上下文；②恢复某个先前被抢占的进程被保存的上下文；③将控制传递给这个新恢复的进程。

如上图所示，为进程A与进程B之间的相互切换。处理器通常使用一个寄存器提供两种模式的区分，该寄存器描述了进程当前享有的特权，当没有设置模式位时，为用户模式；设置模式为为内核模式。用户模式就是运行相应进程的代码段的内容，此时进程不允许运行特权指令，也不允许直接引用地址空间中内核区内的代码和数据；而内核模式中，进程可以运行任何指令。

6.5.2 进程时间片

一个进程执行它的控制流的一部分的每一个时间段叫做时间片，多任务也叫时间分片。

6.5.3 进程调度的过程

在进程执行的某些时刻，内核可以决定抢占当前进程，并重新开始一个先前被抢占的进程，这种决策称为调度，是由内核中的调度器代码处理的。当内核选择一个新的进程运行，我们说内核调度了这个进程。在内核调度了一个新的进程运行后，它就抢占了当前进程，并使用上下文切换机制来将控制转移到新的进程。

hello程序调用sleep函数休眠时，内核将通过进程调度进行上下文切换，将控制转移到其他进程。当hello程序休眠结束后，进程调度使hello程序重新抢占内核，继续执行。

6.5.4 用户态与核心态的转换

为了保证系统安全，需要限制应用程序所能访问的地址空间范围。因而存在用户态与核心态的划分，核心态拥有最高的访问权限，而用户态的访问权限会受到一些限制。处理器使用一个寄存器作为模式位来描述当前进程的特权。进程只有故障、中断或陷入系统调用时才会得到内核访问权限，其他情况下始终处于用户权限之中，一定程度上保证了系统的安全性。

6.6 hello的异常与信号处理

6.6.1 异常的类别

异常可以分为四类：中断、陷阱、故障和终止，下图对这些类别的属性做了小结：

①中断：异步发生的。在执行hello程序的时候，由处理器外部的I/O设备的信号引起的。I/O设备通过像处理器芯片上的一个引脚发信号，并将异常号放到系统总线上，来触发中断。这个异常号标识了引起中断的设备。在当前指令完成执行后，处理器注意到中断引脚的电压变高了，就从系统总线读取异常号，然后调用适当的中断处理程序。在处理程序返回前，将控制返回给下一条指令。结果就像没有发生过中断一样。

②陷阱：陷阱是有意的异常，是执行一条指令的结果，hello执行sleep函数的时候会出现这个异常。

③故障：由错误引起，可能被故障处理程序修正。在执行hello时，可能出现缺页故障。

④终止：不可恢复的致命错误造成的结果，通常是一些硬件错误，比如DRAM或者 SRAM位被损坏时发生的奇偶错误

6.6.2 具体异常与运行结果

①正常运行：

②运行时输入任意字符串：

运行时输入的任意字符串，只是被缓存到缓冲区，待进程结束后又作为命令行进行输入。

③运行时输入回车：

getchar读回车，回车前的字符串当作shell输入的命令。

④运行时输入Ctrl+C：

Ctrl+C：使用SIGINT信号终止前台进程。

⑤运行时输入Ctrl+Z：

Ctrl+Z：使用SIGTSTP信号，停止前台作业。

⑥Ctrl-Z后运行ps、jobs、pstree、fg、kill等命令

Ⅰ. 首先输入Ctrl+Z，进程收到SIGTSTP信号，信号的动作是将hello挂起；

Ⅱ. 通过ps命令看到hello进程没有被回收，其进程号是2312；

Ⅲ. 用jobs命令看到job ID是1，状态是“已停止”；

Ⅳ. 接着输入pstree，以树状图形式显示所有进程；

Ⅴ. 输入fg，使停止的进程收到SIGCONT信号，重新在前台运行；

Ⅵ. 输入kill，-9表示给进程2380发送9号信号，即SIGKILL，杀死进程。

6.7本章小结

本章主要介绍了进程的概念及作用，阐述了壳shell-bash的作用与处理流程，并以hello为例，分析了fork函数的执行过程，execve函数的执行过程，并对进程的创建、执行、上下文切换、用户态与内核态的转化做了详细的分析。最后给出了异常的种类以及对hello进行一些异常操作处理，得到相应的结果。

在hello程序运行的过程中，内核对其进行进程管理，决定何时进行进程调度，在接收到不同的异常、信号时，还要及时地进行对应的处理。通过对本章内容的操作实践，我复习了CSAPP书上第八章异常控制流的相关内容，对进程、信号及异常相关概念有了更加深刻的理解。

第7章 hello的存储管理

7.1 hello的存储器地址空间

①逻辑地址 (Logical Address)：程序经过编译后出现在汇编代码中的地址，用来指定一个操作数或者是一条指令的地址。是由一个段标识符加上一个指定段内相对地址的偏移量；

②线性地址 (Liner Address)：逻辑地址向物理地址转化过程中的一步，逻辑地址经过段机制后转化为线性地址，为描述符、偏移量的组合形式，分页机制中线性地址作为输入；

③虚拟地址 (Virtual Address)：也是逻辑地址；

④物理地址 (Physical Address)：出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。如果启用了分页机制，那么线性地址会使用页目录和页表中的项变换成物理地址；如果没有启用分页机制，那么线性地址就直接成为物理地址了。

7.2 Intel逻辑地址到线性地址的变换-段式管理

一个程序可以由一个主程序、若干子程序、符号表、栈以及数据等若干段组成。每一段都有独立、完整的逻辑意义，每一段程序都可独立编制，且每一段的长度可以不同。段式存储管理支持用户的分段观点，具有逻辑上的清晰和完整性，它以段为单位进行存储空间的管理。

每个作业由若干个相对独立的段组成，每个段都有一个段名，为了实现简单，通常可用段号代替段名，段号从“0”开始，每一段的逻辑地址都从“0”开始编址，段内地址是连续的，而段与段之间的地址是不连续的。段式存储管理的逻辑地址由段号和段内地址两部分所组成，如下图所示：

分段式存储管理是在可变分区存储管理方式的基础上发展而来的。在分段式存储管理方式中，以段为单位进行主存分配，每一个段在主存中占有一个连续空间，但各个段之间可以离散地存放在主存不同的区域中。为了使程序能正常运行，即能从主存中正确找出每个段所在的分区位置，系统为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，记录该段在主存储器中的起始地址和长度。段表实现了从逻辑段到主存空间之间的映射。

当采用分段式存储管理的作业执行结束后，它所占据的主存空间将被回收，回收后的主存空间登记在空闲分区表中，可以用来装入新的作业。系统在回收空间时同样需要检查是否存在与回收区相邻的空闲分区，如果有，则将其合并成为一个新的空闲分区进行登记管理。

段表存放在主存储器中，在访问一个数据或指令时至少需要访问主存两次以上。为了提高对段表的存取速度，通常增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的段表项。

段式存储管理采用动态重定位方式装入作业，作业执行时通过硬件的地址转换机构实现从逻辑地址到物理地址的转换工作，段表的表目起到了基址寄存器和限长寄存器的作用，是硬件进行地址转换的依据。

7.3 Hello的线性地址到物理地址的变换-页式管理

页式存储管理是把主存储器划分成大小相等的若干区域，每个区域称为一块，并对它们加以顺序编号，如0#块、1#块等。与此对应，用户程序的逻辑地址空间划分成大小相等的若干页，同样为它们加以顺序编号，从0开始，如第0页、第1页等。页的大小与块的大小相等。分页式存储管理的逻辑地址由两部分组成：页号和页内地址，其格式如下图所示：

在分页式存储管理系统中，允许将作业的每一页离散地存储在主存的物理块中，但系统必须能够保证作业的正确运行，即能在主存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。页表实现了从页号到主存块号的地址映像。作业中的所有页（0~n）依次地在页表中记录了相应页在主存中对应的物理块号。页表的长度由进程或作业拥有的页面数决定。

调度程序在选择作业后，将选中作业的页表始址送入硬件设置的页表控制寄存器中。地址转换时，只要从页表寄存器中就可找到相应的页表。当作业执行时，分页地址变换机构会自动将逻辑地址分为页号和页内地址两部分，以页号位索引检索页表，如果页表中无此页号，则产生一个“地址错”的程序性中断事件；如果页表中有此页号，则可得到对应的主存块号，再按逻辑地址中的页内地址计算出欲访问的主存单元的物理地址。因为块的大小相等，所以：物理地址=块号×块长＋页内地址。

7.4 TLB与四级页表支持下的VA到PA的变换

7.4.1 翻译后备缓存器（TLB，也叫快表）

每次CPU产生一个虚拟地址，MMU（内存管理单元）就必须查阅一个PTE（页表条目）以便将虚拟地址翻译为物理地址。在最糟糕的情况下，这会从内存多取一次数据，代价是几十到几百个周期。如果PTE碰巧缓存在L1中，那么开销就会下降1或2个周期。许多系统都试图消除即使是这样的时间开销，它们在MMU中包括了一个关于PTE的小缓存，也就是TLB。

TLB是一个小的、虚拟寻址的缓存、其中的每一行都保存着一个由单个PTE组成的块。TLB通常具有高度的相联度，TLB的速度快于一级cache。

TLB通过虚拟页号VPN部分进行索引，分为TLBT（TLB标记）和TLBI（TLB索引），这样每次MMU会从TLB中取出相应的PTE（页表条目），当TLB不命中时，MMU又从L1缓存中取出相应的PTE，新取出的PTE会存放在TLB中此时可能会覆盖一个已存在的条目。

7.4.2 多级页表

使用层次结构的页表来压缩页表，形成相应的k级页表。那么虚拟地址被划分为VPO（虚拟页偏移量）以及k个VPN（虚拟页号），每个VPN i都是一个到第i级页表的索引，其中1≤i≤k。第j级页表中的每个PTE，1≤j≤k-1，都指向第j+1级的某个页表的基址。第k级页表中的每个PTE包含某个物理页面的PPN，或者一个磁盘块地址。为了构造物理地址，在能够确定PPN之前，MMU必须访问k个PTE。对于只有一级的页表结构，PPO和VPO是相同的

7.5 三级Cache支持下的物理内存访问

通用的高速缓存存储器（Cache）组织结构示意图如下所示：

当一条加载指令指示CPU从主存地址A中读一个字时，它将地址A发送到高速缓存。如果高速缓存正保存着地址A处那个字的副本，它就立即将那个字发回给CPU。

根据PA、L1高速缓存的组数和块大小确定高速缓存块偏移（CO）、组索引（CI）和高速缓存标记（CT），使用CI进行组索引，对组中每行的标记与CT进行匹配。如果匹配成功且块的valid标志位为1，则命中，然后根据CO取出数据并返回数据给CPU。

若未找到相匹配的行或有效位为0，则L1未命中，继续在下一级高速缓存（L2）中进行类似过程的查找；若仍未命中，则继续在L3高速缓存中进行查找；三级Cache均未命中则需访问主存获取数据。

若进行了上一步，说明至少有一级高速缓存未命中，则需在得到数据后更新未命中的Cache。首先判断其中是否有空闲块，若有空闲块（有效位为0），则直接将数据写入；若不存在，则需根据替换策略（如LRU、LFU策略等）驱逐一个块再写入。

7.6 hello进程fork时的内存映射

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任何一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

7.7 hello进程execve时的内存映射

6.4节给出了hello的execve过程。execve函数调用驻留在内核区域的启动加载器代码，在当前进程中加载并运行包含在可执行目标文件hello中的程序，用hello程序有效替代当前程序。加载并运行hello需要以下四个步骤：

①删除当前进程虚拟地址中已存在的用户区域；

②映射私有区域，为新程序的代码、数据、bss和栈创建新的区域结构，所有这些新的区域都是私有的、写时复制的；

③映射共享区域，将hello与libc.so动态链接，然后再映射到虚拟地址空间中的共享区域；

④设置当前进程上下文程序计数器（PC），使之指向代码区域的入口点。

7.8 缺页故障与缺页中断处理

在虚拟内存中DRAM缓存不命中称为缺页。缺页异常时会调用内核中的缺页异常处理程序，具体的过程如下图所示：

①处理器生成一个虚拟地址，并把它传送给MMU；

②MMU生成PTE地址，并从高速缓存/主存请求得到它；

③高速缓存/主存向MMU返回PTE；

④若PTE中的有效位是零，则MMU触发一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序；

⑤缺页异常处理程序确定物理内存中的牺牲页，如果这个页面已经被修改，则把它换出到磁盘；

⑥缺页处理程序页面调入新的页面（内核从磁盘复制所需的虚拟页面到内存中），更新内存中的PTE；

⑦缺页处理程序返回到原来的进程中，再次执行导致缺页的指令。CPU将引起缺页的虚拟地址重新发送给MMU，因为虚拟页面已经现在在物理内存中了，所以就会命中。

7.9动态存储分配管理

7.9.1 动态内存分配器

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。堆是一个请求二进制零的区域，它紧接在未初始化数据区域（.bss）后开始，并向上生长（向更高的地址）。对于每个进程，内核维护着一个brk指针，指向堆的顶部。

分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。已分配的块显示地保留为供应用程序使用。空闲块可用来分配。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。

分配器有两种基本风格：①显式分配器：要求应用显式地释放任何分配的块，例如C标准库提供的malloc程序包。②隐式分配器：要求分配器检测一个已分配块何时不再被程序所使用，那么就是放这个块，也被称为垃圾收集器。

7.9.2 隐式空闲链表

每个块是由一个字的头部、有效载荷、可能的额外填充以及一个字的尾部组成的，最后一位指明这个块是已分配的还是空闲的，具体形式如下图所示：

假设块的格式如上图所示，我们可以将堆组织为一个连续的已分配块和空闲块的序列，如下图所示：

我们称这种结构为隐式空闲链表，是因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中的所有块，从而间接地遍历整个空闲块的集合。注意，我们需要某种特殊标记的结束块，在这个示例中，就是设置了一个已分配位而大小为零的终止头部。

隐式空闲链表的优点是操作简单；显著的缺点是任何操作的开销，例如放置分配的块，要求对空闲链表进行搜索，该搜索所需时间与堆中已分配块和空闲块的总数成线性关系。

7.9.3 显式空闲链表

显式空闲链表结构将堆组织成一个双向空闲链表，在每个空闲块的主体中，都包含一个pred（前驱）和succ（后继）指针，其结构如下图所示：

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于空闲链表中块的排序策略。

一种方法是用后进先出（LIFO）的顺序维护链表，将新释放的块放置在链表的开始处；另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。按照地址排序的首次适配比LIFO排序的首次适配有更高的内存利用率，接近最佳适配的利用率。

但显示链表的缺点就是空闲块必须足够大，以包含所需要的指针，以及头部和可能的脚部。如此便导致了更大的最小块的大小，也潜在地提高了内部碎片的程度。

7.10本章小结

本章介绍了hello的存储地址空间，intel的段式管理、hello的页式管理，以及在TLB和四级页表的支持下完成VA到PA的变换过程，三级Cache支持下的物理内存访问。解释了hello进程的fork与execve时的内存映射，缺页故障及其处理，以及进程的动态存储分配的管理。让我对第六章存储器层次结构和第九章虚拟地址的知识有了更加深刻的理解。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

8.1.1 设备的模型化：文件

所有的I/O设备（例如网络、磁盘和终端）都被模型化为文件。例如：/dev/sda2文件是用户磁盘分区，/dev/tty2文件是终端。

8.1.2 设备管理：unix io接口

将设备模型化为文件的方式允许Linux内核引入一个简单、低级的应用接口，称为Unix IO，这使得所有的输入和输出都能以一种统一的方式来执行。

8.2 简述Unix IO接口及其函数

8.2.1 Unix IO接口

① 打开文件。一个应用程序通过要求内核打开相应的文件，来宣告它想要访问一个I/O设备，内核返回一个小的非负整数，叫做描述符，它在后续对此文件的所有操作中标识这个文件，内核记录有关这个打开文件的所有信息。应用程序只需记住这个描述符。

② Linux Shell创建的每个进程都有三个打开的文件：标准输入、标准输出、标准错误。

③ 改变当前的文件位置。对于每个打开的文件，内核保持着一个文件位置k，初始为0，这个文件位置是从文件开头起始的字节偏移量，应用程序能够通过执行 seek，显式地将改变当前文件位置k。

④ 读写文件。一个读操作就是从文件复制n>0个字节到内存，从当前文件位置k开始，然后将k增加到k+n。给定一个大小为m字节的文件，当k>=m时，执行读操作会触发EOF，应用程序能检测到它。类似地，写操作就是从内存中复制n>0个字节到一个文件，从当前文件位置k开始，然后更新k。

⑤ 关闭文件。内核释放文件打开时创建的数据结构，并将这个描述符恢复到可用的描述符池中去。

8.2.2 Unix IO函数

① int open(char* filename,int flags,mode_t mode)，进程通过调用open函数来打开一个存在的文件或是创建一个新文件的。open函数将filename转换为一个文件描述符，并且返回描述符数字，返回的描述符总是在进程中当前没有打开的最小描述符，flags参数指明了进程打算如何访问这个文件，mode参数指定了新文件的访问权限位。

② int close(fd)，fd是需要关闭的文件的描述符，close返回操作结果。

③ ssize_t read(int fd,void *buf,size_t n)，read函数从描述符为fd的当前文件位置赋值最多n个字节到内存位置buf。返回值-1表示一个错误，0表示EOF，否则返回值表示的是实际传送的字节数量。

④ ssize_t wirte(int fd,const void *buf,size_t n)，write函数从内存位置buf复制至多n字节到描述符为fd的当前文件位置。

⑤ lseek函数：off_t lseek(int fd, off_t offset, int whence)，应用程序显示地修改当前文件的位置。

⑥ stat函数：int stat(const char *filename,struct stat *buf)，以文件名作为输入，并填入一个stat数据结构的各个成员。

8.3 printf的实现分析

printf的函数体如下图所示：

在代码的3~5行中，第三行目的是让argv指向第一个字符串；第二句的作用是格式化，并返回要打印的字符串的长度，第三句的作用是调用write函数将buf的前i个字符输出到终端，调用了unix I/O。

从vsprintf生成显示信息，到write系统函数，到陷阱-系统调用int 0x80或syscall等。字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。

8.4 getchar的实现分析

getchar的函数体如下图所示：

getchar函数内部调用了read函数，通过系统调用read读取存储在键盘缓冲区的ASCII码，直到读到回车符才返回。不过read函数每次会把所有的内容读进缓冲区，如果缓冲区本来非空，则不会调用read函数，而是简简单单的返回缓冲区中最前面的元素

异步异常-键盘中断的处理：当用户按键时，键盘接口会得到一个代表该按键的键盘扫描码，同时产生一个中断请求，中断请求抢占当前进程运行键盘中断子程序，键盘中断子程序先从键盘接口取得该按键的扫描码，然后将该按键扫描码转换成ASCⅡ码，保存到系统的键盘缓冲区中。

8.5本章小结

本章介绍了Linux的I/O设备的基本概念和管理方法，以及Unix I/O接口及其函数。最后分析了printf函数和getchar函数的工作过程。本章内容让我对Unix IO 接口在Linux系统中的重要作用有了更加深入的理解，同时也了解了作为异步异常之一的键盘中断处理的工作过程。

结论

一、对hello所经历历程的总结

hello程序这一生：

①hello.c经预处理产生hello.i文本文件；

②hello.i经编译产生hello.s汇编文件；

③hello.s经汇编产生二进制可重定位目标文件hello.o；

④hello.o经链接产生可执行文件hello；

⑤在终端输入“./hello 2022112588向宇1”，shell经过检查后发现其不是内置命令，则将其当作程序执行；

⑥bash进程调用fork，生成子进程；

⑦execve函数加载运行当前进程的上下文中加载并运行新程序

⑧运行hello时，内存管理单元MMU、翻译后备缓冲器TLB、多级页表机制、三级cache协同工作，完成对地址的翻译和请求。

⑨调用sleep函数后进程休眠进入停止状态，调用完成后，内核再次进行上下文切换重新执行hello进程。

⑩hello的输入输出与外界交互，与linux I/O息息相关；

⑪hello最终被shell父进程回收，内核会收回为其创建的所有信息。

二、对计算机系统这门课的感悟

计算机系统这门课的知识点很多，比较抽象，学习难度总体偏大，不过很有趣。通过学习计算机系统（CSAPP）这门课，我认识到计算机专业不只只是写代码这么简单，还涉及许多计算机底层的知识，远比我想象的要复杂；通过动手完成课程的五个实验和一个大作业，让我计算机系统有了更加深入的理解，对课堂上那天抽象、晦涩难懂的知识点能够记忆得更加牢固。总之，计算机系统这门课让我学到了很多，也为我未来学习操作系统、数据库等其他计算机专业课程奠定了雄厚的基础。

附件

本次大作业的中间产物如下图所示：

①hello.c：源程序

②hello.i：预处理后的文本文件

③hello.s：编译后的汇编文件

④hello.o：汇编后的可重定位目标文件

⑤hello：链接后的可执行目标文件

参考文献

[1] 林来兴.空间控制技术[M].北京：中国宇航出版社，1992：25-42.

[2] 辛希孟.信息技术与信息服务国际研讨会论文集：A集[C].北京：中国科学出版社，1999.

[3] 赵耀东. 新时代的工业工程师[M/OL]. 台北：天下文化出版社，1998[1998-09-26]. http://www.ie.nthu.edu.tw/info/ie.newie.htm（Big5）.

[4] 谌颖. 空间交会控制理论与方法研究[D]. 哈尔滨：哈尔滨工业大学，1992：8-13.

[5]KANAMORI H. Shaking Without Quaking[J]. Science，1998，279（5359）：2063-2064.

[6]CHRISTINE M. Plant Physiology: Plant Biology in the Genome Era[J/OL].Science，1998，281：331-332[1998-09-23]. http://www.sciencemag.org/cgi/collection/anatmorp.