读《程序是如何跑起来的》

前言

操作系统将底层的很多抽象的原理封装成面向对象的、方便大众理解和操作的图形界面、这大大提高了计算机操作的便利性，然而，享受方便的同事也付出了代价，对于底层的了解越来越少，只会使用工具，却无法明白工具的底层机制就无法创造出更好的工具。

第1章对程序员来说CPU是什么

热身问题

问：

程序是什么?
程序是由什么组成的?
什么是机器语言?
正在运行的程序存储在什么位置?
什么是内存地址?
计算机的构成元件中，负责程序的解释和运行的是哪个?

答：

指示计算机每一步动作的一组指令
指令和数据
CPU 可以直接识别并使用的语言
内存
内存中，用来表示命令和数据存储位置的数值
CPU

解析

一般所说的程序,譬如运动会、音乐会的程序等,指的是“行事的先后次序”。计算机程序也是一样的道理。
程序是指令和数据的组合体。例如，C 语言“printf(“ 你好”);”这个简单的程序中，printf是指令，” 你好” 是数据。
CPU 能够直接识别和执行的只有机器语言。使用C、Java 等语言编写的程序,最后都会转化成机器语言。
硬盘和磁盘等媒介上保存的程序被复制到内存后才能运行。
内存中保存命令和数据的场所，通过地址来标记和指定。地址由整数值表示。
计算机的构成元件中，根据程序的指令来进行数据运算，并控制整个计算机的设备称作CPU。大家熟知的奔腾( Pentium )就是CPU 的一种。

1.1 CPU内部结构

集成电路 = CPU + 内存

CPU
- 寄存器：暂存指令、数据, 一般一个CPU包含20~100个寄存器.
- 控制器：负责把内存上指令、数据的读入寄存器.
- 运算器: 负责运算，从内存读入寄存器的数据。
- 时钟：发出CPU开始计时的时钟信号。

程序启动后，根据时钟信号，控制器会从内存中读取指令和数据。通过对这些指令加以解释和运行，运算器就会对数据进行运算。控制器根据该运算结果来控制(主要是数据输人输出的时机控制)计算机。

小总结

程序编写好后，被计算机复制到内存中，然后CPU的控制器从内存中读取指令和数据，运算器对数据进行运算，最后控制器根据运算器的结果来控制计算器。因为现在计算机CPU的计算能力很强，所以这个过程很快。

寄存器

寄存器的主要种类和功能

表1-1 寄存器的主要种类和功能

种类	功能
程序计数器( program counter )	存储下一条指令所在内存的地址
标志寄存器( flag register )	存储运算处理后的CPU 的状态

汇编语言

汇编：将汇编语言编写的程序转化成机器语言的过程称为汇编。
反汇编：将机器语言转化成汇编语言程序的过程称为反汇编。

汇编语言：汇编语言采用助记符(memonic )来编写程序,每一个原本是电气信号的机器语言“指令都会有一个与其相应的助记符，汇编语言和机器语言基本上是一一对应的。

条件分支和循环机制

程序的流程
* 顺序执行：按照地址内容的顺序执行指令
* 条件分支：根据条件执行任意地址的指令
* 循环：重复执行同一地址的指令

函数的调用机制

函数实现了代码指令在内存的离散分布。

Call指令：调用函数后需要执行的质量地址存在栈中
Return指令：将保存在栈中的地址设定到程序计数器中，函数处理完后，下一个指令就会被读取出来，再被设定到程序计数器中。
栈(stack) 本来是“干草等堆积如山”的意思。在程序领域中，通常使用
该词来表示不断地存储各种数据的内存区域。函数调用后之所以能正确
地返回调用前的地址，就是栈的功劳。
数组: 是指同样长度的数据, 在内存中进行连续排列的数据构造。一个数组名来表示全体数据，通过索引来区分数组的各个数据(元素)。
位：1位代表二进制数的一个字节位。

综合使用地址和索引来决定实际地址

机器语言

原来CPU可以进行的处理非常少。虽然高级编程语言编写的程序看起来非常复杂,但CPU实际处理的事情就是这么简单。

一点感想

机器语言指令必须要有读写和传送的操作，还有逻辑运算，而跳转和Call、Return指令是高级一点的指令。

感觉CPU其实主要发挥它的性能优势，计算速度快，但是专注于快速处理数据运算，CPU无法处理复杂的高级逻辑，所以才出现了各种方便程序员理解的高级编程语言。反应到生活中，人也要尽量发挥个人的长处，才能创造更大的价值吧

第2章数据是用二进制表示的

问

