目录

第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简介

P2P（Program to Process）过程：

P2P过程指的是hello的源程序，即hello.c经过cpp的预处理得到hello.i文件、经过cc1编译生成hello.s的汇编文件、经过as的处理便为可重定位目标文件hello.o、最后由ld链接生成可执行文件hello。之后用户通过shell键入./hello命令开始执行程序，shell通过fork函数创建一个子进程，再由子进程执行execve函数加载hello。以上就是hello从源程序到一个被执行的进程的P2P过程了。

020（Zero-0 to Zero-0）过程：

020过程指的是再execve执行hello程序后，内核为hello进程映射虚拟内存。在hello进入程序入口后，hello相关的数据就被内核加载到物理内存中，hello程序开始正式被执行。为了让hello正常执行，内核还需要为hello分配时间片、逻辑控制流。最后，当hello运行结束，终止成为僵尸进程后，由shell负责回收hello进程，删除与hello有关的数据内容。

1.2 环境与工具

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

软件环境：Windows7 64位以上；VirtualBox/Vmware 11以上；Ubuntu 16.04 LTS 64位/优麒麟 64位

开发与调试工具：gcc，vim，edb，readelf，HexEdit

1.3 中间结果

1.4 本章小结

本章主要介绍了hello的P2P，020过程，以及进行实验时的软硬件环境及开发与调试工具和在本论文中生成的中间结果文件。

第2章 预处理

2.1 预处理的概念与作用

概念：处理以#开头的指令, 比如拷贝#include包含的文件代码，#define宏定义的替换，条件编译等，为编译做的预备工作的阶段。

作用：通过预处理的内建功能对一个资源进行等价替换，最常见的预处理有：文件包含，条件编译、布局控制和宏替换4种。

1）文件包含：#include是一种最为常见的预处理，主要是做为文件的引用,组合源程序正文。

2）条件编译：#if，#ifndef，#ifdef，#endif，#undef等也是比较常见的预处理，主要是进行编译时进行有选择的挑选，注释掉一些指定的代码，以达到版本控制、防止对文件重复包含的功能。

3）布局控制：#progma，这也是我们应用预处理的一个重要方面，主要功能是为编译程序提供非常规的控制流信息。

4）宏替换： #define，这是最常见的用法，它可以定义符号常量、函数功能、重新命名、字符串的拼接等各种功能。

2.2在Ubuntu下预处理的命令

Linux中预处理hello.c文件的命令是：gcc -E -o hello.i hello.c

图2.2-1 Ubuntu下预处理过程

2.3 Hello的预处理结果解析

结果解析：经过预处理后，hello.c被处理成为hello.i文件。打开hello.o后发现文件内容增加到3060行，其实就是对程序中的宏进行展开。

图2.3-1 Hello的预处理结果

图2.3-2 hello.o部分结果

2.4 本章小结

本章介绍了在预处理的概念与作用，并展示如何在ubuntu下用gcc对hello.c文件进行预处理，并分析了预处理后文本的变化。

第3章 编译

3.1 编译的概念与作用

概念：编译器将文本文件 hello.i 翻译成文本文件 hello.s，它包含一个汇编语言程序。

作用：1、扫描（词法分析）2、语法分析3、语义分析4、源代码优化（中间语言生成）5、代码生成，目标代码优化。

1）将源代码程序输入扫描器，将源代码的字符序列分割成一系列记号。

2）基于词法分析得到的一系列记号，生成语法树。

3）由语义分析器完成，指示判断是否合法，并不判断对错。又分静态语义和动态语义。

4）中间代码（语言）使得编译器分为前端和后端，前端产生与机器（或环境）无关的中间代码，编译器的后端将中间代码转换为目标机器代码。

5）译器后端主要包括：代码生成器:依赖于目标机器，依赖目标机器的不同字长，寄存器，数据类型等。

注意：这儿的编译是指从 .i 到 .s 即预处理后的文件到生成汇编语言程序。

3.2 在Ubuntu下编译的命令

在Ubuntu下编译的命令：gcc -S hello.i -o hello.s

图3.2-1 在Ubuntu下编译的过程

3.3 Hello的编译结果解析

