计算机系统

大作业

题 目 程序人生-Hello’s P2P
专 业 计算机类
学　　 号 1190201802
班　　 级 1903012
学 生 张靓雯 　
指 导 教 师 史先俊

计算机科学与技术学院
2021年5月
摘 要
经过一学期的学习，我们深入了解了计算机操作系统。通过本文，我们将结合本学期所学内容，在ubuntu下利用gcc等操作去领略hello程序的一生经历，借此深化对所学内容的理解，并增强知识的连贯性，梳理知识盲点，深入理解计算机底层的种种操作。

关键词：操作系统；ubuntu；hello程序；编译；链接；进程；

目 录

第1章 概述 - 5 -
1.1 Hello简介 - 5 -
1.2 环境与工具 - 5 -
硬件环境：Intel® Core™ i7-8500U CPU；1.99GHz；16.0G RAM；476.81GHD Disk - 5 -
软件环境：Windows10 64位；Vmware Workstation 15.5.0；Ubuntu 18.04.5 ; LTS 64位 - 5 -
开发工具：vim，gcc，as，ld，edb，readelf，HexEdit - 5 -
1.3 中间结果 - 5 -
1.4 本章小结 - 6 -
第2章 预处理 - 7 -
2.1 预处理的概念与作用 - 7 -
2.2在Ubuntu下预处理的命令 - 7 -
2.3 Hello的预处理结果解析 - 8 -
2.4 本章小结 - 9 -
第3章 编译 - 10 -
3.1 编译的概念与作用 - 10 -
3.2 在Ubuntu下编译的命令 - 10 -
3.3 Hello的编译结果解析 - 11 -
3.3.1. hello.s中的指令 - 11 -
3.3.2. 数据 - 12 -
3.3.3. 赋值 - 12 -
3.3.4. 算数操作 - 13 -
3.3.5. 关系操作 - 13 -
3.3.6. 控制转移操作 - 14 -
3.3.7. 函数操作 - 14 -
3.4 本章小结 - 14 -
第4章 汇编 - 15 -
4.1 汇编的概念与作用 - 15 -
4.2 在Ubuntu下汇编的命令 - 15 -
4.3 可重定位目标elf格式 - 16 -
4.4 Hello.o的结果解析 - 18 -
4.5 本章小结 - 20 -
第5章 链接 - 21 -
5.1 链接的概念与作用 - 21 -
5.2 在Ubuntu下链接的命令 - 21 -
5.3 可执行目标文件hello的格式 - 21 -
5.4 hello的虚拟地址空间 - 24 -
5.5 链接的重定位过程分析 - 25 -
5.6 hello的执行流程 - 27 -
5.7 Hello的动态链接分析 - 28 -
5.8 本章小结 - 29 -
第6章 hello进程管理 - 30 -
6.1 进程的概念与作用 - 30 -
6.2 简述壳Shell-bash的作用与处理流程 - 30 -
6.3 Hello的fork进程创建过程 - 31 -
6.4 Hello的execve过程 - 31 -
6.5 Hello的进程执行 - 32 -
6.6 hello的异常与信号处理 - 33 -
6.7本章小结 - 36 -
第7章 hello的存储管理 - 37 -
7.1 hello的存储器地址空间 - 37 -
7.2 Intel逻辑地址到线性地址的变换-段式管理 - 37 -
7.3 Hello的线性地址到物理地址的变换-页式管理 - 38 -
7.4 TLB与四级页表支持下的VA到PA的变换 - 39 -
7.5 三级Cache支持下的物理内存访问 - 41 -
7.6 hello进程fork时的内存映射 - 41 -
7.7 hello进程execve时的内存映射 - 42 -
7.8 缺页故障与缺页中断处理 - 42 -
7.9动态存储分配管理 - 42 -
7.10本章小结 - 44 -
第8章 hello的IO管理 - 45 -
8.1 Linux的IO设备管理方法 - 45 -
8.2 简述Unix IO接口及其函数 - 45 -
8.3 printf的实现分析 - 46 -
8.4 getchar的实现分析 - 48 -
8.5本章小结 - 48 -
结论 - 48 -
附件 - 50 -
参考文献 - 51 -

第1章 概述
1.1 Hello简介
根据Hello的自白，利用计算机系统的术语，简述Hello的P2P，020的整个过程。
1.P2P（From Program to Process）
编写高级语言程序得到.c文件->cpp处理得到.i文件->ccl编译器编译得到.s汇编语言文件->利用汇编器（as）获得重定位的.o目标文件->链接器（ld）与库函数链接得到可执行文件hello。Linux>./hello执行此文件，shell会调用fork函数为其fork产生子进程，再调用execve函数加载进程。于是hello从程序转变为了进程。
020（From Zero-0 to Zero-0）
子进程调用execve加载hello，创建新的区域结构以提供给hello的代码、数据、bss和栈区域，映射虚拟内存，载入物理内存，然后进入程序入口处开始执行，然后进入main函数，CPU为hello分配时间片执行逻辑控制流。
为让hello程序能够调用硬件进行从键盘读入字符，操作系统将I/O设备都抽象为文件，进而实现向屏幕输入输出。hello执行完成后操作系统回收hello进程，内核从系统中删除hello所有相关数据，hello一生结束。
1.2 环境与工具
硬件环境：Intel® Core™ i7-8500U CPU；1.99GHz；16.0G RAM；476.81GHD Disk
软件环境：Windows10 64位；Vmware Workstation 15.5.0；Ubuntu 18.04.5 ; LTS 64位
开发工具：vim，gcc，as，ld，edb，readelf，HexEdit
1.3 中间结果
列出你为编写本论文，生成的中间结果文件的名字，文件的作用等。
文件名 文件功能
hello.c 源程序
hello.i 预处理之后得到的文本文件
hello.s 编译得到的汇编文件
hello.o 汇编得到的可重定位目标文件
hello 链接得到的可执行目标文件
hello.elf hello.o的ELF格式
hello.elf2 hello的ELF格式

