计算机系统概论第十章.doc

第十章 最后栈我们已经结束了对LC-3指令集结构的处理。在向上进入十一章的又一个抽象层次到达C语言程序设计之前，我们应该花一些时间在一个特别重要的基础话题上：栈。首先，我们将详细的解释其基本结构，然后，我们将描述栈的3个作用：（1）我们在8.5节承诺要介绍的中断驱动的I/O机制的剩余部分；（2）实现临时存储中间结果的算术运算的一个机制是栈，而非通用寄存器；（3）二进制补码整数与ASCII码字符串之间的转换算法。这3个例子只是冰山一角。在计算机科学与工程中，你会发现栈在你所做的大多数工作中都非常有用。我们猜想在本书成为你的一个愉快的回忆之后，你会发现栈的新作用。我们将通过一个计算器的设计，一个使用了在本章讨论的许多主题的复杂应用，来结束我们在指令集结构层次上的介绍。10.1 栈：基本结构10.1.1 栈 一种抽象数据类型 贯穿在你的将来对计算机的使用（或设计）之中，你将会遇到一种名为栈的存储结构。栈可以通过许多不同的方式来实现，我们将立刻开始学习。但是首先，知道栈的概念与其实现毫无关系是很重要的。栈的概念是说明它如何被访问。也就是说，栈的定义是你最后存入栈的东西首先被取出。那就是栈与别的东西的不同之处。简单地说：后进先出 (Last In, First Out)，或者LIFO。 在计算机程序设计语言的术语中，栈是抽象数据类型的一个例子。也就是说，一种抽象数据类型是一类存储机制，这种机制是由对它执行的操作所定义的，而不是实现它的方式。在第19章，我们将使用链表用C语言写程序，链表是另一种抽象数据类型的例子。10.1.2 两个实现栈的例子 汽车扶手中的硬币盒就是栈的一个例子。你取出第一个25美分付高速公路通行税，而这25美分就是你刚刚最后放到25美分的栈中的。当你加入一个25美分的时候，先前的一个就会被压在下面。 图10.1显示了硬币盒的行为。开始时，如图10.1a里面是空的。第一次高速公路通行税是75美分，你给了收费员一美元，她找了你25美分，一个1995年的硬币，你把它插入硬币盒。此时的硬币盒如图10.1b所示。 对于向栈插入元素和从栈移出元素有专门的术语。当我们把一个元素插入栈的时候，我们称之为压栈（push），当我们移出一个元素时，我们称之为出栈（pop）。 第二次高速公路通行税是4.25美元。你给了收费员5美元，她找了你75美分。你把它们放进了硬币盒中。首先放进去的是1982年的，然后是1998年的，最后是1996年的。现在，硬币盒如图10.1c所示。第三次通行税是50美分，你移出（出栈）硬币盒顶上的两个25美分，先拿1996年的，然后再拿1998年的，那么，硬币盒如图10.1d所示。 硬币盒是一个栈的例子。因为它正好符合后进先出的要求。每一次放一个25美分进去，总是从顶部插入。每次取一个25美分出来，也是从顶部去取。你最后放进去的硬币是你首先要拿走的，因此，它是一个栈。 另一个栈的实现，有时被称为硬件栈，如图10.2所示。它的行为类似于我们刚刚描述的硬币盒。它由一定数量的寄存器组成，每个寄存器可以存储一个元素。图10.2中的例子含有5个寄存器。当每个元素被存入或取出时，已经在栈里的元素就会移动。在图10.2a中，栈的初始状态显示为空。访问总是经由第一个元素，它被标记为栈顶（TOP）。如果数值18被压入栈，我们就有了图10.2b。如果3个数值31，5，12被压入栈（按顺序），我们就有图10.2c。最后，如果有2个元素从栈中取出，我们就有图10.2d。图10.2的栈的显著特征，和往硬币盒里放硬币一样，就是当每一个值被存入或取出时，在栈中的所有的值都要移动。10.1.3 在存储器中的实现现在，在计算机中栈的最普遍的实现被显示于图10.3中。这个栈由一组存储单元和被称为“栈指针”的机制组成，栈指针指示了这个栈的栈顶。也就是说，包含最后压入的元素的存储单元。每个压入的值被存储在一个存储单元中。在这种情况下，已经存储在栈中的数据不会进行物理移动。在如图10.3所示的例子中，这个栈由5个单元组成，x3FFF到x3FFB。R6是栈指针。图10.3a显示了一个原来为空的栈。图10.3b显示压入18这个值之后的栈，图10.3c显示依次压入31，5和12这几个值之后的栈。图10.3d显示从栈顶取出2个元素之后的栈。注意到这2个顶部的元素（数值5和12）仍然存在于存储单元x3FFD和x3FFC中。然而，正如我们即将看到的，只要访问存储器被栈机制所控制，5和12这些值就不能从存储器中被访问。Push在图10.3a中，R6包含x4000，即栈第一个单元（BASE）的前面一个地址。这说明这个栈初始为空。图10.3的栈的BASE地址是x3FFF。我们先将数值18压入栈，结果如图10.3b所示。栈指针提供最后被压入的那个值所在的地址，在本例中，是存储18的x3FFF。注意单元x3FFE，x2FFD，x3FFC和x3FFB的内容没有显示。正如即将看到的，这些的单元里的内容是不相关的，因为它们不能被访问，假设x3FFF到x3FFB只能作为栈被访问的话。当我们将一个值压入栈时，栈指针减1，这个数值被存储。这个2条指令的序列将保存在 R0中的数值压入栈。PUSHADDR6,R6,# -1 STRR0,R6,#0 因此，要使栈成为如图10.3b所示，R0必须在这个2条指令的序列被执行之前就存储了18这个数值。31、5、12这3个数值是先后被加载入R0，然后执行这2条指令，这样就被压入栈。在图10.3c中，R6（栈指针）包含x3FFC，这说明12是最后被压入的数值。Pop为了从栈中取出一个数值，这个数值被读取，栈指针加1。下面这个2条指令的序列取出存于栈顶的数值并把它加载入R0中。POPLDRR0,R6,#0ADDR6,R6,#1 如果栈如图10.3c所示，并且我们再执行2次这组指令，我们将会从栈中取出 2个值。在本例中，我们将会先取出12，然后是5。假设取这两个的目的是为了使用这两个值，我们当然将会在取第2个值之前把12从R0移到某个单元中。图10.3d表示经过那一系列操作之后的栈。R6包含着x3FFE，这表示现在31在栈的顶部。注意值12和5仍然分别保存在单元x3FFD和x3FFC中。然而，因为栈要求我们通过执行PUSH指令序列来实现压栈，通过执行POP指令序列来实现出栈，如果违反规则，我们就不能访问这2个值。对于这些规则有个很好的名字叫做“栈协议”。下溢如果我们试图从栈里取出顶上的三个元素会发生什么呢？因为只有两个值留在栈里，我们会遇到一个问题。试着取出以前没有被压入的项目会导致一个下溢（underflow）的情况。在我们的例子中，我们能通过将栈指针与x4000对比来检测下溢，如果在栈顶没有留下任何元素的话，R6的内容就是x4000。如果UNDERFLOW是处理下溢情况的程序的标记，最后得到的POP指令序列将是：POPLDR1, EMPTY ADDR2,R6,R1; 将栈指针与x4000作比较BRzUNDERFLOW LDRR0,R6,#0ADDR6,R6,#1RETEMPTY.FILLxC000；EMPTY为-x4000如果POP失败，通常是让POP程序将下溢信息保存在一个寄存器里，再返回调用它的程序；而不是立即让POP程序跳到UNDERFLOW程序。为了实现这一点，一个常用的习惯是使用一个寄存器提供成功或失败的信息。图10.4显示了如何使用R5报告这种成功和失败的信息，实现POP程序的扩展。当从POP程序返回时，调用程序会检测R5来判断POP是（R5=0）否(R5=1)成功完成。注意，既然POP程序用R5来报告成功或失败，在POP程序被调用之前保存在R5里的任何东西都会丢失。这样，在JSR指令执行之前存储R5里的内容便是调用程序的工作了。回忆一下9.1.7节，这是一个调用者保存情况的例子。最后得到的POP程序如下所示。注意因为在RET指令之前的一条指令设置或清空了条件码，调用程序可以通过简单的检测条件码Z来判断POP是不是成功的完成了。POPLDR1, EMPTY ADDR2, R6 , R1BRzFailureLDRR0 ,R6 ,#0ADDR6 ,R6, # 1ANDR5 ,R5 ,# 0RETFailureANDR5, R5 ,# 0ADDR5 ,R5 ,# 1RETEMPTY.FILLxC000；EMPTY为-x4000上溢当我们把栈中可用的空间用完了，但我们仍试图将一个数值压入栈中，会发生什么呢？在栈中没有空间的时候，我们不能存储值，这就是上溢的情况。我们可以通过对比栈指针(在图 10.3 的例子中)和x3FFB，如果这两个值相等，栈中就没有空间来存储更多的值。如果OVERFLOW是一个处理上溢情况的程序的标记，我们得到最后的PUSH指令序列将是：PUSHLDR1,MAXADDR2,R6,R1BRzOVERFLOW ADDR6,R6,# -1 STRR0,R6,#0RETMAX.FILLxC005；MAX= -3FFBPOP 程序将成功或失败的信息返回调用程序，而不是立即跳转到UNDERFLOW程序，这是很有用的，PUSH程序以相同的方式处理也是非常有用的。我们在PUSH程序中增加存储0（表示成功）或1（表示失败）到R5中的指令，0还是1取决于我们压栈是否成功完成。当从PUSH程序中返回后，调用程序会检查R5来判断PUSH是成功（R5=0），还是失败（R5=1）。我们再一次的注意到，既然PUSH程序使用R5报告成功或失败，我们又有一个调用者保存的情况的例子。也就是说，因为R5中的在PUSH程序被调用之前所保存的一切信息都丢失了，那么调用程序必须在JSR指令执行之前将R5中的内容保存起来。同样，再一次的注意到既然在RET指令之前的一条指令设置或清空条件码，调用程序通过简单的检查Z 或P 来判断PUSH是否成功完成。PUSH程序如下：PUSHLDR1,MAXADDR2,R6,R1BRzFailureADDR6,R6,# -1STRR0,R6,#0ANDR5,R5,# 0RETFailureANDR5, R5 ,# 0ADDR5,R5,# 1RETMAX.FILLxC005；MAX= -3FFB10.1.4 完整的情况POP和PUSH程序允许我们使用存储单元x3FFF到x3FFB作为一个五个元素的栈。如果我们想把一个值压到这个栈里，我们只需将这个值加载到R0里，再执行JSR PUSH便可。为了从这个栈里取出一个值放到R0里，只要执行JSR POP。如果我们想改变单元或栈的大小，只要相应的调整BASE和MAX就行了。在离开这个话题之前，我们必须认真的弄清楚一个细节问题。子程序PUSH和POP使用了R1，R2和R5。如果我们想从PUSH或POP程序返回之后用到这些寄存器里存储的值，最好在使用之前先保存它们。如果是R1和R2，在PUSH和POP程序里在使用它们之前保存，并且在返回到调用程序前恢复是最简单的。这样，调用程序甚至不需要知道这些寄存器在PUSH和POP程序里被使用了。这是9.1.7节里描述的一种被调用者保存的情况的例子。如果是R5的话，由于调用程序必须知道R5里报告的是成功还是失败，所以情况就不同了。因此，如果调用程序想再次使用存储在R5中的值，就需要在运行JSR指令前保存R5里的内容。这是一种调用者保存的情况的例子。最后的PUSH和POP操作的代码如图10.5所示。10.2 中断驱动的I/O 第2部分回忆我们在8.1.4节讨论的中断驱动的I/O是除了轮询之外的另一种选择。正如你所知道的那样，使用轮询，处理器将时间浪费在一次又一次执行LDI和BR指令上，直到就绪位为1。使用中断驱动的I/O，那些测试和分支转移就不再继续。相反的，处理器将时间用于做有用的工作上，它执行一些程序，直到它被通知某个I/O设备需要注意。你还记得对于中断驱动的I/O有两个部分：1、当某个I/O设备有输入或准备好接受输出时，允许它能够中断处理器的允许机制；2、管理I/O数据传送的处理。在8.5节，我们显示了中断处理器的允许机制，也就是说，发出INT信号。我们显示了就绪位如何结合中断允许位，提供一个中断请求信号。我们还显示了如果这个中断请求信号比当前执行的进程的优先级更高，INT信号就被发出。我们看到（图8.8），使用这种机制，处理器不会浪费时间进行轮询。在8.5节中，我们不能研究管理I/O数据传送的处理，因为它需要使用栈，你还不熟悉栈。现在你知道了栈，所以我们就可以完成这个解释了。实际上，管理I/O数据传送经过3个阶段，如图8.6所示：1、发起中断；2、服务该中断；3、从中断返回。我们将按顺序讨论这3个阶段。10.2.1 发起和服务中断回忆8.5节（图8.8），因为某个拥有比当前运行的程序更高的优先级的I/O设备造成一个INT信号的产生，一个中断被发起。对处理器来说，每次完成一个指令周期，就测试INT信号是否出现。如果测试为否，工作照常继续，当前运行的程序的下一条指令被取出来。如果测试为真，就不去取下一条指令。相反的，为了中断正在运行的程序，去执行处理某个请求了更高优先级服务的I/O设备需求的中断服务程序，要做一些准备。有两步必须被实施：（1）足够的正在运行的程序状态必须被保存，以便我们稍后能够从离开的地方继续；（2）足够的中断服务程序状态必须被加载，以便我们能够开始为中断请求服务。程序状态程序状态是程序影响的所有资源所包含的内容的瞬态图。它包括作为程序一部分的存储单元的内容，和所有通用寄存器的内容。它还包括两个非常重要的寄存器，PC和PSR。PC是你非常熟悉的，它包含了下一条要执行的指令的地址。这里显示的PSR是处理器状态寄存器。它包含了关于正在运行的程序的几条重要的信息。PSR15表示正在运行的程序是处于特权（管理员）模式还是非特权（用户）模式。在特权模式下，程序访问了对用户程序不可见的重要资源。我们马上会看到为什么这点对于处理中断很重要。PSR10:8说明优先级（PL）或执行的程序的紧急程度。正如之前已经提到过的，有8个优先级，PL0（最低）到PL7（最高）。最后，PSR2:0被用来存储条件码。PSR2是N位，PSR1是Z位，PSR0是P位。保存被中断的程序状态发起中断的第一步是保存足够的正在运行的程序状态，以便当I/O设备请求被满足之后，它能够在离开的地方继续。在LC-3的情况下，那就意味着，保存PC和PSR。因为PC知道当被中断的程序重新执行时，应该被执行的下一条指令是哪一个，所以必须被保存。因为当程序重新执行后，条件码（N、Z和P标志）可能会被接下来的条件分支指令所需要，因此也必须被保存。因为被中断的程序的优先级说明了被中断的程序对于其他程序的紧急程度，所以必须被保存。当被中断的程序继续执行时，知道哪些优先级程序可以再次中断它，哪些不能中断它，是很重要的。最后，因为程序的特权级别包含了被中断的程序能够访问哪些处理器资源，不能访问哪些处理器资源，所以必须被保存。既然我们假设服务程序在使用任何通用寄存器之前，都会保存其内容，并在返回被中断的程序之前进行恢复，就不必保存通用寄存器的内容了。LC-3将这些状态信息保存在一个特殊的栈中，被称作管理员栈，它只能被以特权模式执行的程序所使用。一段存储器被指派用做该目的。此栈与用户栈不同，用户栈只能被用户程序访问。程序访问这两个栈都是使用R6作为栈指针。当访问管理员栈时，R6是管理员栈指针。当访问用户栈时，R6是用户栈指针。两个内部的寄存器，Saved.SSP和Saved.USP，被用来保存未使用的栈指针。当特权模式从用户改变到管理员时，R6的内容被保存在Saved.USP中，在处理开始之前，R6被加载为Saved.SSP的内容。也就是说，在中断服务程序开始之前，R6被加载为管理员栈指针的内容。然后被中断的程序的PC和PSR被压入管理员栈，当服务程序执行时，它们在栈中保持不变。加载中断服务程序状态一旦被中断的程序状态被安全的保存在管理员栈中，第2步就是加载中断服务程序的PC和PSR。中断服务程序类似于第9章讨论的自陷服务程序。它们是存储在存储器的一些预先安排的单元中的程序片断。它们为中断请求服务。大多数处理器使用中断向量机制。这个概念与包含在TRAP指令中的TRAP向量类似。在中断的情况下，8位的向量被请求处理器中断的设备所提供。也就是说，I/O设备向处理器传递一个8位的中断向量，以及中断请求信号及其优先级。对应于最高优先中断请求的中断向量被提供给处理器。它被指定为INTV。如果中断发生，处理器扩展这个8位的中断向量（INTV），形成一个16位的地址，它是中断向量表的一条记录。回忆第9章，TRAP向量表由单元x0000到x00FF组成，每一个包含一个TRAP服务程序的起始地址。中断向量表由存储单元x0100到x01FF组成，每一个包含一个中断服务程序的起始地址。处理器将通过扩展中断向量INTV形成的地址中的内容，加载到PC中。PSR被加载如下：因为还没有执行服务程序中的指令，PSR2:0被初始化为0。由于中断服务程序运行在特权模式，PSR15被设为0。PSR10:8被设为请求中断的优先级。这就完成了发起阶段，中断服务程序准备进行。服务该中断由于PC包含了中断服务程序的起始地址，服务程序将会执行，I/O设备的请求将被服务。例如，每当坐在LC-3键盘前的人按下一个键时，键盘就可以中断处理器。键盘中断向量将标明调用的处理程序。处理程序然后将数据寄存器的内容复制到存储器中某个预先设定的单元中。10.2.2 从中断返回每个中断服务程序的最后一条指令都是RTI，即从中断返回。当处理器最后访问RTI指令时，I/O设备的所有请求都已经被处理了。RTI指令（操作码=1000）的执行仅包含从管理员栈（PSR和PC一直平静的待在那里）取出PSR和PC，并将它们恢复到处理器中的正确的地方。现在，条件码被恢复为程序被中断时的值，以防它们被程序中接下来的BR指令所需要。PSR15和PSR10:8现在反映了要继续的程序的特权级别和优先级。类似的，PC被恢复为假设程序没有被中断的下一条执行的指令的地址。当所有这些事情都与它们在中断发生前一样时，程序就可以继续，好像什么事也没发生过。10.2.3 一个例子我们通过一个例子完成中断驱动的I/O的讨论。假设程序A在执行，这时比A的PL更高的I/O设备B请求服务。在I/O设备B的服务程序执行的过程中，一个更紧急的设备C请求了服务。图10.6显示了必须发生的执行流程。程序A由单元x3000到x3010中的指令组成，在中间x3006处，执行ADD指令，这时设备B发出中断请求信号和相应的中断向量xF1，结果INT信号被发出。注意设备B的中断服务程序被存储于单元x6200到x6210处，x6210包含RTI指令。注意B的服务程序在中间x6202处执行AND指令时，设备C发出中断请求信号和相应的中断向量xF2。由于设备C的请求比设备B的优先级更高，INT信号被再次发出。注意设备C的中断服务程序被存储于单元x6300到x6315处，x6315包含RTI指令。让我们检查一个处理器的执行顺序。图10.7显示了在这个例子的执行过程中管理员栈和PC包含的内容的瞬态图。处理器执行如下：图10.7a显示了程序A取x3006中的指令之前的管理员栈和PC。注意栈指针被显示为Saved.SSP，而非R6。因为中断尚未发生，R6指向用户栈的当前内容。在x3006的指令执行结束时，INT信号（由设备B的中断造成）被检测到。由于程序A的状态必须被保存在管理员栈中，第一步就是开始使用管理员栈。这一点通过将R6保存在Saved.USP寄存器，将Saved.SSP寄存器的内容加载到R6来实现。PC中的地址x3007，即程序A中将要被执行的下一条指令地址，被压入栈。程序A的PSR，包含了由ADD指令产生的条件码的值，被压入栈。设备B的中断向量被扩展为16位的x01F1，x01F1的内容（x6200）被加载到PC中。图10.7b显示了这时的栈和PC。设备B的服务程序一直执行，直到在x6202中的指令执行结束时检测到一个优先级更高的中断。地址x6203被压入栈，B的服务程序的PSR，包含了AND指令产生的条件码，也被压入。设备C的中断向量被扩展为16位（x01F2），x01F2的内容（x6300）被加载到PC中。图10.7c显示了这时的管理员栈和PC。设备C的中断服务程序一直执行到完成，以x6315中的RTI指令结束。管理员栈被取两次数据，恢复设备B的服务程序的PSR，包括x6202的AND指令产生的条件码，并且恢复PC为x6203。图10.7d显示了这时的栈和PC。设备B的中断服务程序从x6203继续执行，直到完成，以x6210中的RTI指令结束。管理员栈被取两次数据，恢复程序A的PSR，包括x3006的ADD指令产生的条件码，并且恢复PC为x3007。最后，由于程序A在用户模式，R6的内容被存储于Saved.SSP中，而R6被加载为Saved.USP中的内容。图10.7e显示了这时的管理员栈和PC。程序A继续执行x3007中的指令。10.3 使用栈执行算术运算10.3.1 栈作为临时存储有的计算机在进行计算时用栈代替通用寄存器来存储一些临时值。回忆加法指令ADD R0，R1，R2从R1，R2里取源操作数，并把加法的结果存到R0里。我们把LC-3称做三地址机器，因为它所有的三个地址（两个源地址和一个目标地址）都是被明确标识的。有些计算机用栈来存储源操作数和目标操作数，没有一个地址被明确标识。指令就只是简单的ADD我们把这样的计算机称作栈机器，或零地址机器。硬件知道源操作数就是栈最顶上的两个元素，这两个会被取出并提供给ALU，然后结果将被压入栈里。 在栈机器上执行加法，硬件需要执行两次出栈操作，一次加法，和一次压栈。两次出栈会从栈中移走两个源操作数，加法计算出它们的和，压栈会把结果存回到栈中。注意出栈、压栈，和加法不是计算机ISA的一部分，因此它对程序员是不可用的。它们是硬件用来做实际的出栈、压栈，和加法的控制信号。这些控制信号是微结构的一部分，类似于我们在第4章和第5章讨论的加载允许信号和多路选择信号，正如LC-3指令LD和ST中的控制信号PCMUX和LD.MDR的情况一样。程序员简单的指示计算机做ADD，微结构做余下的事。有时（正如我们在本章的最后一个例子会看到的），用栈处理运算是很有用的。中间数值被保存在栈中而不是在通用寄存器中，诸如LC-3的R0到R7。大多数通用微处理器，包括LC-3，使用通用寄存器。大多数计算器使用栈。10.3.2 一个例子例如，假设我们想计算（A+B）（C+D），A包含25，B包含17，C包含3，D包含2，结果存储在E中。如果LC-3有乘法（我们或许称之为MUL），我们可以使用下面的程序：LDR0, ALDR1, BADDR0,R0,R1LDR2, CLDR3, DADDR2,R2,R3MULR0,R0,R2STR0, E使用计算器，我们可以执行下面的8个操作：(1)PUSH25(2)PUSH17(3)ADD(4)PUSH3(5)PUSH2(6)ADD(7)MULTIPLY(8)POPE被取出的最后的结果就是计算结果，即210。图10.8显示了这8个操作的每一次操作之后的栈的瞬态图。在10.5节，我们写了一个程序，让LC-3（有键盘和显示器）像计算器一样工作。我们说当LC-3执行该程序时模拟了计算器。但是首先，让我们检查一下我们需要用来执行不同的算术运算的子程序。10.3.3 OpAdd, OpMult和OpNeg我们在10.5节模拟的计算器具有输入数值、加法、减法、乘法和显示结果的能力。为了做加法、减法和乘法，我们需要3个子程序：1、OpAdd，取出栈中的两个值，做加法，然后再将结果压入栈中。2、OpMult，从栈里取出两个数，做乘法，并把结果放回栈里。3、OpNeg，把栈顶的值取出，转化为补码表示法的负数，并把结果放回栈里。 OpAdd算法 图10.9显示了OpAdd算法流程图。基本来说，这一算法试图从栈里取两个数，如果成功的话，做加法。如果结果在可接受数值范围内（即-999到999间的整数），则结果被压入栈中。 有两件事可能会阻碍加法运算的成功完成：在栈中提供的源操作数少于2个，或者结果超出范围。在每种情况下，栈都将回到OpAdd算法开始前的状态，用R5中的1表示失败，并且控制返回调用程序。如果第一次出栈操作不成功，因为POP程序让栈保持原样，栈未被改变，如果第二次出栈操作返回失败的报告，栈指针减1，即把第一次在栈顶取出的数放回栈中。如果结果超出了可接受的数值范围，栈指针减2，把两个从栈顶取出的值都返还给栈。算法流程图栈顶取出的值都返还给堆回失败的报告，堆果放回堆OpAdd算法如图10.10所示。注意OpAdd算法调用了RangeCheck算法。这是一个简单的测试，看看计算的结果能否成功的存储到单个栈单元中。就我们的目的而言，假设我们把值的范围限制在-999到999的整数之间。在10.5节中，当我们设计自己制作的计算器时这个将会派上用场。RangeCheck算法的流程图如10.11所示。实现这种算法的LC-3程序在图10.12中。OpMult 算法图10.13显示了OpMult算法的流程图。图10.14 显示了实现这个算法的LC-3的程序。类似于OpAdd算法，OpMult算法试图从栈中取出两个值，如果成功，把它们相乘。既然LC-3没有乘法指令，乘法就是按照我们过去做过的一样是一组加法。图10.14中17到19行包含了实际做乘法的关键。如果这个结果在可接受数值范围之内，那么这个结果就要被压入栈中。如果两次出栈操作的第二次不能成功，栈指针就要减1，这样做的效果是返回第一个从栈顶取出的值。如果结果超出可接受的数值范围，就像之前一样被R5为1标识出来，那么栈指针递减2，两个值都要被返回到栈顶部。OpNeg 算法我们已经提供了对两个栈顶元素进行加法和乘法的算法。为了将栈顶的两个元素相减，如果我们先将栈顶元素替换为它的负值，我们就可以用OpAdd算法。也就是说，如果栈顶的数是A，栈的第二个元素是B，我们想取出A和B，压入（B-A），我们通过先对栈顶元素取负数，再运行OpAdd就能完成。法法试图从堆对栈顶元素取负数的算法OpNeg如图10.15所示。10.4 数据类型转换 我们谈论数据类型已经很长时间了。我们已经列举了几种数据类型：做地址运算的无符号整数，做整数运算的二进制补码整数，做逻辑运算的16位二进制串，做科学计算的浮点数，以及与输入输出设备交互的ASCII码。 每条指令被提供了该指令所需的数据类型的源操作数，这点是很重要的。例如，ADD需要二进制补码整数做操作数，如果ALU被提供的是浮点数，计算机就会产生垃圾结果。 在高级语言程序中，经常可以发现形式为A=R+I的指令，其中R（浮点数）和I（二进制补码整数）是以不同的数据类型表示的。 如果运算是被浮点数加法器执行的，那么我们对于I就有一个问题。为了处理这个问题，必须把数值I从它的原始数据类型（二进制补码整数）转换为该运算所需的数据类型（浮点数）。 即使是LC-3也有数据类型转换问题。考虑一个多位的整数通过键盘被输入。它被表示为一个ASCII码字符串。为了对其进行运算，你必须把该数值转换为二进制补码整数。考虑你想在显示器上显示一个值的二进制补码表示，为了做到这点，你必须首先把它转换为一个ASCII码字符串。 在本节，我们将检查在十进制数的ASCII码字符串与二进制补码整数之间的转换程序。10.4.1 例子：错误的程序：2+3=e 首先，让我们检查图10.16，如果一个人没有留意其操作的每个数值的数据类型，他是如何陷入困境的一个具体的例子。 假设我们希望从键盘输入两个十进制数，对其做加法，然后将结果显示在显示器上。首先，我们写了如图10.16所示的简单程序。发生了什么事？假设从键盘输入的第一位数字是2，第二个是3。当程序终止前什么将会显示在显示器上？作为输入2的结果，加载到R0的是2的ASCII码，即x0032。当输入3时，3的ASCII码，x0033将被加载。因此，ADD指令将把二进制串x0032和x0033相加，得到x0065。当该值显示在显示器上时，将作为一个ASCII码被处理。因为x0065是小写的e的ASCII码，那么e将显示在显示器上。我们没有得到5（在最后的计算中，2+3的正确结果是5）的原因是（a）我们在执行加法前没有把输入的两个字符从ASCII码转换为二进制补码整数，而且（b）在显示结果前没有把它转换回ASCII码。练习：更正图10 .16，使得它能将两个一位的正整数相加，并且能得到一个一位的正数和。假设两个一位数相加产生的是一个一位数的和。10.4.2 ASCII码到二进制处理一些多位的数字通常是有用的。图10.17显示了一个三位数295的ASCII码表示，作为一个ASCII码字符串被存储在从ASCIIBUFF开始的三个连续的LC-3存储单元中。R1包含这个数的位数。 注意在图10.17中，为每一个ASCII码字符分配了一个完整的LC-3的字（16位）。一个人可以（事实上，更典型地说，一个人一定是）把每个ASCII码字符存储在存储器的一个字节中。在这个例子中，为了简化算法，我们已经决定为每一个ASCII码字符分配存储器的一个字。图10.18显示的是把图10.17中的ASCII码表示转换成一个二进制整数的流程图。表示的值必须在0到+999的范围内，那就是说，它被限制为一个三位的十进制数。算法系统地取出每一个数，通过只留最后四位把它从ASCII码转换到二进制编码，然后用它去索引一个有十个二进制值的表，每一个都对应于10个十进制数中的一个数。该数值被加到R0上。R0用来累加所有位的贡献。最后的结果被返回到R0中。图10.19显示了实现这个算法的LC-3程序。练习：非常有挑战性假设十进制的数任意长，不采用为千位上的数把十个数值存储于一张表，为万位上的数把十个数值存储于另一张表等做法，不凭借其他任何表，我们可以设计一个算法来做这个转换吗（习题10.20）？ 10.4.3 二进制到ASCII码类似的，将二进制补码整数转换为一个ASCII码字符串也是很有用的，它可以使得该数被显示在显示器上。图10.20显示的是将存储在R0里的二进制补码整数转换为一个存储在四个连续的存储单元里的ASCII码字符串的算法，该存储单元是从ASCIIBUFF开始的。最初在R0里的值被限制在-999到+999的范围内。当该算法执行完之后，ASCIIBUFF含有的是最初存在R0里的数值的符号。下面的三个单元包含了这个十进制数的三位对应的ASCII码。算法运行如下。首先，检测这个数值的符号，存储相应的ASCII码。R0中的值被它的绝对值所取代。算法通过重复的将R0中的值减去100，直到结果为负数，来判断其百位数。接下来，重复这种方法，得到十位数。剩下的值就是个位数。练习：无论被转换的整数的符号和大小，这个算法总是得到四个字符的字符串。设计一个算法，取消在通常的表示中不必要的字符，也就是说，不存储开头的0和正号的算法（习题：10.22）。10.5 最后的例子：计算器我们将以一个综合的例子的代码来结束第10章：计算器的模拟。它的意义就是示范到目前为止的许多被讨论过的概念的应用，也是展示一个好的文档、清晰的代码的例子，这个例子比那些只占一两页的例子更复杂。计算器模拟包含了11个独立的程序。鼓励你在我们进入第11章和高级语言程序设计之前去学习这个例子。计算器工作如下：我们用键盘输入命令和十进制数值。我们用显示器显示结果。我们用10.2节中描述的栈去执行算术运算。数据输入和输出被限定在3位的十进制数，这就是说，仅包括-999到+999的数值。可执行的操作有：X退出模拟D显示在栈顶的数据C清空栈中的数据+用栈顶的两个元素的和去代替这两个数据*用栈顶的两个元素的积去代替这两个数据-取栈顶数据的负数回车将键盘上输入的数据放到栈顶图10.21是一个流程图，它给出了一个模拟计算器的总览。计算器的模拟以初始化开始，它包括了设置栈指针R6，让它指向一个空的栈。然后用户坐在键盘前被提示要求输入。输入被回显，模拟计算器系统的测试用户输入的命令字符。根据用户的命令，模拟计算器执行相应的操作，跟着提示下一个指令的输入。模拟计算器以这种方式继续直到用户按下X，信号代表用户已经结束使用计算器了。11个程序组成了模拟计算器。图10.22是主算法，图10.23是把用户输入的十进制数的ASCII字符串，转化为一个二进制数，并且存于栈顶。图10.19提供了将ASCII码转换为二进制的程序。图10.26从栈顶取出一个元素，把它转换为ASCII码字符串，然后在显示器上显示出来。图10.20提供了将二进制转化为ASCII码的程序。图10.10（OpAdd），10.14（OpMult）和10.15（OpNeg）提供了使用栈的最基本的算术运算。图10.24和10.25包含了适合这个应用的POP和PUSH程序。最后，图10.27清空栈。注意：如果这些程序和图10.17的主程序一起运行，必须做一些小小的变化。例如，OpAdd，OpMult和OpNeg必须以BRnzp NewCommand结束，而不是RET。同时，一些标记在多个子程序中被用到。如果子程序是单独汇编的，而且一些标记被.EXTERNAL认别（9.2.5节），那么，在多个子程序中使用同样标记不存在问题。然而，如果整个程序被作为一个单独的模块汇编，那么，重复的标记是不允许的。在这种情况下，你必须重新命名一些标记（如Restore1，Restore2，Exit和Save），使得所有的标记都是唯一的。习题10.3 修改LC-3的ISA，使其包括Push和Pop指令。Push Rn将寄存器n的值压栈，Pop Rn从栈中取出一个值，放入寄存器n。如下6个栈操作被执行前后，LC-3的8个寄存器的情况如下图所示。请填充(a)(d)。10.4 写一个子程序，实现另一个栈操作：查看（PEEK），该操作返回栈的第一个元素，而不移走该元素，同时也应进行下溢检查。10.6 重写PUSH和POP程序，要求操作的每个元素均占用2个存储单元。10.7重写PUSH和POP程序，使之可以处理任意大小的栈。10.8 在一个栈上进行如下操作：PUSH A, PUSH B, POP, PUSH C, PUSH D, POP, PUSH E, POP, POP, PUSH Fa在PUSH F后，栈中包含什么元素？b在上述操作的结果上，再进行如下操作，请指出在哪一点上，栈包含的元素数最多？PUSH G, PUSH H, PUSH I, PUSH J, POP, PUSH K, POP, POP, POP, PUSH L, POP, POP, PUSH Mc现在，栈包含什么元素？10.9栈的输入流是指压入栈的所有元素按照压入顺序的一个列表，习题10.8的输入流为ABCDEFGHIJKLM。而栈的输出流是指出栈的所有元素按照弹出顺序的一个列表。a习题10.8的输出流是什么？b如果输入流是ZYXWVUTSR，输出流是YXVUWZSRT，那么，PUSH和POP的序列是什么？c如果输入流是ZYXW，那么，有多少种不同的输出流？8.15 中断驱动的I/O：a如下LC-3程序实现了什么？.ORIGx3000LDR3,ASTIR3,KBSRAGAINLDR0,BTRAPx21BRnzpAGAINA.FILLx4000B.FILLx0032KBSR.FILLxFE00.ENDb如果有人键入了一个键，程序将被中断。假设键盘中断向量是x34，存储单元x0134中的内容是x1000。如下此程序做了什么工作？ .ORIGx1000LDIR0,KBDRTRAPx21TRAPx21RTIKBDR.FILLxFE02.ENDc假设程序a开始执行，坐在键盘前的人键入了一个数，那么，屏幕上将显示什么内容？键入的数将显示多少次？9.19 假设LC-3有4个中断设备，某设备请求服务时，发出中断请求信号（IRQ），该信