5.2.  可转子程序的计算机

上节所介绍的计算机仍然是十分简单的，还不能够实现子程序调用，存储容量还不够大。实际上计算机的存储器容量是相当大的，现在人们使用的微型电子计算机的存储器都达到了几百兆甚至上千兆以上，大型的计算机存储器使用则可以达到数千兆以上。本节要介绍的带有转子程序功能的计算机，对存储容量进行了适当的扩大，以满足程序设计的要求。

要实现子程序调用，计算机必须有相应的功能，而要实现子程序调用的功能，计算机必须有相应的组织结构。因此对于能够实现子程序调用的计算机，要先来说明这台计算机新增的功能和计算机结构的变化。

这台计算机欲增加的功能有两条。

（1）       在执行某个程序的过程中暂时停下来，而转去执行另一段程序，当另一段程序执行完之后，又恢复原来的程序执行。这一过程叫子程序调用。

定义6‑4   如果有一个程序执行过程中在某固定位置停下来，将另外一个程序执行一遍，然后再从停下来的位置继续执行，这种现象叫子程序调用。被调用的程序叫子程序，调用的程序叫主程序。

（2）       它还可以将某些数据以“叠放”的形式保存起来，当需要的时候再以“后进先出”的规则拿出来。这就是堆栈的问题。

主程序运行过程中会有一些数据在后面的执行中还要使用，而子程序的执行很可能破坏这些数据，因此必须把有用的数据以“后进先出”的规则保存起来，在恢复主程序执行时，要先恢复这些原来的数据，这种过程叫“保护现场”和“恢复现场”。

新计算机设计的新指令如表6‑4所示，通过这些指令才能够具体实现上述的功能。

表6‑4  增加的指令

程序执行的过程中如果调用子程序，那么必须将主程序的下一条指令的位置记住，还要记住它恢复运行的环境，以便将来恢复运行时不至于出错。由于保护现场是主程序来完成的，而恢复现场必需由子程序来完成，故保护现场的设备必须具有独立性，主程序可以顺序地将数据放进去，子程序又能够按着后进先出的规则进行恢复，保证主程序的运行条件。

图6‑9就是一个带有转子程序功能的计算机结构，它也是在前面计算机的基础上改造而来的，图中没标的双线一律为12条线的组合。这台计算机的总线由8条线增加到12条（数据线用12条，地址线用8条）；寄存器B新增了E门，这样可将B中数据输出；新增加了一个计数器SP，它叫堆栈指针。SP的预置端连在Clr线上，当Clr=1时，SP的值为11111111_（2）。SP具有加1控制线C_s和减1控制线D_s，当C_s=1时，使SP加1，当D_s=1时，使SP减1。

图6‑9  具有子程序调用功能计算机

指令寄存器IR输入线有12条，直接连接在总线上。输出时IR的低8条线用来传送地址信号，高4条线仍然与指令译码器的输入端相连，放置4位的指令代码。

这台计算机的控制字已经达到了20位。如果L_n由其他设备控制，那么计算机控制器发出的控制字应该是19位。

堆栈是计算机执行子程序时保存现场和恢复现场的必要设备，队列在计算机的发展中也担当了十分重要的角色，下面就来介绍队列与堆栈相关的问题。

在资源管理，数据处理中经常要用到队列的概念，队列涉及先进先出的优先顺序。

定义6‑5   按照先进先出原则进行数据处理的存储设备叫做队列。

队列在计算机中应用很广，在多个程序使用一个设备或其他不能同时使用的资源时，常常用队列来处理使用的先后顺序。

在日常生活中人们把物品放入箱子或口袋时，一般后放入的物品反而被先拿出来，这种情况叫“后进先出”。

定义6‑6   按照后进先出的原则进行数据处理的存储设备叫做堆栈。

堆栈的组织形式如图6‑10所示。

图6‑10  堆栈