1.4 本章小结
本章是对hello的一个整体的介绍，简要介绍了hello.c的P2P与O2O，完成本文相关内容需要的实验环境以及工具，并展示了实验过程中的中间结果文件。
（第1章0.5分）

第2章 预处理
2.1 预处理的概念与作用
概念:
在程序设计中，预处理是在编译之前调用预处理器进行的处理。一般指的是在程序源代码被翻译为目标代码的过程中，生成二进制代码之前的过程，预处理器（cpp）会根据以字符#开头的命令，修改原始的C程序，并生成.i文件。
作用：
1.预处理可以扩展源代码，插入所有用#include命令指定的文件。
2.扩展所有用#define声明指定的宏，又称宏展开。
3.根据#if以及#endif和#ifdef以及#ifndef后面的条件决定需要编译的代码
2.2在Ubuntu下预处理的命令
1.cpp hello.c > hello.i

2.gcc -E hello.c -o hello.i（将上一条指令生成的.i文件删除后执行）

2.3 Hello的预处理结果解析
预处理得到了三千多行的.i文件

main函数主体内容没有什么变化，注释部分被删除，文件中的头文件stdio.h、 unistd.h、 stdlib.h展开成为三个头文件的源码。预编译程序可以识别一些特殊的符号，并在源程序中用合适的值进行替换。
2.4 本章小结
本章围绕预处理展开，介绍了预处理的概念和作用，Ubuntu下预处理使用到的的指令，并对hello.c文件的预处理结果hello.i文本文件进行解析，了解了经过预处理后程序会发生什么样的变化，加深了对预处理的理解。

（第2章0.5分）

第3章 编译
3.1 编译的概念与作用

概念：
将源语言经过词法分析、语法分析、语义分析以及一系列优化后生成汇编代码的过程。编译器将预处理得到的文本文件 hello.i 翻译成文本文件 hello.s。
作用：
将源语言经过词法分析、语法分析、语义分析以及一系列优化后生成汇编代码，即将高级语言程序转化为机器可直接识别处理执行的的机器码的中间步骤。
1.词法分析：编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，方法分为两种：自上而下分析法和自下而上分析法。
2.语法分析：在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等
3.语义分析：即静态语法检查，对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。
4.代码优化：对程序进行多种等价变换，使得从变换后的程序出发，能生成更有效的目标代码

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

3.3 Hello的编译结果解析
3.3.1. hello.s中的指令

内容 含义
.filet 声明源文件
.text 声明代码段
.globl 声明全局变量
.secetion .rodata 声明rodata节，只读数据
.align 声明对齐方式
.string 声明一个string类型
.size 声明大小
.type 声明是函数类型还是对象类型

3.3.2. 数据
1.全局变量main：main为全局变量，且类型为function，保存在.text节

2.局部变量int i：

i被保存在%rbp-4的位置处。
3.数组char *argv[]：
数组的起始地址存放在栈中%rbp-32的位置，指针数组，用来存放指向命令行字符串参数的指针，每一个元素指向一个参数。

4.字符串：
有两个字符串，都存在只读数据段中

作为参数：

5.立即数：在代码中直接体现
3.3.3. 赋值
主要用到了movl与movq，如图所示

movl操作四个字节，movq操作八个字节
3.3.4. 算数操作
指令 效果
leaq s,d d=&s
add s,d d=d+s
sub s,d d=d-s
3.3.5. 关系操作
指令 效果 描述
cmp S1,S2 S2-S1 比较-设置条件码

如图中把cmpl指令与je、jle搭配使用，对应原函数中的如下图圈中的位置，用于条件判断

3.3.6. 控制转移操作
1.je：比较argc和4，如果等于则跳转到.L2

2.jle：比较i和7，如果i小于等于7，则跳转到.L4

3.jmp：无条件跳转
3.3.7. 函数操作
1.puts函数：

2.sleep函数：

3.exit函数：

4.atoi函数：

5.printf函数：

6.getchar函数：

3.4 本章小结
本章内容围绕编译展开，介绍了编译的概念以及作用，说明了ubuntu下的编译命令，对hello.i程序进行编译获得了hello.s程序，并对hello.s程序进行了解析，分析了其数据、操作等，加深了对汇编文件的理解。
（第3章2分）

第4章 汇编
4.1 汇编的概念与作用
概念：
汇编器（as）将.s 汇编程序翻译成机器语言指令，把这些指令打包成可重定位目标程序的格式，并将结果保存在.o 目标文件中，.o 文件是一个二进制文件，它包含程序的指令编码。
作用：
汇编就是将高级语言转化为机器可直接识别执行的代码文件的过程，汇编器将.s 汇编程序翻译成机器语言指令，把这些指令打包成可重定位目标程序的格式，并将结果保存在.o 目标文件中，.o 文件是一个二进制文件，它包含程序的指令编码。

4.2 在Ubuntu下汇编的命令
指令：1. as hello.s -o hello.o

