哈尔滨工业大学HIT-ICS2024大作业-程序人生-Hello‘s P2P-海口c网

第1章概述

1.1 Hello简介

①P2P：这一过程是指 Hello如何从C源文件经过预处理转变为可执行文件，这一过程共需经历四个阶段：

1）预处理器处理，生成文本文件hello.i

2）编译器处理，生成汇编程序hello.s

3）汇编器处理，生成文件hello.o

4）连接器处理，将其与库函数连接，最终生成可执行文件hello(之后通过系统创建进程执行hello)

②020：这一过程是指Hello如何在程序中运行，这一过程分为三个阶段：

1）使用shell命令解释程序。Shell将通过execve函数和fork函数将hello加载到相应的上下文中，并将程序内容载入物理内存。

2）调用main函数，运行hello程序。

3）程序运行结束，父进程回收进程，释放hello程序所占据的内存并删除相关内容。

①硬件环境：X64 CPU；2GHz；2G RAM；256GHD Disk 以上

②软件环境：Windows10 64位；VMware Workstation Pro15.5.1；Ubuntu 20.04.4

③开发和调试工具：gdb；edb；objdump；readelf；Code::Blocks20.03

1.3 中间结果

①hello.i：hello.c预处理后的文件。

②hello.s：hello.i编译后的文件。

③hello.o：hello.s汇编后的文件。

④hello：hello.o链接后的文件。

⑤hello1asm.txt：hello.o反汇编后代码。

⑥hello2asm.txt：hello反汇编后代码。

⑦hello.o_elf：hello.o用readelf -a hello.o指令生成的文件。

⑧hello_elf：hello用readelf -a hello指令生成的文件。

1.4 本章小结

本章节是对文章后续处理、展示进行背景陈述，运用术语简介了“Hello的自白”中所包含的计算机系统运行过程，陈列了完成本实验所运用的实验环境、开发工具和中间内容说明，以便后续阅读。

（第1章0.5分）

第2章预处理

2.1 预处理的概念与作用

①预处理的概念：预处理是指预处理器在源代码编译前所进行的一系列文本操作，其主要包括删除注释、处理#开头的预处理指令（如#include、#define）等。

②预处理的作用：

1）去除注释：同字面意义，删除源代码文件中写入的注释行

2）进行宏替换：#define所写内容即为宏，宏替换指的就是执行#define所写内容。

3）展开头文件：将#include所指定的头文件写入并展开。

4）做条件编译：主要与#if系列语句有关，可以在不同条件下执行不同的程序。

2.2在Ubuntu下预处理的命令

命令行：gcc hello.c -E -o hello.i

2.3 Hello的预处理结果解析

Hello.i在ubuntu中可作为文本文件直接打开，可见总共3061行，而3048行起后续与源代码中main函数内容一致，往前翻阅可发现注释已经全部被删除，而#所写已经展开。

2.4 本章小结

本章是hello“程序生”的起点，从最起始的预处理开始，讲解了预处理的概念和作用，展示了ubuntu下预处理操作及操作结果，并对预处理文件hello.i进行了解析，直观反应预处理的作用。

（第2章0.5分）

第3章编译

3.1 编译的概念与作用

①编译的概念：

编译是指利用编译程序，从源代码产生目标程序的过程。

编译也可以说是从高级程序设计语言转换到机器能理解的汇编语言的过程。

②编译的作用：

1）产生目标程序，得到汇编语言文件

2）编译器本身也具有一些功能，比如语法检查等等

3.2 在Ubuntu下编译的命令

命令行：gcc hello.i -S -o hello.s

3.3 Hello的编译结果解析

3.3.1记录文件信息：

①源文件.file

②代码段.text

③只读代码段.section & .rodata

④字节对齐方式.align(此处为.align 8即是八字节对齐方式)

⑤字符串.string

⑥全局变量.global

⑦main函数类型.type

3.3.2操作局部变量：

①当进入main函数时，将根据局部变量的需求，为原本存储在栈中的局部变量申请一段栈上的空间以供使用，这部分空间将在局部变量的生命周期结束后予以释放。

