哈工大计算机系统大作业 程序人生-Hello’s P2P From Program to Process

哈尔滨工业大学

计算机系统

大作业

题 目程序人生-Hello’s P2P

专 业 计算机科学与技术

学　　 号

班 级

学 生

指 导 教 师刘宏伟

计算机科学与技术学院

2022年5月

摘 要

本文对Hello程序为例进行分析，研究一个程序从一个高级C语言程序开始，经过预处理、编译、汇编、链接等到最后变成一个可执行文件的生命周期，以此来了解系统如何通过硬件和系统软件的交织、共同协作以达到运行应用程序的最终目的。将全书内容融会贯通，帮助深入理解计算机系统。

关键词：计算机系统；预处理；编译；汇编；链接；进程管理；存储管理；I/0；

目 录

第1章 概述

1.1 Hello简介

1.2 环境与工具

1.3 中间结果

1.4 本章小结

第2章 预处理

2.1 预处理的概念与作用

2.2在Ubuntu下预处理的命令

2.3 Hello的预处理结果解析

2.4 本章小结

第3章 编译

3.1 编译的概念与作用

3.2 在Ubuntu下编译的命令

3.3 Hello的编译结果解析

3.4 本章小结

第4章 汇编

4.1 汇编的概念与作用

4.2 在Ubuntu下汇编的命令

4.3 可重定位目标elf格式

4.4 Hello.o的结果解析

4.5 本章小结

第5章 链接

5.1 链接的概念与作用

5.2 在Ubuntu下链接的命令

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

5.4 hello的虚拟地址空间

5.5 链接的重定位过程分析

5.6 hello的执行流程

5.7 Hello的动态链接分析

5.8 本章小结

第6章 hello进程管理

6.1 进程的概念与作用

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

6.3 Hello的fork进程创建过程

6.4 Hello的execve过程

6.5 Hello的进程执行

6.6 hello的异常与信号处理

6.7本章小结

第7章 hello的存储管理

7.1 hello的存储器地址空间

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

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

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

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

7.6 hello进程fork时的内存映射

7.7 hello进程execve时的内存映射

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

7.9动态存储分配管理

7.10本章小结

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

8.2 简述Unix IO接口及其函数

8.3 printf的实现分析

8.4 getchar的实现分析

8.5本章小结

结论

附件

参考文献

第1章 概述

1.1 Hello简介

Hello经历了所有计算机程序从诞生到运行的全过程：编写高级语言程序；预处理、编译、汇编、链接；fork创建子进程；execve加载并运行；受到系统的存储管理与I/O管理，最后结束运行，被内核、bash回收。理解了Hello的P2P，020的整个过程，那么就能对整个计算机系统的工作原理作出更深刻的理解。

1.1.1 P2P

P2P(From Program to Process)，意为程序到进程。Hello的P2P过程如下：

（1）编辑hello.c文本。

（2）GCC编译器驱动程序完成从源文件到目标文件的转化：

(i) 预处理：cpp根据以字符#开头的命令，修改原始的C程序，得到hello.i；

(ii) 编译：ccl将hello.i翻译成文本文件hello.s，它包含一个汇编语言程序，每条语句都以一种文本格式描述了一条低级机器语言指令；

(iii) 汇编：as将hello.s翻译成机器语言指令，把这些指令打包成可重定位目标程序，并将结果保存在目标文件hello.o中，它是一个二进制文件；

(iv) 链接：ld将hello.o与printf.o合并，得到可执行目标文件Hello。

（3）在shell中启动，调用fork函数创建进程，调用execve函数加载并运行Hello，通过内存映射，分配空间等让Hello与其他进程并发进行，到这里Hello就顺利变成了进程。

1.1.2 020

020 (From Zero to Zero)，意为从0到0。源程序从无到有被编写，所以是从0开始，然后编译生成可执行目标文件Hello，而后在运行的时候拥有了自己的进程，也在内存中存储了相关信息，进程终止之后被回收并释放，所以是以0结束。这就是Hello的020过程。

