第一章:计算机系统漫游
这本书是为这样一些程序员而写的,他们希望通过了解这些部件如何工作以及如何影响程序的准确性和性能,来提高自身的技能.
系统中所有的信息--包括磁盘文件,存储器中的程序,存储器中存放的用户数据以及网络上传送的数据,都是由一串比特表示的.
c语言是贝尔实验室的Dennis Ritchie于1969-1973年间创建的.美国国家标准化组织在1989年颁布了ANSI C的标准.该标准定义了C语言和一系列函数库,即所谓的标准C库.
c和unix操作系统关系密切.c从开始就是作为一种用于unix系统的程序语言开发出来的.unix内核的大部分,以及所有它支持的工具和函数库都是用c语言编写的.
c是一个小而简单的语言,c语言的设计是由一个人完成的,其结果就是这是一个简洁明了,没有什么冗赘的设计.
c是为实践目的设计的.c是设计用来实现unix操作系统的.它是系统编程的首选.同时它非常适用于应用级程序的编写.
预处理器,编译器,汇编器和连接器一起构成了编译系统.
汇编语言是非常有用的,因为它为不同的高级语言的不同编译器提供了通用的输出语言.
GNU环境包括EMAC编译器,GCC编译器,GDB调试器,汇编器,连接器,处理二进制文件的工具以及其他一些部件.
shell是一种命令行解释器,它输出一个提示符,等待你输入一行命令,然后执行这个命令.如果该命令的第一个单词不是一个内置的shell命令,那么shell就会假设这是一个可执行文件的名字,要加载和执行该文件.
每个I/O设备都是通过一个控制器或适配器于I/O总线连接起来的.控制器和适配器之间的区别主要在它们的组成方式.控制器是I/O设备本身中或是主板上的芯片组,而适配器则是一块插在主板插槽上的卡.
主存是临时存储设备,在处理器执行程序时,它被用来存放程序和程序处理的数据.物理上来说,主存是由一组DRAM芯片组成的,逻辑上来说,存储器是由一个线性的字节数组组成的.
中央处理单元简称处理器,是解释存储在主存中指令的引擎.处理器的核心是一个被称为程序计数器的字长大小的存储设备.在任何一个时间点上,PC都指向主存中的某条机器语言指令.
从系统通电开始,直到系统断电,处理器一直在不假思索的重复执行相同的基本任务:从程序计数器指向的存储器处读取指令,解释指令中的位,执行指令中的简单操作,然后更新程序计数器指向下一条指令,而这条指令并不一定在存储器中和刚刚执行的指令相邻.
利用称为DMA(直接存储器存取)的技术,数据可以不通过处理器而直接从磁盘到达主存.
常字符串的显示过程:存储器到寄存器文件,再从寄存器文件到显示设备.
一个典型的寄存器文件只存储几百字节的信息,主存里可存放几百万字节.然而,处理器从寄存器文件中读数据比从主存中读取要快几乎100倍.
L1和L2高速缓存是用一种叫做静态随机访问存储器的硬件技术实现的.
我们可以把操作系统看成是应用程序和硬件之间插入的一层软件.
操作系统有两个基本功能:防止硬件被失控的应用程序滥用;在控制复杂而又通常广泛不同的低级硬件设备方面,为应用程序提供简单一致的方法.
程序在现代系统上运行时,操作系统会提供一种假象,就好像系统上只有这个程序是在运行的.这些假象是通过进程的概念来实现的,进程是计算机科学中最重要和最成功的概念之一.
在现代系统中,一个进程实际上可以由多个称为线程的执行单元组成.每个线程都运行在进程的上下文中,并共享同样的代码和全局数据.
虚拟存储器是一个抽象概念,它为每个进程提供了一个假象,好像每个进程都在独占的使用主存.每个进程看到的存储器都是一致的.
每 个进程看到的虚拟地址空间由大量准确定义的区组成,从最低的地址开始:程序代码和数据(代码和数据区是由可执行目标文件直接初始化的);堆(作为调用像 malloc和free这样的c标准库函数的结果,堆可以在运行时动态的扩展和收缩);共享库(共享库的概念非常强大,但是也是个相当难懂的概念);栈 (位于用户虚拟地址空间顶部的是用户栈,编译器用它来实现函数的调用);内核虚拟存储器(内核是操作系统总是驻留在存储器中的部分).
虚拟存储器的运作需要硬件和操作系统软件之间的精密复杂的相互合作,包括对处理器生成的每个地址的硬件翻译.基本思想是把一个进程虚拟存储器的内容存储在磁盘上,然后用主存作为磁盘的高速缓存.
Linux逐渐发展成为一个技术和文化现象,通过和GNU项目的力量结合,Linux项目发展成为了一个完整的,符合Posix标准的Unix操作系统的版本,包括内核和所有支撑的基础设施.
操作系统内核是应用程序和硬件之间的媒介,它提供三个基本的抽象概念:文件是I/O设备的抽象概念:虚拟存储器是对主存和磁盘的抽象概念:进程是处理器,支撑和I/O设备的抽象概念.//