32 位是几个字节?
二进制数01011100 转换成十进制数是多少?
二进制数00001111左移两位后，会变成原数的几倍?
补码形式表示的8位二进制数11111111,用十进制数表示
的话是多少?
补码形式表示的8位二进制数10101010，用16位的二进
制数表示的话是多少?
反转部分图形模式时，使用的是什么逻辑运算?

解析

因为8位=1字节，所以32位就是32/8=4字节。
92, 将二进制数的各数位的值和位权相乘后再相加，即可转换成十进制数。
4倍, 二进制数左移1位后会变成原来的值的2倍。左移两位后，就是2倍的2倍，即4倍。
-1, 所有位都是1的二进制数,用十进制数表示的话就是-1。
1111111110101010, 使用原数的最高位1来填充高位。
XOR 运算只反转与1相对应的位。NOT运算是反转所有的位。

二进制的IC

计算机处理信息最小的单位是位——就相当于二进制中的一位（binary digit）

字节

二进制数的位数一般是8位、16位、32位…..也就是8的倍数, 这是因为计算机所处理的信息的基本单位是8位二进制数。

8位二进制数被称为一个字节。字节是最基本的信息计量单位。

位是最小单位，字节是基本单位。

内存和磁盘都使用字节单位来存储和读写数据，使用位单位则无法读写数据。因此，字节是信息的基本单位。

用字节单位处理数据时,如果数字小于存储数据的字节数( 二进制数的位数),那么高位上就用0填补。例如，100111这个6 位二进制数，用8位(=1字节)表示时为00100111,用16位(=2字节)表示时为000000000100111。

对于用二进制数表示的信息，计算机不会区分它是数值、文字，还是某种图片的模式等，而是根据编写程序的各位对计算机发出的指示来进行信息的处理(运算)。具体进行何种处理，取决于程序的编写方式。

位运算

十进制数左移后会变成原来的10倍、100倍、1000倍…..样，二进制数左移后就会变成原来的2倍、4倍、8倍…..之二进制数右移后则会变成原来的1/4、1./…..这样一来，大家应该能够理解为什么移位运算能代替1/2、乘法运算和除法运算了吧。

二进制数中最高位称为符号位。符号位是0 时表示正数，符号位是1时表示负数。

补数

二进制的补数为”取反+1”
一个负数可用它的正补数来代替，而这个正补数可以用模加上负数本身来得到。
一个正数和一个负数互为补数时，两数的绝对值之和为模
正数的补数为其自身。

逻辑右移

算术右移

将二进制数作为带符号的数值进行运算时，移位后要在最高位填充移位前符号位的值(0 或1)。
如果数值是用补数表示的负数值，那么右移后在空出来的最高位补1,就可以正确地实现1/2、1/4、1/8 等的数值运算。如果是正数，只需在最高位补0即可。
只有在右移时才必须区分逻辑位移和算术位移。左移时，只需在空出来的低位补0即可。

第3章计算机进行小数运算出错的原因

问：

二进制数0.1,用十进制数表示的话是多少?
用小数点后有3 位的二进制数，能表示十进制数0.625 吗?
将小数分为符号、尾数、基数、指数4 部分进行表现的形式
称为什么?
二进制数的基数是多少?
通过把0 作为数值范围的中间值，从而在不使用符号位的情
况下来表示负数的表示方法称为什么?
10101100.01010011这个二进制数，用十六进制数表示的
话是多少?

答：

二进制数的小数点后第一位的位权是2^-1= 0.5。也就是说，二进制数0.1—> 1 x 0.5 —> 十进制数0.5。
十进制数0.625 转换成二进制0.101。
浮点数是指把小数用“符号尾数x 基数的指数次幂”这种形式来表示。
二进制数的基数是2,十进制数的基数是10。以此类推，XX进制数的基数就是X X。
EXCESS是“剩余的”的意思。例如，把0111111看作是0 的话，比这个数小1的01111110就是 -1。
整数部分和小数部分一样, 二进制数的4 位，就相当于十六进制数的1位。

3.1 计算机的误差

结果：

1	sum = 10.000002

3.2 用二进制表示小数

计算机之所以会出现运算错误，是因为“有一些十进制数的小数无法转换成二进制数”。例如，十进制数0.1,就无法用二进制数正确表示，小数点后面即使有几百位也无法表示。

因为无法正确表示的数值，最后都变成了近似值。计算机这个功能有限的机器设备,是无法处理无限循环的小数的。因此，在遇到循环小数时，计算机就会根据变量数据类型所对应的长度将数值从中间截断或者四舍五入。

3.4 浮点数

单精度浮点数，32位， float
双精度浮点数， 64位，double

3.7 如何避免计算机计算出错

