《计算机系统概论第十章.doc》由会员分享，可在线阅读，更多相关《计算机系统概论第十章.doc（14页珍藏版）》请在金锄头文库上搜索。
1、第十章 最后栈我们已经结束了对LC-3指令集结构的处理。在向上进入十一章的又一个抽象层次到达C语言程序设计之前，我们应该花一些时间在一个特别重要的基础话题上：栈。首先，我们将详细的解释其基本结构，然后，我们将描述栈的3个作用：（1）我们在8.5节承诺要介绍的中断驱动的I/O机制的剩余部分；（2）实现临时存储中间结果的算术运算的一个机制是栈，而非通用寄存器；（3）二进制补码整数与ASCII码字符串之间的转换算法。这3个例子只是冰山一角。在计算机科学与工程中，你会发现栈在你所做的大多数工作中都非常有用。我们猜想在本书成为你的一个愉快的回忆之后，你会发现栈的新作用。我们将通过一个计算器的设计，一个使
2、用了在本章讨论的许多主题的复杂应用，来结束我们在指令集结构层次上的介绍。10.1 栈：基本结构10.1.1 栈 一种抽象数据类型 贯穿在你的将来对计算机的使用（或设计）之中，你将会遇到一种名为栈的存储结构。栈可以通过许多不同的方式来实现，我们将立刻开始学习。但是首先，知道栈的概念与其实现毫无关系是很重要的。栈的概念是说明它如何被访问。也就是说，栈的定义是你最后存入栈的东西首先被取出。那就是栈与别的东西的不同之处。简单地说：后进先出 (Last In, First Out)，或者LIFO。 在计算机程序设计语言的术语中，栈是抽象数据类型的一个例子。也就是说，一种抽象数据类型是一类存储机制，这种机
3、制是由对它执行的操作所定义的，而不是实现它的方式。在第19章，我们将使用链表用C语言写程序，链表是另一种抽象数据类型的例子。10.1.2 两个实现栈的例子 汽车扶手中的硬币盒就是栈的一个例子。你取出第一个25美分付高速公路通行税，而这25美分就是你刚刚最后放到25美分的栈中的。当你加入一个25美分的时候，先前的一个就会被压在下面。 图10.1显示了硬币盒的行为。开始时，如图10.1a里面是空的。第一次高速公路通行税是75美分，你给了收费员一美元，她找了你25美分，一个1995年的硬币，你把它插入硬币盒。此时的硬币盒如图10.1b所示。 对于向栈插入元素和从栈移出元素有专门的术语。当我们把一个元
4、素插入栈的时候，我们称之为压栈（push），当我们移出一个元素时，我们称之为出栈（pop）。 第二次高速公路通行税是4.25美元。你给了收费员5美元，她找了你75美分。你把它们放进了硬币盒中。首先放进去的是1982年的，然后是1998年的，最后是1996年的。现在，硬币盒如图10.1c所示。第三次通行税是50美分，你移出（出栈）硬币盒顶上的两个25美分，先拿1996年的，然后再拿1998年的，那么，硬币盒如图10.1d所示。 硬币盒是一个栈的例子。因为它正好符合后进先出的要求。每一次放一个25美分进去，总是从顶部插入。每次取一个25美分出来，也是从顶部去取。你最后放进去的硬币是你首先要拿走的，
5、因此，它是一个栈。 另一个栈的实现，有时被称为硬件栈，如图10.2所示。它的行为类似于我们刚刚描述的硬币盒。它由一定数量的寄存器组成，每个寄存器可以存储一个元素。图10.2中的例子含有5个寄存器。当每个元素被存入或取出时，已经在栈里的元素就会移动。在图10.2a中，栈的初始状态显示为空。访问总是经由第一个元素，它被标记为栈顶（TOP）。如果数值18被压入栈，我们就有了图10.2b。如果3个数值31，5，12被压入栈（按顺序），我们就有图10.2c。最后，如果有2个元素从栈中取出，我们就有图10.2d。图10.2的栈的显著特征，和往硬币盒里放硬币一样，就是当每一个值被存入或取出时，在栈中的所有的
6、值都要移动。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
7、）仍然存在于存储单元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只能作为栈被访问的话。当
8、我们将一个值压入栈时，栈指针减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.3
9、c所示，并且我们再执行2次这组指令，我们将会从栈中取出 2个值。在本例中，我们将会先取出12，然后是5。假设取这两个的目的是为了使用这两个值，我们当然将会在取第2个值之前把12从R0移到某个单元中。图10.3d表示经过那一系列操作之后的栈。R6包含着x3FFE，这表示现在31在栈的顶部。注意值12和5仍然分别保存在单元x3FFD和x3FFC中。然而，因为栈要求我们通过执行PUSH指令序列来实现压栈，通过执行POP指令序列来实现出栈，如果违反规则，我们就不能访问这2个值。对于这些规则有个很好的名字叫做“栈协议”。下溢如果我们试图从栈里取出顶上的三个元素会发生什么呢？因为只有两个值留在栈里，我们会
10、遇到一个问题。试着取出以前没有被压入的项目会导致一个下溢（underflow）的情况。在我们的例子中，我们能通过将栈指针与x4000对比来检测下溢，如果在栈顶没有留下任何元素的话，R6的内容就是x4000。如果UNDERFLOW是处理下溢情况的程序的标记，最后得到的POP指令序列将是：POPLDR1, EMPTY ADDR2,R6,R1; 将栈指针与x4000作比较BRzUNDERFLOW LDRR0,R6,#0ADDR6,R6,#1RETEMPTY.FILLxC000；EMPTY为-x4000如果POP失败，通常是让POP程序将下溢信息保存在一个寄存器里，再返回调用它的程序；而不是立即让PO
11、P程序跳到UNDERFLOW程序。为了实现这一点，一个常用的习惯是使用一个寄存器提供成功或失败的信息。图10.4显示了如何使用R5报告这种成功和失败的信息，实现POP程序的扩展。当从POP程序返回时，调用程序会检测R5来判断POP是（R5=0）否(R5=1)成功完成。注意，既然POP程序用R5来报告成功或失败，在POP程序被调用之前保存在R5里的任何东西都会丢失。这样，在JSR指令执行之前存储R5里的内容便是调用程序的工作了。回忆一下9.1.7节，这是一个调用者保存情况的例子。最后得到的POP程序如下所示。注意因为在RET指令之前的一条指令设置或清空了条件码，调用程序可以通过简单的检测条件码Z
12、来判断POP是不是成功的完成了。POPLDR1, EMPTY ADDR2, R6 , R1BRzFailureLDRR0 ,R6 ,#0ADDR6 ,R6, # 1ANDR5 ,R5 ,# 0RETFailureANDR5, R5 ,# 0ADDR5 ,R5 ,# 1RETEMPTY.FILLxC000；EMPTY为-x4000上溢当我们把栈中可用的空间用完了，但我们仍试图将一个数值压入栈中，会发生什么呢？在栈中没有空间的时候，我们不能存储值，这就是上溢的情况。我们可以通过对比栈指针(在图 10.3 的例子中)和x3FFB，如果这两个值相等，栈中就没有空间来存储更多的值。如果OVERFLOW是
13、一个处理上溢情况的程序的标记，我们得到最后的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）。我们再一
14、次的注意到，既然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.FILLx
15、C005；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里报告