第二章:信息的表示和处理
2的n次方的二进制表示为1后面加n个0;
指针变量将用到机器的全字长,long int*也是这样;
可移植性的一个方面就是使程序对不同数据不敏感;
c标准对不同类型的数字范围设置了下限,但是没有上限;
存储数据分大端法和小端法;
反汇编器是一种确定可执行程序文件所表示的指令序列的工具;
不同的机器使用不同的且不兼容的指令和编码方式;
布尔的and和异或分别相当于模2的乘法和加法;
c标准没有明确定义使用那种类型的右移;
c和c++中的有符号树是默认的;
c的标准并没有要求用二进制补码来表示有符号数;
c库中的文件<limits.h>定义了一组常量,来限定运行编译器的这台机器的不同整型数据的范围;
printf没有使用任何输出变量类型的信息(how);
无符号和有符号数混合运算,将有符号数转化为无符号数;
一种有名的用来执行二进制补码的非的技术是取反并加一;
编译器用移位和加法运算的组合来代替乘以常数因子的乘法;
单精度浮点的符号,指数和有效数字分别是1,8,23.双精度为1,11,52.有效数字的第一位总是1,因此我们不需要表示它;
IEEE浮点格式定义了4种不同的舍入方式,默认是找到最接近的匹配.这四种方式为:向偶数舍入,向0舍入,向上舍入,向下舍入;
浮点寄存器使用一种特殊的80位的扩展精度格式;
浮点数取非就是简单的将其符号位取反;

第三章:程序的机器级表示
汇编程序员可以看到程序计数器,整数,浮点数寄存器和条件码寄存器;
汇编代码只是将存储器看成是一个很大且按字节寻址的数组;
对标量数据类型,汇编代码也不区分有符号和无符号数,不区分各种类型的指针,甚至不区分指针和整数;
程序存储器包含程序的目标代码,操作系统需要的一些信息,用来管理过程调用和返回的运行时栈,以及用户分配的存储器块;
IA32 CPU有8个32位值的寄存器,前6个是通用的,后2个保存栈指针和帧指针;
最频繁使用的指令是执行数据传送的指令;
局部变量通常是保存在寄存器中;
除了右移操作,所有的指令都不区分有符号数和无符号数;
IA32程序用程序栈来支持过程的调用,栈用来传递过程参数,存储返回信息,保存寄存器以供以后的恢复之用,以及用于本地存储;
为单个过程分配的那部分栈称为栈帧,它的最顶端是以两个指针定界的;
寄存器%eax可以用来返回值,如果函数要返回整数或指针的话;
IA32中%eax,%edx和%ecx被划分为调用者保存寄存器,其余三个为被调用者保存寄存器;
IA32也仍然在不断增加新的指令类,来支持处理多媒体应用的需要;
许多计算机系统要求某种数据类型的对象必须是某个值的k倍,这种对其限制简化了处理器和存储器系统之间的接口硬件设计;
&操作符可以应用到任何左值类的c表达式上,包括变量,结构,联合和数组元素;
用高级语言编写的程序可在许多不同的机器上编译执行,而汇编代码是于特定机器密切相关的;
1997-PentiumII  1999-PentiumIII  2001-Pentium4;
美国商标局不允许用数字作为商标;
Intel现在称其指令集为IA32;
汇编代码非常接近于机器代码;
汇编代码只是将存储器看成是一个很大的,按字节寻址的数组;
机器实际执行的程序只是对一系列指令进行编码的字节序列,机器对产生这些指令的源代码一无所知;
call过程调用  leave为返回准备栈  ret从过程调用中返回;
指针提供一种统一方式,能够远程访问数据结构;
malloc函数返回一个通用指针;
指针也可以指向函数,这提供了一个很强大的存储和传递代码引用的功能(how);
数年来,AMD的策略一致是在技术上紧跟Intel后面,生产性能稍低但是价格更便宜的处理器;
浮点数使用一组完全不同的指令和寄存器(相对整数来说);
IA32加了一条限制,传送指令的两个操作数不能都指向存储器的位置,第一个是源操作数,第二个是目标操作数;
局部变量通常是保存在寄存器中的,这样就能更快的访问到它;
加载有效地址(load effective address)指令leal实际上是movl指令的变形,但目标操作数必须是一个寄存器;
编译器产生的代码中会用一个寄存器存放多个程序值,还会在寄存器之间传送程序值;
汇编代码提供了实现非顺序控制流的较低层次的机制,这是通过借助条件码寄存器来完成的;
当执行PC相关的寻址时,程序计数器的值是跳转指令后面的那条指令的地址,,而不是跳转指令本身的地址;
switch语句不仅提高了c代码的可读性,而且通过使用一种跳转表的数据结构使得实现更加高效,跳转表是一个数组,表项i是一个代码段的地址,这个代码段实现的是当开关索引值等于i时程序应该采取的动作;
数据传递,局部变量的分配了释放是通过操纵程序栈来实现的;
IA32程序用程序栈来支持过程调用;
当对一个局部变量使用地址操作符&的时候,该变量不能保存在寄存器中;
call指令的效果是将返回地址入栈,并跳转到被调用过程的起始处.返回地址是紧跟在程序中call后面的那条指令的地址.ret指令从栈中弹出地址并跳转到那个位置;
在较老的IA32处理器模型中,整数乘法指令要花费30个时钟周期,所以编译器要尽可能的避免使用它,而大多数新近的处理器模型中,乘法指令只需要3个时钟周期,所以不一定会进行这样的优化;
c和c++都要求程序显式的用free函数来释放已经分配的空间,在Java中,释放是由运行时系统通过一个称为垃圾回收的进程自动完成的;
寄存器溢出是IA32一个很常见的问题,因为处理器的寄存器数量太少了;
结构的实现类似于数组的实现,因为结构的所有组成部分都存放在存储器中连续的区域内,而指向结构的指针就是结构的第一个字节的地址;
struct数据类型的构造函数是c提供的于c++和java对象最为接近的东西;
蠕虫是这样一种程序,它可以自己运行,并且能够将一个完全有效的自己传播到其他的机器上.与此相应的,病毒是这样一段代码,它能将自己添加都包括操作系统在内的其他程序中,但是它不能独立的运行;//
(14 15 16节未看)

