哈工大计算机系统大作业

• 摘要
• 第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.3.1 数据
    • 3.3.2 赋值
    • 3.3.3 类型转换
    • 3.3.4 算术操作
    • 3.3.5 关系操作
    • 3.3.6 数组
    • 3.3.7 控制转移
    • 3.3.8 函数操作
  • 3.4 本章小结
• 第4章 汇编
• • 4.1 汇编的概念与作用
  • 4.2 在Ubuntu下汇编的命令
  • 4.3 可重定位目标elf格式
  • • 4.3.1 ELF头
    • 4.3.2 节头表
    • 4.3.3 符号表
    • 4.3.4 重定位节.rela.text
  • 4.4 Hello.o的结果解析
  • 4.5 本章小结
• 第5章 链接
• • 5.1 链接的概念与作用
  • 5.2 在Ubuntu下链接的命令
  • 5.3 可执行目标文件hello的格式
  • • 5.3.1 ELF头
    • 5.3.2 节头表
    • 5.3.3 符号表
    • 5.3.4 段头表
  • 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.6.1 不停乱按，包括回车
    • 6.6.2 Ctrl-Z
    • 6.6.3 Ctrl-C
    • 6.6.4 Ctrl-z后运行ps jobs pstree fg kill 等命令
  • 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本章小结
• 结论
• 附件
• 参考文献

摘要

本文主要通过观察hello.c程序在Linux系统下的生命周期，探讨hello.c源程序的预处理、编译、汇编、链接、生成可执行文件并运行的主要过程。同时结合课本中所学知识详细说明系统是如何实现对hello程序的进程管理，存储管理和I/O管理。通过对hello.c程序的生命周期的探索，让我们对可执行文件的生成和执行以及其它相关的计算机系统的知识有更深的理解。
关键词：预处理，编译，汇编，链接，加载，进程管理，存储管理，I/O管理

第1章 概述

1.1 Hello简介

根据hello的自白，利用计算机系统的术语，简述hello的P2P，020的整个过程。
P2P：在Linux系统下，hello.c源程序经过预处理(cpp)、编译(ccl)、汇编(as)、链接(ld)最终生成可执行目标文件hello。然后在shell中键入./hello+学号+姓名+秒数，shell会自动fork一个新的子进程，然后再调用execve函数将hello程序加载到新创建的子进程中。由此便实现了由程序(Program)到进程(Process)的转变，即为P2P。
020：Linux加载器execve将程序加载到新创建的进程中，之后通过虚拟内存映射将程序从磁盘载入物理内存中执行，这其中包括段式管理、页式管理等等。然后CPU为该进程分配时间片，执行该程序对应的逻辑控制流。当程序执行结束后，hello进程向其父进程发送一个SIGCHLD信号，最后父进程回收hello进程，释放hello的内存并删除进程上下文。所以整个hello程序就是从无到有最后再到无的过程，即020(From Zero to Zero)。

1.2 环境与工具

硬件环境：X64 CPU；2GHz；2G RAM；256GHD Disk 以上
软件环境：Windows7 64位以上；VirtualBox/Vmware 11以上；Ubuntu 16.04 LTS 64位/优麒麟 64位
开发与调试工具：gcc，gedit，edb，readelf

1.3 中间结果

1.4 本章小结

本章主要介绍了hello.c程序P2P，020的过程。列出了本次实验所需的环境和工具以及过程中所生成的中间结果。

第2章 预处理

2.1 预处理的概念与作用

概念：预处理(或称预编译)是指在进行编译的第一遍扫描(词法扫描和语法分析)之前所作的工作。预处理指令指示在程序正式编译前就由编译器进行的操作，可放在程序中任何位置。
作用：
1.将源文件中以”include”格式包含的文件复制到编译的源文件中。
2.用实际值替换用“#define”定义的字符串。
3.根据“#if”后面的条件决定需要编译的代码。
4.合理使用预处理功能编写的程序便于阅读、修改、移植和调试，也有利于模块化程序设计。

2.2 在Ubuntu下预处理的命令

命令：gcc hello.c -E -o hello.i

2.3 Hello的预处理结果解析

使用gedit查看hello.i内容如下：(部分截取)

由上图可以看出，预处理对原文件中的宏进行了宏展开，头文件中的内容被包含进该文件中。例如声明函数、定义结构体、定义变量、定义宏等内容。最后hello.c文件变为hello.i文件。

2.4 本章小结

本章介绍了预处理的概念以及作用。通过具体的hello实例说明预处理过程中对头文件的解析，同时截图展示了预处理的过程和结果。

第3章 编译

3.1 编译的概念与作用

概念：编译器ccl将文本文件hello.i翻译成文本文件 hello.s，它包含一个汇编语言程序。它以高级程序设计语言书写的源程序作为输入，而以汇编语言或机器语言表示的目标程序作为输出。
作用：将预处理后的程序编译为更接近计算机语言，更容易让计算机理解的语言，相当于一个翻译的过程。除此之外，编译程序还具备语法检查、目标程序优化等功能。