往堆栈里放数据，就如同往箱子里装东西一样，堆栈最底下位置叫栈底，就是第一个数据放入的地方（图6‑10中的7号地址单元）。堆栈最上面要放数据的位置叫栈顶，就是将要放入数据的地方（它的下面位置都已经放入了数据或者没有数据）。指示栈顶的计数器叫堆栈指针。本计算机中的计数器SP就是用来指示栈顶的堆栈指针，它指示的位置就是将要放置新数据的位置。图6‑10就是堆栈STACK的示意图，SP是堆栈指针，它指示的位置3是栈顶，栈底的位置是7。

由于规定栈顶是将要放入数据的存储单元，可以想到，按照这样的规定，如果堆栈的栈顶和栈底的地址相同，那么堆栈就是空的或者全部存储单元都放满了数据。全部存储单元都放满了数据，而堆栈指针指回了栈底，堆栈指针一定有“环绕”功能。这个问题留在后面的环行栈问题再讨论。

堆栈的数据处理是指把数据放进堆栈，或者将数据从堆栈取出来。为了说明问题方便，今后在不作特殊声明的情况下，就规定堆栈的栈底在高地址端，数据装入将向低地址端延伸。

定义6‑7   向堆栈里面放数据的过程，称之为入栈。

根据堆栈指针应该指向空位置的规定，入栈时堆栈指针SP应该减1。实际的操作过程是，先将数据放入SP所指示的单元，然后SP减1。入栈的结果会破坏堆栈中原来位置的数据。

定义6‑8   从堆栈里取出数据的过程称之为出栈。

因为出栈的意思是将堆栈中的数据取出，而堆栈指针一般总是指向没有数据的地方，所以要先将堆栈指针指向应该读走的数据。因为数据入栈的时候，堆栈指针SP进行了减1操作，所以此时堆栈指针SP要先加1。实际上操作过程是：先将SP加1指向要输出的数据，然后将数据输出，此后SP指向的这一位置可以放新的数据。

值得一提的是数据出栈只是数据的复制，因而堆栈内的数据在没有新的数据覆盖的情况下，会完好地保留。这种情况被用在利用堆栈进行排序的例题中，望读者能够留意。

在计算机程序设计中，常常会碰到一个程序的一段内容，正好是以前设计好的程序，这时就不必将这一段程序重新写了。在程序执行中，只要把那个程序在适当的位置执行一次就可以了，这就是子程序调用的问题。

为保证主程序能够准确地在子程序执行完成之后，回到调用子程序的下一条指令执行，一般需要在子程序执行前保存下一条指令执行的条件，这是保护现场。保护现场最重要的是把调用子程序之后要执行的那条指令的地址保存起来，这个工作在设计的调用子程序指令中来完成。当然保护现场也要将有关的其他数据保存起来，比如各种标志位的数值等，这可以设计专门的指令操作。

子程序执行完成后，要将执行前的数据恢复，还要将保存起来的那条指令的地址送回程序计数器，将各种标志恢复到调用子程序之前的样子，这是现场恢复。

在子程序调用的问题中，利用入栈出栈可以保护现场和恢复现场。具体的作法是将要执行的指令的地址入栈，也就是将PC的值入栈，然后将子程序的首地址送到程序计数器PC中，下一个指令周期就开始执行子程序了。当子程序执行完之后，再把入栈的地址回送到程序计数器PC中，使计算机能够接着执行原先的要执行的指令。子程序调用中，如果有数据需要放在堆栈中保存，那么恢复现场时，要注意数据入栈出栈的顺序，不要将位置颠倒了。

可以看出，子程序调用和堆栈是分不开的。尽管堆栈的多少和大小，开口的方向设置的方法不尽相同，但它们要完成的任务是一样的。

根据这个计算机的结构和需求，新增加了入栈指令PUSH，出栈指令POP，R子程序调用指令CALL R，返回指令RET，还有将寄存器B的值送到存储单元R的指令STB R，在上节能判断计算机的基础上，加上这新增加的这5个指令，现在共有16个指令了。

这个计算机的指令编码和指令格式仍然延续前一节的假设，指令操作码还是4位，而操作数是8位的。8位的操作数表明的是存储单元的地址，这样指令就能够访问存储器的256个存储单元。

下面来看一下这些新增指令执行周期的基本动作。

这条指令的作用是将累加器A的内容入栈。它的执行周期是