第五章:优化程序性能
编写高效的程序需要两类活动:第一,我们必须选择一组最好的算法和数据结构;第二,我们必须编写出编译器能够有效优化以转成高效可执行代码的源代码;
事实上,编译器只能执行有限的程序转换,而且妨碍优化的因素还会阻碍这种转换,妨碍优化的因素就是程序行为中那些严重依赖于执行环境的方面;
编译器优化程序的能力受几个因素的限制,包括:要求它们绝不能改变正确的程序行为:它们对程序行为,对使用它们的环境了解有限;需要很快的完成编译工作;
编译器必须假设不同的指针可能会指向存储器中同一个位置,这造成了一个主要的妨碍优化的因素,这也是可能严重限制编译器产生优化代码机会的程序的一个方面;
编译器会假设最糟的情况,并保持所有的函数调用不变;
代码移动的优化包括识别出要执行多次但是计算结果不会改变的计算,因而我们可以将计算移动到代码前面的,不会被多次求值的部分;
c中的字符串是以null结尾的字符序列,strlen必须一步一步的检查这个序列,直到遇到null字符;
过程的调用会带来相当大的开销,而且妨碍大多数形式的程序优化;
消除不必要的存储器引用,具体是用一些临时变量,这些变量很可能被存在寄存器中(如果没有溢出的话);
在汇编代码级,看上去似乎是一次是执行一条指令,每条指令都包括从寄存器或存储器取值,执行一个操作,并把结果存回到一个寄存器或存储器位置.在实际的处理器中,是同时对多条指令求值的.在某些设计中,可以有80或更多条指令在处理中.
P6 微体系结构是自20世纪90年代后期以来许多厂商生产的高端处理器的典型.在工业界称为超标量,意思是它可以在每个时钟周期执行多个操作,而且是乱序的, 整个设计有两个主要部分:ICU(Instruction Control Unit,指令控制单元)和EU(Execution Unit,执行单元).
ICU从指令高速缓存中读取指令,指令高速缓存是一个特殊的高速缓存存储器,它包含最近访问的指令;
指令解码逻辑接收实际的程序指令,并将它们转换成一组基本的操作;
加载和存储单元通过数据高速缓存访问存储器,这是一个高速存储器,包含最近访问的数据值;
退役单元纪录正在进行的处理,并确保遵守机器级程序的顺序语意.退役单元控制着寄存器的更新;
任何对程序状态的更新都只会在指令退役时才发生,只有在处理器能够确信这条指令的所有分支都预测正确了,才能这样做;
执行时间的范围从基本整数操作的一个周期,到加载,存储,整数乘法和更常见的浮点操作的几个周期,到除法和其他复杂操作的许多个周期;
处理器的几个功能单元被流水线化了,这意味着在前一个操作完成之前,它们就可以开始一个新的操作;
浮点乘法器要求连续的操作之间至少要一两个周期,而两个除法器根本就没有流水线化;
标记可以与并不会写道寄存器文件中的中间值相关联;
循环展开本身只会帮助整数求和情况中代码的性能,因为我们的其他情况是被功能单元的执行时间限制的;
编译器可以很容易的执行循环展开,只要优化级别设置得足够高(例如,优化选项-O2)许多编译器都能例行公事的做到这一点,在命令行上以'-funroll-loops'调用GCC,它会执行循环展开;
有时候,我们能够通过使用指针,而不是数组改进一个程序的性能;编译器对数组代码应用非常高级的优化,而对指针只应用最小限度的优化,为了可读性的缘故,通常数组代码更可取一些;
循环分割:我们可以通过将一组合并操作分割成两个或更多的部分,并在最后合并结果来提高性能;
对于整数数据类型的情况,总共只有八个整数据传区可用.其中两个指向栈中的区域;
八 个整数和八个浮点寄存器的限制是IA32指令集的不幸产物,前面讲到国的重命名消除了寄存器名字和寄存器数据实际位置之间的联系.在现代处理器中,寄存器 名字之简单的用来标识在功能单元之间传递的程序值.IA32只提供了很少量的这样的标识符,限制了在程序中能表达的并行性的数量;
某个与及其相关的因素将浮点乘法能达到的CPE限制在了1.5,而不是理论极限值的1.0;
程序优化的通用原则对各种不同的机器都适用,即使某种特殊的特性组合导致最优性能依赖于特殊的机器;
到目前,台式机或服务器中几乎每个处理器都支持投机执行;
一个存储器读的结果依赖于一个非常近的存储器的写叫做读写相关,它导致了处理速度的下降;
movl %edx,(%ecx)被翻译成两个操作:storeaddr指令计算存储操作的地址,创建一个存储缓冲区中的条目,并设置该条目的地址字段;storedata指令设置该条目的数据字段;
通常,处理器/存储器接口是处理器设计中最复杂的部分之一.不查阅详细的文档和使用机器分析工具,我们只能给出实际行为的一个假象的描述;
由于存储器操作占到了程序很大一部分,存储器子系统优化成以独立的存储器操作来提供更大的并行性;
优化程序性能的基本策略:
 1.高级设计,为手边的问题选择适当的算法和数据结构;
 2.基本编码原则,消除函数的连续调用,在可能时,将计算移到循环外.考虑有选择的妥协程序的模块性以获得更大的效率;消除不必要的存储器引用,引入中间变量来保存中间结果,只有在最后的值计算出来的时候,才将结果存放到数组或全局变量中;
 3.低级优化.尝试各种于数组代码相对的指针形式;通过展开循环降低循环开销;通过诸如迭代分割之类的技术,找到使用流水线化的功能单元的方法;