3.2 在Ubuntu下编译的命令

命令：gcc hello.i -S -o hello.s

3.3 Hello的编译结果解析

3.3.1 数据

1.常量

由上图可以看出，hello程序中的常量为两个字符串，这两个字符串都是printf函数的参数。

2.变量

从源程序中可以看出在main函数里声明了一个局部变量i，在编译器编译生成汇编语言后，i被存储在了-4(%rbp)的位置，如下图所示：

除此之外，还有main函数的参数argc和argv，其中argv为指针数组。同时由寄存器规则可知，argc存储在了寄存器%edi(第一个参数)中，argv存储在了寄存器%rsi(第二个参数)中。验证如下：

由上图可知，argc被存储在了-20(%rbp)的位置，argv被存储在了-32(%rbp)的位置。

3.3.2 赋值

hello.c程序中的赋值操作为i=0，具体在汇编代码中的实现形式为movl $0, -4(%rbp)，其中l后缀表明i是双字类型的整数数据，即占4个字节的整数数据(int型)。其它情况的后缀还有b(一个字节)，w(两个字节)，q(八个字节)。

3.3.3 类型转换

hello.c程序中涉及的类型转换为atoi(argv[3])，该语句实现了将字符串类型转换为整数类型。

3.3.4 算术操作

hello.c程序中出现的算术操作为i++，又因为i为int类型，所以实现i++只需要用addl指令即可。具体实现指令为addl $1, -4(%rbp)。

3.3.5 关系操作

(1) argc != 4。该语句用于判断argc的值是否与4相等，该语句被编译为cmpl $4, -20(%rbp)。比较完成后会设置条件码，通过条件码判断跳转位置。如下图：

(2)i<8。该语句用于判断局部变量i和8的大小作为循环的条件，在汇编代码中被编译为cmpl $7, -4(%rbp)。通过比较完成后的条件码确定跳转位置。如下图：

3.3.6 数组

hello.c程序中的数组为argv[]，其为一个指针数组，具体分析见3.3.1中相关内容。

3.3.7 控制转移

(1)if语句。判断argc是否为4，若为4，则执行if体的语句，若不是，则不执行。对应的汇编代码如下：

(2)for循环体。for(i=0;i<8;i++)，每次循环前判断i是否小于8，若满足，则执行循环体，否则不执行。对应的汇编代码如下：

循环体对应的汇编代码如下：

3.3.8 函数操作

(1)main函数
main函数的参数为argc和argv。argc存储在%edi中，argv存储在%rsi中。返回值为int类型，存储在%eax中。
(2)printf函数
hello.c程序中调用了两次printf函数，但是两次调用传入的参数不同。第一次传入的是.LC0处的字符串，汇编代码具体实现如下：

第二次传入的是.LC1处的字符串以及argv[1]和argv[2]，汇编代码具体实现如下：

(3)exit函数
exit函数实现从main函数退出。hello.c程序中传入的参数是1，表示非正常退出。汇编代码具体实现如下：

(4)atoi函数
atoi函数实现将字符串类型的数据转变成int类型的数据，传入的参数为argv[3]。汇编代码具体实现如下：

(5)sleep函数
sleep函数实现程序休眠，传入的参数为atoi(argv[3])(表示休眠秒数)。汇编代码具体实现如下：

(6)getchar函数
getchar函数实现读取缓冲区字符。不需要传递参数，直接调用即可。汇编代码具体实现如下：

3.4 本章小结

本章主要讲述了编译的概念和作用。并且对hello.c程序的编译过程进行了截图展示。详细说明了hello.c程序的编译结果，展示了相应语句的汇编代码。通过对编译过程和结果的展示，加深了对编译结果的理解和运用。

第4章 汇编

4.1 汇编的概念与作用

概念：把汇编语言翻译成机器语言的过程称为汇编。在汇编语言中，用助记符(Memoni)代替操作码，用地址符号(Symbol)或标号(Label)代替地址码。这样用符号代替机器语言的二进制码，就把机器语言变成了汇编语言。于是汇编语言亦称为符号语言。用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言翻译成机器语言，这种起翻译作用的程序叫汇编程序，汇编程序是系统软件中语言处理的系统软件。
作用：汇编过程将汇编代码转换为计算机能够理解并执行的二进制机器代码，这个二进制机器代码是程序在本机器上的机器语言的表示。

4.2 在Ubuntu下汇编的命令

命令：gcc hello.s -c -o hello.o

4.3 可重定位目标elf格式

4.3.1 ELF头

用命令readelf -h hello.o查看
ELF头以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。其中包括ELF头的大小、目标文件的类型、机器类型、节头部表的文件偏移，以及节头部表中条目的大小和数量。
通过readelf命令读取hello.o的ELF头内容如下：