②在hello.c中设定的局部变量即为i，而在hello.s中可以看到，其跳转到了L3的位置后又将栈指针减少4，表明存储了局部变量i。

③跳转到L4，进行下一步操作

3.3.3操作字符串常量

①在进入main函数前，.rodata处已经存储了字符串常量，并标记该位置是只读的。

②在main函数中使用字符串时，将只能得到该字符串的首地址

3.3.4操作立即数：

立即数直接用$+数字的方式表示。

3.3.5传递参数argv：

①进入main函数后，先将%rbp压栈保存起来，以便后续使用

②将栈指针减少32位，由此将%rsi和%rdi所存的值存进栈中。可见，%rbp-20和%rbp-32的位置分别存储了argv数组和argc的值

3.3.6操作数值：

想要操作数组，一般而言都只需要找到数组首地址之后增加偏移量即可。

①%rbp-32即为数组首地址，每次调用时将其传给%rax，再增加偏移量即调用成功，其中16、8的偏移量分别对应了argv[1]与argv[2]

②调用printf之后又进行了类似的操作，本次偏移量为32，对应于argv[4]，将其存入%rdi中供后续使用。

3.3.7函数的调用及返回

①寄存器传参函数的前六个参数，其返回值存储于%rax寄存器。

②调用函数时，需先将相应的值存入相应的寄存器，然后再使用指令进行操作：call-调用函数，ret-返回函数

3.3.9循环操作

对于for循环，一般遵循以下操作原则：

①存储循环变量于寄存器，每次执行完循环体后，更新该循环变量

②通过cmp命令行比较循环变量，当满足条件时脱出循环，否则继续循环

3.3.10 赋值

整个main函数中多次使用了赋值操作，通过movq、movl指令即可完成赋值。

3.4 本章小结

这一章首先阐明了编译的概念和作用，再在ubuntu下实际进行了编译操作并展示结果，通过按类型、操作分析编译结果文件，生动体现了编译的操作方法和重要作用

（第3章2分）

第4章汇编

4.1 汇编的概念与作用

①汇编的概念：

汇编是指把汇编语言编写的程序转换为相匹配的机器语言程序的过程。

汇编程序所输入的是用汇编语言编写的源程序，而输出的是用机器语言编写的目标程序。

②汇编的作用：

1）将程序转写为机器语言，让机器能够理解程序

2）汇编过程中可从汇编程序得到一个可重定位目标文件，便于后续的链接操作。

4.2 在Ubuntu下汇编的命令

命令行：gcc -c hello.s -o hello.o

4.3 可重定位目标elf格式

①命令行：readelf -a hello.o > hello.elf

②elf内容展示：

③elf内容解析：

1）段头表/程序头表：包含页面大小，虚拟地址内存段(节)，段大小

2）.text 节：已编译程序的机器代码内容

3）.rodata 节：用于表明只读数据，如printf的格式串、跳转表等

4）.data 节：用于表示已初始化的全局和静态变量

5）.bss 节：用于表示未初始化或者初始化为0的全局和静态变量。这一节仅有节头，节的本身并不占用磁盘空间

6）.symtab 节（符号表）：内含函数和全局/静态变量名，节名称和位置

7）.rel.text 节（可重定位代码）：指.text 节的可重定位信息，在可执行文件中需要修改的指令地址，需修改的指令等

8）.rel.data 节（可重定位数据）：指data 节的可重定位信息，在合并后的可执行文件中需要修改的指针，数据的地址等

9）.debug 节（调试符号表）：内容为符号调试的信息

10）节头表：内含每个节的在文件中的偏移量、大小等

4.4 Hello.o的结果解析

①命令行：objdump -d -r hello.o

②结果展示：

③结果解析：

其中大部分结果仍然是可读的汇编代码，但也掺杂了相当部分的“机器代码”。这些机器代码是二进制机器指令的集合，每一条机器代码都对应一条机器指令，所有汇编代码都可以通过机器二进制数据进行表示，汇编代码中的操作码和操作数通过某种影响和机器语言一一对应，由此可以让二进制机器也理解代码的含义并正确执行。其中机器代码与汇编代码的不同可简要概括为：