1.2 环境与工具

1.2.1硬件环境

CPU: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz

RAM: 16GB RAM (15.8GB可用)

Disk: 512GB SSD

1.2.2软件环境

Windows 10; VirtualBox11; Ubuntu 16.04 LTS 64

1.2.3开发工具

Visual Studio 2010 64位以上；CodeBlocks 64位；vi/vim/gedit+gcc

1.3 中间结果

1.4 本章小结

本章介绍了P2P和020的过程，以及为编写本论文使用的软硬件环境和开发与调试工具，同时列出了本实验得到的中间结果文件及其作用。

第2章 预处理

2.1预处理的概念与作用

预处理器根据以字符#开头的命令，修改原始的C程序。如hello.c中第一行的#include 命令告诉预处理器读取系统头文件stdio.h的内容，并把它直接插入程序文本中。

预处理的结果得到了另一个C程序，通常以.i作为文件扩展名。

2.2在Ubuntu下预处理的命令

Linux下预处理命令：

（1）gcc -E -o hello.i hello.c

（2）cpp hello.c hello.i

输入预处理命令后，我们得到了如图所示的已完成预处理的文件：

图2-1 预处理过程

2.3 Hello的预处理结果解析

修改得到的C程序hello.i从hello.c的23行增加到3105行，同时发现main函数在文件的最后部分。预处理对头文件和宏定义进行了操作，所有的#include等语句全部被替换，取而代之的是一些路径以及用到的相关语句。并且预处理同时也删除了所有的注释信息。

2.4 本章小结

本章介绍了预处理的概念、作用以及实现方式。查看并分析了hello.c在Ubuntu下预处理的结果。

第3章 编译

3.1 编译的概念与作用

编译器将后缀为.i的文本文件翻译成后缀为.s的文本文件，它包含一个汇编语言程序，其中的每条语句都以一种文本格式描述了一条低级机器语言指令。

汇编语言是非常有用的，因为它为不同高级语言的不同编译器提供了通用的输出语言。

3.2 在Ubuntu下编译的命令

Linux下编译命令：

（1）gcc -S hello.c -o hello.s

（2）ccl hello.i -o hello.s

输入编译命令后，我们得到了如图所示的汇编语言文件：

图3-1 编译过程

3.3 Hello的编译结果解析

3.3.1数据

Hello的后面是两个%s类型的字符串，对应着我们输入的前两个变量：学号和姓名。

图3-2 printf语句中的格式串

分析汇编代码，能够看出循环变量i所存储的位置在-4(%rbp)处。

图3-3 循环变量i声明及变化

argc被存储在-20(%rbp)的位置，argv被存储在-32(%rbp)的位置。

图3-4 变量argc和argv的存储

3.3.2赋值

根据上文，结合这段汇编代码可知把存储在-4(%rbp)位置的i赋值为0。其中movl表示操作的对象是四个字节。

图3-5 给变量i赋值

3.3.3类型转换

调用函数atoi，其参数为argv[3]，这个函数将字符串转换为整型。

图3-6 类型转换

3.3.4算术操作

这条汇编代码将变量i的值+1.

图3-7 算术操作

3.3.5关系操作

地址-20(%rbp)处存储的是argc的值，将argc的值与4进行比较，如果相等则跳转到L2继续执行。

图3-8 关系操作1

地址-4(%rbp)处存储的是i，将i的值与8进行比较，若比较结果为小于等于则跳转到L4，继续执行循环体，若大于则跳出循环。

图3-9 关系操作2

3.3.8数组/指针操作

数组argv存储在地址-32(%rbp)处。

图3-10 数组的存储

然后通过指针访问argv[1], argv[2]和argv[3]的存储地址，将字符串的值存储在寄存器中，作为参数传递给函数printf和atoi。

图 3-11 指针寻址访问数组

3.3.9控制转移

1. if语句