2.gcc -o hello.s -o hello.o

4.3 可重定位目标elf格式
1.指令：readelf -a hello.o > hello.elf

2.ELF头：以 16B 的序列 Magic 开始，Magic 描述了生成该文件的系统的字的大小和字节顺序，余下部分指明了类别，数据，版本，OS/ABI,ABI,ELF头的大小、目标文件的类型、机器类型、字节头部表的文件偏移，以及节头部表中条目的大小和数量等信息

3.节头表：节头表包括节名称，节的类型，节的属性（读写权限），节在ELF文件中所占的长度以及节的对齐方式和偏移量。

4.重定位节：，包含.text 节和.eh_frame中需要进行重定位的信息，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。

5.符号表：存放程序中定义和引用的函数和全局变量的信息。
name：符号名称
value：对于可重定位目标模块，value是符号相对于目标节的起始位置偏移，对于可执行目标文件，该值是一个绝对运行的地址
size：目标的大小
type：类型，数据或函数。
Bind：表明符号是本地的还是全局

4.4 Hello.o的结果解析
（以下格式自行编排，编辑时删除）
objdump -d -r hello.o 分析hello.o的反汇编，并请与第3章的 hello.s进行对照分析。
说明机器语言的构成，与汇编语言的映射关系。特别是机器语言中的操作数与汇编语言不一致，特别是分支转移函数调用等。
1.指令：objdump -d -r hello.o
2.执行结果：

3.与hello.s对比分析：
(1)分支转移：hello.s文件中分支转移使用段名称进行跳转，hello.o文件中通过地址进行跳转。

(2)函数调用：因为 hello.c 中调用的函数都是共享库中的函数，最终都需要通过动态链接器才能确定函数的运行时执行地址，在汇编成为机器语言的时候，对于这些不确定地址的函数调用，将其 call 指令后的相对地址设置为全 0，然后在.rela.text 节中为其添加重定位条目，等待静态链接的进一步确定。所以在.s 文件中，函数调用之后直接跟着函数名称，而在反汇编序中，call 的目标地址是当前下一条指令。
(3)全局变量：hello.s文件中，全局变量通过语句“段地址+%rip”完成，在于hello.o的反汇编后生成的代码中是通过“0+%rip”实现，因为.rodata节中的数据是在运行时确定的，也需要重定位，现在填0占位，并为其在.rela.text节中添加重定位条目。

4.5 本章小结
本章围绕汇编展开，阐述了汇编的概念以及作用，指出了在ubuntu下的汇编指令，利用指令查看了hello.o的可重定位目标文件的格式，对可重定位目标文件进行了简要的介绍。并使用反汇编查看了hello.o经过反汇编后生成的代码并与hello.s进行了对比分析。
（第4章1分）

第5章 链接
5.1 链接的概念与作用
概念：
将各种机器代码和数据的片段进行收集并组合成一个单一的链接后的文件的编译过程, 这个单一文件的链接可被应用程序加载(或者复制)到一个内存并加载和执行。
作用：链接可以执行于编译时，也就是源代码被翻译成机器代码时；也可以执行于加载时，即程序被加载器加载到内存并执行时；甚至执行于运行时，也就是由应用程序来执行。
链接使得应用程序分离的编译过程成为了可能,程序员们可以把一个大的应用程序和连接器分开进行编译,独立进行管理和单独进行修改。极大的提升了进行大型文件编写的效率。
5.2 在Ubuntu下链接的命令
指令：
1.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.3 可执行目标文件hello的格式
分析hello的ELF格式，用readelf等列出其各段的基本信息，包括各段的起始地址，大小等信息。
1.指令：readelf -a hello > hello.elf2

2.ELF头：

3.节头表：各节的基本信息均在节头表（描述目标文件的节）中进行了声明。节头表（包括名称，大小，类型，全体大小，地址，旗标，偏移量，对齐等信息），

4.重定位节：

5.符号表：

5.4 hello的虚拟地址空间
使用edb加载hello，查看本进程的虚拟地址空间各段信息，并与5.3对照分析说明。
1.在data dump中查看加载到虚拟地址情况：

2.各节位置和名称：地址和名称与5.3相对应

3.利用节头表可以去到各个节，比如下图为.text节：

5.5 链接的重定位过程分析
1.指令：objdump -d -r hello
2.执行结果：

3.与hello.o的区别：
hello.o没有经过链接，所以main的地址从0开始，并且不存在调用的如printf这样函数的代码。hello将hello.o需要重定位的部分进行了重定位，并将其地址转变成了虚拟空间中绝对地址，并在后面标出执行函数的地址和函数名；将库函数添加到了文件中，并添加了节。

4.hello中出现了许多新的节：
节名称 描述
.interp 保存 ld.so 的路径
.note.ABI-tag Linux 下特有的 section
.hash 符号的哈希表
.gnu.hash GNU 拓展的符号的哈希表
.dynsym 运行时/动态符号表
.dynstr 存放.dynsym 节中的符号名称
.gnu.version 符号版本
.gnu.version_r 符号引用版本
.rela.dyn 运行时/动态重定位表
.rela.plt .plt 节的重定位条目
.init 程序初始化需要执行的代码
.plt 动态链接-过程链接表
.fini 当程序正常终止时需要执行的代码
.eh_frame 包含异常展开和源语言信息。
.dynamic 存放被 ld.so使用的动态链接信息
.got 动态链接-全局偏移量表-存放变量
.got.plt 动态链接-全局偏移量表-存放函数
.data 初始化了的数据
.comment 包含编译器的NULL-terminated字符串

