程序人生-Hello’s P2P
计算机系统
大作业
题 目 程序人生-Hello’s P2P
专 业 计算机
学 生 王世龙
指 导 教 师 史先俊
摘 要
本文基于Linux平台，通过gcc、objdump、gdb、edb等工具对hello程序代码预处理、编译、汇编、链接与反汇编的过程进行分析与比较，并且通过shell及其他Linux内置程序对hello进程运行过程进行了分析。经过研究，较为深入的研究了一个C语言程序生命周期内包括缓存、虚拟内存、信号在内的各种操作系统与硬件实现的机制，对汇编语言及程序编译的各个阶段都有所讨论。
关键词：操作系统，编译，汇编，虚拟内存
目 录
第1章 概述 - 4 -
1.1 HELLO简介 - 4 -
1.2 环境与工具 - 4 -
1.3 中间结果 - 4 -
1.4 本章小结 - 4 -
第2章 预处理 - 5 -
2.1 预处理的概念与作用 - 5 -
2.2在UBUNTU下预处理的命令 - 5 -
2.3 HELLO的预处理结果解析 - 5 -
2.4 本章小结 - 6 -
第3章 编译 - 7 -
3.1 编译的概念与作用 - 7 -
3.2 在UBUNTU下编译的命令 - 7 -
3.3 HELLO的编译结果解析 - 7 -
3.4 本章小结 - 12 -
第4章 汇编 - 14 -
4.1 汇编的概念与作用 - 14 -
4.2 在UBUNTU下汇编的命令 - 14 -
4.3 可重定位目标ELF格式 - 14 -
4.4 HELLO.O的结果解析 - 15 -
4.5 本章小结 - 16 -
第5章 链接 - 17 -
5.1 链接的概念与作用 - 17 -
5.2 在UBUNTU下链接的命令 - 17 -
5.3 可执行目标文件HELLO的格式 - 17 -
5.4 HELLO的虚拟地址空间 - 19 -
5.5 链接的重定位过程分析 - 21 -
5.6 HELLO的执行流程 - 22 -
5.7 HELLO的动态链接分析 - 23 -
5.8 本章小结 - 24 -
第6章 HELLO进程管理 - 25 -
6.1 进程的概念与作用 - 25 -
6.2 简述壳SHELL-BASH的作用与处理流程 - 25 -
6.3 HELLO的FORK进程创建过程 - 25 -
6.4 HELLO的EXECVE过程 - 25 -
6.5 HELLO的进程执行 - 25 -
6.6 HELLO的异常与信号处理 - 26 -
6.7本章小结 - 31 -
第7章 HELLO的存储管理 - 32 -
7.1 HELLO的存储器地址空间 - 32 -
7.2 INTEL逻辑地址到线性地址的变换-段式管理 - 32 -
7.3 HELLO的线性地址到物理地址的变换-页式管理 - 33 -
7.4 TLB与四级页表支持下的VA到PA的变换 - 35 -
7.5 三级CACHE支持下的物理内存访问 - 36 -
7.6 HELLO进程FORK时的内存映射 - 37 -
7.7 HELLO进程EXECVE时的内存映射 - 38 -
7.8 缺页故障与缺页中断处理 - 38 -
7.9动态存储分配管理 - 39 -
7.10本章小结 - 41 -
第8章 HELLO的IO管理 - 42 -
8.1 LINUX的IO设备管理方法 - 42 -
8.2 简述UNIX IO接口及其函数 - 42 -
8.3 PRINTF的实现分析 - 42 -
8.4 GETCHAR的实现分析 - 42 -
8.5本章小结 - 43 -
结论 - 43 -
附件 - 44 -
参考文献 - 45 -
第1章 概述
1.1 Hello简介
P2P：
在linux中，hello.c经过cpp预处理，cll编译，as汇编，ld链接四个步骤生成可执行目标文件，在bash中输入命令后，bash fork一个子进程，并execve这个可执行文件，给分配时间片，最终在cpu上执行起来
020：
Shell调用execve后，为这个可执行文件映射一个虚拟内存，内核创建页表，进入程序入口，开始执行main函数（程序）。当程序结束，若父进程仍存在，父进程回收此进程；若父进程已经终止，则由init回收此进程。内核删除相关数据结构
1.2 环境与工具
硬件环境：Intel Core i5-6700U x64CPU,8G RAM,256G SSD +1T HDD.
软件环境：Ubuntu18.04.1 LTS
开发与调试工具：vim，gcc，as，ld，edb，readelf，HexEdit
1.3 中间结果
hello.i(hello.c预处理之后的程序文本)
hello.s(hello.i编译成汇编语言之后的程序文本)
hello.o(hello.s生成的二进制文件)
hello(可执行的hello二进制文件)
helloobj.s(hello.o的反汇编)
helloobj1.s(hello的反汇编)
hello.elf(hello的elf信息)
1.4 本章小结
本章主要介绍了hello.c的一生，p2p，020；
还介绍了环境与工具；
还介绍了中间结果
（第1章0.5分）
第2章 预处理
2.1 预处理的概念与作用
概念：
程序设计领域中，预处理一般是指在程序源代码被翻译为目标代码的过程中，生成二进制代码之前的过程。典型地，由预处理器(preprocessor) 对程序源代码文本进行处理，得到的结果再由编译器核心进一步编译。
作用：
这个过程并不对程序的源代码进行解析，但它把源代码分割或处理成为特定的单位——（用C/C++的术语来说是）预处理记号(preprocessing token)用来支持语言特性（如C/C++的宏调用）
预处理指令一般被用来使源代码在不同的执行环境中被方便的修改或者编译。
2.2在Ubuntu下预处理的命令
gcc -E hello.c -o hello.i
图2.2.1 预处理
2.3 Hello的预处理结果解析
这是hello.i文件前面的部分，大段大段的带#号的和库函数是对.c文件里三个include（stdio.h,stdlib.h,unistd.h）的替换
（如果有定义宏常量，也会在这一步替换）
可以看到，程序已经扩充到了3042行
图2.3.1 hello.i里的头文件替换
这是hello.i文件最后面，是main函数
图2.3.2 位于最后面的main函数
2.4 本章小结
本章介绍了通过预处理命令，可以在编译器编译之前，提前进行一些操作，例如调用库函数或自定义.h文件，定义宏常量，也是广义上的模块化编程，而预处理过程，正是把这些预指令替换的过程。
（第2章0.5分）
第3章 编译
3.1 编译的概念与作用
概念：
编译即利用编译程序从源语言编写的源程序产生汇编语言程序的过程。
作用：
编译器经过词法分析，语法分析，语义分析等过程，在检查无误后，将.i文件翻译成.s（汇编语言）文件。
编译得到的.s文件可用于之后的汇编，链接操作
3.2 在Ubuntu下编译的命令
gcc -S hello.i -o hello.s
图3.2.1 编译阶段
3.3 Hello的编译结果解析
先放上编译之后的文件的总体截图，接下来一一说明
图3.3.1 hello.s文件
3.3.1数据
字符常量：
字符常量“用法: Hello 学号 姓名 秒数！\n”和“Hello %s %s\n”在.rodata（只读数据段中。
图3.3.2 rodata中的字符常量
整数
全局变量：未赋初值的在.bss节中，赋初值的在.data中
局部变量：会在汇编语言里用寄存器表示，或存放在堆栈里
例代码中循环计数用的i
图3.3.3 局部变量的表示
立即数：
还有剩下的数直接用立即数在代码中表示
例如图3.3.3中和整数i比较的0x7
数组：
会用指针加偏移量的形式来寻址
例如本题的argv[]数组：rdx存printf的第三个参数argv[2]，rsi存第二个参数argv[1]，rdi存规格化字符串
图3.3.4 argv[]的表示
3.3.2赋值
整数的赋值用mov指令，其后缀根据传输数据大小可分为：
b 1byte
w 2byte
l 4byte
q 8byte
例如下图的赋值操作都是8字节整数
图3.3.5 赋值
3.3.3算数操作
进行算数操作的指令有：
指令 效果
leaq S,D D=&S
inc D D+=1
dec D D-=1
add S,D D+=S
sub S,D D-=S
本程序中涉及的算术操作有：
程序计数器i++操作：
图3.3.6 i++
3.3.4关系操作
关系操作的指令有：
指令 效果 描述
cmp S1,S2 S2-S1 比较并设置条件码
test S1,S2 S2-S1 测试并设置条件码
j** ****** - 根据**和条件码进行跳转
set D - 设置条件码
程序中涉及的关系运算有：
- 程序计数器i和8的比较：
图3.3.7 比较跳转 - Argc和数字4的比较：
图3.3.8比较跳转
3.3.7数组/指针
数组：
数组会用指针加偏移量的形式来寻址，例如本题的argv[]数组：
rdx存printf的第三个参数argv[2]，rsi存第二个参数argv[1]，rdi存规格化字符串
图3.3.9 argv[]的表示
3.3.8控制转移
程序中控制转移有两处： - if(argc!=4):当argc不等于4的时候执行这段操作：跳转到L2处
图3.3.10 if跳转 - for(i=0;i<8;i++):当i小于8的时候，执行for里面的语句：跳转到L4处
图3.3.11for跳转
3.3.9函数操作
函数是一种过程，提供了代码封装的方式，便于模块化编程。在函数P中调用函数Q，有以下过程：
1.传递控制： 把程序计数器设为Q的起始地址
2.传递参数 64位程序用寄存器传参，32位程序用栈传参
3.分配内存 通过移动rsp寄存器所存指针
4.执行Q 执行Q里的一句句指令
5.释放内存 移动rsp栈指针
6.返回数据 rax存放返回值
7.返回控制 Q栈帧最底部存放返回地址，即返回到P之前的指令的下一句
图3.3.12 一些调用函数的步骤
栈帧总体结构如下，可配合上述过程一起看：
图3.3.13栈帧结构
Hello函数中调用的库函数：
printf
atoi
sleep
exit
图3.3.14函数调用
3.4 本章小结
本章主要讲解了编译器如何将hello.i处理为hello.s汇编文件。其中具体讲解了编译时，编译器如何处理整数，字符串，赋值操作，运算操作，关系操作，控制操作等
经过编译，我们的hello变为了更低级的汇编语言
（第3章2分）
第4章 汇编
4.1 汇编的概念与作用
汇编即利用编译生成的汇编语言程序产生机器语言程序（二进制编码），并将指令打包成可重定位文件的过程。生成一个.o文件（二进制文件）
4.2 在Ubuntu下汇编的命令
gcc -C hello.s -o hello.o
图4.2.1 汇编命令行
4.3 可重定位目标elf格式
- ELF Header：描述了生成该文件的系统的字的大小和字节顺序，包括ELF头的大小、目标文件的类型、机器类型、字节头部表（section header table）的文件偏移，以及节头部表中条目的大小和数量等信息。
图4.3.1 elf头 - Section Headers：节头部表，包含了文件中出现的各个节的语义，包括节的类型、位置和大小等信息。
图4.3.2节头表 - 重定位节.rela.text ,一个.text节中需要进行重定位的信息，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
图中包括puts，exit，printf，atoi，sleep，getchar这几个函数位置的描述
图4.3.3重定位节
4.4 Hello.o的结果解析
区别：
- 格式：反汇编工具自动补充了从零开始的地址号，还有部分注释
- 全局变量访问：在.s文件中，采用‘段名称+%rip’的寻址方式，反汇编代码中使用0x0(%rip)，并添加重定位条目来寻址，例如绿色，蓝色部分。
- 函数调用：在.s文件中，采用call+函数名，反汇编代码中call+下一条指令地址（偏移地址为0x0），并添加重定位条目，最终需要通过链接器完成目标地址的确定，例如橙色部分。
- 分支转移：在.s文件中使用段名称如.LC0，反汇编代码中确定的地址。
图4.4.1 hello.s与hello.o反汇编对比
4.5 本章小结
本章主要介绍了汇编过程，通过汇编生成可重定位目标文件，还介绍了可重定位目标文件的elf格式里的节头表，elf头，重定位条目，还对可重定位目标文件的反汇编文件和第三章的汇编文件做了对比，阐述不同。
（第4章1分）
第5章 链接
5.1 链接的概念与作用
概念：
链接即将多个可重定位目标文件链接成为一个可执行目标文件，关键步骤为符号解析和重定位
作用：
链接操作将各个.o里面的函数引用，全局变量引用进行重定位，最终得到一个可执行目标文件，这个文件可以被加载到内存并运行。
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
图5.2.1 链接结果
5.3 可执行目标文件hello的格式
分析hello的ELF格式，用readelf等列出其各段的基本信息，包括各段的起始地址，大小等信息。
输入命令：
图5.3.1命令
Filesize为目标文件中的段大小
Memsiz 内存中的段大小
Offset为偏移量
Virtaddr 虚拟空间地址
Flags 运行时访问权限
Align 对齐要求
图5.3.2 段头表
Size为节大小
Offset为偏移量
图5.3.3各节信息
5.4 hello的虚拟地址空间
用edb查看hello文件，根据5.3查看各段信息
PHDR:程序头表
图5.4.1 PHDR
LOAD表示一个需要从二进制文件映射到虚拟空间的段,例:
代码段:从init开始
图5.4.2 代码段
数据段:易发现数据段开始的部分存着上述讲过的两串字符串常量
图5.4.3 数据段
.interp节
图5.4.1 .interp节
图5.4.2 .interp节内容
.init节
图5.4.3 .init节
.text节
图5.4.4 .text节
.rodate节
图5.4.5 .rodata节位置及其内容
Stack
图5.4.6 stack
5.5 链接的重定位过程分析
objdump -d -r hello 对比分析hello与hello.o的不同
图5.5.1 左为hello反汇编,右为hello.o反汇编
- hello的反汇编多了许多节,如:
.interp 保存ld.so路径
.note.ABI-tag
.hash 符号的哈希表
.gnu.hash GNU拓展的符号的哈希表
.rela.dyn
.init 程序初始化需要的代码 - main开始地址不同
- 函数调用偏移量不同,hello反汇编里经过的重定位，偏移量为非零；hello.o反汇编未经过重定位，偏移量都为零
故，链接操作就是将各个.o里面的函数引用，全局变量引用进行重定位
关于如何进行重定位，这里举一个printf的字符串常量的例子：
图5.5.2 重定位条目
refaddr = ADDR(s) + r.offset= ADDR(main)+r.offset=
0x4010c1+0x18=0x4010d9
*refptr = (unsigned) (ADDR(r.symbol) + r.addend-refaddr) =
ADDR(str1)+r.addend-refaddr=0x402008+(-0x4)-0x4010d9=0xF2B
图5.5.3重定位验证
由截图可发现，重定位计算结果正确！
5.6 hello的执行流程
使用edb执行hello，列出从加载hello到_start，到call main,以及程序终止的所有过程程序名或程序地址。
函数名称 地址
ld-2.29.so!_dl_start 0x7f3325c6b030
ld-2.29.so!_dl_init 0x7f3325c799e0
hello!_start 0x401090
libc-2.29.so!__libc_start_main 0x7f0ca921ba80
libc-2.29.so!__cxa_atexit 0x7ff630a2a740
libc-2.29.so!__libc_csu_init 0x401150
hello!_init 0x401000
libc-2.29.so!_setjmp 0x7efd31390b90
libc-2.29.so!_sigsetjmp 0x7efd31390af0
hello!main 0x4010c1
[email protected] 0x401040
[email protected] 0x401060
[email protected] 0x401080
[email protected] 0x401050
libc-2.27.so!exit 0x7f2c0fd763c0
5.7 Hello的动态链接分析
动态链接库中的函数在程序执行的时候才会确定地址，所以编译器无法确定其地址，在汇编代码中也无法像静态库的函数那样体现。
hello程序对动态链接库的引用，基于数据段与代码段相对距离不变这一个事实，因此代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量。
GNU编译系统采用延迟绑定技术来解决动态库函数模块调用的问题，它将过程地址的绑定推迟到了第一次调用该过程时。
延迟绑定通过全局偏移量表（GOT）和过程链接表（PLT）实现。如果一个目标模块调用定义在共享库中的任何函数，那么就有自己的GOT和PLT。前者是数据段的一部分，后者是代码段的一部分。
进一步介绍，PLT是一个数组，其中每个条目是16字节代码。每个库函数都有自己的PLT条目，PLT[0]是一个特殊的条目，跳转到动态链接器中。从PLT[2]开始的条目调用用户代码调用的函数。
GOT同样是一个数组，每个条目是8字节的地址，和PLT联合使用时，GOT[2]是动态链接在ld-linux.so模块的入口点，其余条目对应于被调用的函数，在运行时被解析。每个条目都有匹配的PLT条目。
从图5.3.3可看出GOT起始位置为0x404000。
通过edb调试：
在dl_init调用之前，对于每一条PIC函数调用，调用的目标地址都实际指向PLT中的代码逻辑，GOT存放的是PLT中函数调用指令的下一条指令地址。如在图5.7.1
图5.7.1 dl_init之前的.got.plt节
在dl_init调用之后，如图5.7.2，0x404008和0x404010处的两个8B数据分别发生改变为0x7f54c84ea190和0x7f54c84d5200，如图5.7.3其中GOT[1]指向重定位表（依次为.plt节需要重定位的函数的运行时地址）用来确定调用的函数地址，如图5.7.4 GOT[2]指向动态链接器ld-linux.so运行时地址。
图5.7.2 dl_init之前的.got.plt节
图5.7.3 GOT[1]指向重定位表
图5.7.4 GOT[2]指向的动态链接器
5.8 本章小结
本章主要介绍了链接过程，ld经过符号解析和重定位将hello.o与其他库文件一同链接起来，与其相关的有elf头，程序头表。在链接后，hello的反汇编与hello.o的反汇编和编译之后生成的汇编语言文件，三者各不相同，只有链接后的才是可执行文件。
到此为止，hello总算是完成了从代码到程序的过程。
（第5章1分）
第6章 hello进程管理
6.1 进程的概念与作用
1.概念
进程是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。
2.作用
进程作为一个执行中程序的实例，系统中每个程序都运行在某个进程的上下文中，上下文是由程序正确运行所需的状态组成的。上下文包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。
6.2 简述壳Shell-bash的作用与处理流程
Shell 是指一种应用程序，Shell应用程序提供了一个界面，用户通过这个界面访问操作系统内核的服务。
处理流程：
从终端读入输入的命令。
将输入字符串切分获得所有的参数放入argv[]
如果是内置命令则立即执行
否则调用相应的程序为其分配子进程并运行
shell应该接受键盘输入信号，并对这些信号进行相应处理
6.3 Hello的fork进程创建过程
shell作为父进程通过fork函数为hello创建一个新的进程，供其执行。调用fork函数创建一个新的运行的子进程，新创建的子进程几乎但不完全与父进程相同，子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份副本，这就意味着，当父进程调用fork时，子进程可以读写父进程中打开的任何文件。父进程与子进程之间最大的区别在于它们拥有不同的PID。
Fork函数调用execve来启动hello程序，当shell发现hello执行完之后，回收子程序。
6.4 Hello的execve过程
创建进程后，在子进程中通过判断pid即fork()函数的返回值，判断处于子进程，则会通过execve函数在当前进程的上下文中加载并运行一个新程序。
子进程调用execve函数（传入命令行参数）在当前进程的上下文中加载并运行一个新程序即hello程序，execve调用驻留在内存中的被称为启动加载器的操作系统代码来执行hello程序，加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆和栈段。新的栈和堆段被初始化为零，通过将虚拟地址空间中的页映射到可执行文件的页大小的片，新的代码和数据段被初始化为可执行文件中的内容。最后加载器设置PC指向hello程序的代码段开头_start,程序便正式开始执行。
6.5 Hello的进程执行
用户模式和内核模式：处理器通常使用一个寄存器提供两种模式的区分，该寄存器描述了进程当前享有的特权，当没有设置模式位时，进程就处于用户模式中，用户模式的进程不允许执行特权指令，也不允许直接引用地址空间中内核区内的代码和数据；设置模式位时，进程处于内核模式，该进程可以执行指令集中的任何命令，并且可以访问系统中的任何内存位置。
时间片：一个进程执行它的控制流的一部分的每一时间段叫做时间片。
逻辑控制流：一系列程序计数器PC的值的序列叫做逻辑控制流，进程是轮流使用处理器的，在同一个处理器核心中，每个进程执行它的流的一部分后被抢占（暂时挂起），然后轮到其他进程。
上下文信息：上下文就是内核重新启动一个被抢占的进程所需要的状态，它由通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的值构成。
看hello的运行，当运行到sleep，shell会并发的去执行另一个进程，如图6.5.1所示，在上下文切换的时候，会进入内核模式，且有以下动作：
1） 保存A进程的上下文
2）恢复B进程被保存的上下文
3）将控制传递给这个B进程 ，来完成上下文切换
图6.5.1 时间片的切换
6.6 hello的异常与信号处理
hello执行过程中可能出现四类异常：中断、陷阱、故障和终止。
中断是来自I/O设备的信号，异步发生，中断处理程序对其进行处理，返回后继续执行调用前待执行的下一条代码，就像没有发生过中断。
陷阱是有意的异常，是执行一条指令的结果，调用后也会返回到下一条指令，用来调用内核的服务进行操作。帮助程序从用户模式切换到内核模式。
故障是由错误情况引起的，它可能能够被故障处理程序修正。如果修正成功，则将控制返回到引起故障的指令，否则将终止程序。
终止是不可恢复的致命错误造成的结果，通常是一些硬件的错误，处理程序会将控制返回给一个abort例程，该例程会终止这个应用程序。
会受到的信号太多太多，收到信号如果未用signal函数，则会按默认行为执行。
程序执行时：
按回车：按下回车，程序不会有响应直到程序结束，会多几个空命令行
图6.6.1 按回车效果图
按Ctrl-C：当按下ctrl-c之后，shell父进程收到SIGINT信号，信号处理函数的逻辑是结束hello，并回收hello进程。
图6.6.2 按Ctrl-C效果图
按Ctrl-Z：
+ps：可发现目前hello也在进程列表里
图6.6.3 ps命令
+jobs：
图6.6.4 jobs命令
+pstree：
图6.6.5 pstree命令
+fg：hello会继续放到前台来执行
图6.6.6 fg命令
+kill：
图6.6.7 kill命令
6.7本章小结
本章讲述了进程的概念，作用，介绍了shell的功能，处理流程，如何启动一个可执行目标程序，以及在进程执行的时候信号的发送和处理
（第6章1分）
第7章 hello的存储管理
7.1 hello的存储器地址空间
物理地址：CPU通过地址总线的寻址，找到真实的物理内存对应地址。 CPU对内存的访问是通过连接着CPU和北桥芯片的前端总线来完成的。在前端总线上传输的内存地址都是物理内存地址。
逻辑地址：程序代码经过编译后出现在 汇编程序中地址。逻辑地址由选择符（在实模式下是描述符，在保护模式下是用来选择描述符的选择符）和偏移量（偏移部分）组成。
线性地址：是指一个非负整数地址的有序集合，例如{0,1,2,3……}。在采用虚拟内存的系统中，CPU从一个有N = 2n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间。
虚拟地址：逻辑地址经过段机制后转化为线性地址，为描述符:偏移量的组合形式。分页机制中线性地址作为输入。
Intel处理器采用段页式存储管理，前者将逻辑地址转换为线性地址从而得到虚拟地址，后者将虚拟地址转换为物理地址。
以hello程序为例，反汇编可以得到这样一段汇编代码“mov $0x400772,%edi”，其中0x400772其实是逻辑地址的偏移地址，必须加上隐含的DS数据段的基地址才能构成线性空间地址，或者说0x400772是当前任务DS数据段的偏移。
这样得到的线性地址其实是数据存储的虚拟地址，还需要经过MMU转换为物理地址，转换为其物理内存的地址。
7.2 Intel逻辑地址到线性地址的变换-段式管理
（以下格式自行编排，编辑时删除）
图7.2.1虚拟地址空间
Intel处理器从逻辑地址到线性地址的变换通过段式管理，介绍段式管理就必须了解段寄存器的相关知识。段寄存器对应着内存不同的段，有栈段寄存器（SS）、数据段寄存器（DS）、代码段寄存器（CS）和辅助段寄存器（ES/GS/FS）。
段寄存器用于存放段选择符，通过段选择符可以得到对应段的首地址。段选择符分为三个部分，分别是索引、TI（决定使用全局描述符表还是局部描述符表）和RPL（CPU的当前特权级）。
图7.2.2 段选择符
这样，Intel处理器在通过段式管理寻址时，首先通过段描述符得到段基址，然后与偏移量结合得到线性地址，从而得到了虚拟地址。至于偏移量，基址寄存器还是变址寄存器有不同的计算方法，后者需要经过乘比例因子等处理。
7.3 Hello的线性地址到物理地址的变换-页式管理
（以下格式自行编排，编辑时删除）
虚拟地址（VA）到物理地址（PA）之间的转换通过分页机制完成。而分页机制是对虚拟地址内存空间进行分页。
首先Linux系统有自己的虚拟内存系统，其虚拟内存组织形式如图7.5，Linux将虚拟内存组织成一些段的集合，段之外的虚拟内存不存在因此不需要记录。内核为hello进程维护一个段的任务结构即图中的task_struct，其中条目mm指向一个mm_struct，它描述了虚拟内存的当前状态，pgd指向第一级页表的基地址（结合一个进程一串页表），mmap指向一个vm_area_struct的链表，一个链表条目对应一个段，所以链表相连指出了hello进程虚拟内存中的所有段。
图7.3.1 页表
如图7.3.1，页表是这类地址转换的另一个重要概念，它将虚拟页映射到物理页，其每一项称为页表条目（PTE），由有效位和一个n位的地址字段组成。如果设置有效位说明该页已缓存，否则未缓存，在地址字段不为空的情况下指向虚拟页在磁盘上的起始地址。
从虚拟地址到物理地址的翻译通过MMU（内存管理单元），它通过虚拟地址索引到对应的PTE，如果已缓存则命中，否则不命中称为缺页。发生缺页时，MMU会选择一个牺牲页，在物理内存将之前缺页的虚拟内存对应的数据复制到它的位置，并更新页表，然后重新触发虚拟地址翻译事件。
通过页表，MMU可以实现从虚拟地址到物理地址的映射。
图7.3.2 地址翻译
如图7.3.2，不考虑TLB与多级页表（在7.4节中包含这两者的综合考虑），虚拟地址分为虚拟页号v*n和虚拟页偏移量VPO，根据位数限制分析（可以在7.4节中看到分析过程）可以确定v*n和VPO分别占多少位是多少。通过页表基址寄存器PTBR+v*n在页表中获得条目PTE，一条PTE中包含有效位、权限信息、物理页号，如果有效位是0+NULL则代表没有在虚拟内存空间中分配该内存，如果是有效位0+非NULL，则代表在虚拟内存空间中分配了但是没有被缓存到物理内存中，如果有效位是1则代表该内存已经缓存在了物理内存中，可以得到其物理页号PPN，与虚拟页偏移量共同构成物理地址PA。
7.4 TLB与四级页表支持下的VA到PA的变换
每次CPU产生一个虚拟地址，MMU就必须查阅相应的PTE，这显然造成了巨大的时间开销，为了消除这样的开销，MMU中存在一个关于PTE的小的缓存，称为翻译后备缓冲器（TLB）。
TLB通过虚拟地址v*n部分进行索引，如图7.4.1，分为索引（TLBI）与标记（TLBT）两个部分。
图7.4.1虚拟地址访问TLB的用法
这样，MMU在读取PTE时会直接通过TLB，如果不命中再从内存中将PTE复制到TLB。
图7.4.2 TLB命中与不命中
在Intel Core i7环境下虚拟地址空间48位，物理地址空间52位，页表大小4KB，4级页表，如图7.4.3。TLB 4路16组相联。
解析前提条件：由一个页表大小4KB，一个PTE条目8B，共512个条目，使用9位二进制索引，一共4个页表共使用36位二进制索引，所以v*n共36位，因为VA 48位，所以VPO 12位；因为TLB共16组，所以TLBI需4位，因为v*n 36位，所以TLBT 32位。
如图 ，CPU产生虚拟地址VA，VA传送给MMU，MMU使用前36位v*n作为TLBT（前32位）+TLBI（后4位）向TLB中匹配，如果命中，则得到PPN（40bit）与VPO（12bit）组合成PA（52bit）。
如果TLB中没有命中，MMU向页表中查询，CR3确定第一级页表的起始地址，v*n1（9bit）确定在第一级页表中的偏移量，查询出PTE，如果在物理内存中且权限符合，确定第二级页表的起始地址，以此类推，最终在第四级页表中查询到PPN，与VPO组合成PA，并且向TLB中添加条目。
如果查询PTE的时候发现不在物理内存中，则引发缺页故障。
图7.4.3 多级页表
7.5 三级Cache支持下的物理内存访问
（以下格式自行编排，编辑时删除）
三级cache的访问原理相同，故不分开讲解。
Cache有三种：直接映射高速缓存，组相联高速缓存，全相联高速缓存。
1.直接映射高速缓冲：
直接映射高速缓存每个组只有一行，当CPU执行一条读内存字w的指令，它会向L1高速缓存请求这个字。确定是否命中然后抽取的过程分为三步：1）组选择；2）行匹配；3）字抽取。
图7.5.1 直接映射的cache的组选择
如图7.5.1，组选择即从w的地址中间抽取出s个索引位，将其解释为一个对应组号的无符号整数，从而找到对应的组；行匹配即对组内的唯一一行进行判断，当有效位为1且标记位与从地址中抽取出的标记位相同则成功匹配，否则就得到不命中。
图7.5.2 行匹配和字选择
而字选择即在行匹配的基础上通过地址的后几位得到块偏移，从而在高速缓存块中索引到数据。
2.组相联高速缓存：
每个组内可以多于一个缓存行，总体逻辑类似于直接映射高速缓存，不同之处在于行匹配时每组有更多的行可以尝试匹配，遍历每一行。如果不命中，有空行时也就是冷不命中则直接存储在空行；如果没有空行也就是冲突不命中，则替换已有行，通常有LFU（最不常使用）、LRU（最近最少使用）两者替换策略。
3.全相联高速缓存：
全相联高速缓存只有一个组，且这个组包含所有的高速缓存行。对于全相联高速缓存，因为只有一个组，组选择变的十分简单。地址中不存在索引位，地址只被划分为一个标记位和一个块偏移。行匹配和字选择同组相联高速缓存。
7.6 hello进程fork时的内存映射
shell通过fork为hello创建新进程。当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给hello进程唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和样表的原样副本。它将两个进程中的每个页面都标记为只读，并将每个进程中的每个区域结构都标记为写时复制。
图7.6.1 fork的复制过程
当fork在新进程中返回时，新进程现在的虚拟内存刚好的和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就是为每个进程保持了私有地址空间的概念。
7.7 hello进程execve时的内存映射
加载并运行hello需要以下几个步骤：
删除已存在的用户区域，删除当前进程虚拟地址的用户部分中的已存在的区域结构。
映射私有区域，为新程序的代码、数据、bss和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为hello文件中的.text和.data区，bss区域是请求二进制零的，映射到匿名文件，其大小包含在hello中，栈和堆地址也是请求二进制零的，初始长度为零。
映射共享区域， hello程序与共享对象libc.so链接，libc.so是动态链接到这个程序中的，然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器（PC），execve做的最后一件事情就是设置当前进程上下文的程序计数器，使之指向代码区域的入口点。
图7.7.1 execve
7.8 缺页故障与缺页中断处理
假设MMU在试图翻译某个虚拟地址A时，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序随后就执行下面的步骤：
图7.8.1 访问内存几种情况
首先判断虚拟地址A是否合法，缺页处理程序会搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较。如果指令不合法则触发段错误，从而终止该进程。
然后处理程序会判断试图进行的内存访问是否合法，也就是进程是否有读写这个区域内页面的权限。如果访问不合法，那么处理程序会触发一个保护异常，终止这个进程。
最后，确保了以上两点的合法性后，根据页式管理的规则，牺牲一个页面，并赋值为需要的数据，然后更新页表并再次触发MMU的翻译过程。
7.9动态存储分配管理
Printf会调用malloc，请简述动态内存管理的基本方法与策略。
动态内存分配器维护着一个进程的虚拟内存区域，称为堆。分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用。空闲块可用来分配。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。
- 隐式空闲链表：
图7.9.1 隐式链表
空闲块通过头部中的大小字段隐含地连接着。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。
（1）放置策略：首次适配、下一次适配、最佳适配。
首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配从上一次查询结束的地方开始。最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。
（2）合并策略：立即合并、推迟合并。
立即合并就是在每次一个块被释放时，就合并所有的相邻块；推迟合并就是等到某个稍晚的时候再合并空闲块。
带边界标记的合并:
图7.9.2 边界标记
在每个块的结尾添加一个脚部，分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，从而使得对前面块的合并能够在常数时间之内进行。 - 显式空闲链表：
图7.9.3显式空闲链表结构
每个空闲块中，都包含一个pred（前驱）和succ（后继）指针。使用双向链表使首次适配的时间减少到空闲块数量的线性时间。
空闲链表中块的排序策略：一种是用后进先出的顺序维护链表，将新释放的块放置在链表的开始处，另一种方法是按照地址顺序来维护链表，链表中每个块的地址都小于它后继的地址。
分离存储：维护多个空闲链表，每个链表中的块有大致相等的大小。将所有可能的块大小分成一些等价类，也叫做大小类。
分离存储的方法：简单分离存储和分离适配。
7.10本章小结
本章讨论了存储器地址空间，段式管理、页式管理，TLB与四级页表支持下的VA到PA的变换，三级Cache支持下的物理内存访问，hello进程fork时和execve时的内存映射，缺页故障与缺页中断处理和动态存储分配管理。
（第7章 2分）
第8章 hello的IO管理
8.1 Linux的IO设备管理方法
设备的模型化：文件
设备管理：unix io接口
所有的I/O设备（例如网络、磁盘和终端）都被模型化为文件，而所有的输入和输出都被当做对相应文件的读和写来执行。这种将设备优雅地映射为文件的方式，允许Linux内核引出一个简单、低级的应用接口，称为Unix I/O，这使得所有的输入和输出都能以一种统一且一致的方式来执行。
8.2 简述Unix IO接口及其函数
打开和关闭文件:open()and close()
读写文件:read() and write()
改变当前的文件位置 lseek()
8.3 printf的实现分析
https://www.cnblogs.com/pianist/p/3315801.html
从vsprintf生成显示信息，到write系统函数，到陷阱-系统调用 int 0x80或syscall.
字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。
显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。
8.4 getchar的实现分析
异步异常-键盘中断的处理：键盘中断处理子程序。接受按键扫描码转成ascii码，保存到系统的键盘缓冲区。
getchar等调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。
8.5本章小结
输入输出看似简单，实际是一个非常精巧的过程，从程序发出请求到系统函数调用到设备相应，需要执行许多步骤，往往也是拖慢程序的主要因素和一些崩溃异常的高发地，需要谨慎选用函数、命令实现目的
（第8章1分）
结论
通过上文的学习与实践，可以大体概括hello程序所经历的过程：
生成阶段：预处理→编译→汇编→链接；
加载阶段：shell fork子进程→execve；
执行阶段：磁盘读取、虚拟内存映射、CPU执行指令、内核调度、缓存加载数据、信号处理、Unix I/O输入与输出；
终止阶段：进程终止、shell与内核对其进行回收。
一个简单的hello程序涉及一系列复杂的编译器、操作系统、硬件实现机制。程序的运行与内核、硬件的多方面协调工作密不可分。一个计算机系统的实现是从最简单的几条指令开始的。简单的一条指令需要底层的几个动作步骤，无论是内部处理还是输入输出。通过这些微小的部分的分工合作却能够完成那么多very cool的事。
做大作业的过程相当于复习了一下这个学期的知识，尤其是通过分析各种文件，我对编译汇编链接等过程的理解更加深刻了。这个大作业要求我们分析了hello程序运行各个阶段的底层实现，使我具体地认识到计算机系统的各个部分是怎样协调工作的。
（结论0分，缺失 -1分，根据内容酌情加分）
附件
列出所有的中间产物的文件名，并予以说明起作用。
hello.i(hello.c预处理之后的程序文本)
hello.s(hello.i编译成汇编语言之后的程序文本)
hello.o(hello.s生成的二进制文件)
hello(可执行的hello二进制文件)
helloobj.s(hello.o的反汇编)
helloobj1.s(hello的反汇编)
hello.elf(hello的elf信息)
（附件0分，缺失 -1分）
参考文献
为完成本次大作业你翻阅的书籍与网站等
1.深入理解计算机系统第三版
2.https://baike.baidu.com/item/预处理命令/10204389
3.https://blog.****.net/shiyongraow/article/details/81454995
4.https://blog.****.net/u011555996/article/details/70211315
5.https://docs.oracle.com/cd/E26926_01/html/E25910/chapter6-54839.html
6.https://baike.baidu.com/item/逻辑地址/3283849?fr=aladdin
7.https://baike.baidu.com/item/线性地址
8.https://baike.baidu.com/item/虚拟地址
9.https://www.cnblogs.com/huangwentian/p/7487670.html
10.https://blog.****.net/youyou519/article/details/82659007
11.https://docs.oracle.com/cd/E26926_01/html/E25910/chapter6-83432.html
12.https://www.cnblogs.com/pianist/p/3315801.html
（参考文献0分，缺失 -1分）