3.3.1 数据

1）局部变量int i

i作为局部变量通常是会被保存在栈或者寄存器中，在此,i存储在栈上-4(%rbp)处。

图3.3.1-1 局部变量i

2）函数参数int argc、char *argv[]

通过对函数参数传递给寄存器的顺序可知agrc作为第一个参数存放在%edi中，agrv[]作为第二个参数存放在%rsi中。

图3.3.1-2 函数参数agrc、agrv[]

3）字符串

程序中有两个字符串，位于只读数据段。

图3.3.1-3 字符串

3.3.2 赋值

程序中赋值操作为i = 0，在汇编中用mov实现，将立即数0赋给 i，因为i是int类型，占4个字节。

图3.3.2-1 i的赋值

3.3.3 类型转换

hello.c中的atoi(argv[3])将字符串类型转换为整形。

图3.3.3-1 atoi(agrv[3])类型转换

3.3.4 算术操作

hello.c中的算术操作为i++。

图3.3.4-1 i++算术操作

3.3.5 关系操作

1）hello.c中 argc!=4，是一个关系操作语句，被编译为：cmpl$4, -20(%rbp)。

图3.3.5-1 agrc!=4关系操作

2）hello.c中i<8，被编译为cmpl$7,-4(%rbp)。

图3.3.5-2 i<8关系操作

3.3.6 数组操作

数组访问有argv[1]、argv[2]、argv[3]，在汇编代码中访问这三个量是通过数组首地址加偏移量的方式。

图3.3.6-1 agrv[2]数组访问

图3.3.6-2 agrv[1]数组访问

图3.3.6-3 agrv[3]数组访问

3.3.7 控制转移

控制转移有if语句和for循环，在汇编代码中这两者都是通过条件跳转指令来完成的。

图3.3.7-1 if条件跳转

图3.3.7-2 for循环跳转

3.3.8 函数操作

1）printf函数：

第一个printf转换成了puts，把.L0段的立即值传入%rdi，然后call跳转到puts。

图3.3.8-1 第一个printf函数

第二个printf有三个参数，第一个是.LC1中的格式化字符串%eax中，后面的依次是%rdi，%rsi，然后跳转到printf。

图3.3.8-2 第二个printf函数

2）exit是把立即数1传入到%edi中，然后call跳转到exit。

3）sleep有一个参数传到%edi中，之后call跳转到 sleep中。

4）getchar不需要参数，直接call跳转即可。

图3.3.8-3 exit、sleep、getchar函数

5）返回值：函数的返回值一般在寄存器%eax中，如果有返回值，则要先把返回值存到%eax中，再用ret返回。

图3.3.8-4 return返回值

3.4 本章小结

本章主要介绍了编译器处理程序的基本过程，编译器分别从数据，赋值语句，类型转换，算术操作，逻辑/位操作，关系操作，控制转移与函数操作这几点进行分析，程序从高级程序设计语言变成了低阶的汇编语言。

第4章 汇编

4.1 汇编的概念与作用

概念：汇编是指从 .s文件到 .o文件，即编译后的文件到生成机器语言二进制程序的过程。汇编器（as）将.s汇编程序翻译成机器语言并将这些指令打包成可重定目标程序的格式存放在.o目标文件中，.o 文件是一个二进制文件，它包含程序的指令编码。

作用：将汇编语言翻译成机器语言，使其在链接后能够被机器识别并执行。

注意：这儿的汇编是指从 .s 到 .o 即编译后的文件到生成机器语言二进制程序的过程。

4.2 在Ubuntu下汇编的命令

Ubuntu下的命令：gcc hello.s -c -o hello.o

图4.2-1 在Ubuntu下汇编的命令

4.3 可重定位目标elf格式

在linux下生成hello.o文件elf格式的命令：readelf -a hello.o > hello.elf

图4.3-1 生成hello.elf文件的命令

ELF头：

ELF头（ELF header）以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。剩下的部分包含了帮助链接器语法分析和解释目标文件的信息，其中包括ELF头的大小、目标文件的类型、机器类型、节头部表的文件偏移，以及节头部表中条目的大小和数量。不同节的位置和大小是有节头部表描述的，其中目标文件中每个节都有一个固定大小的条目。