Unix系统提供了一个剖析程序GPROF.这个程序产生两种形式的信息.首先,它确定程序中每个函数花费了多少CPU时间.其次,它计算每个函数被调用的次数,以调用函数来分析;
库函数qsort是际遇快速排序算法进行排序的;
剖析是工具箱中一个很有用的工具,但是它不应该是唯一一个,即使测量不是很准确,特别是对较短的运行时间来说.结果只适用于被测试的那些特殊的数据;
Amdahl定律的主要观点:要想大幅度提高整个系统的速度,我们必须提高整个系统很大一部分的速度;
Amdahl 定律描述了一个改进任何过程的通用原则.除了适用于提高计算机系统的速度外,它还能指导一个公司试着降低生产剃须刀的成本,或是指导一个学生改进他或她的 平均绩点.或许它在计算机世界里最有意义,在计算机世界中,我们通常将性能提高一倍或更多.只有通过优化系统很大一部分才能获得这么高的提高率;

第六章：存储器层次结构
RAM分SRAM和DRAM
DDR-SDRAM:双倍数据速率同步DRAM.通过时钟的两个边沿作为控制信号,从而使DRAM的速度加倍.
ROM是以它们能被重编程的次数和对它们进行重新编程的机制来区分的:PROM,EPROM,EEDROM.闪存是基于EEPROM的;
存储在ROM设备中的程序通常被称为固件,当一个计算机系统通电以后,它会运行存储在ROM中的固件;
总线是一组并行的导线,能携带数据,地址和控制信号;
系统总线将CPU连接到I/O桥接器,存储器总线将I/O桥接器连接到主存,I/O桥接器也将系统总线和存储器总线连接到I/O总线;
扇区包含相等数量的数据位,扇区之间由一些间隙分隔开,间隙用来存储标识扇区的格式化位;
多个盘面时,任何时刻,所有读写头都位于同一柱面上;
磁盘是以扇区大小的块来读写数据的;
磁盘中有一个小的硬件/固件设备,称为磁盘控制器,维护着逻辑块号和实际磁盘扇区之间的映射关系;
在磁盘可以存储数据之前,它必须被磁盘控制器格式化,这包括标识扇区的信息填写扇区之间的间隙,标识出表面有故障的柱面并且不适用它们,以及在每个区中预留出一组柱面作为备用;
在使用存储器映射I/O的系统中,地址空间中有一块地址是为与I/O设备通信保留的,每个这样的地址称为一个I/O端口;
现代计算机频繁使用基于SRAM的高速缓存;
有良好局部性的程序比局部性差的程序运行得更快;
代码区别于程序数据的一个重要属性是在运行时不能修改;
局部变量的反复引用是好的,步长为1的引用模式是好的;
如果你的程序需要的数据是存储在CPU寄存器中的,那么在执行期间,在零个周期内就能访问到它们;如果存储在高速缓存中,需要1-10个周期;如果存储在主存中,需要50-100个周期;而如果存储在磁盘上,需要大约20 000 000个周期;
具有良好局部性的程序倾向于一次又一次的访问相同的数据项集合,或是倾向于访问邻近的数据项集合;
特别的,我们将注意力集中在CPU和主存之间作为缓存区域的高速缓存存储器上,因为它们对应用程序性能影响最大;
随机访问存储器(random-access memory,RAM)分为两类--静态的和动态的.静态RAM(SRAM)比动态RAM(DRAM)更快,但也贵得多;
SRAM将每个位存储在一个双稳态的存储器单元里;每个单元是用一个六晶体管电路来实现的.这个电路有这样一个属性,它可以无限期的保持在两个不同的电压配置或状态之一;
DRAM存储器可以制造的非常密集--每个单元由一个电容和一个访问晶体管组成;
只要有电,SRAM就是持续的,与DRAM不同,它不需要刷新.SRAM的存取比DRAM快.SRAM对诸如光和电噪音这样的干扰不敏感.代价是SRAM单元比DRAM单元使用更多的晶体管,因而没那么密集,而且更贵,功耗更大;
电路设计者将DRAM组织成二维阵列而不是线性数组的一个原因是降低芯片上地址管脚的数量;
DRAM芯片包装在存储器模块中,它插到主板的扩展槽上;二维阵列组织的缺点是必须分两步发送地址,这增加了访问时间;
增 强的DRAM:FPM DRAM(fast page mode DRAM,快页模式DRAM);EDO DRAM(extended data out DRAM,扩展数据输出DRAM);SDRAM(synchronous DRAM, 同步DRAM);DDR SDRAM(double data-rate synchronous DRAM,双倍数据速率同步);Rambus DRAM;
一些系统在固件中提供了少量的输入和输出函数--例如,PC的BIOS例程;I/O桥接器将系统总线的电信号翻译成存储器总线的电信号;
磁盘是由一个或多个叠放在一起的盘片组成的,它们放在一个密封的包装里,正个装置通常别叫做磁盘驱动器,虽然我们通常简称位磁盘;
对扇区的访问时间有三个主要部分:寻道时间,旋转时间,传送时间;
从存储器中读一个512字节扇区大小的块的时间对SRAM来说大约是256ns,对DRAM来说大约是4000ns.磁盘访问时间比SRAM大约大4000倍;比DRAM大约大2500倍;
当 操作系统想要执行一个I/O操作时,例如读一个磁盘扇区的数据到主存,操作系统会发送一个命令到磁盘控制器,让它读某个逻辑块号.控制器上的固件执行一个 快速表查找,将一个逻辑块号翻译成一个(盘面,磁道,扇区)的三元组,这个三元组唯一的标识了对应的物理扇区.控制器上的硬件解释这个三元组,将I/O头 移动到适当的柱面,等待扇区移动到I/O头下,将I/O头感知到的位放到控制器上的一个小缓冲区中,然后将它们拷贝到主存中;
像图形卡,监视器,鼠标,键盘,这样的设备都是通过诸如Intel的PCI(peripheral component interconnect外围设备互联)总线这样的I/O总线连接到CPU和主存的;
虽然I/O总线比系统总线和存储器总线慢,但是它快页容纳种类繁多的第三方I/O设备;
USB控制器是一个将设备连接到USB的电路,USB的吞吐率可以达到12Mbit/s,是为慢速或中速串行设备设计的;
图形卡包含硬件和软件逻辑,它们负责代表CPU在显示器上画像素;
磁盘控制器包含硬件和软件逻辑,它们用来代表CPU读写磁盘;
当一个设备连接到总线时,它与一个或多个端口相关联;
逻辑块的概念不仅能够提供给操作系统一个更简单的接口,还能够提供一层抽象,使得磁盘更加健壮;
磁盘中有一个小的硬件/固件设备,称为磁盘控制器,维护着逻辑块号和实际磁盘扇区之间的映射关系;
操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块;
对于取指令来说,循环有好的时间和空间局部性,循环体越小,循环次数越多,局部性越好;
一般而言,层次结构中较低层的设备的访问时间较长,因此为了补偿这些较长的访问时间,倾向于使用较大的块;
在一个有虚拟存储器的系统中,DRAM主存作为存储在磁盘上的数据块的缓存,是有操作系统软件和CPU上的地址翻译硬件共同管理的;
高速缓存确定一个请求是否命中,然后抽取出被请求的字的过程,分为三步:组选择;行匹配;字抽取;
冲突不命中在真实的程序中很常见,会导致令人困惑的性能问题;
即使程序有良好的空间局部性,而我们的高速缓存中也有足够的空间来存放两个数组的块,每次引用还是会导致冲突不命中,这是因为这些块被映射到了同一个高速缓存组;
直写高速缓存通常是非写分配的,写回高速缓存通常是写分配的;
只保存指令的高速缓存称为i-cache,只保存程序数据的高速缓存称为d-cache.一个典型的桌面系统CPU芯片本身就包括一个L1 i-cache和一个L1 d-cache;
一方面,较大的高速缓存可能会提高缓存命中率;另一方面,使得大存储器运行得更快总是要难一些的;
现代系统通常会折中,使高速缓存块包含4-8个字;
传统上,努力争取时钟频率的高性能系统会选择直接映射L1高速缓存,而在较低层上使用比较小的相关度,但是没有固定的规则;
一般而言,高速缓存越往下层,越可能使用写回而不是直写;
因为一行总是存储一个块,术语行和块通常互换使用,例如,系统专家总是说高速缓存的行大小,实际上他们指的是块大小;
理 解存储器层次结构本质的程序员能够利用这些知识,编写出更有效的程序,无论具体的存储系统是怎样的.特别的,我们推荐下列技术:将你的注意力集中在内部循 环上,大部分计算和存储器访问都发生在这里;通过按照数据对象存储在存储器中的顺序来读数据,从而使得你程序中空间局部性最大;一旦从存储器中读入一个数 据对象,就尽可能多的使用它,从而使得你程序中的时间局部性最大;记住,不命中率只是确定你代码性能的一个因素,存储器访问数量也扮演着重要的角色,有时 候要在两者之间做一下折中;//(6.6未看)