判断argc是否等于4，若相等则跳转，执行后续操作，若不等则继续执行下一条语句。

图3-12 if语句

1. for循环语句

先将变量i赋初值0，然后跳转到L3，将i的值与8进行比较，如果i小于等于8则执行循环体，单次循环结束后i++，重复上述操作直到i大于8跳出循环。

图3-13 for循环语句

3.3.10函数操作

main函数

传参为argc和argv，分别存储在-20(%rbp)和-32(%rbp)中。返回值存储在%eax中。

puts函数

取出.LC0(%rip)中的字符串存入%rdi中，作为参数传递给puts。

图3-14 puts函数

printf函数

将argv[1]和argv[2]的值取出，存储在%rsi和%rdx中，取出.LC1(%rip)处的字符串存入%rsi中，作为参数传递给printf。

图3-15 printf函数

exit函数

将立即数1赋值给%edi，作为参数传递给exit。（exit(1)）

图3-16 exit函数

1. atoi函数

通过指针将argv[3]的值存入%rax中，再将%rax赋给%rdi，参数通过%rdi进行传递，返回值存储在%eax中。

图3-17 atoi函数

1. sleep函数

将%eax中存储的atoi函数的返回值赋给%edi，参数通过%edi进行传递，通过call指令调用。

图3-18 sleep函数

1. getchar函数

通过call指令直接调用，无需传参。

图3-19 getchar函数

3.4 本章小结

本章讲述了编译的概念和作用，并结合hello.c的编译结果对于汇编语言中的各部分以及各种操作进行了详细的说明。在编译完成的汇编语言程序中，我们可以看到汇编代码对内存以及寄存器的各种底层操作。理解汇编语言和编译器等细节是理解更深和更基本概念的先决条件。

第4章 汇编

4.1 汇编的概念与作用

汇编器将hello.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件hello.o中。

4.2 在Ubuntu下汇编的命令

Linux下汇编命令：

（1）gcc hello.s -c -o hello.o

（2）as hello.s -o hello.o

图4-1 汇编过程

4.3 可重定位目标elf格式

图4-2 通过命令导出elf文件

4.3.1 ELF头

图4-3 ELF头

ELF头以一个16字节的序列开始，这个序列是对于声称该文件系统下一些字的大小等信息的描述。而后包含一些能够帮助链接器语法分析并解释目标文件的信息，包括ELF头的大小、目标文件的版本、机器类型、节头部表的文件偏移、以及节头部表中条目的大小和数量。

4.3.2节头表

图4-4 节头表

节头表描述了.o文件中每一个节出现的位置、大小，目标文件中的每一个节都有一个固定大小的条目。

4.3.3重定位节

图4-5 重定位节

重定位节包含了在代码中使用的一些外部变量等信息，在链接的时候需要根据重定位节的信息对于某些变量符号进行修改。链接的时候链接器会根据重定位节的信息对于外部变量符号决定选择何种方法计算正确的地址，例如通过偏移量等信息计算。

本程序需要重定位的信息有：.rodata中的模式串，puts，exit，printf，atoi, sleep，getchar。

4.3.4符号表

图4-6 符号表

symtab是一个符号表，它存放于程序中定义和引用的函数和全局变量的信息。例如本程序中的getchar、puts、exit等函数。

4.4 Hello.o的结果解析

从hello.o的反汇编中可以看出，机器语言中每个不同的指令，即使操作数不同，长度也是固定的，相同的指令具有相同的前缀。依照这个原则，如果有了机器码和汇编指令的对照表，就可以完成汇编语言与机器语言的互相翻译。

(a)hello.s (b)asm_hello.s

图4-7 hello.s与hello.o的反汇编结果对照

（1）分支转移：反汇编代码跳转指令的操作数由段名称变成了确定的地址。

（2）函数调用：在hello.s中，函数调用之后直接跟着函数名称，而在反汇编程序中，call的目标地址是当前下一条指令。这是因为hello.c中调用的函数都是共享库中的函数，最终需要通过动态链接器才能确定函数的运行时执行地址。