计算机计算出错的原因之一是，采用浮点数来处理小数(另外,也
有因“位溢出”而造成计算错误的情况)。

将小数转换成整数计算
在一定误差范围内忽略

第4章熟练使用有棱有角的内存

问：

二进制数0.1,用十进制数表示的话是多少?
用小数点后有3 位的二进制数，能表示十进制数0.625 吗?
将小数分为符号、尾数、基数、指数4 部分进行表现的形式
称为什么?
二进制数的基数是多少?
通过把 0 作为数值范围的中间值，从而在不使用符号位的情
况下来表示负数的表示方法称为什么?
10101100.01010011这个二进制数，用十六进制数表示的
话是多少?

答：

二进制数的小数点后第一位的位权是2^-1= 0.5。也就是说，二进制数0.1—> 1 x 0.5 —> 十进制数0.5。
十进制数0.625 转换成二进制0.101。
浮点数是指把小数用“符号尾数x 基数的指数次幂”这种形式来表示。
二进制数的基数是2,十进制数的基数是10。以此类推，XX进制数的基数就是X X。
EXCESS是“剩余的”的意思。例如，把0111111看作是0 的话，比这个数小1的01111110就是 -1。
整数部分和小数部分一样, 二进制数的4 位，就相当于十六进制数的1位。

4.1 内存的物流机制

内存IC
- DRAM Dynamic 随机存储器, 需要不断是刷新电路
- SRAM Staic 随机存储器，不需要不断是刷新电路
- ROM 只读存储器
- 电源
- 地址信号
- 数据信号
- 控制信号

4.2 内存的逻辑模型是楼房

内存为1KB时，表示的是如图所示的有1024层的楼房(这里地址的值是从上往下逐渐变大，不过也有与此相反的
情况)。

物理上以1个字节为单位来逐一读写数据的内存，在程序中，通过指定其类型(变量的数据类型等),也能实现以特定字节数为单位进行读写。

根据程序中所指定的变量的数据类型的不同，读写的物理内存大小也会随之发生变化。C 语言中，8字节(=64 位)的double 类型是最大的。

4.3 简单的指针

指针也是一种变量
它所表示的不数据的值，而是存储着数据的内存的地址。
通过使用指针，就可以对任意指定地址的数据进行读写。
定义指针时候，常在变量名前加一个星号（*）
定义指针的数据类型表示从指针存储的地址中一次能读写的数据字节数

4.4 数组

数组是指多个同样数据类型的数据在内存中连续排列的形式。
作为数组元素的各个数据会通过连续的编号被区分开来，这个编号称为索引index。
指定索引后，可以对该索引所对应地址的内存进行读写操作。
索引和内存地址的变换工作则是由编译器自动实现的。

数组可以使编程工作变得更加高效，如果在循环中反复使用数组，使用索引可以很方便的达到按顺序进行读写数组元素的目的。

4.5 栈和队列

在对内存数据进行读写时

栈用的是LIFO (Last Input First Out,后人先出)方式
队列用的则是FIFO( First Input First Out,先人先出) 方式

队列的环状缓冲区(ring buffer )方式

有6 个元素的数组来实现一个队列。从数组的起始位置开始有序存储数据，再按照存储的顺序读出数据。数组末尾写人数据后，后一个数据就会被写人数组的起始位置(此时数据已经被读出所以该位置是空的)。这样，数组的末尾就和开头连接了起来，数据的写人和读出也就循环起来了

4.6 链表

链表：使数组元素的添加和删除更容易
在数组的各个元素中，除了数据的值之外，通过为其附带上下一
个元素的索引，即可实现链表。数据的值和下一个元素的索引组合在一起，就构成了数组的一个元素。

链表删除元素

链表追加元素

如果单纯通过移动元素来挪出空间，每次都需要移动数千至数万个元素，那么哪怕是高速计算机也会花费很长时间。

4.7 二叉树

二叉查找树：可以更加高效地对数组数据进行检索。

在链表的基础上
往数组中追加元素时，根据数据的大小
分成左右两个方向的表现形式
二叉查找树是由链表构造发展而来的表现形式，因此在追加或删除元素方面也同样是有效的。

在使用一般的数组时，必须从数组的开头按照索引顺序来查找目标数据。
而使用二叉查找树时，当目标数据比现在读出来的数据小时就可以转到左侧，反之目标数据较大时即可转到链表的右侧
这样就加快了找到目标数据的速度。

第5章内存和磁盘

问：

存储程序方式指的是什么?
通过使用内存来提高磁盘访问速度的机制称为什么?
把磁盘的一部分作为假想内存来使用的机制称为什么?
Windows 中，在程序运行时，存储着可以动态加载调用的
函数和数据的文件称为什么?
在EXE 程序文件中，静态加载函数的方式称为什么?
在Windows 计算机中，一般磁盘的1个扇区是多少字节?

