《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

本节书摘来自华章计算机《计算机系统:核心概念及软硬件实现(原书第4版)》一书中的第3章,第3.6节,作者:[美] J. 斯坦利·沃法德(J. Stanley Warford)著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.6跨层的表示方法

C++是一种HOL6层语言,当程序员在C++中声明变量时,必须指定变量值的类型。而在ISA3层,变量是二进制的。
假设在一个C++程序中声明了
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

并在一台7位计算机上运行这个程序。在ISA3层,int类型的值以补码二进制表示法存储。如果i和j的值分别是8和-2,程序包含语句
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

那么在ISA3层对这个表达式求值是这样的:
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

在ISA3层,char类型的值以ASCII或其他字符编码的形式存储。如果ch1的值是-,ch2的值是2,那么这些值在ISA3层被存储为
010 1101011 0010
这个位模式当然和整数j的值不一样,j的值是111 1110。
在C++中,在HOL6层,每个字符在数轴上都有一个序数值位置。在ISA3层,机器层,这个序数值就是作为无符号整数来解释的字符编码的二进制值。因为不同的计算机可以选择使用不同的二进制符号编码,所以它们的序数值可能会不同。
例3.46根据ASCII表,D用100 0100代表,而100 0100(bin)=68(dec)。在一台使用ASCII码的计算机上,D的序数值就是68。 □
例3.47要在你的计算机上振铃,可以执行如下产生振铃的语句
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

在HOL6层,高级语言的一个典型语句是
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

字符串常量Tom被传送到输出设备。这条语句在ISA3层并不这么简单。在机器语言中,你没法“写出Tom”,而是必须把位序列
101 0100
110 1111
110 1101
发送到输出设备。
为什么我们要处理位而不是我们习惯的英文字母和十进制数字呢?因为计算机是电子的。最便宜最可靠的制造计算机电子部件的方法是把它们做成二进制的,因此我们只能用二进制机器来处理信息。ISA3层的问题是我们要处理的信息是十进制数字和英文字母的形式,而机器语言是以1和0的形式表示信息,因此需要进行编码,例如补码二进制表示法和ASCII。
要处理的信息形式和表示信息的语言之间的不匹配并不只是在ISA3层有,这也是所有较高层次要考虑的重要问题。
通过旅行推销员问题可以说明HOL6层的这种情况。一个推销员负责8个不同城市的业务,他乘坐航空公司航班穿梭在这些城市之间,这8个城市之间有14条航空线路。要处理的信息形式是航空公司提供的地图,地图展示了连接推销员负责范围内城市之间的所有航线。地图如图3-34所示,它也标出了每条航线航班的价格。

《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

推销员必须从洛杉矶出发,访问他职责范围内的每个城市,然后返回洛杉矶,他当然想把他的行程计划为花费最少的。
确定最佳行程表听起来像是计算机的完美工作。推销员把地图给程序员,程序员知道怎样用HOL6层语言(例如,C++)来说话。
但是现在程序员要面对这个计算机科学的根本问题。地图和HOL6层语言这两种数据形式不匹配,C++不认识地图,它只能认识诸如实数、整数和数组之类的东西。
程序员必须决定怎样用C++能够处理的形式来表达数据。例如,他可以用如图3-35所示的二维实数数组来表示地图。在这个方案中,顶行和左列的整数代表推销员所负责范围内的城市,表中每个实数表示从行索引代表的城市到列索引代表的城市的美元价格。如果这个二维数组叫cost,那么
cost 0 = 65
表示从城市0(洛杉矶)飞到城市5(萨克拉门托)的费用是65美元。
cost 1 = le30
表示城市1(圣地亚哥)和城市7(拉斯维加斯)之间没有航线。

《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