（3）数的表示：hello.s里的数是十进制表示，asm_hello.s里的数是十六进制表示。

（4）全局变量访问：hello.s中直接通过段名称+%rip访问rodata，但是在asm_hello.s中，由于不知道rodata的数据地址，所以只能先写成0+%rip进行访问，再在后续的操作中利用重定位和链接来访问rodata。

4.5 本章小结

本章介绍了hello从hello.s到hello.o的汇编过程，比较了前后的的结果，了解了从汇编语言映射到机器语言汇编器需要实现的转换。

第5章 链接

5.1 链接的概念与作用

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。链接可以执行于编译时、加载时或运行时。

在现代系统中，链接是由叫做链接器的程序自动执行的。链接器使得分离编译成为可能，无需将大型的应用程序组织成为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的一个时，只需简单地重新编译它，并重新链接应用，而不必重新编译其他文件。

5.2 在Ubuntu下链接的命令

Linux下链接命令：

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

图5-1链接过程

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

5.3.1 elf头

hello.elf的elf头和elf.txt的elf头所包含的信息种类基本相同，不同的是程序头大小和节头数量都得到了增加，并且获得了入口地址。

图5-2 elf头

5.3.2节头表

相较于elf.txt，内容更加丰富详细。当完成链接之后程序中的一些文件就被添加进来了，每一节都有了实际地址。

图5-3 节头表

5.3.3重定位节

可以发现hello.elf的重定位节与elf.txt的重定位节的名字以及内容都完全不一样，现在的所有加数都是0，证明在链接环节确实完成了各种重定位效果。

图5-4 重定位节

5.3.4.符号表

与elf.txt相同的是，符号表的功能没有发生变化，所有重定位需要引用的符号都在其中说明；不同的是，main函数以外的符号也拥有了type，这证明完成了链接。

图5-5 符号表

5.3.5.程序头

程序头是一个结构数组，描述了系统准备程序执行所需的段或者其他信息。程序头描述了可执行目标文件的连续的片与连续的虚拟内存段之间的映射关系。从程序头中可以看到根据可执行目标文件的内容初始化为了两个内存段，分别为只读内存段（代码段）和读写代码段（数据段）。

图5-6 程序头

5.4 hello的虚拟地址空间

用edb打开hello，由data dump部分可以看出，程序是从0x400000开始加载的，结束在约0x400ff0位置。

图5-7 hello的虚拟地址空间

然后查看.elf 中的程序头部分。程序头表在执行的时候被使用，它告诉链接器运行时加载的内容并提供动态链接的信息。每一个表项提供了各段在虚拟地址空间和物理地址空间的大小、位置、标志、访问权限和对齐等信息。各表项功能如下：
PHDR：程序头表
INTERP：程序执行前需要调用的解释器
LOAD：保存常量数据、程序目标代码等
DYNAMIC：保存动态链接器使用信息
NOTE：保存辅助信息
GNU_STACK：异常标记
GNU_RELRO：保存重定位后只读区域的位置

5.5 链接的重定位过程分析

重定位指的是链接器在完成符号解析以后，就把代码中的每个符号引用和正好一个符号定义关联起来。此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。然后就可以开始重定位步骤了，在这个步骤中，将合并输入模块，并为每个符号分配运行时的地址。然后是重定位节中的符号引用，链接器会修改hello中的代码节和数据节中对每一个符号的引用，使得它们指向正确的运行地址。

可以看到这次的汇编代码中call时的地址都变为了绝对地址，不再是最初的函数名字或相对地址。而且多了很多通过链接加进来的函数的源代码，如printf等。

图5-8 hello的反汇编代码

5.6 hello的执行流程

5.7 Hello的动态链接分析