图4.3-2 ELF头内容

节头：

记录各节名称、类型、地址、偏移量、大小、全体大小、旗标、链接、信息、对齐。

图4.3-3 节头的内容

重定位节：

重定位节保存的是.text节中需要被修正的信息（任何调用外部函数或者引用全局变量的指令都需要被修正），调用外部函数的指令和引用全局变量的指令需要重定位，调用局部函数的指令不需要重定位。.rela.eh_frame节是.eh_frame节的重定位信息。

偏移量(Offset):需要被修改的引用节的偏移

信息(Info)：包括symbol和type两个部分，symbol在前面四个字节，type在后面四个字节,

类型(Type)：告知链接器应该如何修改新的应用

加数(Attend)：一个有符号常数，一些重定位要使用它对被修改引用的值做偏移调整。

名称(Name):重定向到的目标的名称。

图4.3-4 重定位节的内容

符号表(Symbol table):

存放程序中定义和引用的函数和全局变量的信息。由于还未进行链接重定位，偏移量Value还是0。

图4.3-5 符号表的内容

4.4 Hello.o的结果解析

命令：objdump -d -r hello.o > hello0.txt。将反汇编的结果存储在hello0.txt中。

图4.4-1 反汇编命令过程

不同之处：

数据访问：在汇编语言中，访问rodata（printf中的字符串），使用段名称+%rip，而在机器语言对应的反汇编程序中为0+%rip。因为rodata中数据地址也是在运行时确定，故访问也需要重定位。所以在汇编成为机器语言时，将操作数设置为全0并添加重定位条目。

分支转移: 在汇编语言中，分支转移命令是由助记符来标识，通过用符号.L2等助记符，跳转到相应的位置。而在机器语言反汇编程序中，分支转移命令是直接跳转入目的地址。

函数调用:在汇编语言中，函数调用之后直接跟着函数名称。而在机器语言的反汇编程序中，call的目标地址是下一条指令的地址。这是因为 hello.c 中调用的函数都是共享库中的函数，最终需要通过动态链接器才能确定函数的运行时执行地址，在汇编成为机器语言的时候，对于这些不确定地址的函数调用，将其call指令后的相对地址设置为全0(目标地址正是下一条指令），然后在.rela.text 节中为其添加重定位条目，等待静态链接的进一步确定。

图4.4-2 反汇编结果

4.5 本章小结

本章对hello.s进行了汇编，生成了hello.o可重定位目标文件，并且分析了可重定位文件的ELF头、节头部表、符号表和可重定位节，比较了hello.s和hello.o反汇编代码hello0.txt的不同之处，分析了从汇编语言到机器语言的一一映射关系。

第5章 链接

5.1 链接的概念与作用

概念:链接（linking）是将各种代码和数据片段收集并合成为一个单一文件的过程，这个文件可被加载（复制）到内存并执行。链接可以执行于编译时（compile time），也就是在源代码被翻译成机器代码时；也可以执行于加载时（load time），也就是在程序被加载器（loader）加载到内存并执行时；甚至执行于运行时（run time），也就是在由应用程序来执行。

作用：链接器在软件开发过程中扮演着一个关键的角色，因为它们使得分离编译（separate compilation）成为可能。我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的一个时，只需简单地重新编译它，并重新链接应用，而不必重新编译其它文件。

注意：这儿的链接是指从 hello.o 到hello生成过程。

5.2 在Ubuntu下链接的命令

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

图5.2-1 Ubuntu下链接的过程

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

1)ELF Header: hello的文件头和hello.o文件头的不同之处在类型和节数上。Type类型为EXEC表明hello是一个可执行目标文件，有25个节。

图5.3-1 ELF 头的内容

2）节头Section Headers：Section Headers 对 hello中所有的节信息进行了声明，其中包括大小 Size 以及在程序中的偏移量 Offset，因此根据 Section Headers 中的信息我们就可以用 HexEdit 定位各个节所占的区间。其中 Address 是程序被载入到虚拟地址的起始地址。

图5.3-2 节头的内容

3) 符号表.symtab