原始数据转换为C++可以处理的表示后,HOL6层程序员可以继续他的算法设计,并最终解决这个问题。但是第一步必然用这种语言能够处理的形式来表示这些数据。
ISA3层的问题是怎样用机器语言来表示数字和字母,HOL6层的问题是怎样用C++的整数、实数和数组来表示一个有城市、线路和航班费用的地图。在这两个层次上,都有最根本的数据表示问题。
3.6.1另一种表示
信息表示问题具有挑战性的一面是通常会有多种不同的方法来表示数据。选择哪种表示取决于要怎样处理数据。
这里有一个在ISA3层表示正整数的另一种方法。尽管本章用无符号二进制来表示正数,但这并不是唯一的可能,正整数也能以二进制编码的十进制数(Binary Coded Decimal,BCD)形式来存储。
在BCD中,每个十进制的位刚好需要4位。十进制数142会以二进制0001 0100 0010的形式存储。因为只有10个十进制数字,因此4 位的BCD组是0000、0001、0010、0011、0100、0101、0110、0111、1000和1001,从1010到1111的位模式未被使用。
如果数据更多的是在计算机内进行算术运算而不是I/O操作,通常会选择无符号二进制;当数据是金融业务并有很多I/O操作时,通常选用BCD。BCD更容易转换为十进制用于打印报表,然而BCD算术运算电路通常比无符号二进制算术运算电路慢。
推销员问题中也有类似的选择。例如,航空公司没有在所有可能的城市之间开通航线,尤其是小城市。要从棕榈泉到里诺,必须首先从棕榈泉飞到洛杉矶,然后从洛杉矶再到里诺。在图3-35中,尽管只有14条航线,但是cost有64个元素,大多数元素是le30,有28个元素不是le30,而只有14个是真正必需的。
例如,这两项
cost0 = 65
cost5 = 65
代表洛杉矶和萨克拉门托之间只有一条航线,假设两个方向的航班费用是相等的,那么实际上只需要一个项,另一项是多余的。

《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法