1）函数调用方式不同。汇编代码中，函数的调用直接通过函数名进行；而在机器代码中，call的目标地址是当前指令的下一条地址。机器代码中，对于这种不确定地址的调用，需要在链接时才能确定其地址。

2）分支跳转方式不同。汇编代码中使用标识符来确定跳转目标；机器代码中经过转写直接使用地址实现跳转。

4.5 本章小结

这一章首先简要说明了汇编在“程序生”中的概念与作用，随后在ubuntu中实际操作了汇编并生成重定向文件，对elf文件的内容进行了详细解析。接着还进行了反汇编并对反汇编结果进行阐释，由此衍生，解释了机器代码与汇编代码的关系与不同。

（第4章1分）

第5章链接

5.1 链接的概念与作用

①链接的概念：

链接是指将各种代码和数据片段整合为一个单一文件的过程，这一文件可以被加载到内存执行，由此使得程序可被执行。

②链接的作用：

1）分离编译。链接可以使程序被分为不同的小模块，更加便于管理、修改和维护

2）确定地址。使得机器代码中所调用的不确定地址可以被确定

5.2 在Ubuntu下链接的命令

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

可以看到生成了hello文件

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

①查看ELF头：

其中文件类型发生了变化，变为了EXEC（可执行文件）。节头部数量（Number of section headers）也发生了变化，变为了27个。

②Section头：

节头部表对hello中所有信息进行了声明，包括了大小（Size）、偏移量（Offset）、起始地址（Address）以及数据对齐方式（Align）等信息。

根据始地址和大小，我们就可以计算节头部表中的每个节所在的区域。

③符号表：

可以看到经过链接符号表的符号数量急剧增加，表明经过链接后符号表中引入了很多其他库函数的符号。

④可重定位段信息：

5.4 hello的虚拟地址空间

①edb结果图：

②.inrep段：

在readlf中可以查看到.inrep的地址为0x04002e0

由此地址在edb中继续查看（goto expression）：

③.text段：

在readlf中可以看到.text地址为0x4010f0

Edb中查看结果为：

④.rodata段：

在readlf中可以看到.rodata段地址为0x402000

Edb中查看结果为（symbolviewers）：

5.5 链接的重定位过程分析

①反汇编结果展示：

②过程分析：

可以看出，在hello.o中跳转指令和call指令后为绝对地址，而在hello中已经是重定位之后的虚拟地址。以0x4011f6的call指令举例解析连接过程：

1）

在此处，应该绑定的是第0xc（十进制12）个符号

2）

打开符号表，可以找到第12个符号为puts，即此处应绑定puts的地址

3）

在前面hello反汇编结果中可见，puts地址为0x401090。而由于机器代码跳转的特殊性，PC的值为call指令的下一条地址0x4011fb。跳转目标位0x401090，中间存在0x16b的距离。

由此反推，PC需要减去0x16b，最终反映为加上0xff ff fe 95，遵从小端法输入规则，重定位目标应该为95 fe ff ff。

5.6 hello的执行流程

使用edb中的symbolviewer进行查看，截图结果依次如下：

5.7 Hello的动态链接分析

（以下格式自行编排，编辑时删除）

分析hello程序的动态链接项目，通过edb/gdb调试，分析在动态链接前后，这些项目的内容变化。要截图标识说明。

①动态链接的概念：动态链接的概念是基于共享库建立的。在程序运行或者加载时，共享库可以加载到程序的任意内存地址并和一个程序链接起来。相较于把所有模块链接起来成为一个单独的可执行文件的静态链接，它在运行时才成为一个完整的程序，因此称为动态链接。

②.plt与.got：

PLT是一个数组，每个条目是16字节代码。其中PLT[0]是个特殊条目，它直接跳转动态连接器。一般来说，被可执行程序调用的库函数都有自己的PLT条目并负责调用一个具体的函数，其存在对应关系