（4）       E_s=1      L_m=1               （SP →MAR选择栈顶）

（5）       E_a=1      M_e=1   IO=1        （A →RAM将A的内容入栈）

（6）       D_s=1                         （SP-1→SP）

微指令（4） 是将堆栈指针的内容送到地址寄存器，选中栈顶存储单元。微指令 （5）是将累加器的内容送到栈顶。微指令 （6）是写存储器后将堆栈指针的值减1。

这条指令的作用是将堆栈的内容送到累加器A中。它的执行周期是

（4）       C_s=1                   （SP+1 →SP）

（5）       E_s=1     L_m=1          （SP →MAR选择栈顶数据）

（6）       L_a=1     M_e=1          （RAM→A将栈顶数据送A）

微指令（4）是将堆栈指针加1以便指向出栈的存储单元。微指令 （5）是选中存储单元。微指令 （6）是将存储器的内容送到A。

这条指令是中断当前程序的执行，保存下一条将执行指令的地址，即将当前程序计数器的内容入栈，到R单元去取指令执行。它的执行周期是

（4）       E_s=1     L_m=1                     （SP →MAR选择栈顶）

（5）       D_s=1     E_p=1     M_e=1     IO=1    （SP-1→SP，PC→RAM）

（6）       E_i=1     L_p=1                     （IR→PC将子程序地址送到PC）

微指令（4）和微指令 （5）是将下一条执行指令的地址，即将当前程序计数器的内容入栈。微指令（6）是将子程序的地址送入PC。这里将堆栈指针减1的控制放在微指令 （5）或微指令 （6）都可以，不会影响指令的执行效果。

这条指令的任务是从当前执行的位置返回到中断的位置。它的执行过程要把保存在堆栈的指令地址弹回到程序计数器。它的执行周期是

（4）       C_s=1                 （SP+1→SP）

（5）       E_s=1      L_m=1       （SP →MAR选择栈顶）

（6）       L_p=1      M_e=1       （RAM→PC将中断地址送到PC）

这三条微指令的作用是在子程序执行完之后返回到主程序。

这台机器为了能灵活地传送数据，还设计了一个将寄存器B的值送到存储单元R的指令STB。它的执行周期是

（4）       E_i=1    L_m=1                （IR→MAR选中存储单元地址）

（5）       E_b=1    M_e=1     IO=1       （B→RAM）

（6）          

由于这个计算机的地址线已经是8位的，故可以访问256个存储单元。就利用现有这256个存储单元就能设计出一些带有调用子程序的例子。

【例6‑3】  输入3个数比较它们的大小，输出其中最大的。

这个程序的流程图如图6‑11所示，具体编写的程序也在下面。为了熟悉存储器的分配，这个例子特地使用了实际地址。将数据区定在150号地址单元开始，代码区设计了一个主程序，两个子程序。其中，一个子程序用来判断程序是否停止，具体的说，就是当3个输入数字都输入0时，停止程序执行。另一个子程序是找出最大的数。

主程序:

图6‑11   程序流程

检查结束的子程序(输入的3个数都是0就结束)：

比较大小的子程序（大数放在153号单元）：

【例6‑4】  编程输出n!（n是正整数）。

解答：考虑用乘法子程序MULT，将N放入X，(N-1)放入Y， N(N-1)放在POW中，最终结果由POW输出。ONE、POW的初值是1，RESULT的初值是0。

MAIN:   IN   N

IN   ONE    ；输入值是1

IN   POW    ；输入值是1

IN   RESULT ；输入值是0

CALL MAKE

OUT  POW

END:    STP

MAKE:   LDA   N

JZ    EXIT

STR   X

LDA   POW

STR   Y

CALL  MULT

LDA   N

SUB   ONE

STR   N

JMP   MAKE

EXIT:   RET

MULT:   LDA   X

JZ    EXIT1

SUB   ONE

STR   X

LDA   RESULT

ADD   Y

STR   RESULT

JMP   MULT

EXIT1:  LDA   RESULT

STR   POW

SUB   RESULT

STR   RESULT   ；置零

RET