对于动态共享链接库中PIC函数，编译器没有办法预测函数的运行时地址，所以需要添加重定位记录，等待动态链接器处理，为避免运行时修改调用模块的代码段，链接器采用延迟绑定的策略。动态链接器使用过程链接表PLT+全局偏移量表 GOT实现函数的动态链接，GOT中存放函数目标地址，PLT使用GOT中地址跳转到目标函数。

5.8 本章小结

本章介绍了链接的概念与作用、hello的ELF格式，通过使用edb以及阅读文件elf，可以看到程序的执行过程以及其中涉及到的程序地址动态链接内容与相关函数调用。分析了hello的重定位过程、执行流程、动态链接过程。

第6章 hello进程管理

6.1 进程的概念与作用

进程的概念：

一个执行中程序的实例，系统中的每个程序都运行在某个进程的上下文之中。上下文是由程序正确运行所需的状态组成的。这种状态包括存放在内存中的程序的代码以及数据、栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。

进程的作用：

进程能够提供给应用程序的一些关键抽象：

（1）一个独立的逻辑控制流，它提供一个假象，好像程序能够独占使用处理器。

（2）一个私有的地址空间，它提供一个假象，好像程序能够独占使用内存系统。

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

Shell是一个命令行解释器，它输出一个提示符，等待输入一个命令行，然后执行这个命令。如果该命令行的第一个单词不是一个内置的Shell命令，那么Shell就会假设这是一个可执行文件的名字，它将加载并运行这个文件。在运行Hello时，Shell将加载并运行Hello程序，然后等待程序终止。程序终止后，Shell随后输出一个提示符，等待下一个输入的命令行。

6.3 Hello的fork进程创建过程

pid_t fork(void);

进程通过调用fork函数创建一个新的运行的子进程。子进程得到与父进程用户级虚拟地址空间相同但独立的一份副本，包括代码、数据段、堆、共享库以及用户栈，子进程获得与父进程任何打开文件描述符相同的副本，这就意味着当父进程调用fork时，子进程可以读写父进程中的内容，但它们有着不同的PID，在父进程中，fork返回子进程的PID，在子进程中，fork返回0。

6.4 Hello的execve过程

int execve(const *filename, const char *argv[], const char *envp[]);

execve过程发生在调用fork创建新的子进程之后。作用是在当前进程的上下文中加载并运行一个新的程序。filename是可执行目标文件，argv是参数列表，envp是环境变量列表。它调用一次，从不返回，只有出现错误时execve才会返回到调用程序。

6.5 Hello的进程执行

内核为每个进程维持一个上下文，它由一些对象的值组成，这些对象包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构。

在进程执行的某些时刻，内核可以决定抢占当前进程，并重新开始一个先前被抢占了的进程，这种决策就叫做调度。在内核调度了一个新的进程运行后，他就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。上下文切换1）保存当前进程的上下文，2）恢复某个先前被抢占的进程被保存的上下文，3）将控制传递给这个新恢复的进程。

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

进程从用户模式变为内核模式的唯一方法是通过诸如中断、故障或者陷入系统调用这样的异常。当异常发生时，控制传递到异常处理程序，处理器将模式从用户模式变为内核模式，处理程序运行在内核模式中，当它返回到应用程序代码是，处理器就把模式从内核模式改回到用户模式。

图6-1 进程上下文切换的剖析

6.6 hello的异常与信号处理

脸滚键盘（输入回车、随机字符串）

图6-2 输入回车、随机字符串

可以发现回车和随机字符串对于程序的运行并没有影响，终端中会出现所有相关的输入，并不会影响到现有程序运行。

Ctrl-C:

图6-3 输入Ctrl-C

当向hello程序输入Ctrl-C后，会导致中断异常产生SIGINT信号，向子进程发出SIGKILL信号终止并回收，进程终止。

Ctrl-Z：

图6-4 输入Ctrl-Z

当向hello程序输入Ctrl-Z后，会导致中断异常产生SIGSTP信号，进程被挂起，与输入Ctrl-C结果不同。

此时分别输入ps,jobs,pstree,fg,kill指令进行查看相关信息。