GOT也是一个数组，但每个条目是8字节。GOT和PLT联合使用时，GOT[O]和GOT[1]用于存放信息以供动态连接器使用，而GOT[2]是动态链接器在1d-linux.so模块中的入口点。其余每个条目与PLT条目类似，对应于一个被调用的函数。

③hello在动态连接器加载前后的重定位存在差异，其变化如截图所示：

（加载前的.init）

（加载后的.init）

5.8 本章小结

这一章讲解了链接相关的知识，首先阐述了链接的概念与作用，随后在ubuntu下实际操作并展示了链接结果，之后重定位分析链接过程、解读hello虚拟内存空间，并详细展示了动态链接的概念、作用和带来的影响。

（第5章1分）

第6章 hello进程管理

6.1 进程的概念与作用

①进程的概念：

进程是指一个执行中的程序的实例，系统中每个程序都运行在某个进程的上下文中，其内含多种程序正常执行所需要的状态。

②进程的作用：

进程提供给程序两个关键的假象：

1）一个独立的逻辑控制流，好像我们的程序独占地使用处理器。

2）一个私有的地址空间，好像我们的程序独占地使用内存系统。

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

①Shell-bash的作用：

它是一种命令解释器，可以解释用户输入的命令并将其送入内核以供机器读取理解，代表用户运行其他程序。

②Shell-bash的处理流程：

1）读/取值步骤：由读取用户的一个命令行开始，壳进行一系列的读/取值步骤至终止

2）求值步骤：解析命令行并代表用户运行程序。在解析命令行后eval函数将调用builtin_command函数检查其是否是内置命令：

若命令行第一个参数是一个shell内置命令名，则shell立刻执行这个命令；

若命令行第一个参数不是一个shell内置命令名，shell则认为这个参数是一个可执行目标文件的名字，这个文件将会被加载到另一个新的进程上下文中运行。

3）判断最后一个参数是否为“&”，若是则shell不会等待这个命令完成，若否则shell在前台执行该命令直至其完成

6.3 Hello的fork进程创建过程

使用fork函数：pid_t fork(void)创建子进程。所创建的子进程将得到一份与父进程拥有相同虚拟地址空间但又与之独立的副本，从而得到相同的代码、共享库、栈等基础信息。同时，子进程还会获得与父进程打开文件描述符相同的副本，由此当父进程fork时，子进程可以读取父进程当中的任意文件。

父进程与子进程拥有不同的PID，而子进程的PID总是非零的，因此返回值是判断程序究竟是在子进程还是父进程的重要手段。

6.4 Hello的execve过程

①使用execve函数，在当前进程的上下文中将加载并运行一个新程序

②若程序运行出现错误，则execve将返回到调用程序，若成功则不返回

6.5 Hello的进程执行

①进程调度：在进程执行中，内核可以决定抢占当前进程，并重新开始一个先前被抢占过的进程，这种决策叫做调度，其由内核中的调度器进行。这一机制建立在上下文切换机制的基础之上。

②上下文切换机制：这一机制需要在内核模式（核心态）下进行。进程若要从用户态进入核心态，只能通过发生异常来实现。当异常发生时，系统进入和心态，内核可以执行从某个进程A到进程B的上下文切换，

在切换的第一部分，内核代表进程A在核心态下执行指令，而在某一时刻开始又代表进程B在内核模式下执行指令。切换完成后，内核代表进程B在用户态下执行指令。由此可实现多任务处理。

6.6 hello的异常与信号处理

（

①

类别	原因	异步/同步	返回行为
中断	来自I/O设备的信号	异步	总是返回到下一条指令
陷阱	有意的异常	同步	总是返回到下一条指令
故障	潜在可恢复的错误	同步	可能返回到当前指令
终止	不可恢复的错误	同步	不会返回

②在hello中可能发生的异常：

1）中断：在进程运行过程中出现一些I/O输入，比如敲击键盘等等，就可能触发中断。此时系统会陷入内核，调用中断处理程序进行返回。