第七章:连接
连接器完成的两个主要任务:符号解析和重定位.
编译器和汇编器生成地址0开始的代码和数据节.
目标文件:可重定位目标文件,可执行目标文件,共享目标文件.
ELF 可重定位目标文件:ELF头以一个16字节的序列开始,这个序列描述了字的大小和生成该文件的系统的字节顺序. .test.:已编译程序的机器代码;.rodata.:只读数据;.data.:已初始化的全局变量;.bss.:为初始化的全局变 量;.symtab.:存放程序中被定义和引用的函数和全局变量的信息.
连接器上下文中有三种符号:块内定义的全局符号;块外定义的全局符号和本地符号;
定义为带c static属性的本地过程变量不是在栈中管理的,编译器在.data.和.bss.中为每个定义分配空间;
任何声明为static属性的全局变量或函数是模块私有的;
编译器来保证本地符号的唯一性;
当编译器遇到一个不是在当前模块中定义的变量时,它会假设该符号是在其他某个模块中定义的,生成一个连接器符号表表目;
运行时的存储器映像:未使用->只读段->读写段->运行时堆->共享库的存储器映射区域->用户栈->内核虚拟存储器;
加载运行:可执行文件中段头表的指导下,加载代码和数据->程序入口点_start->初始化函数->注册函数->主函数->返回;
c的启动代码对于每个c程序都是相同的,都需要跳到main函数;
链接就是将不同部分的代码和数据收集和组合成为一个单一文件的过程,这个文件可被加载到存储器并执行.链接可以执行于编译时,也就是在源代码被翻译成机器代码时;也可以执行于加载时,也就是在程序被加载器加载到存储器并执行时;甚至执行于运行时,由应用程序来执行;
链接器在软件开发中扮演着一个关键的角色,因为他们使得分离编译成为了可能;
理解链接器将帮助你构造大型程序;理解链接器将帮助你避免一些危险的编程错误;理解链接器将帮助你理解语言的作用域规则是如何实现的;理解链接器将帮助你理解其他重要的系统概念;理解链接器使你能够开发共享库;
目 标文件纯粹是字节块的集合,这些块中,有些包含程序代码,有些则包含程序数据,而其他的则包含指导链接器和加载器的数据结构.链接器将这些块连接起来,确 定链接块的运行时位置,并且修改代码和数据块中的各种位置.链接器对目标机器了解甚少,产生目标文件的编译器和汇编器已经完成了大部分工作;
目标 文件有三种形式:1.可重定位目标文件 包含二进制代码和数据,其形式可以在编译时与其他可重定位目标文件合并起来,创建一个可执行目标文件;2.可执行目标文件 包含二进制代码和数据,其形式可以被直接拷贝到存储器并执行;3.共享目标文件 一种特殊类型的可重定位目标文件,可以在加载活着运行时,被动态的加载到存储器并链接;
各个系统之间,目标文件的格式都不相同;
SUN  Solaris使用的是Unix ELF(可执行可链接格式).尽管我们的讨论集中在ELF上,但是不管是那种格式,基本的概念是相似的;
ELF 头以一个16字节的序列开始,这个序列描述了字的大小和生成该文件的系统的字节顺序.ELF头剩下的部分包含帮助链接器解析和解释目标文件的信息.其中包 括了ELF头的大小,目标文件的类型(可重定位,可执行或是共享等),机器类型(IA32等),节头部表的文件偏移,以及节头部表中的表目大小和数量.不 同节的位置和大小是有节头部表描述的,其中目标文件中每个节都有一个固定大小的表目;
每个可重定位目标文件m都有一个符号表,它包含m所定义和引 用的符号的信息.在链接器的上下文中,有三种不同的符号:1.由m定义并能被其他模块引用的全局符号.全局链接器符号对应于非静态的c函数以及被定义为不 带c的static属性的全局变量;2.由其他模块定义的并被模块m引用的全局符号.这些符号称为外部符号,对应于定义在其他模块中的c函数和变量;3. 只被模块m定义和引用的本地符号.有的本地链接器符号对应于代static属性的c函数和全局变量.这些符号在模块m中的任何地方都是可见的,但是不能被 其他模块引用.
.symtab中的符号表不包含对应于本地非静态程序变量的任何符号.这些符号在运行时在栈中被管理,链接器第此类符号不感兴趣;
c程序员使用static属性在模块内部隐藏变量和函数声明;
链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义联系起来;
编译器只允许每个模块中的每个本地符号只有一个定义,编译器还确保静态本地变量,他们也也会有本地链接器符号,拥有唯一的名字;
当编译器遇到一个不是在当前模块中定义的符号(变量或是函数)时,它会假定该符号是在其他模块中定义的,生成一个链接器符号表表目,并把它交给链接器处理;
c++和java中能使用重载函数,是因为编译器将每个唯一的方法和参数列表组合编码成一个对链接器来说是一个唯一的名字.这种编码过程叫做毁坏,而相反的过程叫做恢复;
函数和已初始化的全局变量是强符号,未初始化的全局变量是弱符号;
根据强弱符号的定义,Unix链接器使用下面的规则来处理多处定义的符号:1.不允许有多个强符号;2.如果有一个强符号和多个弱符号,那么选择强符号;3.如果有多个弱符号,那么从这些弱符号中任意选择一个;
所有的编译系统都提供一种机制,将所有相关的目标文件打包为一个单独的文件,称为静态库,它也可以作为链接器的输入;
在Unix系统中,静态库以一种称为存档的特殊文件格式存放在磁盘中.存档文件是一组连接起来的可重定位目标文件的集合,有一个头部描述每个成员目标的大小和位置;
在符号解析的阶段,Unix链接器从左到右按照它们在编译器驱动程序命令行上出现的相同顺序来扫描可重定位目标文件和存档文件;
一 旦链接器完成了符号解析这一步,它就把代码中的每个符号引用和确定的一个符号定义(也就是它的一个输入目标模块中的一个符号表表目)联系起来.在此时,链 接器就知道它的输入目标模块中的代码节和数据节的确切大小.现在就可以开始重定位步骤了,在这个步骤中,将合并输入模块,并为每个符号分配运行时的地址. 重定位由两部分组成:重定位节和符号定义(这步完成时,程序中的每个指令和全局变量都有一个唯一的运行时存储器地址了);重定位节中的符号引用.
当 汇编器生成了一个目标模块时,它并不知道数据和代码最终将存放在存储器的什么位置.它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置.所 以,无论何何时编译器遇到对最终位置未知的目标引用,它就会生成一个重定位表目,告诉链接器在将目标文件合并成可执行文件时如何修改这个引用,代码的重定 位表目放在.relo.text中,已初始化数据的重定位表目放在.relo.data中;
可执行文件的.init节定义了一个小函数,叫做_init,程序的初始化代码会调用它;
ELF可执行文件被设计为一个很容易加载到存储器,连续的可执行文件组块被映射到连续的存储器段.段头表描述了这种映射关系;
加载器将可执行目标文件中的代码和数据从磁盘拷到存储器中,然后通过跳转到程序的第一条指令,即入口点,来运行该程序.这个将程序拷贝到存储器并运行的过程叫做加载;
当 加载器运行时,它创建了一个存储器映像.在可执行文件中段头表的知道下,加载器将可执行文件的相关内容拷贝到代码和数据段,接下来,加载器跳转到程序的入 口点,也就是符号_start的地址._start地址处的启动代码是在目标文件ctrl.o中定义的,对所有的c程序都是一样的.在从.text 和.init节中调用了初始化例程后,启动代码调用atexit例程,这个程序附加了一系列在应用调用exit函数时应该调用的程序.exit函数运行 atexit注册函数,然后通过调用_exit将控制返回给操作系统,接着,启动代码调用应用程序的main程序,这就开始执行我们的c代码了,在应用程 序返回之后,启动代码调用_exit程序,它将控制返回给操作系统;
Unix系统中的每个程序都运行在一个进程上下文中,这个进程上下文有自己的 虚拟地址空间,当shell运行一个程序时,父shell进程生成一个子进程,他是父进程的一个复制品.子进程通过execve系统调用启动加载器.加载 器删除子进程已有的虚拟存储器段,并创建一组新的代码,数据,堆和栈段.新的栈和堆段被初始化为零.通过将虚拟地址空间中的页映射到可执行文件的页大小的 组块,新的代码和数据段被初始化为可执行文件的内容.最后,加载器跳转到_start地址,它最终会调用应用的main函数.除了一些头部信息,在加载过 程中没有任何从磁盘到存储器的数据拷贝.直到CPU引用一个被映射的虚拟页,才会进行拷贝,此时,操作系统利用它的页面调度机制自动将页面从磁盘传送到存 储器;
共享库是致力于解决静态库缺陷的一个现代创新产物.共享库是一个目标模块,在运行时,可以加载到任意的存储器地址,并在存储器中和一个程序链接起来.这个过程称为动态链接,是由一个叫做动态链接器的程序来执行的;
在存储器中,一个共享库的.text节只有一个副本可以被不同的正在运行的进程共享;
生成动态链接的可执行文件时,链接器拷贝了一些重定位和符号表信息,它们使得运行时可以解析对动态库中代码和数据的引用;
加 载器将可执行文件的内容映射到存储器,并运行这个程序.链接器还可能生成部分链接的可执行程序,这样的文件中有未解析的到定义在共享库中的程序和数据的引 用.在加载时,加载器将部分链接的可执行文件映射到存储器,然后调用动态链接器,它通过加载共享库和重定位程序中的引用来完成链接;
(7.7 7.11 7.12未理解)