5.6 hello的执行流程
利用edb执行hello获得各个过程以及各个过程地址：
ld-2.27.so!_dl_start
ld-2.27.so!_dl_init
hello!_start
libc-2.27.so!_libc_start_main
libc-2.27.so!_cxa_atexit
libc_2.27.so!_new_exitfn
hello!_libc_csu_init
hello!_init
libc-2.27.so!_sigsetjmp
libc-2.27.so!_sigjmp
Call main hello!main
libc-2.27.so!exit
如图所示:

5.7 Hello的动态链接分析
由于无法预测函数的运行时地址，对于动态共享链接库中 PIC 函数，编译器需要添加重定位记录，等待动态链接器处理。链接器采用延迟绑定的策略，防止运行时修改调用模块的代码段。
动态链接器使用过程链接表PLT+全局偏移量表GOT实现函数的动态链接，GOT中存放函数目标地址，PLT使用GOT中地址跳转到目标函数。
如果一个目标模块调用定义在共享库中的任何函数，那么就有自己的GOT和PLT。前者是数据段的一部分，后者为代码段的一部分。PLT是一个数组，其中每个条目是16字节代码。每个库函数都有自己的PLT条目，PLT[0]是一个特殊的条目，跳转到动态链接器中。从PLT[2]开始的条目调用用户代码调用的函数。GOT同样是一个数组，每个条目是8字节的地址，和PLT联合使用时，GOT[2]是动态链接在ld-linux.so模块的入口点，其余条目对应于被调用的函数，在运行时被解析。每个条目都有匹配的PLT条目。当某个动态链接函数第一次被调用时先进入对应的PLT条目例如PLT[2]，然后PLT指令跳转到对应的GOT条目中例如GOT[4]，其内容是PLT[2]的下一条指令。然后将函数的ID压入栈中后跳转到PLT[0]。PLT[0]通过GOT[1]将动态链接库的一个参数压入栈中，再通过GOT[2]间接跳转进动态链接器中。动态链接器使用两个栈条目来确定函数的运行时位置，用这个地址重写GOT[4]，然后再次调用函数。经过上述操作，再次调用时PLT[2]会直接跳转通过GOT[4]跳转到函数而不是PLT[2]的下一条地址。
根据下图可知，GOT起始表位置为0x601000。

在调用dl_init之前0x601008后的16个字节均为0，对于每一条PIC函数调用，调用的目标地址都实际指向PLT 中的代码逻辑，GOT存放的是PLT中函数调用指令的下一条指令地址，如下图：

调用_start之后该位置发生了发生改变，如下图：

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

5.8 本章小结

本章围绕链接展开，阐述了链接的概念以及作用，说明了ubuntu下的链接指令，并对hello的ELF格式各个部分进行了分析，还使用edb加载hello，查看本了进程的虚拟地址空间各段信息，并通过反汇编hello文件，将其与hello.o反汇编文件进行了对比，详细了解了重定位过程；此外，还遍历了整个hello的执行过程，在最后对hello进行了动态链接分析。
（第5章1分）

第6章 hello进程管理
6.1 进程的概念与作用
概念：
狭义定义：进程是正在运行的程序的实例（an instance of a computer program that is being executed）。
广义定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。
进程的概念主要有两点：第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用的指令和本地变量。第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时（操作系统执行之），它才能成为一个活动的实体，我们称其为进程。 [3]
进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念,所有多道程序设计操作系统都建立在进程的基础上。
作用：
进程为应用程序提供两个抽象，一是独立的逻辑控制流，一个是私有的地址空间。提高CPU的执行效率，减少因为程序等待带来的CPU空转以及其它计算机软硬件资源浪费。在现代计算机中，进程为用户提供了以下假象：我们的程序好像是系统中当前运行的唯一程序 一样，我们的程序好像是独占的使用处理器和内存，处理器好像是无间断的执行 我们程序中的指令，我们程序中的代码和数据好像是系统内存中唯一的对象。

6.2 简述壳Shell-bash的作用与处理流程
作用：
Shell是用户与操作系统之间完成交互式操作的一个接口程序，它为用户提供简化了的操作。而NU组织发现sh是比较好用的又进一步开发Borne Again Shell，简称bash，它是Linux系统中默认的shell程序。
处理流程：
（1）从终端读入输入的命令。
（2）切分命令行字符串，获取命令行参数
（3）检查第一个命令行参数是否是一个内置的shell命令，是则立即执行，如果不是，则用fork创建子程序
（4）子进程中，进行步骤（2）获得参数，调用exceve（）执行制定程序
（5）命令行末尾没有&，代表前台作业，shell使用waitpid等待作业终止后返回
（6）命令行末尾有&，代表后台作业，shell返回
6.3 Hello的fork进程创建过程
终端程序通过调用fork()函数创建一个子进程，子进程得到与父进程完全相同但是独立的一个副本，包括代码段、段、数据段、共享库以及用户栈。子进程还获得与父进程任何打开文件描述符相同的副本，父进程和子进程最大的不同时他们的PID是不同的。父进程与子进程是并发运行的独立进程，内核能够以任意方式交替执行它们的 逻辑控制流的指令。在子进程执行期间，父进程默认选项是显示等待子进程的完成。
在终端Terminal中键入./hello 1190201802，运行的终端程序会对输入的命令行进行解析，发现hello 不是一个内置的shell命令所以解析之后终端程序判断./hello 的语义为执行当前目录下的可执行目标文件 hello，之后终端程序首先会调用 fork 函数创建一个新的运行的子进程，新创建的子进程几乎父进程相同，但是是独立的一个副本，包括代码段、段、数据段、共享库以及用户栈。内核能够以任意方式交替执行父子进程的逻辑控制流的指令，父进程与子进程是并发运行而独立的。在子进程执行期间，父进程默认选项是显示等待子进程的完成。

