程序原本(三十二):程序设计的核心思想——数据结构:顺序存储(用有限大的区域来代表一个待运算的数据)

阅读数:46 2019 年 9 月 28 日 18:22

程序原本(三十二):程序设计的核心思想——数据结构:顺序存储(用有限大的区域来代表一个待运算的数据)

冯•诺依曼体系的计算机,是以控制器、运算器和存储器为核心的,分别映射我们此前讨论的计算(范式)、算和数这三个方面。因此,如同我们对“算数”的理解一样1存储器的结构以及它在计算系统中的抽象,也直接限制了计算及其逻辑。对于这个“抽象”,我们简单地说就是:顺序地址存储。

1 即所谓“算”是程序之表,“数”是程序之本。

除了 Bit、Byte、Word、DWord 等与位宽直接相关的、具有数学或物理传输含义的类型——它们显然是顺序表示的值——之外,我们常见的在计算机中用的信息 / 数据有哪几种形式呢?布尔值算一种,它表示开关、正误等判断,是我们执行逻辑的一个基础;数值算一种,作为数学运算的对象,与我们计算系统的本质设定有关;字符(以及字符串)算是一种,因为它是我们程序员或用户可以正常理解的东西。这三类数据,构成了计算系统向(可用的)计算机发展的主要条件2。而这三种数据中,除了布尔值可以由计算系统的最小存储单元(bit)来表示之外,其他两种都必然面临“如何存储”的问题。

2 这里我并不强调它是“必备条件”,因为有些计算机和计算机系统并不是由“人”来使用的,因此与它们交互的数据形式也不相同。关于这一点,应退回到本书“第 1 章 数,以及对数据的性质的思考”中,在与“数据的提出”有关的话题中去讨论。

对于这个问题,“顺序地址存储”的核心思想是:设运算器可以通过一个(数值标识的)地址,从存储中获得一个(有限大小的)区域,则该区域可以表示为一个待运算的数据。以 Intel 系统的个人计算机(PC,Personal Computer)中,x86 芯片(CPU,运算器)为例3

3 我们只假设了一种最简单的情况以便于后续讨论。现实是,需要考虑运算器与存储器之间的总线,以及指令与数据缓存、预取装置等,在整个数据的传输过程中的位宽,决定了这些数值的大小以及存取效率。

  • 芯片通过寄存器来读这个地址的值,因此寄存器可以表示的数值大小,决定了地址值的大小;
  • 同上,因为芯片也使用寄存器存储计算所需数据,因此上述区域(连续可读取的位数)的大小也是由寄存器可以表示的数值大小来决定的。

那么,首先,待运算的数据的大小就被转义成了区域的大小,进而变成了运算器与存储器之间的位宽问题。所以 32 位的机器上一个(能直接参与 CPU 运算的)值的大小,就是 232,如果要理解为“有符号整型数”则是 ±231,因为符号用掉了一个位(bit)。同样,我们要运算浮点数的话,也要把它“挤”在这 32 位中去表示,例如常用的 IEEE 754 浮点数表示法4。再者,我们要表示字符的话,也是通过对 32 位的组合序列做出定义,将它们一一表示为我们的书写字符,例如 ASCII 字符集、GB2312 字符集,以及 UTF8、UTF32 字符集等。

4 这样的表示法显然有非常非常多种可能性,而且也确实存在着好几种在用的方案。

接下来,可能表示的地址,也被转义为上述的位宽问题。因为地址是数值标识的5,所以它表达的是一个连续空间中的位置(可以想象为数轴上有限区间的点)。根据上述的原则,以 32 位的 CPU 为例,该“顺序地址存储”方案:

5 地址标识与寻址问题是一个复杂而一体的问题,并非此处所说的“整型增量”这样简单。例如,在硬盘读写的寻址方面,就有多套完全独立的体系。这些体系与磁头、磁盘片以及高速马达的惯性等都有关系。地址标识与如何提高设备存取的效能,是计算机系统中“存储”相关的焦点问题。而在此处及后文中,我们仅从软件开发视角上讨论该问题的一个子集,并且事实上“顺序地址”也是软件开发中有关存储的一般抽象。

  • 可以找到的最后的数据的位置索引就是 232
  • 可以从该位置(以及其他任意位置上)读取的最大可能值是一个无符号的 32 位整型数(DWORD)6

6 这里涉及表示的地址索引与存取大小之间的约定。实际上 x86 约定的地址是字节序的,因此在最后的这个地址上只有一个 Byte 能被处理,而其他的位置将因为无法编码地址而溢出。

所以跳开我们熟悉的 x86 芯片去做软件开发的时候(例如单片机),我们常常需要问:寻址空间有多大,基本数据单元是多大。如果没有这样的信息,就无法通过某种语言编程去控制它,因为连一个基本的、与计算机交流的环境都搭建不起来。

评论

发布