由上图可以看出，hello.o为64位文件；数据采用补码表示，小端存储；文件类型为REL(可重定位的目标文件)；程序的入口地址为0x0，因为hell.o还未实现重定位；可重定位文件没有段头表(Start of program headers的值为0)；节头表的起始位置为1240；文件中共有14节。

4.3.2 节头表

用命令readelf -S hello.o查看
节头表包含了文件中出现的各个节的语义，包括节的类型、位置和大小等信息。 由于是可重定位目标文件，所以每个节都从0开始，用于重定位。在文件头中得到节头表的信息，然后再使用节头表中的字节偏移信息得到各节在文件中的起始位置，以及各节所占空间的大小，同时可以观察到，代码是可执行的，但是不能写；数据段和只读数据段都不可执行，而且只读数据段也不可写。
通过readelf命令读取hello.o的节头表内容如下：

由上图可以看出，节头表中一共有14项，其中第一项为空。剩下13项对应于可重定位文件中每一节的相关内容，其中包含每一节的名字，类型，地址(由于还未重定位所以每一节的地址都用0代替)，在文件中的偏移量，节的大小，访问权限，对齐方式等等。

4.3.3 符号表

用命令readelf -s hello.o查看
符合表存放程序中定义和引用的函数和全局变量的信息。
通过readelf命令读取hello.o的符号表内容如下：

由上图可以看出，符号表中存储了程序中定义和使用的各种符号，包括函数名，全局变量名等等。其中每一个符号有其对应的值，大小，类型，名字等等内容。Bind字段表明符号是本地的还是全局的。

4.3.4 重定位节.rela.text

用命令readelf -r hello.o查看
重定位节：一个.text 节中位置的列表，包含.text 节中需要进行重定位的信息，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
通过readelf命令读取hello.o的.rela.text节内容如下：

由上图可以看出，.rela.text节包含很多项，每一项中包含了很多个字段。
各个字段的含义如下：
Offset:需要被修改的引用节的偏移。
Info：包括symbol和type两个部分，symbol在前面四个字节，type在后面四个字节。symbol：标识被修改引用应该指向的符号；type:重定位的类型。
Type：告知链接器应该如何修改新的应用。
Addend：一个有符号常数，一些重定位要使用它对被修改引用的值做偏移调整。 Name:重定向到的目标的名称。

4.4 Hello.o的结果解析

hello.o的反汇编代码如下：

hello.s的内容如下：

通过观察可以看出反汇编代码和hello.s中的代码并没有太大的差别。只是反汇编代码中不仅有汇编代码，还有其对应的机器语言代码。机器语言代码是完全面向计算机的二进制数据表示的语言。机器语言代码中包含操作码，数据，寄存器编号等内容，其中机器语言的每一个操作码，寄存器编号等都与汇编语言一一对应。机器语言中的数据采用小端存储的二进制形式表示，而在汇编语言中采用的是顺序十六进制形式表示。通过这些映射关系就可以实现机器语言与汇编语言的一一对应。
分支转移：反汇编代码中用的不是hello.s中的符号来代表位置，如.L1等。而是用的相对地址表示。hello.s中的.L1等只是便于编写的助记符，在变成机器语言后自然就不会存在了。
函数调用：在.s 文件中，函数调用之后直接跟着函数名称，而在反汇编代码中，call的目标地址是当前下一条指令。这是因为 hello.c 中调用的函数都是共享库中的函数，最终需要通过动态链接器才能确定函数的运行时执行地址。在汇编成为机器语言的时候，对于这些不确定地址的函数调用，将其call指令后的相对地址设置为全0，最后在链接时才填入正确的地址。

4.5 本章小结

本章介绍了汇编的概念和作用，并通过对hello.s的汇编结果的分析简要讲述了可重定位文件的格式，重点讲述了可重定位文件的ELF头，节头表，符号表和.rela.text节的内容。最后比较了反汇编结果与汇编文件hello.s的区别。

第5章 链接

5.1 链接的概念与作用

概念：链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可以被加载到内存并执行。链接可以执行于编译时，也就是在源代码被编译成机器代码时；也可以执行于加载时，也就是在程序被加载器加载到内存并执行时；甚至于运行时，也就是由应用程序来执行。
作用：链接使得分离编译成为可能。我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以把它分解为更小、更好管理的模块，可以独立地修改和编译这些模块。当我们改变这些模块中的一个时，只需简单地重新编译它，并重新链接应用，而不必重新编译其它文件。

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.3 可执行目标文件hello的格式

5.3.1 ELF头

由上图可以看出，hello的ELF头中指出hello的类型为EXEC类型，即hello为可执行目标文件，同时hello的入口地址非零，说明重定位工作已完成。注意到hello的ELF头中program headers的偏移量非零，说明hello文件中比hello.o文件中多了一个段头表。同时hello文件中节头表的条目数量为27，比hello.o文件中的数目多。