2）陷阱：其同于系统调用，它是一种有意的异常，也是执行某一条指令的结果，hello运行过程中执行sleep函数就有可能触发这种异常。

3）故障：这是由错误引起的，并且这种错误可能会被恢复。Hello执行过程中可能会存在缺页导致的故障

4）终止：不可恢复的致命错误将导致终止的出现，通常是一些硬件上的错误。

③命令结果展示：

1）运行过程中按回车：

2）输入Ctrl+c

3）输入Ctrl+z

4）输入ps：

其是对后台程序的监视

5）输入jobs：

可以看到暂停的进程

6）输入pstree：

以树状图的形式展示了全部进程

7）输入fg：

停止的进程重新在前台运行

8）输入kill：

向指定进程号发送9号信号，杀死了该进程。

6.7本章小结

这一章详细讲述了程序如何从可执行文件变成进程。首先讲解了进程相关的概念和功能，在此之上又对壳Shell-bash的结构与作用进行简介，接着对hello进程的创建、执行过程梳理，并对其中可能产生的异常做详细分析。

（第6章1分）

第7章 hello的存储管理

7.1 hello的存储器地址空间

①逻辑地址：

逻辑地址是指由程序产生的与段相关的偏移地址部分。在C语言程序中，使用或操作读取指针变量的值就是其逻辑地址，它是相对于当前进程数据段的地址。一个逻辑地址由两部分组成：段标识符和段内偏移量。

②线性地址：

线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，即段中的偏移地址，加上相应段的基地址就生成了一个线性地址。

如果启用了页式管理，那么线性地址可以再变换产生物理地址。若没有启用页式管理，那么线性地址直接就是物理地址。

③虚拟地址：

虚拟内存空间的概念与逻辑地址类似，因此虚拟地址和逻辑地址实际上是一样的，它们都与实际物理内存容量无关。

④物理地址：

存储器中的每一个字节都有一个唯一的存储器地址，这个存储器地址称为物理地址，又叫实际地址或绝对地址，是地址总线上实际传输的地址。

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

①段式管理的概念：

段式管理是指将程序拆解为多个由逻辑实体组成的段进行存储，其产生与程序模块化直接相关。

②段式管理的操作：

段式管理需要通过段表来进行操作，段表中包含了段号段名、段起点等基础信息，此外还需要主存占用区域表、主存可用区域表来辅助段式管理操作。

③段式管理的变换法则：

逻辑地址 = 段标识符+段内偏移量

这一变换将逻辑地址映射至线性地址。其中段标识符由索引号、表指示器和请求者特权级组成，而段内偏移量则是一个不变的常量，直接进入计算即可。

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

①页式管理的概念：

页式管理是指线性地址（VA）到物理地址（PA）之间的转换对虚拟地址内存空间进行分页的分页机制完成。

②页式管理的操作：

想要进行页式管理，需要在内存中增加“页表”作为索引。与段表类似，每一个进程都有自己的页表，记录着该进程中对应的一页所投影到的物理地址、是否有效等基本信息。为节省内存空间，系统往往采用多级页表的结构进行索引。

每一个页表条目是由一个有效位和一个n为地址字段组成。有效位表明虚拟页是否缓存在DRAM中，n位地址字段是物理页的起始地址或者虚拟页在磁盘的起始地址。

③页式管理的变换法则：

要将虚拟地址转换为物理地址，需要先查询页表来判断一个虚拟页是否缓存在DRAM的某个地方，如果它不在DRAM的某个地方，通过查询页表条目可以知道虚拟页在磁盘的位置。此后，页表将虚拟页映射到物理页完成变换。

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

①关于多级页表：

在7.3中提到，为了节省页表所占用的内存空间，往往采用多级页表的形式进行索引。在多级页表中，一级页表中每个PTE映射虚拟存储空间中一个由很多虚拟页组成的片，假设该片中至少有一个虚拟页已经被分配，则一级页表的PTE将指向一个二级页表的基址，二级页表中每个PTE再映射一个更小的片，如此循环往复，直到第k级页表的PTE存储的是PPN。由于一级页表项为空，所以对应的二级页表就不存在而无需保存，这样一来只有一级页表需要常驻在主存中，而二级页表可以根据需要进行创建、页面调入或调出。如此便节省了用于存储页表的空间。