图5.3-3 符号表内容

4)重定位节.rela.text

图5.3-4 重定位节内容

5.4 hello的虚拟地址空间

通过查看edb，得hello的虚拟地址空间开始于0x400000,结束于0x400ff0。

图5.4-1 虚拟空间开始

图5.4-2 虚拟空间结束

5.5 链接的重定位过程分析

命令：objdump -d -r hello >hello.out,获得hello的反汇编代码。

hello与hello.o的不同：

与hello.o的反汇编文件对比发现，hello.out中多了许多节。hello0.txt中只有一个.text节，而且只有一个main函数，函数地址也是默认的0x000000。hello.out中有.init,.plt,.text三个节，而且每个节中有很多函数。库函数的代码都已经链接到了程序中，程序各个节变的更加完整。

hello的重定位过程：

1）重定位节和符号定义链接器将所有类型相同的节合并在一起后，这个节就作为可执行目标文件的节。然后链接器把运行时的内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号，当这一步完成时，程序中每条指令和全局变量都有唯一运行时的地址。

2）重定位节中的符号引用这一步中，连接器修改代码节和数据节中对每个符号的引用，使他们指向正确的运行时地址。

3）重定位条目当编译器遇到对最终位置未知的目标引用时，它会生成一个重定位条目。代码的重定位条目放在.rel.txt中。

图5.5-1 hello反汇编代码

5.6 hello的执行流程

5.7 Hello的动态链接分析

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

GOT表位置在调用_init之前0x404008后的16个字节均为0

图5.7-1 未调用init前的GOT.PLT表

图5.7-2 调用init后的GOT.PLT表

在之后的函数调用时，首先跳转到PLT执行.plt中逻辑，第一次访问跳转时，GOT 地址为下一条指令，将函数序号压栈，然后跳转到PLT[0]，在 PLT[0]中将重 定位表地址压栈，然后访问动态链接器，在动态链接器中使用函数序号和重定位 表确定函数运行时地址，重写 GOT，再将控制传递给目标函数。

5.8 本章小结

本章主要介绍了链接的概念及作用，以及生成链接的命令，对hello的elf格式文件进行了深入的分析，同时也分析了hello的虚拟地址空间，重定位过程，遍历了整个hello的执行过程，并且比较了hello.o和hello的反汇编不同处。

第6章 hello进程管理

6.1 进程的概念与作用

概念：进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。

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

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

作用：Linux系统中，Shell是一个交互型应用级程序，为使用者提供操作界面，接收用户命令，然后调用相应的应用程序。

处理流程：

1）从终端读入输入的命令。

2）将输入字符串切分获得所有的参数

3）如果是内置命令则立即执行

4）否则调用相应的程序为其分配子进程并运行

5）shell应该接受键盘输入信号，并对这些信号进行相应处理

6.3 Hello的fork进程创建过程

在终端中输入./hello 学号 姓名 1命令后，shell会处理该命令，判断出不是内置命令，则会调用fork函数创建一个新的子进程，子进程几乎但不完全与父进程相同。通过fork函数，子进程得到与父进程用户级虚拟地址空间相同的但是虚拟地址独立、PID也不相同的一份副本。

6.4 Hello的execve过程

调用fork函数之后，子进程将会调用execve函数，来运行hello程序，如果成功调用则不再返回，若未成功调用则返回-1。

完整的加载运行hello程序需要以下几个步骤：

1）加载器会删除当前子进程虚拟地址端。然后创建一组新的代码、数据、堆端，并初始化为0。

2）映射私有区域和共享区域，将新的代码和数据段初始化为可执行文件中的内容。

3）设置程序计数器，使其指向代码区的入口，下一次调度这个进程时，将直接从入口点开始执行。

6.5 Hello的进程执行

并发流：一个逻辑流的执行时间与另一个流重叠，成为并发流，这两个流成为并发的运行。多个流并发的执行的一般现象成为并发。

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

私有地址空间：进程为每个流都提供一种假象，好像它是独占的使用系统地址空间。一般而言，和这个空间中某个地址相关联的那个内存字节是不能被其他进程读或者写的，在这个意义上，这个地址空间是私有的。