5.3.2 节头表

由上图可以看出，hello中节头表的条目数多于hello.o中节头表的条目数。值得注意的是每一节都有了实际地址，而不是像在hello.o中那样地址值全为0。这说明重定位工作已完成。同时多出的节是为了能够实现动态链接，如.interp这一节包含动态链接器的路径名，动态链接器通过执行一系列重定位工作完成链接任务。

5.3.3 符号表

由上图可以看出，hello程序的符号表包含编号Num、Value、Size、Type、Bind、Vis、Ndx、Name字段。

5.3.4 段头表

通过命令readelf -l hello查看。

段头表描述了可执行目标文件的连续的片与连续的虚拟内存段之间的映射关系。从段头表中可以看到根据可执行目标文件的内容初始化为两个内存段，分别为只读内存段(代码段)和读写代码段(数据段)。

5.4 hello的虚拟地址空间

通过查看edb可以看出程序从0x400000开始。
从5.3.1的ELF头中可以看出程序的入口地址为0x4010f0，对应于节头表中.text节的起始地址。通过edb查看如下：

5.3.2的节头表中的.interp节的起始地址为0x4002e0。通过edb查看如下：

由上图可以看出0x4002e0位置处放的正是动态链接器的路径名。

根据5.3.2节头表中的各个节的位置信息可以找到各个节在内存中的位置。比如.rodata节的起始位置为0x402000。通过edb查看如下：

从图中可以看出printf语句中的格式串%s %s位于.rodata节，属于只读数据。

5.5 链接的重定位过程分析

通过命令objdump -d -r hello > hello2.txt得到hello文件的反汇编代码。

通过比较hello和hello.o的反汇编代码，可以得到如下不同：
1.hello.o的反汇编代码的地址从0开始，而hello的反汇编代码从0x400000开始。这说明hello.o还未实现重定位的过程，每个符号还没有确定的地址，而hello已经实现了重定位，每个符号都有其确定的地址。
2.hello中除了main函数的汇编代码，还有很多其它函数的汇编代码。如下图所示：

其中_init是程序初始化需要执行的代码，.plt是动态链接的过程链接表。

3.对于跳转，返回指令的地址hello中已经有了明确的数据(PC相对或者是绝对)，而hello.o中的地址位置全为0。

由此可以看出链接是会为地址不确定的符号分配一个确定的地址，而在该符号的引用处也将地址改为确定值。

hello的重定位过程：
在汇编器生成一个目标模块时，它并不知道数据和代码最终将放在内存中的什么位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码的重定位条目放在.rel.text节中，已初始化数据的重定位条目放在.rel.data中。重定位条目具有如下结构：

其中offset是需要被修改的引用的节偏移。symbol标识被修改引用应该指向的符号。type告知链接器如何修改新的引用。addend是一个有符号常数，一些类型的重定位要使用它对被修改引用的值做偏移调整。
ELF中定义了32中不同的重定位类型。其中比较常用的是R_X86_64_PC32和R_X86_64_32。前者重定位一个使用32位PC相对地址的引用，后者重定位一个使用32位绝对地址的引用。
PC相对寻址的重定位代码如下：

下图为hello.o反汇编代码中的一节，从中可以看出该重定位采用PC相对寻找。

通过查询hello的ELF文件内容得到main函数地址为0x401125，.rodata的地址为0x402008。将数据带入运算可得：
*refptr = （unsigned）（ADDR（.rodata）+addend - ADDR（main）- Offset）
  =（unsigned）(0x402008 + (-4) – 0x401125-0x1c)
  =（unsigned）(0xec3)
将结果与hello的反汇编代码比较，发现结果正确。
同理可以得到其他重定位条目。

5.6 hello的执行流程

5.7 Hello的动态链接分析

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。虽然动态链接把链接过程推迟到了程序运行时，但是在形成可执行文件时（注意形成可执行文件和执行程序是两个概念），还是需要用到动态链接库。比如我们在形成可执行程序时，发现引用了一个外部的函数，此时会检查动态链接库，发现这个函数名是一个动态链接符号，此时可执行程序就不对这个符号进行重定位，而把这个过程留到装载时再进行。

PLT：PLT是一个数组，其中每个条目是16字节代码。PLT[0]是一个特殊条目，它跳转到动态链接器中。每个被可执行程序调用的库函数都有它自己的PLT条目。每个条目都负责调用一个具体的函数。
GOT：GOT是一个数组，其中每个条目是8字节地址。和PLT联合使用时，GOT[O]和GOT[1]包含动态链接器在解析函数地址时会使用的信息。GOT[2]是动态链接器在1d-linux.so模块中的入口点。其余的每个条目对应于一个被调用的函数，其地址需要在运行时被解析。每个条目都有一个相匹配的PLT条目。
通过查看hello的ELF文件如下图：