ps：

图6-5 输入ps

可以看出hello进程并未停止，而是被挂起。

jobs：

图6-6 输入jobs

验证了hello进程确实被挂起，处于停止的状态。

pstree：

图6-7 输入pstree

可以通过进程树来查看所有进程的情况。

fg：

图6-8 输入fg

fg指令使第一个后台作业变成前台作业，这里hello是第一个后台作业，所以fg会使得hello回到前台并完成运行。

kill：

图6-9 输入kill

结合ps指令输出的进程列表以及提示信息可知，kill指令成功杀死进程hello。

6.7本章小结

本章简述了进程的概念与作用，以及shell的执行流程，总结了fork和execve的运行过程，以及在上下文切换中用户态和内核态的切换，探究了在进程运行过程中信号的作用。

第7章 hello的存储管理

7.1 hello的存储器地址空间

（1）逻辑地址（logical address）

包含在机器语言指令中用来指定一个操作数或一条指令的地址。它促使程序员把程序分成若干段。每一个逻辑地址都由一个段（segment）和偏移量（offset）组成，偏移量指明了从段开始的地方到实际地址之间的距离。对应于hello.o中的相对偏移地址。

1. 线性地址（Linear Address）

逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，或说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。如果启用了分页机制，那么线性地址能再经变换以产生一个物理地址。若没有启用分页机制，那么线性地址直接就是物理地址。

1. 虚拟地址（Virtual Address）

程序运行中程序中使用的逻辑地址，程序通常运行在虚拟地址空间中。由于是段式存储模式，所以虚拟地址是二维的，用段基址和段内位移表示。

1. 物理地址（Physical Address）

线性地址经过页式变换得到的实际内存地址，这个地址被送到地址总线上，定位实际要访问的内存单元。计算机系统的贮存被组织称一个有M个连续的字节大小的单员组成的数组。每个字节都有一个唯一的物理地址。

在hello程序中，需要将各个指令的虚拟地址变为物理地址并完成各种操作，具体的过程为：先将hello虚拟地址或逻辑地址通过运算映射等方式得到线性地址，而后线性地址再通过页式管理变换的方式转变为物理地址，从而实现hello程序的相关执行。

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

一个逻辑地址由两部分组成，段标识符和段内偏移量。段标识符是由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节。通过段标识符的前13位，可以直接在段描述符表中找到一个具体的段描述符，这个描述符就描述了一个段。

段描述符有三类，全局的段描述符放在全局段描述符表(GDT)中，局部的段描述符放在局部段描述符表(LDT)中，最后中断的描述符放在中断描述符表(IDT)中。

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

计算机利用页表，通过MMU（内存管理单元）来完成从虚拟地址到物理地址的转换。线性地址即虚拟地址，用VA来表示。VA被分为虚拟页号(VPN)与虚拟页偏移量(VPO)，CPU取出虚拟页号，通过页表基址寄存器来定位页表条目，在有效位为1时，从页表条目中取出信息物理页号(PPN)，通过将物理页号与虚拟页偏移量(VPO)结合，得到由物理地址(PPN)和物理页偏移量(PPO)组合的物理地址。

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

TLB是一个小的、虚拟寻址的缓存，其中每一行都保存有一个单个PTE组成的块。TLB通常有高度的相连度，用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。关键点在于所有的地址翻译步骤都是在芯片的MMU执行的，因此速度非常快。一般的处理流程为：

（1）CPU产生一个虚拟地址；

（2）MMU从TLB中取出相应的PTE；

（3）MMU将这个虚拟地址翻译成一个物理地址，并将其发送至高速缓存、主存；

（4）高速缓存、主存将所请求的数据字返回给CPU。