6.4 Hello的execve过程
Execve函数加载并运行可执行目标文件hello，且包含相对应的一个带参数的列表argv和环境变量的列表exenvp,，只有当出现错误时，例如找不到hello文件时，execve才会返回-1到调用程序，execve调用成功则不会产生返回。

1. 为子进程调用函数fork之后，子进程调用execve函数（传入命令行参数）在当前进程的上下文中加载并运行一个新程序hello。
2. 为执行hello程序加载器、删除子进程现有的虚拟内存段，execve 调用驻留在内存中的、被称为启动加载器的操作系统代码，并创建一组新的代码、数据、堆和栈段。
3. 新的栈和堆段被初始化为零，通过将虚拟地址空间中的页映射到可执行文件的页大小的片，新的代码和数据段被初始化为可执行文件中的内容。最后加载器设置PC指向_start 地址，_start 最终调用 hello中的 main 函数。
4. 除了一些头部信息，在加载过程中没有任何从磁盘到内存的数据复制。直到 CPU 引用一个被映射的虚拟页时才会进行复制，这时，操作系统利用它的页面调度机制自动将页面从磁盘传送到内存。

6.5 Hello的进程执行
进程的执行并不一定是完整、连续地执行完成，每一个进程在执行时都会有其对应的时间片。
1.逻辑控制流：一系列程序计数器 PC 的值的序列叫做逻辑控制流，在同一个处理器核心中，每个进程执行它的流的一部分后被抢占（暂时挂起），然后轮到其他进程，进程轮流使用处理器，。
2.时间片：一个进程执行它的控制流的一部分的每一时间段叫做时间片。
3.上下文信息：上下文就是内核重新启动一个被抢占的进程所需要的状态。它由通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的值构成。
4.用户模式和内核模式：处理器通常使用一个寄存器描述了进程当前享有的特权，对两种模式区分。设置模式位时，进程处于内核模式，该进程可以访问系统中的任何内存位置，可以执行指令集中的任何命令；当没有设置模式位时，进程就处于用户模式中，用户模式的进程不允许执行特权指令，也不允许直接引用地址空间中内核区内的代码和数据。
Linux 系统中的每个程序都运行在一个进程上下文中，有自己的虚拟地址空间。当shell 运行一个程序时，父进程生成一个子进程，它是父进程的一个复制。子进程通过execve 函数系统调用启动加载器。加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆和栈段。新的栈和堆段被初始化为零。通过将虚拟地址空间中的页映射到可执行文件的页大小的片(chunk), 新的代码和数据段袚初始化为可执行文件的内容。最后，加载器跳转到_start地址，它最终会调用应用程序的main 函数。
sleep进程调度：

6.6 hello的异常与信号处理
（以下格式自行编排，编辑时删除）
hello执行过程中会出现哪几类异常，会产生哪些信号，又怎么处理的。
程序运行过程中可以按键盘，如不停乱按，包括回车，Ctrl-Z，Ctrl-C等，Ctrl-z后可以运行ps jobs pstree fg kill 等命令，请分别给出各命令及运行结截屏，说明异常与信号的处理。
hello执行过程中可能出现四类异常：中断、陷阱、故障和终止。

中断：来自I/O设备的信号，异步发生，中断处理程序对其进行处理，返回后继续执行调用前待执行的下一条代码，就像没有发生过中断。

陷阱：有意的异常，是执行一条指令的结果，调用后也会返回到下一条指令，用来调用内核的服务进行操作。帮助程序从用户模式切换到内核模式。

故障：由错误情况引起的，它可能能够被故障处理程序修正。如果修正成功，则将控制返回到引起故障的指令，否则将终止程序。

终止：不可恢复的致命错误造成的结果，通常是一些硬件的错误，处理程序会将控制返回给一个abort例程，该例程会终止这个应用程序。
ctrl+Z操作：向进程发送了一个sigtstp信号，让进程暂时挂起，输入ps命令符可以发现hello进程还没有被关闭。

ctrl+C操作：向进程发送一个sigint信号，让进程直接结束，输入ps命令可以发现当前hello进程已经被终止了。

fg命令：使后台挂起的进程继续运行。

jobs命令：可以查看当前的关键命令

pstree命令：用进程树的方法把各个进程用树状图的方式连接起来

kill命令：向固定进程发送某些信号，kill -s 30 81664，就表示向PID为81664的进程hello，发送了一个电源故障的信号，然后用fg命令让他继续运行就会出现故障内容提醒。

6.7本章小结

本章围绕hello的进程管理展开，简述了进程的概念与作用、shell-bash的作用与处理流程，并对hello的fork进程创建过程、execve过程以及进程的执行进行了阐述与操作展示。
（第6章1分）