GOT表在调用dl_init之前的内容如下：

在dl_init调用后内容如下图：

从图中可以看出，在dl_init调用之后，该处的两个8字节的数据都发生了改变。
和PLT联合使用时，GOT[0]和GOT[1]包含动态链接器在解析函数地址时会使用的信息。其中GOT[1]指向重定位表（依次为.plt节需要重定位的函数的运行时地址）用来确定调用的函数地址， GOT[2]是动态链接器ld-linux.so模块中的入口点。

5.8 本章小结

本章主要介绍了链接的概念和作用，详细介绍了hello.o是如何链接生成一个可执行文件的。同时展示了可执行文件中不同节的内容。最后分析了程序是如何实现的动态链接的。

第6章 hello进程管理

6.1 进程的概念与作用

概念：进程的经典定义是一个执行中程序的实例，系统的每个程序都运行在某个进程的上下文。上下文是由程序正确运行所需的状态组成的，这个状态包括存放在内存里的程序的代码和数据，它的栈，通用目的寄存器的内容，程序计数器，环境变量以及打开文件描述符的集合。
作用：向用户提供了一种假象。 我们的程序好像是系统中当前运行的唯一程序一样，我们的程序好像是独占的使用处理器和内存。处理器好像是无间断的执行我们程序中的指令，我们程序中的代码和数据好像是系统内存中唯一的对象。

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

Linux系统中，Shell是一个交互型应用级程序，代表用户运行其他程序(是命令行解释器，以用户态方式运行的终端进程)。