用户模式和内核模式：处理器通常使用一个寄存器提供两种模式的区分，该寄 存器描述了进程当前享有的特权，当没有设置模式位时，进程就处于用户模式中， 用户模式的进程不允许执行特权指令，也不允许直接引用地址空间中内核区内的 代码和数据；设置模式位时，进程处于内核模式，该进程可以执行指令集中的任何命令，并且可以访问系统中的任何内存位置。

上下文信息：上下文就是内核重新启动一个被抢占的进程所需要的状态，它由 通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的值构成。

上下文切换：当内核选择一个新的进程运行时，则内核调度了这个进程。在内核调度了一个新的进程运行后，它就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程：

1）保存以前进程的上下文

2）恢复新恢复进程被保存的上下文，

3）将控制传递给这个新恢复的进程，来完成上下文切换

hello程序在调用了sleep程序后会陷入内核状态，内核可能会进行上下文切换。到程序运行到getchar的时候，内核也会进行上下文切换，让其他进程运行。除了这些，系统还会为hello程序分配时间片，即使没有执行到getchar或者sleep函数，只要接收到中断信号，系统就会判断当前程序以及执行够久了，从而进行上下文切换，将处理器让给其他进程。

图6.5-1 hello的部分上下文切换

6.6 hello的异常与信号处理

执行过程可能出现的异常一共有四种：中断、陷阱、故障、终止。

中断：来自I/O设备的信号，异步发生，总是返回到下一条指令。

陷阱：有意的异常，同步发生，总是返回到下一条指令。

故障：潜在可恢复的错误，同步发生，可能返回到当前指令或终止。

终止：不可恢复的错误，同步发生，不会返回。

1）正常运行

图6.6-1 hello正常运行

2）Ctrl+C终止

图6.6-2 hello被Ctrl+C终止

3）Ctrl+Z暂停，输入ps观察到hello并未关闭

图6.6-3 hello被Ctrl+Z暂停

4）运行过程中乱按，无关输入随着printf指令被输出到结果。

图6.6-4 运行过程中乱按结果

6.7本章小结

在本章中，阐述进程的定义与作用，同时介绍了 Shell 的一般处理流程和作用，并且着重分析了调用 fork 创建新进程，调用execve函数执行 hello，hello的进程执行，以及hello 的异常与信号处理。

第7章 hello的存储管理

7.1 hello的存储器地址空间

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

线性地址：也叫虚拟地址，和逻辑地址类似，也是一个不真实的地址，如果逻辑地址是对应的硬件平台段式管理转换前地址的话，那么线性地址则对应了硬件也是内存的转换前地址。

虚拟地址：也就是线性地址。

物理地址：存储器中的每一个字节单元都给以一个唯一的存储器地址，用来正确地存放或取得信息，这个存储器地址称为物理地址，又叫实际地址或绝对地址。

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

逻辑地址由段标识符和段内偏移量两部分组成。段标识符由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号，是对段描述符表的索引，每个段描述符由8个字节组成，具体描述了一个段。后3位包含一些硬件细节，表示具体是代码段寄存器还是栈段寄存器还是数据段寄存器等。通过段标识符的前13位，可以直接在段描述符表中索引到具体的段描述符。每个段描述符中包含一个Base字段，它描述了一个段的开始位置的线性地址。将Base字段和逻辑地址中的段内偏移量连接起来就得到转换后的线性地址。

图7.2-1 段选择符

对于全局的段描述符，放在全局段描述符表中，局部的（每个进程自己的）段描述符，放在局部段描述符表中。给定逻辑地址，看段选择符的最后一位是0还是1，用于判断选择全局段描述符表还是局部段描述符表。

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

页表是一个页表条目（PTE）的数组，虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。每个PTE由一个有效位和一个n位地址字段组成，有效位表明该虚拟页是否被缓存在DRAM中。如果设置了有效位，那么地址字段表示相应的物理页的起始位置；如果没有设置有效位，那么空地址表示虚拟页还未被分配，否则这个地址指向该虚拟页在磁盘的起始位置。