当进程运行时，它的页目录表地址被加载到CR3控制寄存器中。36位VPN被划分成四个9位的片，每个片被用作到一个页表的偏移量。CR3寄存器包含L1页表的物理地址，CPU通过CR3得到页目录表的地址，进行地址变换。变换的过程是：先用页目录号作为索引，在页目录表中定位对应的表项，从中得到页表的页帧号。同样再以页表号为索引在页表中找到对应的页表项，从中得到被映射地址的页帧号。即：VPN1提供到一个L1PTE的偏移量，这个PTE包含L2页表的基地址。VPN2提供到一个L2PTE的偏移量，以此类推依次向下。页帧号与页内位移相拼即得到物理地址。

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

在三级Cache下，将物理地址分成CT（标记）+CI（索引）+CO（偏移量），首先在一级Cache下找，若发生不命中，则到下一级缓存即二级Cache下找，若不命中则到三级Cache下访问。

7.6 hello进程fork时的内存映射

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

7.7 hello进程execve时的内存映射

execve函数在当前进程中加载并运行新程序a.out时：

（1）删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。

（2）创建新的区域结构，这些新的区域都是私有的、写时复制的，代码和初始化数据映射到.text和.data区，.bss和栈堆映射到匿名文件。

（3）映射共享区域。如果a.out程序与共享对象链接，那么这些对象都是动态链接到这个程序的，再映射到用户虚拟地址空间中的共享区域内。

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

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

当出现缺页故障时，即DRAM缓存不命中，此时调用缺页处理程序，内存会确定一个牺牲页，若页面被修改，则换出到磁盘，再将新的目标页替换牺牲页写入，缺页处理程序返回到原来的进程，重启导致缺页的指令。

7.9动态存储分配管理

C程序当运行时需要额外虚拟内存时，用动态内存分配器是一种更加方便也有更好可移植性的方法。

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。系统之间的细节不同，但是不失通用性，假设堆是一个请求二进制零的区域，它紧接在未初始化的数据区域后开始，并向上生长。对于每个进程，内核维护着一个变量brk，它指向堆的顶部。

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

在hello中，printf函数会调用malloc函数。malloc函数返回一个指针，指向大小至少为size字节的内存块。有时，当我们运行程序时，才会直到某些数据结构的大小，这样便需要使用到动态内存分配。

动态内存管理的基本方法：

当进行动态内存分配时，任何分配器都需要一些数据结构，以隐式空闲链表为例，带边界标签的隐式空闲链表中的每个块是由一个字的头部和一个字的脚部，有效载荷以及可能的额外填充组成的。头部和脚部编码了块的大小以及块是已分配还是空闲的。它们之间便是malloc时请求的有效载荷，以及为了满足8字节对齐要求的填充部分。他是通过头部脚部中的大小字段隐式连接的。在应用请求k字节的块时，分配器搜索空闲链表，查到一个足够大可以放置所请求块的空闲块。一旦其找到匹配的空闲块，就要分配空闲块的空间，若剩余部分足以形成新的空闲块，则将其分割。若分配器找不到合适的空闲块，则需要向内核额外请求堆内存，将其转化为大的空闲块，插入到空闲链表中，然后将请求块放置于此。当分配器释放一个已分配块时，可能有其他空闲块与新释放的相邻，这时需要进行合并，这时由于每个块的头部脚部记录了块是否空闲，那么便可通过检查其前面块的脚部和后面块的头部来判断是否有空闲块相邻。若是，也只需通过修改头部脚部便可进行合并。

动态内存管理的策略：

首先，对与堆中的块的组织，可以选择隐式、显示、分离空闲链表等。当分配器查找空闲块时，又可以采用不同的放置策略，如首次适配（从头开始搜索链表）、下一次适配（从上一次找到的空闲块的剩余块除法）以及最佳适配等。在分割空闲块时，又可以采用将剩余块分割为新的空闲块的策略。在合并时，可以采用带边界标记的合并，就像在上一段基本方法中所描述，通过边界标记来判断当前块周围是否也同样是空闲块，以此来判断是否需要合并。

7.10本章小结