其基本功能是解释并运行用户的指令，重复如下处理过程：
(1)终端进程读取用户由键盘输入的命令行。
(2)分析命令行字符串，获取命令行参数，并构造传递给execve的argv向量
(3)检查第一个(首个、第0个）命令行参数是否是一个内置的shell命令
(4)如果不是内部命令，调用fork( )创建新进程/子进程
(5)在子进程中，用步骤2获取的参数，调用execve( )执行指定程序。
(6)如果用户没要求后台运行(命令末尾没有&号）否则shell使用waitpid（或wait)等待作业终止后返回。
(7)如果用户要求后台运行(如果命令末尾有&号），则shell返回。

6.3 Hello的fork进程创建过程

当在shell上输入./hello命令时，命令行会首先判断该命令是否为内置命令，如果是内置命令则立即对其进行解释。否则将其看成一个可执行目标文件，再调用fork创建一个新进程并在其中执行。
当shell运行一个程序时，父进程通过fork函数生成这个程序的进程。新创建的子进程几乎但不完全与父进程相同，包括代码、数据段、堆、共享库以及用户栈。父进程和新创建的子进程之间最大的区别在于他们有不同的PID。父进程与子进程是并发运行的独立进程，内核能够以任意方式交替执行它们的逻辑控制流的指令。

6.4 Hello的execve过程

execve函数加载并运行可执行目标文件filename，且带参数列表argv和环境变量列表envp。只有当出现错误时，例如找不到filename，execve才会返回到调用程序。加载并运行需要以下几个步骤：

1.删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。
2.映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些区域结构都是私有的，写时复制的。虚拟地址空间的代码和数据区域被映射为hello文件的.txt和.data区。bss区域是请求二进制零的，映射匿名文件，其大小包含在hello文件中。栈和堆区域也是请求二进制零的，初始长度为零。
3.映射共享区域。如果hello程序与共享对象链接，比如标准C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域。
4.设置程序计数器（PC）。exceve做的最后一件事就是设置当前进程的上下文中的程序计数器，使之指向代码区域的入口点。下一次调用这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。

6.5 Hello的进程执行

上下文信息：上下文就是内核重新启动一个被抢占的进程所需要的状态，它由通用寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构等对象的值构成。
进程时间片：一个进程执行它的控制流的一部分的每一时间段叫做时间片。
用户态和内核态：处理器通常使用一个寄存器提供两种模式的区分，该寄存器描述了进程当前享有的特权，当没有设置模式位时，进程就处于用户模式中，用户模式的进程不允许执行特权指令，也不允许直接引用地址空间中内核区内的代码和数据；设置模式位时，进程处于内核模式，该进程可以执行指令集中的任何命令，并且可以访问系统中的任何内存位置。
上下文切换：当一个进程正在执行时，内核调度了另一个新的进程运行后，它就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。在进行上下文切换时，需要保存以前进程的上下文，恢复新恢复进程被保存的上下文，将控制传递给这个新恢复的进程来完成上下文切换。

hello的进程执行过程如下：
hello初始运行在用户模式，在hello进程调用sleep之后陷入内核模式，内核处理休眠请求主动释放当前进程以加载新的进程进行执行。同时将hello进程从运行队列中移入到等待队列，定时器开始计时，内核进行上下文切换将当前进程的控制权交给其他进程并执行，当定时器到时时发送一个中断信号，此时进入内核状态执行中断处理，将hello进程从等待队列中移出重新加入到运行队列，成为就绪状态，hello进程就可以继续进行自己的控制逻辑流了。

当hello调用getchar的时候，实际落脚到执行输入流是stdin的系统调用read，hello之前运行在用户模式，在进行read调用之后陷入内核，内核中的陷阱处理程序请求来自键盘缓冲区的DMA传输，并且安排在完成从键盘缓冲区到内存的数据传输后，中断处理器。此时进入内核模式，内核执行上下文切换，切换到其他进程。当完成键盘缓冲区到内存的数据传输时，引发一个中断信号，此时内核从其他进程进行上下文切换回hello进程。

6.6 hello的异常与信号处理

异常分为以下几类：

在hello程序执行过程中这几类异常都可能出现。当出现异常时，操作系统会根据异常表进行一个间接过程调用，找到异常对应的异常处理程序。当异常处理程序完成处理后，根据引起异常的事件的类型，会发生以下3种情况中的一种：
1.处理程序将控制返回给当前指令，即当事件发生时正在执行的指令。
2.处理程序将控制返回给当前指令的下一条指令，即如果没有异常发生将会执行的下一条指令。
3.处理程序终止被中断的程序。

6.6.1 不停乱按，包括回车

如果乱按过程中没有按回车，则只会在屏幕上显示输入的内容。如果输入回车，则getchar读回车，并把回车前的字符串当作shell输入的命令。

6.6.2 Ctrl-Z

如果输入Ctrl+Z会发送一个SIGTSTP信号给前台进程组的每个进程，结果是停止前台作业。

6.6.3 Ctrl-C

如果在程序运行过程中输入Ctrl+C,会让内核发送一个SIGINT信号给到前台进程组中的每个进程，结果是终止前台进程。

6.6.4 Ctrl-z后运行ps jobs pstree fg kill 等命令

Ctrl-Z后输入ps,jobs等命令仍会正常工作，同时可以看出此时hello程序的状态为Stopped。fg的功能是使第一个后台作业变为前台，而第一个后台作业是hello，所以输入fg 后hello程序又在前台开始运行。

6.7本章小结

本章介绍了进程的概念和作用，同时介绍了Shell的一般处理过程和作用。分析了fork和execve函数的功能，展示了hello进程的执行以及hello的异常和信号处理。

第7章 hello的存储管理

7.1 hello的存储器地址空间

逻辑地址：程序经过编译后出现在汇编代码中的地址。逻辑地址用来指定一个操作数或者是一条指令的地址。是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 [段标识符：段内偏移量]。
线性地址：也叫虚拟地址，和逻辑地址类似，也是一个不真实的地址，如果逻辑地址是对应的硬件平台段式管理转换前地址的话，那么线性地址则对应了硬件也是内存的转换前地址。
虚拟地址：也就是线性地址。
物理地址：用于内存芯片级的单元寻址，与处理器和CPU链接的地址总线相对应。可以直接把物理地址理解成插在机器上那根内存本身，把内存看成一个从0字节一直到最大空量逐字节的编号的大数组，然后把这个数组叫做物理地址。

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

一个逻辑地址由两部分组成，段标识符，段内偏移量。段标识符是一个16位长的字段组成，称为段选择符，其中前13位是一个索引号。后面三位包含一些硬件细节。
索引号就是段描述符的索引。段描述符具体描述了一个段地址，这样，很多段描述符就组成段描述符表。可以通过段标识符的前13位，直接在段描述符表中找到一个具体的段描述符。
Base字段，表示的是包含段的首字节的线性地址，也就是一个段的开始位置的线性地址。
一些全局的段描述符，就放在“全局段描述符表(GDT)”中，一些局部的，例如每个进程自己的，就放在所谓的“局部段描述符表(LDT)”中。GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中，而LDT则在ldtr寄存器中。
首先，给定一个完整的逻辑地址[段选择符：段内偏移地址]，
看段选择符的T1=0还是1，知道当前要转换是GDT中的段，还是LDT中的段，再根据相应寄存器，得到其地址和大小。我们就有了一个数组了。
拿出段选择符中前13位，可以在这个数组中，查找到对应的段描述符，这样，它了Base，即基地址就知道了。把Base + offset，就是要转换的线性地址了。

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

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

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

每次CPU产生一个虚拟地址，MMU（内存管理单元）就必须查阅一个PTE（页表条目），以便将虚拟地址翻译为物理地址。在最糟糕的情况下，这会从内存多取一次数据，代价是几十到几百个周期。如果PTE碰巧缓存在L1中，那么开销就会下降1或2个周期。然而，许多系统都试图消除即使是这样的开销，它们在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓存器（TLB）。
TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单一PTE组成的块。TLB通常有高的相联度。

多级页表：将虚拟地址的VPN划分为相等大小的不同的部分，每个部分用于寻找由上一级确定的页表基址对应的页表条目。VPN被分为k个部分，第一级VPN结合基址寄存器得到一个页表条目，其中存放下一级页表的基址，再结合VPN2，得到第三级页表基址，继续寻找，以此类推，直到最后确定对应的物理页号，与VPO结合，得到由PPN与PPO结合成的物理地址，用于物理地址寻址。

多级页表的使用从两个方面减少了内存要求。第一，如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在。第二，只有一级页表才需要总是在主存中。虚拟内存系统可以在需要时创建、页面调入或调出二级页表。

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

在从TLB或者页表中得到物理地址后，根据物理地址从cache中寻找。到了L1里面以后，寻找物理地址要检测是否命中，不命中则紧接着寻找下一级cache L2，接着L3，如果L3也不命中，则需要从内存中将对应的块取出放入cache中，其中可能会发生块的替换等其它操作。这里就是使用到CPU的高速缓存机制了，一级一级往下找，直到找到对应的内容。

7.6 hello进程fork时的内存映射

当fork 函数被shell调用时，内核为hello进程创建各种数据结构，并分配给它一个唯一的PID。为了给hello进程创建虚拟内存，它创建了hello进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。当fork 在hello进程中返回时，hello进程现在的虚拟内存刚好和调用fork 时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

7.7 hello进程execve时的内存映射

execve的加载步骤在6.4节中已经给出，如下：
1.删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。
2.映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些区域结构都是私有的，写时复制的。虚拟地址空间的代码和数据区域被映射为hello文件的.txt和.data区。bss区域是请求二进制零的，映射匿名文件，其大小包含在hello文件中。栈和堆区域也是请求二进制零的，初始长度为零。
3.映射共享区域。如果hello程序与共享对象链接，比如标准C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域。
4.设置程序计数器（PC）。exceve做的最后一件事就是设置当前进程的上下文中的程序计数器，使之指向代码区域的入口点。下一次调用这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。

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

缺页故障：当指令引用一个相应的虚拟地址，而与改地址相应的物理页面不再内存中，会触发缺页故障。
缺页中断处理：通过查询页表PTE可以知道虚拟页在磁盘的位置。缺页处理程序从指定的位置加载页面 到物理内存中，并更新PTE。然后控制返回给引起缺页故障的指令。当指令再次执行时，相应的物理页面已经驻留在内存中，因此指令可以没有故障的运行完成。

7.9动态存储分配管理

动态内存分配器维护者一个进程的虚拟内存区域，称为堆。(如图7.9.1所示),分配器将堆视为一组不同的大小的块的集合来维护。每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。分配器有两种基本风格。两种风格都是要求显示的释放分配块。
(1) 显式分配器：要求应用显示的释放任何已分配的块。例如C标准库提供一个叫做malloc程序包的显示分配器。
(2) 隐式分配器：要求分配器检测一个已分配块何时不再被程序使用，那么就释放这个块。隐式分配器也叫垃圾收集器。

隐式空闲链表：
一个块是由一个字的头部、有效载荷，以及可能的填充组成。头部编码了这个块的大小(包括头部和所有的填充),以及这个块是已分配的还是空闲的。块的头最后一位指明这个块是已分配的还是空闲的。

具体的隐式空闲链表形式如下：

放置已分配的块当一个应用请求一个k字节的块时，分配器搜索空闲链表。查找一个足够大可以放置所请求的空闲块。分配器搜索方式的常见策略是首次适配、下一次适配和最佳适配。
当分配器找到一个匹配的空闲块时，通常将空闲块分割为两部分。第一部分变为了已分配块，第二部分变为了空闲块。
当分配器找不到合适的空闲块一个选择是合并那些在物理内存上相邻的空闲块，如果这样还不能生成一个足够大的块，分配器会调用sbrk函数，向内核请求额外的内存。
合并空闲块合并的情况一共分为四种：前空后不空，前不空后空，前后都空，前后都不空。为了提高合并效率，Knuth提出了一种采用边界标记的技术快速完成空闲块的合并。其所用到的结构如下图所示：

显示空闲链表：
显示空闲链表是将空闲块组织为某种形式的显示数据结构。在每个空闲块中，都包含一个前驱和后继的指针。

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线 性时间减少到了空闲块数量的线性时间。
维护链表可以采用后进先出(LIFO)的顺序或者按照地址增大的顺序来维护。

7.10本章小结

本章主要介绍了有关内存管理的知识。详细阐述了hello程序是如何存储，如何经过地址翻译得到最终的物理地址。介绍了hello的四级页表的虚拟地址空间到物理地址的转换。阐述了三级cashe的物理内存访问、进程 fork 时的内存映射、execve 时的内存映射、缺页故障与缺页中断处理、动态存储分配管理。

第8章 hello的IO管理

8.1 Linux的IO设备管理方法

所有的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)，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;
}