MMU利用页表实现从虚拟地址到物理地址的变换。CPU中的一个控制寄存器，页表基址寄存器指向当前页表。n位的虚拟地址包含一个p位的虚拟页面偏移VPO和一个n-p位的虚拟页号VPN。MMU利用VPN选择适当的PTE，如果这个PTE设置了有效位，则页命中，将页表条目中的物理页号和虚拟地址中的VPO连接起来就得到相应的物理地址。

图7.3-1 使用页表的地址翻译

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

TLB：在MMU中包括一个关于PTE的缓存，称为翻译后备缓冲器（TLB）。TLB是一个小的、虚拟寻址的缓存，每一行保存着一个由单个PTE组成的块。由于VA到PA的转换过程中，需要使用VPN确定相应的页表条目，因此TLB需要通过VPN来寻找PTE。和其他缓存一样，需要进行组索引和行匹配。如果TLB有2t个组，那么TLB索引T由VPN的t个最低位组成，TLB标记由VPN中剩余的位组成。

图7.4-1 MMU使用VPN部分访问TLB

变换步骤：CPU产生一个VA，MMU在根据VPN在TLB中搜索PTE，若命中，MMU取出相应的PTE，根据PTE将VA翻译成PA；若没命中，则通过多级页表查询PTE是否在页中，若在页中，找到对应的PIE，MMU将VA翻译成PA，若没有在页中，则进行缺页处理。

多级页表：将虚拟地址的VPN划分为相等大小的不同的部分，每个部分用于寻找由上一级确定的页表基址对应的页表条目。

图7.4-2 使用多级页表翻译地址

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

对已经获得的物理地址，首先取组索引对应位，向L1cache中寻找对应组。如果存在，则比较标志位，并检查对应行的有效位是否为1。如果上述条件均满足则命中。否则按顺序对L2、L3、内存进行相同操作，直到出现命中。然后向上级cache返回直到L1。如果有空闲块则将目标块放置到空闲块中，否则将缓存中的某个块驱逐，将目标块放到被驱逐块的原位置。

图7.5-1 三级Cache物理内存访问

7.6 hello进程fork时的内存映射

在shell输入命令行后，内核调用fork创建子进程，为hello程序的运行创建上下文，并分配一个与父进程不同的PID。通过fork创建的子进程拥有父进程相同的区域结构、页表等的一份副本，同时子进程也可以访问任何父进程已经打开的文件。当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同，当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间。

7.7 hello进程execve时的内存映射

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

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

2）映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为hello文件中的.text和.data区，bss区域是请求二进制零的，映射到匿名文件，其大小包含在hello中，栈和堆地址也是请求二进制零的，初始长度为零。

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

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

图7.7-1 加载器映射用户地址空间

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

缺页故障：当CPU想要读取虚拟内存中的某个数据，而这一片数据恰好存放在主存当中时，就称为页命中。相对的，如果DRAM缓存不命中，则称之为缺页。如果CPU尝试读取一片内存而这片内存并没有缓存在主存当中时，就会触发一个缺页异常。

缺页故障处理：发生缺页故障时，缺页处理程序确认出物理内存中的牺牲页，如果这个页已经被修改了，则把它换到磁盘。缺页处理程序调入新的页面，并更新内存中的PTE，缺页处理程序返回到原来的进程，再次执行导致缺页的命令。CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面已经缓存在物理内存中，所以就会命中。

图7.8-1 Linux缺页处理

7.9动态存储分配管理

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

图7.9-1 动态内存管理的堆

A、隐式空闲链表：空闲块通过头部中的大小字段隐含地连接着。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

1）放置策略：首次适配、下一次适配、最佳适配。首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配从上一次查询结束的地方开始。最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。

2）合并策略：立即合并、推迟合并。立即合并就是在每次一个块被释放时，就合并所有的相邻块；推迟合并就是等到某个稍晚的时候再合并空闲块。

图7.9-2 带边界的隐式空闲链表

B、显式空闲链表：每个空闲块中，都包含一个pred（前驱）和succ（后继）指针。使用双向链表使首次适配的时间减少到空闲块数量的线性时间。

空闲链表中块的排序策略：一种是用后进先出的顺序维护链表，将新释放的块放置在链表的开始处，另一种方法是按照地址顺序来维护链表，链表中每个块的地址都小于它后继的地址。