②翻译后备缓冲器TLB：

考虑以下两点：1.每次访问PTE都需要耗费一定的时间；2.每次最近访问的PTE和存储器层次结构中其他地方一样具有局部性，因此可以设立一个页表的缓存来加速地址翻译。

TLB（翻译后备缓冲器）是MMU中一个小的具有高相联度的集合，其每一行都保存着一个单个PTE组成的块，最常用的PTE可以缓存在TLB中，这样就省去了每次访问PTE需要访问L1甚至内存的时间开销。

③实际变换流程：

以intel i7的VM系统为例，该系统有4级页表，36位VPN被划分成4个9位的片，每个片被用作到一个页表的偏移量。CR3寄存器包含L1页表的物理地址，VPN1提供到L1 PTE的偏移量，这个PTE包含L2页表的基地址，VPN2提供到L2 PTE的偏移量.

在实际访问时，首先访问TLB，若TLB里缓存了要访问的PTE则可以直接从这个PTE里拼接得到物理地址，若TLB里没有缓存要访问的PTE，则需要依次访问一到四级页表。四级页表的PTE里包含PPN，将其与VPO拼接后即可得到物理地址。

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

三级Cache支持下的物理内存访问与TLB相似：

利用局部性原理，采用组相联的方式，存储一段时间内所加载的地址附近的内容。在得到物理地址后，优先从L1 cache中寻找，若没有则从L2 cache中寻找，如此依次访问L1 cache、L2 cache、L3 cache和主存，完成访问。

7.6 hello进程fork时的内存映射

①fork被shell调用时：

内核将为hello进程创建各种数据结构，分配给它唯一的PID。同时为了给hello进程创建虚拟内存，它还将创建hello进程的mm_struct 、区域结构和页表的原样副本。

与此同时，它还将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

②fork从hello中返回时：

hello进程此时的虚拟内存将与调用fork 时存在的虚拟内存相同。

而当这两个进程中的任一个进程之后进行写操作时，写时复制机制就会创建新页面，由此为每个进程保持了私有地址空间的抽象概念。

7.7 hello进程execve时的内存映射

①删除已存在的用户区域。这一删除操作包括了所有虚拟地址中的用户部分已存在的区域结构。

②映射私有区域。Execve将为新程序的代码、数据等创建新的区域结构，execve此时所创建的所有新区域都是私有且写时复制的，即是其私有区域。

③映射共享区域。hello 程序与共享对象 libc.so 链接，而libc.so 是动态链接到这个程序中的，然后再映射到用户虚拟地址空间中的共享区域内。

④设置程序计数器PC。这是execve所进行的最后一个步骤，设置计数器并使之指向代码区域的入口点。

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

①缺页故障的概念：

常说的“缺页”其实指的就是DRAM缓存未命中。当指令中取出一个虚拟地址时，若我们发现对该页的内存访问是合法的，但其对应的有效位却为0，则表明该页没有能正常保存在主存当中，即发生了缺页故障。

②缺页中断处理：

当发生缺页故障时，进程将暂停。此时内核会选择某一个主存中的某一个页面进行牺牲，若该牺牲页面是其他进程或者这个进程本身的页表项，则将这个页表对应的有效位改为0，同时把所缺的页存入主存中的一个位置，并在该页表项将其对应的有效位置为1。在这之后重启进程执行该条语句，此时MMU就可以正常翻译这个虚拟地址了。缺页故障由此得到解决。

7.9动态存储分配管理

①动态存储分配管理的概念：

动态存储分配管理是指在程序运行时可以使用动态内存分配器，这些分配器将堆视为一组不同大小的块(blocks)的集合来维护每个块的分配与空闲状态。

②堆：