第十章:虚拟存储器
存储器很容易被破坏.如果某个进程不小心写了另一个进程使用的存储器,那么进程可能以某种完全和程序逻辑无关的令人迷惑的方式失败;
为 了更加有效地管理存储器并且少出错,现代系统提供了一种对主存的抽象概念,叫做虚拟存储器.虚拟存储器是硬件异常,硬件地址翻译,主存,磁盘文件和内核软 件的完美交互,它为每个进程提供了一个大的,一致的,私有地址空间.通过一个很清晰的机制,虚拟存储器提供了三个重要的能力:它将主存看成是一个存储在磁 盘上的地址空间的高速缓存,在主存中只保存活动区域,并根据需要在磁盘和主存之间来回传送数据,通过这种方式,它高效地使用了主存;它为每个进程提供了一 个一致的地址空间,从而简化了存储器管理;它保护了每个进程的地址空间不被其他进程破坏;
虚拟存储器是危险的.每次应用程序引用一个变量,间接引用一个指针,或者调用一个诸如malloc这样的动态分配包程序时,它就会和虚拟存储器发生交互;
本章的前一部分描述虚拟存储器是如何工作的,后一部分描述的是应用程序如何使用和管理虚拟存储器;
计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组,每个字节都有一个唯一的物理地址;
早起的PC使用物理地址寻址,为通用计算设计的现代处理器使用的是虚拟寻址;
CPU芯片上叫做MMU的专用硬件,利用存放在主存中的查询表来动态的翻译虚拟地址,该表的内容由操作系统管理的;
一个地址空间的大小是由表示最大地址所需要的位数来描述的;
这就是虚拟存储器的思想.主存中的每个字节都有一个选自虚拟地址空间的虚拟地址,和一个选自物理地址空间的物理地址;
概念上而言,虚拟存储器被组织为一个存放在磁盘上的N个连续的字节大小的单元组成的数组.每字节都有唯一的虚拟地址,这个唯一的虚拟地址是作为到数组的索引的;
VM系统通过将虚拟存储器分割为称为虚拟页的大小固定的块,来处理这个问题.每个虚拟页的大小为2的P次方字节.类似的,物理存储器被分割为物理页,大小也是2的p次方字节.
在任意时刻,虚拟页的集合都分为三个不相交的子集:
    未分配的:VM系统还未分配的页,未分配的块没有任何数据和它们相关联,因此就不占用任何磁盘空间;
    缓存的:当前缓存在物理存储器中的已分配页;
    未缓存的:没有缓存在物理存储器中的已分配页;