printf程序按照格式fmt结合参数args生成格式化之后的字符串，并返回字串的长度。printf用了两个外部函数，一个是vsprintf，还有一个是write。
vsprintf函数作用是接受确定输出格式的格式字符串fmt（输入）。用格式字符串对个数变化的参数进行格式化，产生格式化输出。
write函数将buf中的i个元素写到终端。
从vsprintf生成显示信息，到write系统函数，到陷阱-系统调用 int 0x80或syscall等.
字符显示驱动子程序：从ASCII到字模库到显示vram（存储每一个点的RGB颜色信息）。
显示芯片按照刷新频率逐行读取vram，并通过信号线向液晶显示器传输每一个点（RGB分量）。

8.4 getchar的实现分析

getchar的函数体如下：

int getchar(void)
{
	static char buf[BUFSIZ];//缓冲区
	static char* bb=buf;//指向缓冲区的第一个位置的指针
	static int n=0;//静态变量记录个数
	if(n==0)
	{
		n=read(0,buf,BUFSIZ); 
		bb=buf;//并且指向它
	}
	return(--n>=0)?(unsigned char)*bb++:EOF;
}

异步异常-键盘中断的处理：键盘中断处理子程序。接受按键扫描码转成ascii码，保存到系统的键盘缓冲区。
getchar等调用read系统函数，通过系统调用读取按键ascii码，直到接受到回车键才返回。