由动态存储分配管理器维护着的进程虚拟内存区域称为堆。当内存中的碎片和垃圾被回收之后，内存中就会产生多余的空闲空间。为了避免内存空间的浪费，需要记录这些空闲块，而采用隐式空闲链表和显式空闲链表的方法则可以实现这一操作。

③隐式空闲链表：

当隐式空闲链表工作时，若分配块比空闲块小，则还可以把空闲块分为两部分，一部分用来承装分配块从而避免可能导致的浪费。

隐式链表采用边界标记的方法进行双向合并。即脚部与头部是均为 4 个字节，这一部分用来存储块的大小并表明这个块的空闲与分配状态。同时定位头部和尾部，可以以常数时间来进行块的合并。由此，无论是与下一块还是与上一块合并，都可以通过他们的头部或尾部得知块大小，从而定位整个块，避免了从头遍历链表导致的时间花销极高。

④显式空闲链表：

与隐式空闲链表不同，显式空闲链表只记录空闲块而不记录所有块。

显示空闲链表的思路是维护多个空闲链表，每个链表中的块有大致相等的大小，分配器维护着一个空闲链表数组，每个大小类一个空闲链表。当需要分配块时，只需要在对应的空闲链表中搜索即可。

7.10本章小结

这一章聚焦于hello程序在计算机系统当中的存储与管理问题，并引出计算机系统当中的一个重要概念“虚拟内存”。在本章当中，我们详细讲述了hello的四种地址及其寻找、变换、翻译的过程，阐释了TLB相关概念和流程，多（三）级缓存、动态内存管理的要点重点。

（第7章 2分）

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

设备的模型化：文件

设备管理：unix io接口

所有的I/O设备都会被模型化为文件，而所有的输入和输出都被当做对相应文件的读和写来执行，这种将设备映射为文件的方式，允许Linux内核引出一个简单低级的应用接口，称为Unix I/O。这就是Linux的I/O设备管理方法。

8.2 简述Unix IO接口及其函数

①Unix I/O接口：

1）一个程序想要声明其欲访问I/O设备，只需要通过内核打开相应的文件即可。内核将返回一个非常小的非负整数，称之为“标识符”，通过它对后续此文件的所有操作进行标识。内核需要记录有关该文件的所有信息，而这个程序只需要记忆这一标识符即可。

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

3）改变文件位置。每个已经打开的文件，内核中都保持着一个对应的文件位置k。k初始为 0，而这个文件位置则是从文件开头起始计的字节偏移量，程序能够通过执行指令seek显式地将改变当前文件位置k。

4）读写文件。

读操作：一个读操作就是从文件复制一定数量个字节到内存。比如若要复制n个字节到内存，则从当前文件位置 k 开始，然后将 k 增加到 k + n。若给定一个大小为 m 字节的文件，当 k >= m 即起始位置超出文件大小时，执行读操作就会触发 EOF。

写操作：类似地，写操作就是从内存中复制一定数量个字节到一个文件，比如若要从内存写n个字节，则从当前文件位置 k开始，然后更新k直至k+n即可。

②函数

1）Open函数：int open(char *filename,int flags,mode_t node);

将filename转换为一个文件描述符，并且返回描述符数字。返回的描述符总是在进程中当前没有打开的最小描述符。flags 参数指明了进程打算如何访问这个文件，mode参数指定了新文件的访问权限位。

2）close函数：int close(int fd);

其功能是关闭一个打开的文件，若选取对象是已关闭的文件则描述符会出错。

3）read函数：ssize_t read(int fd,void *buf,size_t n);

从描述符为fd的当前文件位置赋值最多n个字节到内存位置buf。

当返回值为0时，即为触发了EOF。

4）write函数：ssize_t write(int fd,const void *buf,size_t n);

从内存位置buf复制至多n个字节到描述符fd的当前文件位置。

5）lseek函数：off_t lseek(int fd, off_t offset, int whence);

这一函数使程序显式地改变文件的当前位置

6）stat函数：int stat(const char *filename,struct stat *buf);

以文件名作为输入，并填入一个stat数据结构的各个成员。

8.3 printf的实现分析