DRAM比SRAM要慢大约10倍,而磁盘要比DRAM慢大约100000多倍.因此,DRAM缓存中的不命中比起SRAM缓存中的不命中要昂贵的多;
因为大的不命中处罚和访问第一字节的开销,虚拟页趋向于很大,典型的是4-8KB;
比起硬件对SRAM缓存,操作系统对DRAM缓存使用了更复杂精密的替换算法,最后,因为对磁盘的访问时间很长,DRAM缓存总是使用写回,而不是直写;
同 任何缓存一样,虚拟存储器系统必须有某种方法来判定一个虚拟页是否放在DRAM中的某个地方.如果是,系统还必须确定这个虚拟页存放在哪个物理页中.如果 不命中,系统必须判断这个虚拟页存放在磁盘的哪个位置,在物理存储器中选择一个牺牲页,并将虚拟页从磁盘拷贝到DRAM中,替换这个牺牲页;
这些 功能是由许多软硬件联合提供的,包括:操作系统软件,MMU中的地址翻译硬件,和一个存放在物理存储器中叫做页表的数据结构.页表将虚拟页映射到物理页. 每次地址翻译硬件将一个虚拟地址转换为物理地址时,都会读取页表.操作系统负责维护页表的内容,以及在磁盘与DRAM之间来回传送页;
页表就是一个PTE的数组.虚拟地址空间中的每个页在页表中的一个固定偏移量处都有一个PTE;
因为DRAM缓存是全相关联的,任意物理页都可以包含任意虚拟页;
地址翻译硬件将虚拟地址作为一个索引;
虚拟存储器是在20世纪60年代早起发明的,远在CPU-存储器之间的差距的加大引发产生SRAM缓存之前;
虚拟存储器工作的相当好,这主要归功于我们的老朋友局部性;
操作系统为每个进程提供了一个独立的页表,因而也就是一个独立的虚拟地址空间;
多个虚拟页面可以映射到同一个共享物理页面上;
独立的地址空间允许每个进程为它的存储器映像使用相同的基本格式,而不管代码和数据实际存放在物理存储器的何处;
这样的一致性极大的简化了链接器的设计和实现,允许链接器生成全链接的可执行文件,这些可执行文件是独立于物理存储器中代码和数据的最终位置的;
一般而言,每个进程都有自己的私有代码,数据,堆以及栈区域,是不和其他进程共享的.在这种情况中操作系统创建页表,将相应的虚拟页映射到不同的物理页;
然而,在一些情况中,还是需要进程来共享代码和数据的.例如,每个进程必须调用相同的操作系统内核代码,而每个c程序都会调用标准库中的程序;
当一个运行在用户进程中的程序要求额外的堆空间时,操作系统分配一个适当的数次和连续的虚拟存储器页面,并且将它们映射到物理存储器中任意位置的k个任意的物理页面.由于页表工作的方式,操作系统没有必要分配k个连续的物理存储器页面.页面可以随机的分散在物理存储器中;
有趣的一点是加载器从不真正的从磁盘中拷贝任何数据到存储器中.当每个页面第一次被引用时,虚拟存储器系统将自动并按需的把数据从磁盘上调入到存储器,页面引用或者是当CPU取一条指令时,或者是当一条正在执行的指令引用一个存储器位置时;
任 何现代计算机系统必须为操作系统提供手段来控制对存储器系统的访问.不应该允许一个用户进程修改它的只读文本段,而且也不应该允许它读或者修改任何内核中 的代码和数据结构.不应该允许它读或者写其他进程的私有存储器,并且不允许它修改任何与其他进程共享的虚拟页面,除非所有的共享者都显式的允许它这么做;
运行在内核模式中的进程可以访问的任何页面,但是运行在用户模式中的进程只能访问那些SUP为0的页面;
CPU中的一个控制寄存器,页表基址寄存器指向当前的页表;
MMU利用VPN来选择适当的PTE.例如vpn0选择pte0等.将页表条目中的PPN和虚拟地址中的VPO串联起来,就得到相应的物理地址,注意,因为物理和虚拟页面都是P字节的,所以PPO和VPO是相同的;
当出项页面命中时,CPU硬件执行的步骤:
    处理器生成一个虚拟地址,并把它传送给MMU;
    MMU生成PTE地址,并从高速缓存/主存请求得到它;
    高速缓存/主存向MMU返回PTE;
    MMU构造物理地址,并把它传送给高速缓存/主存;
    高速缓存/主存返回所请求的数据字给处理器;