第7章 hello的存储管理
7.1 hello的存储器地址空间
逻辑地址：
逻辑地址（Logical Address）是指由程序hello产生的与段相关的偏移地址部分（hello.o）。逻辑地址空间的格式为“段地址：偏移地址”，例如“23:8048000”，在实模式下可以转换为物理地址：逻辑地址CS：EA = 物理地址CS × 16 + EA。保护模式下以段描述符作为下标，通过在GDT/LDT表获得段地址，段地址加偏移地址得到线性地址。
线性地址：
线性地址（Linear Address）是逻辑地址到物理地址变换之间的中间层。程序hello的代码会产生逻辑地址，或者说是（即hello程序）段中的偏移地址，它加上相应段的基地址就生成了一个线性地址。
物理地址：
物理地址（Physical Address）是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。计算机的主存被组织成一个由M个连续的字节大小的单元组成的数组，每个字节都有一个唯一的物理地址，CPU访问内存的最自然的方式就是物理寻址。
虚拟地址：
有时我们也把逻辑地址称为虚拟地址。因为与虚拟内存空间的概念类似，逻辑地址也是与实际物理内存容量无关的，是hello中的虚拟地址。

7.2 Intel逻辑地址到线性地址的变换-段式管理
（1）实地址模式：在实地址模式下，处理器使用20位的地址总线，可以访问1MB(0~FFFFF)内存。而8086的模式，只有16位的地址线，不能直接表示20位的地址，采用内存分段的解决方法。段地址存放于16位的段寄存器中（CS、DS、ES或SS）

（2）保护模式：在保护模式下，段寄存器存放段描述符在段描述符表中的索引值，称为段选择器，此时CS存放代码段描述符的索引值，DS存放数据段描述符的索引值，SS存放堆栈段描述符的索引值。以段描述符作为下标，到GDT/LDT表查表获得段地址，段地址+偏移地址=线性地址。
段寄存器：段寄存器用于存放段选择符，通过段选择符可以得到对应段的首地址。段选择符分为三个部分，分别是索引、TI（决定使用全局描述符表还是局部描述符表）和RPL（CPU的当前特权级）。
段选择符：
15 14 32 10
索引 TI RPL
TI=0，选择全局描述符表(GDT)，TI=1，选择局部描述符表(LDT)，RPL=00，为第0级，位于最高级的内核态，RPL=11，为第3级，位于最低级的用户态，第0级高于第3级。高13位-8K个索引用来确定当前使用的段描述符在描述符表中的位置
7.3 Hello的线性地址到物理地址的变换-页式管理
页表是一个页表条目(PTE)的数组，将虚拟页地址映射到物理页地址：
虚拟地址空间中的每个页（VP）在页表固定位置有一个PTE
虚拟页存在未分配的、缓存的、未缓存的三种状态。其中缓存的页对应于物理页。
PTE由一个有效位和一个n位地址字段组成，有效位表示虚页是否被缓存，当有效位为0，空地址（地址为空）表示虚拟页还未分配

页表基址寄存器存放当前进程的物理页表地址，虚拟地址通过在页表中匹配页表条目来获得PPN，加上物理页偏移量即物理地址。若与页表中的条目不匹配则触发缺页错误，缺页处理程序调入新的页面并更新PTE，再次执行访存指令
线性地址被分成了3部分，由低位到高位依次为VPO、TLB索引、TLB标记。其中TLB是位于MMU中的关于PTE的缓存，称为翻译后备缓冲器。
进行地址翻译时，现根据TLB索引及标记找到相应PPN，若标记位的有效位为0，则直接到PTE中去找，将PPN与VPO串联起来，就得到了相应的物理地址。

每次将虚拟地址转换为物理地址，都会查询页表来判断一个虚拟页是否缓存在DRAM的某个地方，如果不在DRAM的某个地方，通过查询页表条目可以知道虚拟页在磁盘的位置。页表将虚拟页映射到物理页。如下图所示，页表就是一个页表条目的数组，每一个页表条目是由一个有效位和一个n为地址字段组成。

7.4 TLB与四级页表支持下的VA到PA的变换
每次CPU产生一个虚拟地址，MMU就必须查阅相应的PTE，这显然造成了巨大的时间开销，为了消除这样的开销，MMU中存在一个关于PTE的小的缓存，称为翻译后备缓冲器（TLB）。

如上图所示：36位VPN 被划分成四个9 位的片，每个片被用作到一个页表的偏移量。CR3 寄存器包含Ll页表的物理地址。VPN 1 提供到一个Ll PET 的偏移量，这个PTE 包含L2 页表的基地址。VPN 2 提供到一个L2 PTE 的偏移量，以此类推。

如上图所示，CPU 会产生虚拟地址 VA，VA 传送给 MMU，MMU 使用前 36 位 VPN 作为 TLBT（前 32 位）+TLBI（后 4 位）向 TLB 中匹配。
如果命中，则得到 PPN （40bit）与 VPO（12bit）组合成 PA（52bit），如果 TLB 中未命中，MMU 向页表中查询，CR3 确定第一级页表的起始地址，VPN1（9bit）确定在第一级页表中的偏移量，查询出 PTE，如果在物理内存中且权限符合，确定第二级页表的起始地址，以此类推，最终在第四级页表中查询到 PPN，与VPO组合成 PA，并且向 TLB 中添加条目。如果查询 PTE的时候发现不在物理内存中，则引发缺页故障。如果发现权限不够，则引发段错误。

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