答：

在存储装置中保存程序，并逐一运行的方式
Disk Cache( 磁盘缓存)
虚拟内存( virtual memory )
DLL( DLL 文件)
静态链接
512 字节

内存

用电流来实现存储的内存
高速高价

磁盘

利同利用磁效应来实现存储
低速廉价
磁盘中，利用磁极的不同来标记0、1

5.1 程序的运行需要被读入内存

存储程序方式(程序内置方式)： 程序保存在存储设备中，通过有序地被读出来实现运行

原因：负责解析和运行程序内容的CPU,
需要通过内部程序计数器来指定内存地址，然后才能读出程序。

CPU可以直接从读磁盘中存储的程序，但是磁盘读取速度太慢，程序的运行速度会大大降低。

5.2 磁盘缓存加快了磁盘访问速度

磁盘缓存

指的是把从磁盘中读出的数据存储到内存空间中的方式。
需要读取同一数据时，就不用通过实际的磁盘，而是从磁盘缓存中把内容读出。加快访问速度

5.3 虚拟内存把磁盘作为部分内存来使用

虚拟内存( virtual memory )

虚拟存储：在有限容量的内存中，以页为单位自动装入更多更大的程序
虚拟内存是指把磁盘的一部分作为假想的内存来使用。
这与磁盘缓存是假想的磁盘(实际上是内存)相对，虚拟内存*是假想的内存(实际上是磁盘)*。

实现方式

覆盖（overlay）：应用程序手动把需要的指令和数据保存在内存中
交换（swapping）：操作系统自动把暂时不能执行的程序保存到外存中

CPU 只能执行加载到内存中的程序。虚拟内存虽说是把磁盘作为内存的一部分来使用，但实际上正在运行的程序部分，在这个时间点上是必须存在在内存中的。

为了实现虚拟内存,就必须把实际内存(也可称为物理内存)的内容，和磁盘上的虚拟内存的内容进行部分置换(swap ),并同时运行程序。

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存(一个连续完整的地址空间)，而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

虚拟内存无法彻底解决内存不足的问题

而虚拟内存也确实能避免因内存不足导致的应用无法启动。
不过，由于使用虚拟内存时发生的Page In 和Page Out 往往伴随着低速的磁盘访问，因此在这个过程中应用的运行会变得迟钝起来。
虚拟内存无法彻底解决内存不足的问题。

5.4 节约内存的编程方法

从根本上解决内存不足的问题

需要增加内存的容量
尽量把运行的应用文件变小

(1)通过DLL 文件实现函数共有
DLL( Dynamic Link Library )文件”，顾名思义,是在程序运行时可以动态加载Library( 函数和数据的集合)的文件。

那就是多个应用可以共有同一个DLL 文件。而通过共有同一个DLL 文件则可以达到节约内存的效果。

栈清理

5.5 磁盘的物理结构

扇区是对磁盘进行物理读写的最小单位。Windows 中使用的磁盘, 一般1个扇区是512 字节。不过，Windows 在逻辑方面(软件方面)对磁盘进行读写的单位是扇区整数倍簇。根据磁盘容量的不同，1簇可以
是512字节(1簇=1扇区)、1KB(1簇=2扇区)、2KB、4KB、8KB、16KB、32KB (1簇= 64 扇区)。磁盘的容量越大,簇的容量也越大。不过，在软盘中，1簇=512 字节= 1扇区，簇和扇区的大小是相等的。

附：

硬盘的存储原理是什么？为什么一张小小的硬盘可以存下如此多的数据？

磁铁有两个极性, 一个是南极(S极) , 一个是北极(N 极) , 硬盘正是利用磁粒子的极性来记录数据的。
盘片表面的那些磁粉就是磁粒子。盘片被划分成若干个同心圆( 称为磁道),在每个同心圆的磁道上就好像有无数的任意排列的小磁铁, 当这些小磁铁受到来自磁头磁场的影响时,排列的方向随之改变, 利用磁头的磁力统一某区域小磁铁的方向, 就可以使该区域磁场呈现相同极性, 如果把 S/N 两种极性与二进制中的 0和 1 对应, 就可以表示二进制数据, 这些磁粒子都是永磁体, 即便磁头离开, 它依然可以长时间保持形成的极性, 这样就能达到储存信息的目的了。
磁头在读取数据时, 可以感应磁粒子的不同极性, 从而转换成不同的电脉冲信号, 利用解码器将这些原始信号翻译出来, 就成为了电脑能使用的数据。