8.5本章小结

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

结论

用计算机系统的语言，逐条总结hello所经历的过程。
1.首先编写hello.c的源程序，从此hello.c诞生。此时hello.c仍是一个文本文件，还没有变成二进制文件。
2.对hello.c进行预处理(gcc -E)，hello.c变成了hello.i。
3.对hello.i进行编译处理(gcc -S)，hello.i变成了hello.s。
4.对hello.s进行汇编处理(gcc -c)，hello.s变成了hello.o。此时hello变成了二进制文件。
5.对hello.o进行链接处理，将其与其它可重定位目标文件以及动态链接库进行链接生成可执行目标文件hello。此时hello程序就可以在计算机上执行。
6.在shell命令行上输入./hello 1190201809 夏韵 1来运行hello程序。
7.shell首先判断输入命令是否为内置命令。经过检查后发现其不是内置命令，则shell将其当作程序执行。
8.shell调用fork函数创建一个子进程。
9.shell调用execve函数，execve函数会将新创建的子进程的区域结构删除，然后将其映射到hello程序的虚拟内存，然后设置当前进程上下文中的程序计数器，使其指向hello程序的入口点。
10.运行hello时，内存管理单元MMU、翻译后备缓冲器TLB、多级页表机制、三级cache协同工作，完成对地址的翻译和请求。
11.execve函数并未将hello程序实际加载到内存中。当CPU开始执行hello程序对其进行取指时，发现其对应的页面不在内存中。此时会出现缺页故障这一异常，操作系统通过异常表对缺页处理程序进行间接调用，缺页处理程序实现虚拟内存和物理内存的映射，将缺失的页面加载到内存中。此时CPU重新执行引起故障的指令，指令可以正常执行，程序从而继续向下执行。
12.当hello程序调用sleep函数后进程休眠进入停止状态。而CPU不会等待hello程序休眠结束，而是通过内核进行上下文切换将当前进程的控制权转移到其它进程。当sleep函数调用完成后，内核再次进行上下文切换重新执行hello进程。
13.当hello程序执行printf函数时，会调用malloc函数从堆中申请内存。
14.在hello进程执行时，当在命令行中输入Ctrl-C时，shell会向前台作业发送SIGINT信号，该信号会终止前台作业，即hello程序终止执行。当输入Ctrl-Z时，shell会向前台作业发送SIGTSTP信号，该信号会挂起当前进程，即hello程序停止执行，之后再向其发送SIGCONT信号时，hello程序会继续执行。
15.当hello进程执行完成后，父进程会对子进程进行回收。内核删除为这个进程创建的所有数据结构。

你对计算机系统的设计与实现的深切感悟，你的创新理念，如新的设计与实现方法。
计算机系统是由硬件和系统软件组成的，它们共同工作来运行应用程序。抽象是计算机系统设计与实现的重要基础：文件是对I/O设备的抽象，虚拟内存是对程序存储器的抽象，进程是对一个正在运行的程序的抽象，虚拟机是对整个计算机的抽象。
计算机的工作效率是评价其好坏的一个重要的方面。为了提高计算机的工作效率，解决不同设备之间速度差异大的问题，利用缓存的机制设计了高速缓存来作为更底层的设备的缓存，如cache就是设计为主存的缓存，快表设计为虚拟内存页表的缓存等等。

附件

参考文献

[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.
[7]  https://www.cnblogs.com/pianist/p/3315801.html