HITICS大作业——–程序人生

摘要

本文将围绕hello的整个生命周期，具体介绍程序的预处理、汇编、编译、链接过程，以及系统的进程管理、存储管理、I/O管理等方面。本文将用具体的例子来阐述这些概念，以及概念背后的原理

关键词：Hello；进程；Shell；系统

第1章概述 -4-

1.1Hello简介 -4-

1.2环境与工具 -4-

1.3中间结果 -4-

1.4本章小结 -4-

第2章预处理 -5-

2.1预处理的概念与作用 -5-

2.2在Ubuntu下预处理的命令 -5-

2.3Hello的预处理结果解析 -5-

2.4本章小结 -5-

第3章编译 -6-

3.1编译的概念与作用 -6-

3.2在Ubuntu下编译的命令 -6-

3.3Hello的编译结果解析 -6-

3.4本章小结 -6-

第4章汇编 -7-

4.1汇编的概念与作用 -7-

4.2在Ubuntu下汇编的命令 -7-

4.3可重定位目标elf格式 -7-

4.4Hello.o的结果解析 -7-

4.5本章小结 -7-

第5章链接 -8-

5.1链接的概念与作用 -8-

5.2在Ubuntu下链接的命令 -8-

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

5.4hello的虚拟地址空间 -8-

5.5链接的重定位过程分析 -8-

5.6hello的执行流程 -8-

5.7Hello的动态链接分析 -8-

5.8本章小结 -9-

第6章hello进程管理 -10-

6.1进程的概念与作用 -10-

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

6.3Hello的fork进程创建过程 -10-

6.4Hello的execve过程 -10-

6.5Hello的进程执行 -10-

6.6hello的异常与信号处理 -10-

6.7本章小结 -10-

第7章hello的存储管理 -11-

7.1hello的存储器地址空间 -11-

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

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

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

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

7.6hello进程fork时的内存映射 -11-

7.7hello进程execve时的内存映射 -11-

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

7.9动态存储分配管理 -11-

7.10本章小结 -12-

第8章hello的IO管理 -13-

8.1Linux的IO设备管理方法 -13-

8.2简述UnixIO接口及其函数 -13-

8.3printf的实现分析 -13-

8.4getchar的实现分析 -13-

8.5本章小结 -13-

结论 -14-

附件 -15-

参考文献 -16-

第1章概述

1.1Hello简介

根据Hello的自白，利用计算机系统的术语，简述Hello的P2P，020的整个过程。

Hello.cP2P的全过程：程序预处理———–>编译—————->汇编—————–>链接————–>生成可执行文件——————>调用fork函数创建进程—————–>使用execve函数加载进程

1.2环境与工具

软件环境：Ubuntu22.04LTS

硬件环境：12thGenIntel(R)Core(TM)i7-12700H2.30GHz

工具：VSCode、vim、gdb、gcc、edb、objdump、readelf、Shell（Bash）

1.3中间结果

图1中间产物

Makefile：简化一些过程使用的文件，如编译、预处理、执行等等。

Hello.i：hello.c预处理的产物

Hello.s：hello.i编译后的产物

Hello.o：hello.s汇编形成的产物

Hello：链接形成的产物

Hellodump.txt：hello.o反汇编（OBJDUMP，下同）形成的产物

Helloelf2.txt：hello反汇编产物。

Helloelf.txt：对hello.o使用readelf的产物

1.4本章小结

本部分简要介绍了hello有关的基本情况，中间产物等。

第2章预处理

2.1预处理的概念与作用

预处理的概念：根据原始C程序中以#开头的语句（宏），对源代码进行替换、插入、删除等一系列操作，并最终生成.i文件（预处理文件）。如将所有包含#define后面的别名的语句全部替换为其代表的文本，或者将#include对应的头文件内容全部插入到C程序中。

预处理的作用：将宏定义替换为具体的变量名或者函数体，或者针对不同的宏定义选取不同的代码，最终形成完整的预处理文件。

如编译器将会把程序中与#define后面的宏命名相同的名称全部替换成该宏定义的内容，直至遇到第一个#undef。

又如编译器会根据#if、#elif等条件编译语句后的条件来取舍其包括的代码。

再如编译器会将#include后面的头文件内部代码全部拷贝进.c文件中。

2.2在Ubuntu下预处理的命令

命令如下所示：

图2预处理命令

最终生成的文件如下所示：

图3生成产物

2.3Hello的预处理结果解析

