《编程机制探析》第四章 运行栈与内存寻址

《编程机制探析》第四章 运行栈与内存寻址

计算机启动之后，操作系统程序首先从硬盘进入内存条，成为最先运行起来的一批进程。这一批操作系统进程可了不得，它们规定了CPU工作的总流程。CPU工作的时候，必须严格遵守操作系统进程定义的工作流程。
为了满足人类用户的需求，现代的操作系统都是带有图形界面的多任务（多进程）系统。在计算机运行期间，内存里总是会跑着多个进程。这一点，我们可以在任务管理器已经看到了。
在这种工作模式下，CPU不得不在内存中的多份工作流程（即进程）之间来回穿梭忙碌，每件事都是做了一会儿就放下，赶紧去做另一件事。这就有了一个问题。CPU在放下手头工作之前，必须先把手边的一摊子工作找个地方暂存起来，以便一会儿回来接着干。那么，手头这摊子工作存在哪儿呢？当然是存在内存里。
CPU按照操作系统进程规定的工作流程，会为每一个进程在内存中开辟一块空间，叫做进程空间。
我们可以想象一下，在内存那个巨大的木架上，有无数的小格子。CPU在把程序从硬盘中调入到内存中的时候，就会给每个进程都分配一些小格子，作为进程空间。
进程空间里面首先放进去的东西，自然是进程本身定义的工作流程。除此之外，进程空间中还放了一些CPU在按章办事过程中打开的其他资源。总之，与该进程的工作流程相关的一切资源都记录在进程空间中。CPU在进行工作切换之前，手头的一摊子工作也要暂存到进程空间中的某一块地方。那块存放当前工作状态的空间有一个特殊的学名，叫做“运行栈”。
“栈”这个词翻译于英文Stack，是数据结构中的概念。“栈”是一种非常简单的数据结构，很容易理解。它的特性是“先进后出，后进先出”，即，你先放进去的东西压在最底下，你最后才能拿出来。你最后放进去的东西在最上面，你可以最先拿出来。
运行栈，顾名思义，就是CPU在运行进程时，需要的一个栈结构。CPU在运行时，需要一个空间存放当时运行状态，这一点不难理解。但是，这块空间为什么要是“栈”结构的，这一点就不那么容易理解了。为了理解这一点，我们必须深入探讨CPU在执行进程时的运行机制。
一份进程就是一份工作流程，但这份工作流程的结构并不简单，很有可能包含很多分支工作流程。这就像人类社会中的相互参照的各种条款一样，一份条款的内容很可能引用到其他条款中。比如，网上流传着这么一份脍炙人口、含义隽永的婚姻协议：
第一条，老婆永远是对的。
第二条，如有不同意见，请参照第一条。
在上述两个条款中，第二条就引用了第一条。进程的情况也是如此，一份主工作流程中经常包含很多分支流程，不仅主工作流程经常引用分支流程，分支流程之间也经常相互引用。当CPU遇到引用分支流程的情况，就会暂停本流程的执行，先跳转到被引用的分支流程，执行完那个分支流程之后，才回到之前的流程继续执行。那么，之前那个暂停的流程的当前工作状态存放在哪里呢？没错，就是我们前面讲过的运行栈。
CPU先把之前流程的当前工作状态存放到运行栈中，然后跳转到一个分支流程，开始执行。CPU在执行当前这个分支流程的过程中，也使用同一个运行栈来存放当前工作状态，而且是放在之前那个工作流程的工作状态的上面。当完成当前分支流程之后，CPU就会移走运行栈中当前分支流程的工作状态，这时候，上一个没完成的工作流程的工作状态就浮出水面，出现在运行栈的最顶层。CPU正好就接着上次未完成的工作状态继续进行。
我们可以看到，运行栈这种“先进后出，后进先出”的特点，恰好就是“栈”这个数据结构的特点，因而得名“运行栈”。
如果你有过调试程序的经验，幸运的话，你可能会遇到这样一个错误——Stack Overflow（栈溢出）。这里的Stack（栈），指的就是运行栈。
关于“Stack”这个英文名词的译法，还有些说道。在一些技术书籍里，Stack被翻译成“堆栈”。这种译法还挺常见。但我认为，“堆栈”这种说法是不准确的。因为，“堆”和“栈”是两种不同的数据结构。
“堆”这种数据结构主要用于内存的分配、组织、管理，结构比“栈”结构复杂得多，本书不会展开详述，因为对于应用程序员来说，并不需要掌握“堆”这个结构的具体原理。不过，应用程序员还是应该掌握一些内存管理的基本概念。
我们可以把内存想象成一个巨大无比的木架，上面有无数的大小相同的格子。那些格子就是内存单元。如同信箱一样，每一个小格子（内存单元）都有自己的地址编号，叫做内存地址，由操作系统进程统一管理和编制。
小格子的数量就是内存容量。同样，操作系统进程所管理的虚拟内存容量并不一定和内存卡的物理内存容量一致。操作系统进程有可能在硬盘上开辟一块空间，作为虚拟内存的备用空间，当内存卡的物理内存容量不够时，就把内存中一些暂时不用的内容暂存道硬盘上，然后把需要的内容导入腾出的内存空间。这种技术叫做虚拟内存置换。
为了便于讨论，避免歧义，在本书后面提到“内存”的时候，不再指物理内存卡，而是指操作系统管理的“虚拟内存”。
在“虚拟内存”这个巨大的木架上，每一个小格子的大小都是完全一致的，每个小格子都有自己唯一的内存地址。我们可以把各种数据存放到小格子里面。如果数据尺寸足够小的话，自然没问题。如果数据尺寸超过了小格子的大小怎么办？不用担心，相邻的小格子之间都是相通的，我们可以把大尺寸的数据放在相邻的多个小格子里面。
乍看起来，一个数据放在一个小格子里面和多个小格子里面，并没有太大的区别。但是，在某些情况下，却会产生微妙的差别，甚至会对我们的程序设计产生影响。
CPU工作的时候，经常需要把数据从内存这个大木架中取到自己的“寄存器”工作台上。当数据存放在一个小格子里面的时候，CPU只需要取一次就够了。这种操作叫做原子操作，即不会被打断的最小工作步骤。
在物理学中，原子，这个词的含义就是最本原的粒子，不可能再被分割。当然，后来物理学家又发现了更小的粒子。但原子这个词的本意却是不可分割的。原子操作也是这个意思，即不可分割的操作。
当数据存放在多个小格子里面的时候，CPU有可能需要分几次从内存中取出数据，这样就分成了几个步骤，中间有可能被打断，在某些特殊的情况下，可能发生不可预知的后果，这种操作就叫做非原子操作。
从程序设计的角度来讲，原子操作自然是比非原子操作安全的。因此，我们在设计程序时，脑子里应该有这个意识，尽量避免引起的非原子操作。这类非原子操作通常由长数据类型引起。至于数据类型是什么，什么又是“长”数据类型，非原子操作又可能产生怎么样的意外，后面会有专门的章节讲解这方面的内容，我们现在不必关心。
从这里我们看出，操作系统的内存单元的尺寸对于原子操作的意义。内存单元越大，就能够容纳更大的数据，就越容易保证原子操作。
我们常听到，32位操作系统或64位操作系统之类的说法。这里的32位或者64位的说法，指的就是CPU的工作台（寄存器）的位数。
64位操作系统的内存单元32位操作系统大了一倍，那么，原子操作能够容纳的数据尺寸也大了一倍。这意味着，在取用某些“长”数据类型的时候，CPU按照64位操作系统的规则，只需要取一次，就可以把数据取到寄存器中。而CPU按照32位操作系统的规则，却分两次把数据取到寄存器中。因此，从处理长数据类型的速度上来说，64位操作系统是优于32位操作系统的。
内存单元是操作系统定义的，原子操作自然也是操作系统来保证的，同时也需要CPU的相应支持。至少，CPU的“寄存器”工作台尺寸不能小于内存单元，CPU才能一次就把一个内存单元中的数据取到寄存器中。现代的CPU已经进入多核时代，都已经支持64位宽度的内存单元，从而支持64位操作系统。
我们已经屡次提到32位操作系统和64位操作系统。那么，这个“位”到底是什么呢？
要理解这个概念，我们必须首先理解什么是二进制。
我们在日常生活中计算数目用的都是十进制，满十进位。据说是因为我们人类有十个手指头，每次算数的时候都会掰手指头，掰到十个的时候，就没得掰了，就开始进位。这种说法并非空穴来风。英文Digit就是十进制数字的意思（从0到9之间的个位数字），同时还有手指头或者脚趾头的含义（脚趾头也是十个）。所幸当年的人类先祖并没有把手指头和脚趾头一起数，否则，我们今天用的就是二十进制了。
另外，十二进制也是日常生活经常见到的进制。比如，十二个就是一打（Dozen），十二个月就是一年。同时，人类的时间计数也采用各种其他的进制。比如，七天是一周，六十秒是一分钟，六十分钟是一小时，二十四小时就是一天。不管是怎样的进制，能够表达同样的数量。不同的进制之间是可以相互转换的。比如，一年两个月，这种表达是十二进制，转换成十进制表达，就是十四个月。
底层的计算机硬件只识得“0”和“1”这两个数字，因此，它自然而然就采用了二进制，逢二进一。
注意，这里我们说，计算机只识得“0”和“1”，并非计算机本身的能力所限，而是我们人类特意这么设计的。
原因很简单，二进制的表达只需要两个数字——0和1，那么，我们只需要让计算机硬件识别两个不同的状态就可以了。
十进制的表达则需要十个数字——0到9。如果我们想让计算机硬件实现十进制的话，那么计算机硬件就必须能够识别十个状态。这样的实现难度将成几何级数成长。而这样的设计是完全没有必要的。因为，二进制的表达能力与十进制是完全一致的，所有的十进制数字都可以和二进制数字之间*转换。它们只是两种不同的数量表达方式。下面给出十进制数字与二进制数字之间的相互对应。
十进制 二进制
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
为了更好地理解这种转换，我们来看一个更加形象化的例子——八卦图。八卦，顾名思义，总共有8个卦象。如果用二进制来表示，那么，需要最少的数字位数是几呢？从上面的表格可以看出，0到7恰好是八个数字，其中7对应的二级制数字111是3位。再往上一个数字，就是8，对应的二进制数字是1000，就是4位数了。因此，0到7这个八个数字，恰好用完了三位二进制数字的所有容量。
如果用组合原理来表达的话，这个问题可以表述为，现在我们有n个位置，每个位置有0和1两种状态，现在，我们需要表达8个状态。请问n最小是几？
运用组合原理来求解的话，2的3次方恰好就是8，这就是说，n = 3。我们需要3个位置，来表达8个状态。
进制转换和组合原理都是很有趣、很有用的主题。不过，本书是关于计算机原理的书籍，而不是一本数学科普读物。因此，请读者自行查阅和弥补这两方面的知识。这些最基本的数学知识对于程序员，或者非程序员来说，都是非常重要的。
做了上述理论准备之后，我们就可以来看真正的八卦图了。