本章简述了在计算机中的虚拟内存管理，虚拟地址、物理地址、线性地址、逻辑地址的区别以及它们之间的变换，linux 系统下CPU产生的虚拟地址是如何被翻译成物理地址的，以及段式、页式的管理模式。还介绍了hello进程fork时的内存映射、execve时的内存映射、缺页故障与缺页中断处理、动态存储分配管理。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

设备的模型化：所有IO设备都被模型化为文件，所有的输入和输出都能被当做相应文件的读和写来执行。

设备管理：Linux内核有一个简单、低级的接口，成为Unix I/O，是的所有的输入和输出都能以一种统一且一致的方式来执行。

8.2 简述Unix IO接口及其函数

Unix I/O接口统一操作：

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

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

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

（3）读写文件：一个读操作就是从文件复制n>0个字节到内存，从当前文件位置k开始，然后将k增加到k+n，给定一个大小为m字节的而文件，当k>=m时，触发EOF。类似一个写操作就是从内存中复制n>0个字节到一个文件，从当前文件位置k开始，然后更新k。

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

Unix I/O函数：

1. int open(char* filename,int flags,mode_t mode)

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

1. int close(fd)

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

（3）ssize_t read(int fd,void *buf,size_t n)

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

（4）ssize_t wirte(int fd,const void *buf,size_t n)

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

8.3 printf的实现分析

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;

}

((char*)(&fmt) + 4)表示的是可变参数中的第一个参数的地址。而vsprintf的作用就是格式化。它接收确定输出格式的格式化字符串fmt。用格式字符串对个数变化的参数进行格式化，产生格式化输出。接着从vsprintf生成显示信息，到write系统函数，到陷阱-系统调用 int 0x80或syscall等.

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

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

8.4 getchar的实现分析

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

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

8.5本章小结

本章介绍了 Linux 的 I/O 设备的基本概念和管理方法以及Unix I/O 接口及其函数，最后分析了printf 函数和 getchar 函数的工作过程。

结论

Hello终于走完了它的一生，我们来回顾一下它是如何从一个.c文件一步一步变成一个可执行的程序：

（1）首先通过文本编辑器，将高级语言编写的程序存储到hello.c中；

（2）预处理器将hello.c文件经初步处理变成hello.i；

（3）接着编译器将hello.i文件处理成为了汇编代码并保存在了hello.s中；

（4）然后汇编器将hello.s文件处理成可重定位目标程序，也就是hello.o；

（5）最后链接器将hello.o与外部文件进行链接，得到可执行目标文件hello。

Hello在运行时，它又会经历许多有趣的过程：

1. 创建进程、加载程序：shell收到运行./hello的指令之后，通过 fork创建子进程，并在其中由 execve.创建虚拟内存空间映射、调用高速缓存与缺页处理将hello加载进内存与cpu；

（2）执行命令：cpu取指令，控制 hello的逻辑流进行运行，其间调用printf、getchar等函数调用IO设备，进行屏幕的显示和键盘读入；

（3）异常处理：对于运行程序时键盘输入的ctrl-c、ctrl-z等指令系统中断并调用相应的信号处理程序进行处理；

（4）结束：当hello执行完所有工作之后，由父进程回收子进程占用的资源。它也就结束了精彩的一生。

通过对hello的一生的学习、梳理，深入理解了现代计算机操作系统各部分之间的协作、调用，对系统各部分的设计思想、处理方式有了基本的认识，同时感受到了计算机系统的复杂性以及严密性。hello程序从一开始的编写到最终的实现回收，其中经历了很多复杂的过程，一个小小的程序如今也可以有大大的世界。我们通过这个程序以小见大，探寻更深入的原理。Hello World不仅是Hello的自白，更是作为一个计算机专业学生，初次站在计算机世界的大门前时，由面对新事物的好奇，和面对计算机系统的精妙和伟大时，心中千言万语，最终汇集成的一句话。

附件

参考文献

[1] Bryant,R.E. 等. 深入理解计算机系统[M]. 北京: 机械工业出版社, 2016.