Hello.c中包含三个头文件：、和。在预处理后，原来的宏定义（#include）被替换，这三个头文件的内容被复制进了hello.i中。如下图所示：

图4-图5预处理后的程序

原hello.c剩余内容如下：(最底部）

图6预处理后原代码部分

2.4本章小结

预处理阶段，hello.c中的宏被编译器处理，经过一系列的替换、添加、删除等操作，最终生成了hello.i文件，为接下来的汇编等工作做好前期准备。

第3章编译

3.1编译的概念与作用

编译是指将预处理文件（.i）经编译器翻译为汇编文件（.s）的过程。根据不同的优化选项（-Og、-Ox（x=1,2,3）），最终编译产生的汇编文件也有所不同。此外，不同的机器、不同的操作系统，其编译出来的汇编文件也有所不同。

编译的作用：将高级语言翻译为机器语言，使之能够更好地被机器所理解并执行。

3.2在Ubuntu下编译的命令

编译命令如下图所示：

图7编译命令

编译后如图：

图8生成产物

3.3Hello的编译结果解析

hello.i被编译为hello.s后，其代码被翻译为汇编语句。hello.s的汇编语句中包含如下成分：

3.3.1常量

字符串常量”Hello%s%s”和“用法:Hello学号姓名秒数”（以Unicode形式存储）存放于如图所示区域：

图10常量

汇编中.string字段表明将部分空间开辟给该字符串。

3.3.2局部变量

局部变量i被存放在寄存器%ebp中，并在循环中被调用：

《———-

图11局部变量

3.3.3赋值操作

局部变量i在上述循环中被赋予初值0。相关汇编代码如下所示：

图12赋值操作

该段代码将立即数0传送给%ebp所在内存位置，并把高32位设置为0。

3.3.4算术操作

上述循环对局部变量i进行了自增操作。对应汇编代码如下：

图13自增操作

3.3.5关系操作

在条件分支【if（argc!=4）】中出现了比较是否相等操作。相关汇编代码如下：

图14关系操作

该部分将立即数4和存放于%edi的argc比较，若不相等则跳转到.L6段调用exit函数（jne==jumpifnotequal，条件跳转指令），相等则继续执行下列操作。

在循环体【for(i=0;i<8;i++)】中出现了比较大小的操作。相关汇编代码如下所示：

图15比较操作

该段代码将立即数7与存储于%ebp的数i进行比较。若i<=7（jle，jumpiflessthanorequalto）则跳转到.L3部分，否则继续执行下列操作。注意到此处与原代码不同的是，编译器将i<8翻译为了i<=7。

3.3.6指针操作

Hello.c中使用了字符串数组argv，并在以下语句中出现相关调用：

Argv数组的基址一开始存储于%rsi寄存器中，后移入%rbx寄存器：

图16基址移动

而后，printf函数调用了argv[1]、argv[2]：

图17参数传递

以上语句是将位于%rbx+0x16处的值（argv[2]的起始地址）传送给了寄存器%rcx（第四个参数），将%rbx+0x8处的值（argv[1]的起始地址）传送给了%rdx（第三个参数）。

最后，atoi函数调用了argv[3]，传值方式同上：

图18参数传递2

3.3.7控制转移

条件语句

原代码条件语句如下所示

图19原代码条件语句

该条件语句判断argc是否等于4，若不等于4则执行代码块内内容。对应汇编代码如下所示：

图20汇编代码的条件语句

此处先比较%edi的值和4的大小(cmpl$4,%edi，argc在%edi中），若不相等则跳转（jne.L6）到.L6段代码（即代码块内的内容）。此处使用了条件跳转指令jne和比较指令cmpl来实现该条件分支。

循环语句

原代码的循环语句如下图所示：

图21原代码的循环语句

该循环语句共执行8次循环体内部内容。其对应的汇编代码使用了下列结构：

图22汇编代码的循环语句

若上述的条件判断为假，代码会跳转到.L2段。此时会先比较%ebp中的值（i）是否小于等于7，若满足条件则跳转到循环体内部代码（.L3段）。在.L3段的最后，使用了addl指令实现了i++的操作。

由上述可知，条件分支和循环语句的实现离不开判断语句（cmp、test等）和条件跳转语句（jne、jle等）。

3.3.8函数调用

函数参数传递

主函数main中共有两个参数：argc（存放于%rdi中）和argv（存放于%rsi中）。这两个参数由命令行传递，故其传递过程无法在hello.s中体现。

Hello.c中一共有四个函数有参数传递过程：printf、exit、atoi和sleep。

Printf参数传递：

第一处：

图23第一处printf

对应汇编代码：

图24汇编代码

该处把存储于.LC0段的字符串常量传递给了%edi（第一个参数）。注意到此处使用了puts函数代替了printf函数。

第二处：

图25第二处printf

对应汇编代码：

图26汇编代码

该段代码将函数体内的三个参数分别传给了%esi、%edx和%ecx。这之后调用了__printf_chk函数执行字符串的打印。

Exit函数部分：

图27exit函数

汇编代码：

图28exit调用对应的汇编代码

参数1传给了%edi后调用了exit函数。

Atoi函数和Sleep函数部分：

图29sleep和atoi函数

汇编代码：

图30sleep和atoi函数的汇编代码

Atoi函数首先将参数传递给%rdi，调用该函数，而后Atoi的返回值再赋给sleep（%eax->%edi）的参数，调用sleep。

函数调用

由上述可知，所有调用函数的操作均使用了call语句。

3.4本章小结

.i文件需要先编译为.s文件才能进行后续的操作。相比.i文件，.s文件更接近机器语言，更容易被机器执行。

第4章汇编

4.1汇编的概念与作用

汇编的概念：汇编即将汇编文件.s翻译为可重定向二进制文件.o的过程

汇编的作用：将汇编语言翻译为机器码，使之能够更好地被机器所理解。同时，这一操作使得文件可以被链接，为后续的链接工作做好准备。

4.2在Ubuntu下汇编的命令

命令如下：

图31汇编命令

4.3可重定位目标elf格式

一般elf文件的格式如下：

图32ELF文件的基本格式

通过对hello.o使用readelf得到以下内容：

首先是elf头：

图33ELF头

通过elf头可以知道许多信息，例如系统为64位（Class）、使用小端法（Data）、机器类型、版本号等等。

接下来是各节的头（SectionHeader），这一部分会保存各个节起始位置的地址、名称、大小、偏移量等信息。

图34节头表

以上节中，.text节保存代码，.data节保存已初始化的全局/静态变量，.bss节保存未初始化或初值为0的全局/静态变量，.symtab为符号表（包含函数以及全局/静态变量），.strtab为字符串表，.rodata为只读数据区。带.rel开头的部分均为重定向后的部分。.eh_frame则是栈回溯时使用的信息，当需要查看某一时刻的栈帧变化将会调用这部分信息。

图35sectiongroup、程序头表和动态链接部分

由于目标文件不可执行，故不存在“段”，从而不存在programheader。

由于此时并未进行链接操作，故dynamicsection和sectiongroup并不存在。

以下是重定位节和符号表部分：

图36重定位部分和符号表

其中.rela.text是重定位的代码，即存放着.text节的重定位信息。.rela.text此时并不会存放函数的绝对地址，而是存放相对于.text的偏移量，因为系统并未为程序分配内存，故不知道各函数的具体位置。

.rela.text的Type部分显示着各函数/变量的重定位类型。其中R_X86_64_32为重定位对绝对地址的引用，R_X86_64_PC32为重定位对PC地址的相对引用，R_X86_64_PLT32为PLT的延迟绑定。

.rela.eh_frame保存着栈帧入栈时的相关信息

.symtab部分则是一些符号表，包含函数、全局变量、静态变量以及一些字符串常量等等。这些符号是链接器在符号解析过程中需要处理的部分。

4.4Hello.o的结果解析

以下是objdump反汇编后的结果，首先是main函数的起始部分：

图31main函数起始部分的汇编

可以看到相比.s文件，其增添了指令对应的机器码。此外，它将.s文件中所有跳转语句（jne、jle等）的.L2、.L6等替换成了相对于main函数的偏移量（如jne19

）。

由上可以知道汇编语言在被gcc汇编后会转换成机器码，而不同指令的机器码其对应的长度是不同的。一些指令的操作数也会被嵌入到对应的机器码中，如cmp、mov、sub等。

其他全部重定位部分如下图所示：

图38重定向部分的汇编

和上文类似，调用函数的call指令后面的操作数全部变成了相对main的偏移量。而且有一些函数，如getc、__printf_chk等，由于并未进行链接，其在转换成.o文件时并没有出现实现对应功能的机器码。

4.5本章小结

汇编的过程即将汇编语言转换为带有机器码的.o文件。机器码的形式使得机器可以识别并对其做出反应。尽管如此，.o文件无法被执行，然而.o文件可以被重定向，这使得其可以与其它的目标文件进行链接，从而得到完整的可执行文件。

第5章链接

5.1链接的概念与作用

链接的概念：通过调用链接器ld，对一系列的目标文件进行符号解析和重定向等操作，最终整合生成可执行目标文件的过程。

链接的作用：对目标文件中的代码节、数据节等重新进行组合、排序、复制、插入等，最终形成一个具有完整功能的可执行目标文件。

此外，链接的存在使得程序员不必将所有的代码全部整合到一个文件中去，这大大降低了编程时的麻烦，并使得项目的组织变得清晰且有序。动态链接的存在降低了程序对内存的要求，共享库使得多个文件可以共享同一份代码，也降低了内存的使用量。

5.2在Ubuntu下链接的命令

图39链接时的命令

以上为链接时的命令。

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

以下是hello通过readelf得出的具体信息。

首先是ELF头：

图40ELF头

相比链接前，该段的一些数据发生了变化，例如programheader的相关数据。而后是各节的header：

图41节头表

图42节头表

相比链接前，这一部分多了几个头，如.hash、.init、.plt、.got等等。其中GOT为全局偏移量表，主要和PLT配合用于动态链接库相关的重定向。

接下来是节到段的映射，以及与动态链接有关的部分。

图43链接相关

而后是与重定向有关的内容：

图44重定向相关

接下来是动态链接相关的和hello.o中的符号表：

图45符号表

5.4hello的虚拟地址空间

edb下hello的数据段如下所示：

图46DataDump

节头表的一些头地址可以再此处找到，例如.text头（004010e0）。这一段仅展示到.rodata头为止（地址为00402000）。

堆栈区域如图所示：

图47Stack

代码区域如图所示：

图48代码区域

5.5链接的重定位过程分析

观察objdump-d-rhello指令反汇编后的结果如下。首先，hello中多出了以下部分：

图49过程链接表

此段为过程链接表PLT，和全局偏移量表GOT（GlobalOffsetTable）一起对共享库中的函数进行管理。共享库的函数使用延迟绑定机制，仅在过程被第一次调用的时候进行过程地址的绑定，这样会大大节省程序的内存占用。PLT和GOT的协调配合使得调用共享库的函数成为可能。

以下是对应共享库函数的PLT：

图50共享库函数的PLT

此外，hello中还多了_start函数部分，这是程序的入口函数：

图51_start函数

Main函数也进行了重新构造：

图52main函数

结尾处还多了fini：

图53fini

可以观察到，上述所有的语句全部都与一个绝对地址绑定，并且call和jmp（以及变种）后的操作数变成了绝对地址，一些变量的值变成了其地址值。可知，重定位过程中，（非共享库）函数与内存地址进行了绑定。

由上可知，链接器在链接的过程中进行了重定位，而与hello.o不同的是，程序员所写的代码均与内存中的地址进行了绑定，相对应的偏移量操作数换成了具体的地址值。而共享库由于延迟绑定机制，库函数地址只有在它们第一次被调用的时候被确定，而调用操作由PLT和GOT共同管理。

5.6hello的执行流程

以下是edb执行hello的执行过程：

调用ld-linux-x86-64.so.2的内部函数加载hello(loader)

地址：0x00007f998ec22290

图54ld-linux-x86-64.so.2

执行_start

地址：0x00000000004010e0

图55_start

执行__libc_start_main

地址：0x00007f33c4029dc9

图56_libc_main_start

执行__cxa_ateixt

地址：0x00007fbe766458c0

图57__cxa_ateixt

调用__setjmp

地址：0x00007f6952a421e0

图58__setjmp

……

6.执行main

函数名：main地址：0x0000000000401115

图59main

7.程序调用__printf_chk函数（通过PLT和GOT）

地址：0x0000000000401040（PLT）

图60__printf_chk

8.程序调用atoi函数（通过PLT和GOT）

地址：0x0000000000401090（PLT）

图61atoi

9.程序调用sleep函数（通过PLT和GOT）

地址：0x00000000004010c0（PLT）

图62sleep

10.上述7-9步骤循环8次

11.程序调用getc函数（通过PLT和GOT）

地址：0x0000000000401090（PLT）

12.调用exit函数

地址：0x00007fbb0da455f0

图63exit函数

5.7Hello的动态链接分析

hello程序中的动态链接项目有printf（__printf_chk）、exit、getchar（getc）、sleep。

动态链接的共享库函数采用延迟绑定机制，仅在第一次调用的时候这些函数的地址才会被确定。以__printf_chk函数为例，根据PLT和GOT得知该函数对应的地址信息将会被存放于0x404028。故观察该区域：

dl_init前：

图64dl_init前

dl_init后：

图65dl_init后

可以看到在动态链接后，这一段的信息发生了变动。该过程为：首先程序跳转到了PLT中地址为0x4010a0的部分，而后通过PLT取出GOT对应条目，再通过一系列操作最终得到__printf_chk的函数地址，而后返回。

5.8本章小结

通过链接，程序员可以通过多文件编译的方式来实现更高效的程序编写，同时可以一定程度上减少程序所需的内存空间，提高程序的性能。共享库和动态链接的存在使得程序员在调用函数的时候可以让多个文件使用同一个副本，大大减少了函数调用时的麻烦。

第6章hello进程管理

6.1进程的概念与作用

进程的概念：进程即一个执行中程序的实例。

进程的作用：使用进程这一抽象概念，系统可以更好地管理各个程序的运行状况，可以同时独立地执行多个程序，等等。

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

Shell-bash的作用：shell作为一种可交互的程序，可用于管理系统的前后台作业，可以让用户执行一些系统命令、发送信号、创建并管理进程等等。Shell相当于用户和内核之间的桥梁。

Shell-bash的处理流程：Shell接受到用户命令或读取脚本命令———->Shell解析命令（对命令进行拆分解析）—————–>Shell根据解析结果调用相关程序或执行相应命令。

一般而言，Shell命令中有一部分是内置命令。若出现内置命令，Shell有一套专门的机制用于处理这些内置命令。若为执行某一程序，Shell会创建进程（fork），而后根据命令来将其置于前台/后台，而后执行该进程（execve）。一般而言，进程终止后会对其进行回收。

6.3Hello的fork进程创建过程

Shell中输入./hello————>Shell解析该命令——->Shell检查该文件是否存在，若存在则创建进程。

创建进程时，Shell会将hello分配到一个单独的进程组中。一般而言，fork函数创建进程会为该进程分配一个唯一的PID（进程号），各个进程的进程号各不相同，进程组号默认为该进程的进程号。创建出的进程为父进程的一个副本，但与父进程独立。Fork函数会为这些进程创建mm_struct，并且将进程虚拟页均标记为只读，并将这两个进程的区域结构标记位私有的写时复制。

6.4Hello的execve过程

Shell创建hello进程———–>调用execve函数使hello进程运行。Execve运行过程如下：

删除已存在的用户区域
映射私有区域
映射共享区域
设置程序计数器

6.5Hello的进程执行

进程上下文切换的过程如下所示：

图66进程的上下文切换

一般而言，系统并不只执行hello进程，一些系统级进程需要在内核同步执行。当一些事件如中断发生的时候，或是用户执行某种系统调用，用户态运行下的程序需要把控制权转交给内核进行处理，此时系统会通过上下文切换的方式把当前用户态的状态保存，而后切换到内核态执行相应操作，等待操作执行完毕后再将程序的控制权转交给用户代码，从而再切换回用户态继续执行当前程序。

除了上下文调用，大多数进程采取并发机制。Hello程序是在用户态下执行的。而此时操作系统仍然有其它进程需要执行，例如桌面、终端，或是其它的应用程序，故操作系统会让这些进程轮流执行，而轮流的速度很快以至于产生了这些程序在一起执行的假象，此为所谓的并发执行，即多个逻辑流的执行在时间上有所重叠，因而同时执行。各进程包括hello在不同的时间片下并发的执行着。

6.6hello的异常与信号处理

可能出现的异常：中断异常、缺页异常、陷阱（系统调用）

信号：SIGINT、SIGTSTP、SIGKILL、SIGCONT

Hello执行过程中，输入的随机字符串其并不会处理，而是等到程序结束后再进行处理：

图67随机键盘输入

缺页异常的处理方式：触发缺页处理程序，从磁盘中读取页到物理内存中，进行页面调度。

陷阱：程序中存在sleep函数，该函数会调用内核操作使程序休眠一段时间，此时程序会执行syscall指令，控制权被移交给陷阱的相关处理程序，调用对应的内核程序让进程休眠。

SIGINT：该信号会触发中断异常，此时程序终止运行。

该信号可以通过Ctrl+C发送给进程。如图所示：

图68Ctrl+C触发SIGINT

此时通过ps命令查看：

图69SIGINT下的ps

可以发现该进程不复存在（被回收）。

SIGTSTP：由终端发送的停止信号。该信号会使前台进程停止运行，直到收到SIGCONT为止。

SIGTSTP可以通过Ctrl+Z进行发送。如图所示：

图70Ctrl+Z发送SIGTSTP

此时通过ps命令查看：

图71SIGTSTP下的ps

或通过pstree查看如下所示：

图72SIGTSTP下的pstree（部分）

T表示Terminated，此时可以通过fg命令使其重新运作（或者kill-18[进程号]，用于向进程发送SIGCONT信号）

通过jobs命令获取进程号并让其重新运作：

图73jobs和fg命令

SIGCONT：见上，该信号可让停止进程重新运行。

SIGKILL：杀死进程，由kill发送，不可阻塞。如下所示：

Kill前：

图74kill前

Kill后：

图75kill后

6.7本章小结

进程调度使得hello得以正常运行及回收，同时使得操作系统中的其它程序合理有序的运行。

第7章hello的存储管理

7.1hello的存储器地址空间

逻辑地址：表现为【段标识符：段偏移量】，逻辑地址需要通过MMU（MemoryManagementUnit，内存管理单元）变换成物理地址进行寻址。在保护模式下，段标识符为GDT（全局描述符表）的索引。

线性地址：当地址空间中的整数是连续的，这样的地址空间为线性地址空间，对应的地址称为线性地址。逻辑地址经过转化之后会变成线性地址。

虚拟地址：是一种线性地址，对应着虚拟内存中的某个位置。

物理地址：CPU用于访问物理内存时使用的地址，对应着物理内存上的一串字节序列。

可执行文件hello中存放的地址均为虚拟地址，具体调用的时候需要翻译成物理地址进行访存。

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

Intel的段式管理方式实现了从逻辑地址到线性地址（虚拟地址）的转变。

操作系统在实模式下，通过运算将逻辑地址变换为线性地址，具体公式为：线性地址=段基址<<4+段偏移量。而在保护模式下，线性地址的计算也采用类似的方法，但是不再是段基址，而是段标记值（段描述符）。

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

线性地址到物理地址的变换需要通过MMU来完成。Hello程序想要访问一个物理页，首先须生成一个虚拟地址发送给MMU，MMU将其翻译为物理地址而后发送给内存，内存再返回相应的索引信息。

虚拟地址一般由虚拟页号VPN（VirtualPageNumber）和虚拟页偏移量VPO（VirtualPageOffset）组成。访问内存的时候，VPN获取到物理页号PPN（第一个P是Physical），再将PPN与VPO串联得到了相应的物理地址。

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

为了加快对内存的访问，系统引入了TLB（快表，TranslationofLookasideBuffer），它被存放在MMU的一个Cache中。

TLB的虚拟页号访问和上述类似，但是VPN又可以分为TLB索引（TLBI）和TLB标记（TLBT）。访问物理内存可以直接使用VPN进行翻译。通过TLB访问内存都是在MMU上进行的，速度比普通的虚拟页（在磁盘上）快。

图76TLB虚拟地址组成

多级页表可以用来节省页表所占用的空间。前几层页表均指向下一层页表的基址，而最后一层页表指向物理内存。如果有某一级的页表为空，那么其后所有的页表均不存在。

通过多级页表的访问与单个页表的方式较接近，区别在于需要从一级页表取出二级页表的基址，而后根据该基址继续访问下一级页表，以此类推。但这样会大大节约空间的开销，而且速度上不比单个页表慢。

图77k级页表的访问

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

程序得到物理地址后开始对物理内存进行访问。首先访问三级Cache中是否存在相关的物理页。

访问Cache的地址和TLB类似，其地址结构如图所示：

图78Cache地址的构成

CT为标记位，CI为组索引，CO为块偏移量。地址之所以如此设计，与Cache的结构有关。一般Cache的结构如下所示，包含S组，每组E行，每行B位缓存。

图79Cache一般结构

寻址方式如下：首先通过组索引找到对应的组，而后根据标记位找到对应的行，再根据块偏移找到该行缓存对应的起始位置。这样就完成了一次访问。

对Cache的访问也有失败的情况，称为缓存不命中。不命中的类型一般有三种：冷不命中，冲突不命中和容量不命中。冷不命中即缓存内并没有存放所需的索引条目，或者缓存为空。容量不命中则是工作集（某阶段访问缓存块的某个相对不变的集合）超出了缓存的大小而导致的。引发冲突不命中的其中一种因素是多个不同地址映射到了同一组内的同一行中，造成了存取的时候可能会把原先的值覆盖掉。Cache访问的缓存不命中导致需要寻找的值必须再次从低一级的缓存甚至磁盘中寻找，这会大大增加时间开销。

以上为Cache的读过程，Cache也可以进行写。写主要有两种方式，直写和写回。直写即将缓存的字立即写入低一层内存，写回则是在缓存需要替换某一块的时候才把该块写入低一层内存中，但是写回需要额外的修改位来标记块是否被修改过。

与上文类似，存在Cache的写不命中，即缓存区找不到要写的数据。主要有两种策略，其一是写分配，即将所需数据从低一级的内存读入Cache并更新对应的块；其二是非写分配，即不读入Cache，直接写入低一层。一般而言，直写是非写分配的，而写回是写分配的。

7.6hello进程fork时的内存映射

系统执行hello程序的时候，会调用fork函数创建进程。Fork函数会为该进程创建一个（代码、数据、栈帧状态、区域结构和页表等）一模一样但是独立于父进程的副本，即子进程，并为该子进程分配一个唯一的PID。同时，fork为该进程分配了虚拟内存并创建了当前进程的mm_struct（用于维护当前的进程状态）。Fork将这两个进程的区域结构均标记为私有的写时复制，并将这两个进程的每一页标记为只读。

7.7hello进程execve时的内存映射

hello进程被创建后，系统执行execve函数运行该进程，过程如下：

删除已存在的用户区域。
映射私有区域。这是为新程序的代码、数据、bss和栈区创建新的区域结构（均为私有写时复制）。代码和数据区被映射到.out文件的.text和.data区。bss区是请求二进制零的，被映射到长度不为零的匿名文件上；栈区也是请求二进制零的，被映射到长度为零的匿名文件上
映射共享区域。hello中存在共享库函数如printf、getchar等，这些程序通过libc.so动态链接到该程序，对应的hello会讲这些程序映射到虚拟地址空间的共享区域上。
设置程序计数器。execve需要设置当前的程序计数器，使之指向hello程序的入口。

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

缺页故障发生在缓存中找不到对应的页的时候。一般而言此时的虚拟页表对应条目的状态为未分配或者未缓存，有效位为0。缺页中断会触发缺页异常处理程序进行页面调度操作，若物理内存已满则从物理内存中选择一个牺牲页进行替换。

现在的操作系统基本上使用按需页面调度方式处理缺页异常，即当真正使用该页面时才进行页面调度。

对于Linux系统，首先MMU会判断虚拟地址的合法性，若不合法则会触发缺页中断，产生段错误信息，从而终止该程序，否则程序继续执行；而后，MMU会判断该地址的内存访问是否合法，若非法则处理方式同上。若以上步骤都合法，则不会触发缺页中断，则会正常处理缺页异常。

7.9动态存储分配管理

动态内存分配是通过堆实现的，而该操作是由动态内存分配器来完成。分配器将堆视为不同大小的内存块，每个内存块可视为虚拟内存片，其中空闲的虚拟内存片可以用于分配动态内存。

分配器有两种风格。显式分配器需要程序显式地释放任何已分配的块，而隐式分配器则会自动回收程序不需要的已分配块（通常这一机制也被称为垃圾收集）。显式分配可以通过malloc函数来实现，同时需要free函数将其释放。

一些分配器在分配内存的时候会发生碎片现象，也就是当前内存不能满足分配的请求时，这部分内存就会变成碎片。碎片有分外部碎片和内部碎片。内部碎片的大小和数量可以估量，而外部碎片由于内存的分散性，使得其量化极其困难，故大多数分配器都会尽可能的维持少量的大空闲块来避免这类碎片的发生。

分配器的实现通常采用空闲链表的方式，这些空闲链表中记录着和块有关的信息，以区别空闲块和已分配块，以及区分块的边界。隐式空闲链表可以用一种线性的方式对已分配块和空闲块进行排列，实现方式十分简单，但块分配和对快的总数是呈线性关系的，所以对于通用的分配器，隐式空闲链表是不适合的。故有了显式空闲链表。这种链表为双向链表，把访问时间降低到了空闲块数量的线性时间，而其维护策略可以是LIFO（后进先出）的，也可以是按照地址顺序来维护的。但是显式空闲链表也有使内部碎片程度提高的风险。

当应用发起内存申请时，分配器会使用适当的放置策略来请求空闲块，而后通过适当的分割来进行空闲块的分配，最后为了避免假碎片的产生，分配器必然要对相邻的空闲块进行合并操作。

如今一些高级语言，如Java，提供了垃圾回收机制，使得分配内存和释放内存变得更加方便。

7.10本章小结

虚拟内存为程序提供了施展手脚的空间，动态内存分配解决了程序的空间问题，fork和execve使得程序能正常且独立地运作。而对于程序逻辑流中发生的一系列事件，操作系统也有对应的处理方案。

第8章hello的IO管理

8.1Linux的IO设备管理方法

设备的模型化：文件

设备管理：unixio接口

在Linux/Unix中，一切设备都被模型化为文件进行管理，所有的读和写操作都会被视为文件的读和写。

8.2简述UnixIO接口及其函数

Unix系统中常用的I/O函数主要有open、read、write、lseek等。

函数open用于将给定的文件名转换成对应的文件描述符，并且返回描述符数字。其原型为：

intopen(char*filename,intflags,mode_tmode)

其中，flags控制打开文件的方式，如只读方式、只写方式、可读可写方式等。参数mode则指定了新文件的访问权限位。

read函数用于读取文件中的内容，并把它存储到缓冲区中。该函数是按字节读取的，而对于字符的读取还可以采用标准I/O库里面的fgets函数。

write函数用于将缓冲区里的字节写入对应文件中。而字符串的写入还可以采用标准I/O库里的fputs函数。

lseek函数可以用于修改当前文件的位置。

除了上述函数以外，进行I/O操作还可以采用RIO包，该包的函数是线程安全的，因而有着更好的健壮性。当然，C语言还有标准I/O库用于替代上述的函数。标准I/O库采用了流的概念进行对应功能的实现。

8.3printf的实现分析

字符序列输入到终端：以下是printf的函数体：

intprintf(constchar*fmt,…)
{
inti;
charbuf[256];
va_listarg=(va_list)((char*)(&fmt)+4);
i=vsprintf(buf,fmt,arg);
write(buf,i);
returni;
}

第一个参数为格式串，后面的省略号代表着可变参数。printf函数通过vsprintf函数将字符串分割成元字符放入buf中，并将格式串全部替换为参数列表中的参数，最终返回参数的个数。而后，printf函数再通过write函数把buf里的字符全部输出到终端上。由于write是系统调用，故此处需要使用syscall指令触发陷阱机制，调用相关的处理函数对write进行处理，从而实现printf函数字符串的输出。

字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。

显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。

8.4getchar的实现分析

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

getchar等调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。

8.5本章小结

通过一系列的I/O接口，hello得以和文件进行交互，甚至可以和外部设备进行操作。Unix系统将设备抽象成文件的操作，使得各设备的交互大大简化了。

结论

用计算机系统的语言，逐条总结hello所经历的过程。

你对计算机系统的设计与实现的深切感悟，你的创新理念，如新的设计与实现方法。

hello程序从生到死，经历了预处理、编译、汇编、链接等操作，而后又经历了进程的创建、运行、终止、回收等操作，这其中不乏操作系统和硬件的倾力配合。

hello.c通过预处理，形态变得完整，而后通过汇编、编译的过程，hello程序从汇编语言到机器语言，正一步步地投入机器的拥抱中。最终，hello.o通过链接器与其它.o文件水乳交融、通过动态链接与.so文件共享，最终生成了完整的hello程序，这样hello就迈入了可执行的第一步。

紧接着，通过shell的调度，hello被纳入到新创建的进程中，并在execve的驱动下走上了执行的快车道。在这期间，异常控制流处理着hello运行过程中所发生的一系列事情，例如读和写、程序的中断和停止等等。这一系列的过程使得hello得以正常运行。最终，hello完成了它的生命周期，shell完美的回收了它，属于hello的舞台就此落幕。

计算机系统便是这样由软硬件共同编写的华美乐章，每一个操作、每一条语句都是这个大乐章中不可或缺的音符。当然这个乐章并非完美，仍然需要我们去不断地完善它。

附件

附件如图所示：

图80附件