1. 得到物理地址VA，首先使用物理地址的CI进行组索引（每组8路），对8路的块分别匹配 CT进行标志位匹配。如果匹配成功且块的valid标志位为1，则命中hit。然后根据数据偏移量 CO取出数据并返回。
2. 若没找到相匹配的或者标志位为0，则miss。那么cache向下一级cache，这里是二级cache甚至三级cache中寻找查询数据。然后逐级写入cache。
3. 在更新cache的时候，需要判断是否有空闲块。若有空闲块（即有效位为0），则写入；若不存在，则进行驱逐一个块（LRU策略）。

7.6 hello进程fork时的内存映射

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

1. 删除已存在的用户区域，将shell与hello都有的区域结构删除。
2. 映射私有区域，为新程序的代码、数据、bss和栈区域创建新的区域结构，均为私有的、写时复制的。
3. 映射共享区域，将一些动态链接库映射到hello的虚拟地址空间
4. 最后设置程序计数器，使之指向hello程序的代码入口。
   7.8 缺页故障与缺页中断处理
   缺页故障是当指令引用一个虚拟地址，在 MMU 中查找页表时发现与该地址相对应的物理地址不在内存中，因此必须从磁盘中取出的时候就会发生故障。

缺页中断处理：
1.首先判断虚拟地址A是否合法，缺页处理程序会搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较。如果指令不合法则触发段错误，从而终止该进程。
2.处理程序会判断试图进行的内存访问是否合法，也就是进程是否有读写这个区域内页面的权限。如果访问不合法，那么处理程序会触发一个保护异常，终止这个进程。
3.确保了以上两点的合法性后，根据页式管理的规则，选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面并更新页表。当缺页处理程序返回时，CPU 重新启动引起缺页的指令，这条指令再次发送 VA 到MMU，这次 MMU 就能正常翻译 VA 了。
7.9动态存储分配管理
动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap) 。系统之间细节不同，但是不失通用性，假设堆是一个请求二进制零的区域，它紧接在未初始化的数据区域后开始，并向上生长（向更高的地址） 。对于每个进程，内核维护着一个变量brk, 它指向堆的顶部。
分配器分为两种基本风格：显式分配器和隐式分配器，显式分配器必须在严格的约束条件下工作。
维护块时有不同的记录方法：
1.显式空闲链表：
显式空闲链表采用的方式是维护空闲块链表, 而不是所有块。在空闲块中储存前/后指针，而不仅仅是大小，此外还需要边界标记，用于块合并。幸运的是，只需跟踪空闲块，因此可以使用有效载荷区域
将空闲块组织成链表形式的数据结构。堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个 pred（前驱）和 succ（后继）指针，如下图所示：

2.分离的空闲链表：
分离存储，是一种流行的减少分配时间的方法。一般思路是将所有可能的块大小分成一些等价类/大小类。
分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。
3.隐式空闲链表：隐式空闲链表分配器的实现涉及到特殊的数据结构。其所使用的堆块是由一个子的头部、有效载荷，以及可能的一些额外的填充组成的。头部含有块的大小以及是否分配的信息。有效载荷用来存储数据，而填充块则是用来对付外部碎片以及对齐要求。
1）找到一个空闲块，有以下适配方法：
首次适配 (First fit)：从头开始搜索空闲链表，选择第一个合适的空闲块。此时搜索时间与总块数是线性关系，且倾向在靠近链表起始处留下小空闲块的
“碎片”，增加对较大块的搜索时间
下一次适配 (Next fit)：和首次适配相似，只是从链表中上一次查询结束的地方开始，这种适配比首次适应更快，可以避免重复扫描那些无用块
最佳适配 (Best fit)：查询链表，选择一个最好的空闲块：满足适配且剩余空闲空间最少，保证碎片最小，提高内存利用率，运行速度通常会慢于首次适配
2）分割 (splitting)：申请空间比空闲块小，可以把空闲块分割成两部分
3）释放并分配：清除已分配标志，合并相邻的空闲块，和下一个空闲块合并或者双向合并

7.10本章小结
本章围绕hello的存储管理展开，阐述了储存器的地址空间、Intel逻辑地址到线性地址的变换-段式管理、Hello的线性地址到物理地址的变换-页式管理、TLB与四级页表支持下的VA到PA的变换、 三级Cache支持下的物理内存访问，说明了进程fork和execve时的内存映射的内容，描述了系统如何应对出现的缺页异常，并说明了malloc的动态内存分配管理机制。
（第7章 2分）