页面命中完全由硬件来处理的,而处理缺页要求硬件和操作系统内核协作完成的;
    第一步到第三步同上
    PTE中的有效位是零,所以MMU触发了一次异常,传递CPU中的控制到操作系统内核中的缺页异常处理程序;
    缺页处理程序确定出物理存储器中的牺牲页面,如果这个页面已经被修改了,则把它页面换出到磁盘;
    缺页处理程序页面调入新的页面,并更新存储器中的PTE;
    缺页处理程序返回到原来的进程,驱使导致缺页的指令重新启动,CPU将引起缺页的指令重新发送给MMU.因为虚拟页面现在缓存在物理存储器中,所以就会命中,在MMU执行了如上的步骤,主存就会将所请求的自返回给处理器;
MMU中包括了一个关于PTE的小的缓存,称为TLB(翻译后备缓冲器)
用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的;
用来压缩页表的常用方法是使用 层次结构的页表;
一级页表转中的每个PTE负责映射虚拟地址空间中的一个4MB的组块;
如果组块i中的每个页面都未分配,那么一级PTE i就为空,然而,如果在组块i中至少有一个页是分配了的,那么一级PTE i就指向一个二级页表的基址;
二级页表中的每个PTE都负责映射一个4KB的虚拟存储器页面,每个一级和二级页表都是4KB的;
这 种方法从两个方面减少了存储器要求:第一,如果一级页表中的一个PTE是空的,那么相应的二级页表就根本不会存在;第二,只有一级页表需要总是在主存中, 虚拟存储器系统可以在需要的时候创建并页面调入或调出二级页表,这就减少了主存的压力.只有最经常使用的二级页表才需要缓存在主存中;
为了方便,我们用索引它的VPN来标识每个PTE,但是要记住这些VPN并不是页表的一部分,也不在存储器中;