我们可以看到，八卦图的表现也是一种二进制，最基本的表达只有两种状态：一个连续的长横线，和一根双线段组成的断横线。
我们可以把长横线看做0，把断横线看做1。那么，上面的八卦恰好就是0到7的二进制表达：000,001,010，011,100,101，110,111。可见，中国人很久之前就开始使用二进制了。
我从各方面举出各种例子，希望能够帮助读者更好地、更感性地、更贴近实际地理解二进制。如果这些例子还是不足以说明问题的话，那不是读者的问题，是我的表达和组织的问题。读者可以去查阅一些关于二进制的更好的、更清晰易懂的资料。
我们前面提到的32位操作系统和64位操作系统，其中的“位”的意思就是一个二进制数字。32位就表示一个位数为32的二进制数字，表达的最大数量是2的32次方。64位就表示一个位数为64的二进制数字，表达的最大数量是2的64次方。
“位”这个词，对应的英文单词是“bit”。这个词经常被音译为“比特”。比如，数字信号的传输速率就经常被译成“比特率”。
我个人十分讨厌这种译法。因为这种译法极容易与英文中另一个重要的计算机词汇“Byte”弄混。事实上，也确实有很多人弄混，造成了不必要的困扰和混淆。
英文“Byte”一般意译成“字节”。我喜欢这种翻译方式，因为不会引起同音混淆。
但是，在有些技术资料甚至一些应用软件中，却把“Byte”音译成“比特”，这很容易与“Bit”（位）弄混。
现在，我们这里澄清一下“Bit”（位）和“Byte”（字节）之间的区别。
Bit就是一位二进制数字，要么是0，要么是1，只能表达两个状态。
Byte（字节）则是一个位数为8的二进制数字，能够表达的状态数量达到2的8次方，即256个状态。Byte和Bit之间足足差了2的7次方的倍数，即128倍。
Bit一般用来表述数字信号传输率，而Byte一般用来表示计算机中文件的大小或者存储介质的容量。在网络传输的速度计量中，这两种计量单位经常被混用。尤其是局域网速度与互联网速度相差巨大的情况下。有时候，我甚至都觉得，这种混用是不是故意造成的，其目的是为造成用户的误判。读者在判断网速的时候，要特别注意一下这两个计量单位的区别。
Bit（位）这个单位太小，一般在硬件底层通信开发中用到。在一般的应用软件开发中，我们只需要关心Byte（字节）这个单位就够了。
我们经常用“Byte”（字节）这个单位来表达数据的尺寸（有时候，也叫宽度）。
一个Byte（字节）的位数是8，那么，32位就是4个字节，64位就是8个字节。以前还有16位的操作系统，内存单元就是两个字节。
与内存单元的尺寸规格相对应的，是CPU的“寄存器”工作台的尺寸规格。作为计算机整个体系结构中的核心部件，CPU得到了最多资源的支持。CPU并非只有一个“寄存器”工作台，它有好几种尺寸规格的工作台，有可能是一个字节，两个字节，四个字节，八个字节，等等。有时候，大的寄存器工作台是由两个小的寄存器工作台拼起来的。不管怎么说，每种尺寸规格的工作台都有好几个，以备CPU不时之需。
CPU的所有寄存器加起来，有可能达到几十个之多。这些寄存器根据尺寸规格和功用，分成好几个组。
同内存单元一样，每个寄存器都有自己的地址编号。当然，由于寄存器的个数实在太少，它们的地址编号并不需要以数字的方式来表达，直接给每个寄存器取一个名字就好了。寄存器的名字通常都与其功用及尺寸相关。
比如，AX, AH, AL等，表示不同尺寸规格的加法器。A是英文Add的首字母。其他的寄存器的名称也都代表了各自的功用或者尺寸规格。
寄存器里可以放置什么样的数据呢？答案是，任何数据，只要寄存器够大。
比如，寄存器中可以直接放入一个用于数学计算的数字。这种含义普通的数据在汇编语言中有一个专用名词，叫做“立即数”。
除了“立即数”之外，寄存器中还可以放入一种特殊的数据——地址数据。这类数据是专门用来计算内存地址的。
用来放置“地址数据”的寄存器，是一类特殊的寄存器，叫做“寻址”寄存器。故名思意，这类寄存器的功用，是为了寻找内存地址。这类寄存器里面放置的数据，都是用来计算内存地址的“地址数据”。寻址寄存器可以细分为更小的组，比如，“基址”寄存器，“变址”寄存器等。这些寻址寄存器的用法也很简单，就是把不同寻址寄存器中的地址数据或者地址偏移数据加在一起，就可以得到最终的内存地址。
寄存器这个概念，在汇编语言中大量用到。但是，在我们的日常编程工作中，汇编语言并不是一门广泛应用的编程语言，我们更多地使用高级语言，以便更轻松、更高效地完成编程工作。而高级语言中，并没有寄存器这个概念。因此，本书不打算深入讲解汇编语言语法和寄存器概念。但是，内存地址这个概念，在高级编程语言中，尤其在命令式编程语言汇中，内存地址是一个极其重要的概念。可以这么说，所有的命令式编程语言，全都是基于“内存地址”这个核心概念来编程的。因此，内存地址这个概念怎么强调都不为过，必须大讲特讲。
当然，在一些极力标榜“高级语法特性”、极力隔离硬件底层实现的命令式语言中，你并不会直接看到“内存地址”这个概念。那些语言会用一种极其蹩脚的方式，把“内存地址”这个概念改头换面，换成“变量”（Variable）、“指针”（pointer）、“对象引用”（Object Reference）、“数组下标”（Array Index）、“对象成员”（Object Member）等貌似高级的概念。如果你对这些眼花缭乱的名词术语感到头晕的话，不要着急。这些都是表象，本书会逐渐揭开这些表象下面的共同本质——内存地址。
对于使用高级语言的程序员来说，并不需要直接碰触到寄存器这个概念。为了简化起见，我们可以简单地把寄存器当做内存中的延伸部分。即，我们可以把每个寄存器都理解为一个特殊的内存地址。这样，概念模型上就统一了。
在结束本章之前，我们玩一个寻宝游戏。这个游戏是这样玩的。藏宝人把一个小礼物藏在屋子里面的某个地方，并提供给寻宝人一系列的寻宝线索。寻宝人则根据藏宝人提供的寻宝线索，一步步按图索骥，顺藤摸瓜，最终找到藏宝地点。
寻宝线索通常是一系列小纸条组成的。比如，第一张小纸条上写着，“请打开书桌第一个抽屉。”寻宝人就会按照这个线索去打开书桌第一个抽屉，结果看到里面放着另一个小纸条，上面写着，“请打开梳妆台上的小盒子”。于是，寻宝人就去梳妆台，找到一个小盒子，打开，里面又是一张小纸条，“请去厨房，打开橱柜第三个格子”……就这样，寻宝人根据小纸条写的方位地址，一步步顺藤摸瓜，最终找到藏宝地点。
我们可以看到，在这个藏宝游戏中，线索都藏在某个具体的方位地址中，而且，该方位地址里面的内容，又是另一个方位地址。这个过程，很类似于“内存寻址”的过程。下面，我们就在内存中来模拟这个寻宝游戏。
首先，我们要在内存中定义一个起始地址。我们假设该地址编号是0001。我们可以在脑海中想象一个大书柜，里面全都是小格子，第一个每个小格子都有一个编号。其中一个编号就是0001。我们给可以0001这个地址编号标注的格子起一个名字，叫做“寻宝起点”。为了更加形象，我们可以想象，自己在0001编号的小格子的边框上贴了一个标签，上面写着“寻宝起点”。
然后，我们在“寻宝起点”这个小格子里面放一张纸条，上面写着“请打开书桌第一个抽屉。内存地址是1001”。
于是，我们迅速移动到1001编号的小格子前，一看，果然，那个小格子的边框上已经贴了一个标签，上面写着“书桌第一个抽屉”。我们再看小格子里面，那里也放了一张小纸条，上面写着，“请去厨房，打开橱柜第三个格子。地址编号是2001”。
于是，我们迅速移动到2001编号的小格子前，一看，果然，那个小格子的边框上已经贴了一个标签，上面写着“橱柜第三个格子”。我们再看小格子里面，那里也放了一张小纸条，上面写着，“……”
好吧，游戏到此结束，Game Over，让我们进入下一章。