第8章 hello的IO管理
8.1 Linux的IO设备管理方法
设备管理：unix io接口
设备的模型化：所有的 IO 设备都被模型化为文件，而所有的输入和输出都被当做对相应文件的读和写来执行，这种将设备优雅地映射为文件的方式，允许Linux 内核引出一个简单低级的应用接口，称为 Unix I/O
8.2 简述Unix IO接口及其函数
接口：
1.打开文件。一个应用程序通过要求内核打开相应的文件，来宣告它想要访问一个 I/O 设备，内核返回一个小的非负整数，叫做描述符，它在后续对此文件的所有操作中标识这个文件，内核记录有关这个打开文件的所有信息，应用程序只需要记住这个描述符。
2.linux shell 创建的每个进程开始时都有三个打开的文件：标准输入（描述符为0) 、标准输出（描述符为1) 和标准错误（描述符为2) 。头文件< unistd.h> 定义了常量STDIN_FILENO 、STOOUT_FILENO 和STDERR_FILENO, 它们可用来代替显式的描述符值。
3.改变当前的文件位置：对于每个打开的文件，内核保持着一个文件位 置 k，初始为 0，这个文件位置是从文件开头起始的字节偏移量，应用 程序能够通过执行 seek，显式地将改变当前文件位置 k。
4.读写文件。一个读操作就是从文件复制n>0 个字节到内存，从当前文件位置k 开始，然后将k增加到k+n 。给定一个大小为m 字节的文件，当k~m 时执行读操作会触发一个称为end-of-file(EOF) 的条件，应用程序能检测到这个条件。在文件结尾处并没有明确的“EOF 符号” 。类似地，写操作就是从内存复制n>0 个字节到一个文件，从当前文件位置k开始，然后更新k 。
5.关闭文件。当应用完成了对文件的访问之后，它就通知内核关闭这个文件。作为响应，内核释放文件打开时创建的数据结构，并将这个描述符恢复到可用的描述符池中。无论一个进程因为何种原因终止时，内核都会关闭所有打开的文件并释放它们的内存资源.
函数：
1.打开和关闭文件。
打开文件函数原型：int open(char* filename,int flags,mode_t mode)
返回值：若成功则为新文件描述符，否则返回-1；
flags：O_RDONLY（只读），O_WRONLY（只写），O_RDWR（可读写）
mode：指定新文件的访问权限位。
关闭文件函数原型：int close(fd)
返回值：成功返回0，否则为-1
2.读和写文件
读文件函数原型：ssize_t read(int fd,void *buf,size_t n)
返回值：成功则返回读的字节数，若EOF则为0，出错为-1
描述：从描述符为fd的当前文件位置复制最多n个字节到内存位置buf
写文件函数原型：ssize_t wirte(int fd,const void *buf,size_t n)
返回值：成功则返回写的字节数，出错则为-1
描述：从内存位置 buf 复制至多 n 个字节到描述符为 fd 的当前文件位置

8.3 printf的实现分析
printf函数：
static int printf(const char *fmt, …)
{
va_list args;
int i;
va_start(args, fmt);
write(1,printbuf,i=vsprintf(printbuf, fmt, args));
va_end(args);
return i;
}
函数调用了两个外部函数：vsprintf和write。
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); 

}
则知道 vsprintf 程序按照格式 fmt 结合参数 args 生成格式化之后的字符串，并返回字串的长度。
在 printf 中调用系统函数 write(buf,i)将长度为i的buf输出。write 函数如下：
write:
mov eax, _NR_write
mov ebx, [esp + 4]
mov ecx, [esp + 8]
int INT_VECTOR_SYS_CALL
来看sys_call函数
sys_call:
call save
push dword [p_proc_ready]
sti
push ecx
push ebx
call [sys_call_table + eax * 4]
add esp, 4 * 3
mov [esi + EAXREG - P_STACKBASE], eax
cli
ret
函数功能：显示格式化的字符串。将要输出的字符串从总线复制到显卡的显存中。
字符显示驱动子程序将通过ASCII码在字模库中找到点阵信息将点阵信息存储到vram中。
显示芯片会按照一定的刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。
于是我们的打印字符串就显示在了屏幕上。
从vsprintf生成显示信息，到write系统函数，到陷阱-系统调用 int 0x80或syscall.
字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。
显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。

8.4 getchar的实现分析

getchar等调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。运行到getchar函数时，程序将控制权交给os。当你键入时，内容进入缓寸并在屏幕上回显。按enter，通知 os输入完成，这时再将控制权在交还给程序。异步异常-键盘中断的处理：键盘中断处理子程序。接受按键扫描码转成ascii码，保存到系统的键盘缓冲区。getchar调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。

8.5本章小结
本章是最后一章，围绕hello的IO管理，阐述了Linux的IO设备管理方法，Unix IO接口及其函数，进行了printf的实现分析和getchar的实现分析。
（第8章1分）
结论
用计算机系统的语言，逐条总结hello所经历的过程。
你对计算机系统的设计与实现的深切感悟，你的创新理念，如新的设计与实现方法。
Hello的一生经历了被编写成代码、预处理、编译、汇编、链接、运行、创建子进程、加载、执行指令、访问内存、动态内存分配、发送信号、终止。
它的一生充实饱满，完成了它所能实现的所以事情。
hello利用它充实的一生向我们展示了一个程序的生命历程，带我们加深了对计算机系统的理解。
(1)预处理：从.c生成.i文件，将.c中调用的外部库展开合并到.i中
(2)编译：由.i生成.s汇编文件
(3)汇编：将.s文件翻译为机器语言指令，并打包成可重定位目标程序hello.o
(4)链接：将.o可重定位目标文件和动态链接库链接成可执行目标程序hello
(5)运行：在shell中输入命令
(6)创建子进程：shell用fork为程序创建子进程
(7)加载：shell调用execve函数,将hello程序加载到该子进程，映射虚拟内存
(8)执行指令：CPU为进程分配时间片，加载器将计数器预置在程序入口点，则hello可以顺序执行自己的逻辑控制流
(9)访问内存：MMU将虚拟内存地址映射成物理内存地址，CPU通过其来访问
(10)动态内存分配：根据需要申请动态内存
(11)信号：shell的信号处理函数可以接受程序的异常和用户的请求
(12)终止：执行完成后父进程回收子进程，内核删除为该进程创建的数据结构

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

附件
列出所有的中间产物的文件名，并予以说明起作用。
（附件0分，缺失 -1分）

参考文献
为完成本次大作业你翻阅的书籍与网站等
[1] https://baike.baidu.com/item/%E8%BF%9B%E7%A8%8B/382503