https://www.cnblogs.com/pianist/p/3315801.html

①printf的函数体：

int printf(const char *fmt, ...)

{

int i;

char buf[256];

va_list arg = (va_list)((char*)(&fmt) + 4);

i = vsprintf(buf, fmt, arg);

write(buf, i);

return i;

}

②vsprintf的函数体：

int vsprintf(char *buf, const char *fmt, va_list args) {

char* p;

char tmp[256];

va_list p_next_arg = args;

for (p=buf;*fmt;fmt++) {

if (*fmt != '%') {

*p++ = *fmt;

continue;

}

fmt++;

switch (*fmt) {

case 'x':

itoa(tmp, *((int*)p_next_arg));

strcpy(p, tmp);

p_next_arg += 4;

p += strlen(tmp);

break;

case 's':

break;

default:

break;

}

return (p - buf);

}

③实现分析：

printf程序按照格式fmt结合参数args生成格式化之后的字符串，并返回该字串的长度。Printf中调用了两个外部函数，分别为vsprintf和write。

而vsprintf函数作用是接受确定输出格式的格式字符串fmt。用格式字符串对个数变化的参数进行格式化，产生格式化输出。write函数的作用则是将buf中的i个元素写到终端。

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

8.4 getchar的实现分析

①getchar函数体：

int getchar(void)

{

static char buf[BUFSIZ];//缓冲区

static char* bb=buf;//指向缓冲区的第一个位置的指针

static int n=0;//静态变量记录个数

if(n==0)

{

n=read(0,buf,BUFSIZ);

bb=buf;//并且指向它

}

return(--n>=0)?(unsigned char)*bb++:EOF;

}

②实现分析：getchar函数中还调用了read函数，通过系统调用read读取存储在键盘缓冲区的ASCII码，直到读到回车符才返回。

需要注意的是，read函数每次会把所有的内容读进缓冲区，如果缓冲区本来非空，则不会调用read函数，而是直接返回缓冲区中最前面的元素。

③异步异常-键盘中断的处理：：键盘中断处理子程序。接受按键扫描码转成ascii码，保存到系统的键盘缓冲区。

8.5本章小结

本章就是整篇文章的最后一章，也是我们hello“程序生”的句号。这一章我们谈论了程序的最外层-（读写）I/O设备的有关概念，并对分别代表读写的getchar和printf函数的实现进行了分析。

（第8章1分）

结论

源代码是一切程序的开端，对于hello来说一样如此。它的生命，萌芽于新建Empty file，铸就于C语言的每一字节，并在“另保存为hello.c”时初具雏形，只待萌芽破土，“一如数万年前的初夜”。

当预处理器与它相见，hello的“程序生”便由此蓬勃生长一发不可收拾。预处理器为它展开了头文件做了宏替换，深知万丈高楼起于平地的道理；接着又受编译器和汇编器做媒，让它转写成机器语言足以和刻板冰冷的计算机纹枰论道。最终经过链接，它们真正地合而为一，得到了可执行文件hello。

为了执行好它们共力而育的果实，还须得做千百般努力。通过shell解析命令行输入的命令，然后调用fork创建子进程，再用execve映射到虚拟内存中，让hello也有容身之处。当CPU执行到hello时，读取虚拟内存地址、借缺页异常之手将hello载入主存中，让hello有了施展手脚的天地。利用多级页表、层层缓存，hello终于是被加载到了处理器内部。万事俱备，只欠“输出”。

最终，在I/O设备的帮助下，结果输出到终端，它也向着世界发出了最原初又最深远的呼唤：hello，world！

Hello这一程序是我们每个C语言程序员入门所实践的第一个程序，其简单短小不言而喻。然人不可貌相，程序也不可器量，在hello这么浅显的小程序背后，也同样蕴含着庞大的计算机系统知识。正所谓万变不离其宗，重视每一个程序的每一处细节，才能在更大的尺度上做出更恢弘的伟业。千里之行始于足下，与君共勉！

（结论0分，缺失 -1分，根据内容酌情加分）