图7.9-3 显示空闲链表

C、分离的空闲链表

维护多个空闲链表，每个链表中的块有大致相等的大小。将所有可能的块大小分成一些等价类，也叫做大小类。

7.10本章小结

本章主要介绍了hello的存储器的地址空间，介绍了四种地址空间的差别和地址的相互转换。同时介绍了hello的四级页表的虚拟地址空间到物理地址的转换。阐述了三级cache的物理内存访问、进程 fork 时的内存映射、execve 时的内存映射、缺页故障与缺页中断处理、动态存储分配管理。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

一个linux文件就是一个m个字节的序列。所有的I/O设备（如网络、磁盘和终端）都被模型化为文件，而所有的输入和输出都被当做相应的文件的读和写来执行。这种将设备优雅地映射为文件的方式，运行linux内核引出一个简单、低级的应用接口，称为Unix I/O，这使得所有的输入和输出都能以一种统一且一致的方式来执行。

设备的模型化：文件

设备管理：unix io接口

8.2 简述Unix IO接口及其函数

Unix I/O 接口：

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

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

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

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

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

Unix I/O函数：

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

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

2、int close(fd)

进程通过调用close函数关闭一个打开的文件，fd是需要关闭的文件的描述符。

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函数是格式化输出函数, 用于向标准输出设备按规定格式输出信息。对于va_list ，有typedef char *va_list这说明它是一个字符指针。对于(char*)(&fmt) + 4) 表示的是…中的第一个参数。

vsprintf函数根据格式串fmt，并结合args参数产生格式化之后的字符串结果保存在buf中，并返回结果字符串的长度。

write函数将buf中的i个字符写到终端，由于i保存的是结果字符串的长度，因此write将格式化后的字符串结果写到终端。

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

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

图8.3-1 printf函数实体

图8.3-2 vsprintf函数实体

图8.3-3 write函数实体

8.4 getchar的实现分析

getchar函数会从stdin输入流中读入一个字符。调用getchar时，等待用户输入，输入回车后，输入的字符会存放在缓冲区中。第一次调用getchar时，需要从键盘输入，但如果输入了多个字符，之后的getchar会直接从缓冲区中读取字符。getchar的返回值是读取字符的ASCII码，若出错则返回EOF。

图8.4-1 getchar函数实体

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

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

8.5本章小结

本章主要介绍了 Linux 的 IO 设备管理方法、Unix IO 接口及其函数，分析了 printf 函数和 getchar 函数的实现。

结论

hello朴实无华的一生：

1）预处理：hello.c预处理到hello.i文本文件；

2）编译：hello.i编译到hello.s汇编文件；

3）汇编：hello.s汇编到二进制可重定位目标文件hello.o；

4）链接：hello.o链接生成可执行文件hello；

5）运行：输入./hello 120L000000 ZY 1运行程序

6）创建子进程：bash进程调用fork函数，生成子进程；

7）加载程序：execve函数加载运行当前进程的上下文中加载并运行新程序hello；

8）访问内存：hello的运行需要地址的概念，虚拟地址是计算机系统最伟大的抽象；

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

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

对计算机系统的设计与实现的感悟。

hello文件在面对程序员时，只需要通过一些简单的规约就能能够设计实现。然而当hello移植到计算机上时，计算机需要对其进行预处理、编译、汇编、链接、运行、创建子进程、加载程序、访问内存、交互、终止等众多繁琐的过程。尤其是具体到每个过程时，每个过程自身还有许多晦涩难懂的实现。就此而言，hello的一生倒也算不上朴实无华了。

通过对hello的分析可以知晓，计算机实现一个程序是按顺序进行的，未来计算机的变革是否能够打破这一束缚，让程序的实现更加简单，这样或许在低门槛下的计算机理解能够创建更多具有想象力的高级程序。同时计算机系统下的hello是抽象的，对于从事计算机研究的人员来说，抽象能力是重要的，提醒了自己在将来的学习过程中要重视抽象能力的培养以及运用。

附件

表 附件-1

图 附件-1

参考文献

[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.