因此程序员可以决定采用图3-36所示的方式来表示地图。在HOL6层语言中,线路可以实现为一个数组route,数组中的每个记录包含3个字段:from、to和cost,那么
route[4].from = 0
route[4].to = 5
route[4].cost = 65
表示洛杉矶和萨克拉门托之间的飞行花费是65美元。
用这种方式表示地图,不会为不存在的航线浪费存储空间。如果城市9和城市11之间没有航线,那么就不用存储它们。
在HOL6层,地图还有其他表示方式, 与在ISA3层无符号整数有其他表示方式一样。在任何层,都可能会有多种表示数据的方法,任何一种方法都能得到正确的结果。
确定哪一种表示最好通常是很困难的。实际上,通常要定义什么是“最好的”都很困难。如果你的计算机有大内存,那对你来说,最好的表示可能是一种有点儿浪费存储的方式,因为有足够的空间。另一方面,如果内存不足,最好的表示就是少用点儿存储空间,尽管用这种方式处理数据的算法会很慢。这种空间/时间的折中适用于计算机系统的各个抽象层次。与所有创造性努力会遇到的一样,这种选择并不总是很明确的。
3.6.2模型
模型是某些物理系统的简化表示。每个科学领域的工作人员,包括计算机科学,构建模型并研究它们的性质,比如天文学家构建和研究的一些太阳系模型。
大约公元前350年,希腊的亚里士多德提出了一个模型,在这个模型中,地球位于宇宙的中心,环绕地球的是55个天球。太阳、月亮、行星和恒星每个都在一个天球上环绕天空。
这个模型和现实相符的程度如何呢?它能成功地解释天空的形状像球的顶部一样,也能解释行星大概的运行。千百年来,亚里士多德的模型被认为是准确的。
1543年,波兰天文学家哥白尼出版了《De Revolutionibus》(天体运行论),在这本书中,他建立了以太阳为中心的太阳系模型,行星围绕太阳做圆周运转。这个模型比地心模型更接近实体系统。
16世纪后期,丹麦天文学家Tycho Brahe(第谷·布拉赫)进行了一系列精确的天文观察,这些观察与哥白尼的模型有一定的差异。然后,1609年,Johannes Kepler(约翰内斯·开普勒)设想了一个模型,在这个模型中,地球和所有行星围绕太阳运行,但轨道不是圆形而是扁平的圆形(即椭圆形)。这个模型成功地详细解释了Tycho Brahe观察到的行星的复杂运行。
每个模型都是太阳系的一个简化表示。没有一个模型能够完全精确地描述真实的物理世界。现在我们知道,根据爱因斯坦的相对论,甚至Kepler的模型也是一个近似模型。没有模型是完美的,每个模型都是现实世界的一个近似。
当信息在计算机存储器中表示时,这个表示也仅仅是一个模型。如同太阳系的每个模型描述真实系统的某个方面比其他方面更加精确一样,一种表示方法描述信息的某个性质比其他性质更精确。
例如,正整数的一个性质是有无穷大的数。不管你写一个多大的整数,别人总能写出更大的数。计算机的无符号二进制表示不能很精确地描述这个性质,因为内存中存储整数的空间大小是有限制的。
我们知道=1.4142136...是无限不循环的。存储实数的表示方法是一个模型,对于像2的平方根这样的数,它只能存储近似数,它不能准确地表示2的平方根。
在任何层次解决问题都涉及构建一个不完美的模型并研究它的性质。HOL6层的推销员问题是确定最少花费的行程,用航线地图把他的花费模型化。这个模型并不包括一些因素,比如一些城市的某些酒店可能在周末比工作日价格更贵。如果采用一个更接近现实花费的模型可能会改变最佳行程。
前面的例子说明计算机在任何时候解决问题,由于模型的限制,总会涉及近似。近似可能由于表示方法的限制而导致产生的,例如在存储2的平方根值时实数的精度是有限的,或者由于对问题的简化导致产生的,例如没有把不同的酒店价格计算在内。
计算机能模型化各种实体系统—库存清单、国民经济、账务系统和生物种群系统,这里仅举几个例子。在计算机科学中,要模型化的通常是计算机本身。
实际上,计算机只有的实体部分是在LG1层。从本质上说,计算机只是一个复杂的、有组织的大量电路和电子信号。在ISA3层,高电平信号被模型化为1,低电平信号被模型化为0。ISA3层的程序员在使用模型时,不需要知道电子电路和信号。记住在ISA3层,单词Tom用1和0表示为
101 0100
110 1111
110 1101
HOL6层的程序员在使用模型时,不需要知道位。实际上,在任何层,对计算机编程只需有那个层的计算机模型知识即可。
HOL6层的程序员可以把计算机模型化为C++机器,这个模型接受C++程序并用它来处理数据。当程序员指示机器
《计算机系统:核心概念及软硬件实现(原书第4版)》——3.6跨层的表示方法

他不需要考虑计算机在ISA3层怎样被模型化为二进制机器。类似地,当ISA3层程序员写位序列时,他无须考虑在LG1层计算机怎样被模型化为电路的组合。
这种逐级为计算机系统建模的方法并不是计算机科学独有的。考虑一个有6个分公司分布全国的大公司,公司总裁的模型是6个分公司,每个分公司有一个副总裁向他汇报,他通过看每个分公司的业绩来看全公司的业绩。当要求产品部门增加利润时,他无须考虑产品部门副总裁的模型。
当副总裁给产品部门的每个小部门经理下达命令时,他无须考虑小部门经理的模型。让总裁亲自处理小部门层的事务几乎是不可能的,整个公司有太多小部门层的细节,不可能由一个人去管理。
App7层的计算机用户就像总裁,他给HOL6层的程序员写的程序发出诸如“计算所有大二学生的平均分”的指令,他无须考虑HOL6层模型怎样发布指令。最终,这条App7层指令逐层向下传送到LG1层。最终结果是App7层的用户能够用非常简化的计算机模型控制大量的电子电路和信号。

上一篇:配置sendmail转发邮件


下一篇:《钉钉应用开发者速成手册》之“API实战——搭建审批工作流”