快速低切换开销的堆栈处理器架构研究与实现

郭金辉，代红兵，周永录，刘宏杰

(云南大学 信息学院，云南 昆明 650504)

0 引 言

James Bowman等[1]设计的J1处理器是一种16位的28个指令的处理器，有独立的32深度的返回堆栈和数据堆栈，采用Verilog设计，核心代码不超过200行的Verilog。J1处理器所有的指令都在单位系统时钟时间内执行，在Xilinx Spartan-3E FPGA以80 MHz的时钟频率运行，可以提供100 MIPS(每秒处理百万级的机器语言指令数)的速度运行。

Anatoliy Sergiyenko等[2]采用VHDL设计的纳米性8位堆栈处理器体系结构，该体系结构设计用于FPGA实现。具有这种架构的微处理器具有较小的硬件成本，减少的软件数量，并且能够向其指令集添加多达一百个新的用户指令。纳米性8位微处理器体系结构适用于对串行端口通信进行编程，并能够执行数据流解析，它能有效地用于物联网应用程序。

上述Forth堆栈处理器虽然执行速度很快，但都只有一个返回栈和参数栈，仅支持单任务，无法完成多任务调度和任务启动/结束时间有严格约束的实时任务(如果上下文切换时将处理器中硬堆栈的信息保存到内存，必将丢失堆栈处理器的优点)。本文在J1处理器模型的基础上，针对当前Forth堆栈处理器架构不支持多任务并发和事件实时响应等问题，通过引入新的指令、定时器、中断机制以及采用多任务堆栈技术，设计实现一种快速低切换开销的Forth堆栈处理器架构，支持实时多任务的运行，弥补了Forth堆栈处理器在实时多任务研究方面的不足。

1 Forth及堆栈处理器工作原理

1.1 Forth介绍

Forth有两个堆栈——返回栈和参数栈，Forth程序的运行相当于在这两个堆栈中做进出和算术运算操作[3]。

Forth语言由一个个词以积木式方式链接在一起[4]，Forth程序运行分为执行态(解释态)和编译态[5]。执行过程和编译过程如图1和图2所示。

图1 Forth执行态执行过程

图2 Forth编译态编译过程

执行态时，输入的字符被送到输入缓冲区中，首先从输入缓冲区中以空格为分隔符分离出一个个词，然后在Forth已定义词集中搜索分离出的词是否存在。若匹配成功，则运行该Forth词，若未匹配成功，则判断是否能转换为数值，若成功则把该数放到参数栈中，否则系统报错。循环上述步骤，直到在用户输入的一行字符解释结束[6,7]。

编译态是定义新词时需要用到的一种状态[8]。定义新词时，Forth系统进入编译状态。编译程序和执行程序类似，不同的是匹配到已定义词时，查看该词是否为立即词(在名字域中用一位表示该词是否为立即词)，若是立即词，就会立即执行该词，否则把该词记录到定义词中[9]。

1.2 Forth堆栈处理器工作原理

Forth堆栈处理器根据系统时钟以心跳的方式运行[4,5]，如图3所示。时钟上升沿来临时，取指令，在上升沿到下次上升沿之间的时间进行指令译码、指令执行和修改指令计数器，系统时钟再次上升时执行结果写回，同时再次取出指令。Forth堆栈处理器以此循环的运行。

图3 Forth堆栈处理器指令执行周期

取指令：Forth堆栈处理器中有专门存放指令的随机存取存储器RAM。根据指令计数器PC的值向RAM中取出指令，然后译码执行。初始时指令计数器为0，存放的是Forth系统冷启动代码。

指令译码：取出指令后，按照指令编码规则对指令进行解码，决定取出的指令应该进行哪些操作。不同的Forth堆栈处理器有着不同的编码规则[10]。

执行指令：指令的执行主要涉及对参数栈栈顶元素、参数栈次栈顶元素和返回栈栈顶元素的操作，执行的同时也要对参数栈和返回栈的栈顶指针做相应调整。

修改指令计数器：指令被执行后，根据当前的指令的类型，确定下一条即将被执行的指令地址(_PC)。

执行结果写回：心跳频率方式运行的Forth堆栈处理器，指令执行完后，结果暂存在某寄存器中，当系统时钟上升沿来临时，需要写回到正确位置，保障下一个指令的正确执行。例如_PC赋值给即将被执行的指令地址(PC)。

2 快速低切换开销的堆栈处理器架构

200多行的Verilog语言代码就构造出了快速低切换开销的Forth堆栈处理器架构，其框架结构如图4所示。

图4 Forth堆栈处理器框架

2.1 指令集的设计

16位的Forth堆栈处理器一共有五大类指令集，分别是literal、jump、conditional jump、call、ALU，其编码格式如图5所示。

图5 Forth堆栈处理器指令格式

literal指令集用于读取终端输入字符串为数字的情况，最大允许输入的数为32 767，但想要输入32 768～65 535之间的数字需要额外的指令使该数的最高位置特殊标记。literal指令集时，_PC值指向当前PC的下一个地址，即PC加一操作。

jump、conditional jump两类指令集分别用于无条件跳转和条件跳转。jump指令会无条件的使_PC被赋值为target的值。conditional jump指令,若参数栈(D)栈顶的值为0元素，_PC被赋值为target，若D栈顶的值为非0元素，则不会发生跳转。无论跳转不跳转，conditional jump都会使D栈顶指针减一。条件跳转conditional jump指令不满足跳转条件时，_PC的值指向当前PC的下一个地址。

当遇到call指令集时，会使PC加一的值存放到返回堆栈(R)中，R栈顶指针加一，_PC被赋值为target的值。与此同时存在return指令，译码时，把R栈顶元素赋值给_PC，R栈顶指针减一。

ALU指令集是Forth堆栈处理器最复杂的指令集。13位～15位表示是ALU指令集的标志。12位的R→pc表示使R栈顶元素的值赋值给_PC。8位～11位的T’即在对参数栈(D)中的值进行算术运算(加减移位等等)，不包含乘除指令，乘除运算是经过循环加减指令代替。5位～7位是针对某些Forth词而设计，例如swap、>r、!等Forth词。T→N表示D栈顶元素赋值给次栈顶，T→R表示D顶元素赋值给R栈顶，N→[T]表示次栈顶元素放到T地址中，T为D栈顶元素。4位为保留位。rstack±表示R栈顶指针做±1操作，同理dstack±表示D栈顶指针做±1操作。ALU指令集在根据相应情况，对_PC赋值，除了R→ip是return指令操作，其它的都是_PC值指向当前PC的下一个地址。

在ALU指令集的4位是保留位，合并5位～7位，可以增设12种不同的微指令。

为了实时多任务正常运行，本文在Forth堆栈处理器指令集中设计了sp!、rp!、t→[R]、intrpt_on、intrpt_off、timer_on、timer_off和clk_n指令。设计的这些指令实现原理是当Forth堆栈处理器PC值指向设计的指令时，Forth堆栈处理器会根据指令的功能进行相应的操作。其指令功能、实现方法结合图4分别如下介绍。

sp!：表示把某数置为D栈顶指针，相应的D栈顶元素和次栈顶元素进行了的改变。实现方法是，把原D栈栈顶元素取出，赋值给D栈栈顶指针，并重新获取新D栈栈顶元素，R栈不进行任何操作。

rp!：表示把某数置为R栈顶指针，相应的R栈顶元素进行了改变。实现方法是，把原D栈栈顶元素取出，赋值给R栈栈顶指针，同是D栈栈顶指针减一，并重新获取新D栈栈顶元素。

t→[R]：表示把D栈栈顶元素放到R中，且存放地址即堆栈指针为D次栈顶元素。实现方法是，取原D栈栈顶元素和原D栈次栈顶元素，并把原D栈次栈顶元素存放到指针为原D栈栈顶元素的R栈中，D栈栈顶指针分两次进行减一操作，并重新获取新D栈栈顶元素和D栈次栈顶元素。

intrpt_on：表示允许响应中断。实现方法是，允许响应中断标志位置为1。

intrpt_off：表示禁止响应中断。实现方法是，允许响应中断标志位置为0。

timer_on：表示开启时钟中断。实现方法是，允许响应时钟中断标志位置为1。

timer_off：表示关闭时钟中断。实现方法是，允许响应时钟中断标志位置为0。

clk_n：统计系统时钟跳转次数，方便计算Forth堆栈处理器任务进行调度时的切换时间。实现方法是，在Forth堆栈处理器中加入计数器，统计系统时钟跳转次数，以此来确定运行时间。

2.2 定时器

为了能适合分时系统以时间片轮转的方式调度，在Forth堆栈处理器中加入了时钟中断机制。Verilog HDL重要部分代码如下。

(1) always @(posedge sys_clk_i) //当系统时钟上升沿来临时

(2) begin

(3) if(timer==0) //若定时器关闭

(4) clk_n <= 0;

(5) else //若定时器开启

(6) begin

(7) if(clk_n==time_slice_55 ms)/*达到定值清零*/

(8) clk_n <=0;

(9) else

(10) clk_n <=clk_n +1；//循环加一

(11) end

(12) end

sys_clk_i是系统时钟信号，上升沿来临时，判断定时器是否开启，若关闭，计数器clk_n一直为0，若开启，计数器clk_n计数，直到计数到time_slice_55 ms。

在图4中，指令timer_on、timer_off开启和关闭定时器(timer)。若开启，timer=1，并且当clk_n=0时，产生时钟中断信号，若禁止时钟中断，则时钟中断无效，_PC正常赋值。若允许响应时钟中断，则把当前任务的_PC放到R栈顶(断点保护)，_PC被置为时钟中断的中断向量地址。同样的，若允许时钟中断，在发生一次时钟中断后，clk_n不再等于0，继续进行计数，再次计数到time_slice_55 ms时，clk_n=0，然后就会再次出现时钟中断，达到分时调度的效果。

如图6加入定时器实现的Forth分时系统调度，Task1是终端任务，创建了后台非实时任务Task2(Task2的创建方式也可以是任意其它任务，同时就绪、唤醒等操作也同样如此)，并就绪Task2。Task1与Task2同优先级，系统允许响应中断。当时钟中断来临时，Task2开始运行，之后Task1和Task2交替运行，直到Task2完成。之后再次遇到时钟中断时，需判断后台是否有任务，若无后台任务不需要进行上下文切换，继续运行Task1。若有多个后台任务与终端任务同等级，可实现以时间片轮转调度的方式，多个任务循环的占用Forth堆栈处理器资源。

图6 Forth分时系统调度

2.3 中断机制

为了能适合抢占式实时系统方式调度，在Forth堆栈处理器中加入了简单的中断机制。

在图4中，突发情况下产生外部中断，外部中断传递给Forth堆栈处理器产生intrpt信号，等到完成正在执行的指令后，才能响应中断。首先判断是否允许响应中断，若禁止响应中断，_PC正常赋值；若允许响应中断，判断是否有中断信号，若无，_PC正常赋值，若有中断信号，当前任务_PC的值送到返回堆栈中，并响应中断信号，待恢复中断时，保存在返回堆栈的值重新赋值给_PC。

若时钟中断和外部中断同时到来时，根据中断类型，优先处理高级外部中断[11]。Forth堆栈处理器实时多任务系统中任务创建、删除、阻塞、唤醒、就绪、调度和修改优先级等操作属于原语，不允许被打断，需禁止响应中断。正在进行原语操作时，不能及时的响应外部中断，需要等原语操作完成后再响应外部中断。

如图7加入中断机制后实现了Forth实时系统调度。终端任务Task1创建了与Task1同优先级的后台非实时性任务Task2和实时性任务Task3，然后就绪Task2。实时任务Task3必须在中断来临前已经创建，可由其它任务创建，也可在Forth堆栈处理器冷启动时自动创建。时钟中断来临后，切换到Task2执行，Task2时间片用完后然后再切换到Task1执行。在Task1时间片未用完前，发生了突发事件，以中断服务程序的方式就绪了Task3，并禁止响应时钟中断信号。调度后，Task3一直运行，直至结束，并开启允许响应时钟中断信号。然后重新调度，选择Task2，后面部分同分时系统调度。禁止响应时钟中断信号后再次开启允许响应时钟中断信号，会立即产生时钟中断，并进行调度，选择新的任务运行，并占用Forth堆栈处理器资源。

图7 Forth实时系统调度

2.4 多任务堆栈的设计

原Forth堆栈处理器堆栈深度为32[7]，只能满足单任务正常运行，想要实时多任务正常运行，需要扩充Forth堆栈处理器堆栈深度，使得每个实时任务都拥有独立的R和D。

Forth堆栈处理器中的堆栈是用单独的随机存取寄存器来存放数据的，只需要扩充随机存取寄存器的深度，即可扩充Forth堆栈处理器中堆栈的深度。

当堆栈深度固定时，很多的非实时性任务占用了堆栈资源但得不到运行和释放，导致实时性任务无法获得堆栈资源，为了解决该问题，所有非实时性任务共用32深度的堆栈，每次任务切换时需要额外的时间把原任务的堆栈数据搬移到某段地址的RAM空间中，并把现任务的堆栈数据从RAM搬回到堆栈里。这是一种以时间换取堆栈空间的处理方法。

实时性任务和非实时性任务上下文切换有些差异，实时性任务只需保存原任务D栈顶指针和R栈顶指针，而非实时性任务不仅要保存堆栈栈顶指针，而且还需要把堆栈数据搬移到指定的地址空间中。还需要查找到下一个占用CPU资源的任务。实时性任务的断点恢复，需要sp!指令恢复D栈顶指针和rp!指令恢复R栈顶指针，然后return指令把R栈顶元素赋值给_PC，即可恢复断点。而非实时性任务堆栈恢复需要把指定RAM空间数据再次搬回到堆栈中。

3 实验评估

Forth堆栈处理器正常运行，需要在RAM中存放指令。本文利用gForth软件编写代码，首先构造出适合生成新Forth系统的框架和一些必备词，在gForth系统软件中生成eForth系统，需要定义3个Forth词汇meta、assembler、target，即Forth系统整体架构，必备词是指如何在gForth系统软件中生成可运行eForth程序的编码，并将其生成二进制/十六进制文件，重要的必备词有t：开始定义eForth基础词、t；结束定义eForth基础词、save-hex保存生成的十六进制eForth系统等等。然后根据Forth堆栈处理器指令集编码规则，定义汇编词，接着用汇编词定义Forth高级词(任务创建、删除、就绪、阻塞、唤醒、修改优先级等Forth词)，最后生成可在Forth堆栈处理器中运行eForth程序的指令文件。本文设计的基于优先级的抢占式与时间片轮转调度机制也被定义成Forth高级词，存放在RAM中，可在Forth堆栈处理器上实现实时多任务调度。

生成的编码指令文件存入到RAM中，使用ISE14.7软件对硬件描述语言Verilog HDL程序进行综合，生成的比特流文件通过iMPACT软件烧录到Xilinx Spartan-6 FPGA实验板中，使用secureCRT软件作为Forth终端仿真，FPGA中的Forth堆栈处理器上电后以16 MHz的时钟频率运行，图8为ALINX型号为AX309的实验开发板。

图8 实验开发板

开发板中有4个按键，本实验为模拟突发事件，以按键的发生当作突发事件。开发板中有6个LED灯，本实验让其显示Forth堆栈处理器从启动到某时刻的时间，分为时分秒单位，创建任务时可根据最迟发生时间设置任务优先级。

本设计中堆栈深度为256，224深度堆栈用于实时性任务，32深度用于非实时性任务。时钟中断计数器计时55 ms，可实现同优先级任务时间片轮转调度，不同优先级抢占式调度。在Forth堆栈处理器中再增添clk_n指令，统计系统时钟周期的个数，以此来测量相关时间差。

在终端任务创建后台任务Task1、Task2(实时任务也可以在处理器冷启动时自动创建)，就绪Task1任务后，Task1开始运行，某时刻发生中断，中断服务程序就绪Task2任务，中断服务程序运行完后，重新进行调度，响应了实时性强的Task2任务。

任务创建时创建一个任务控制块，并分配一定的空间地址，对该任务优先级进行设置。对任务控制块的管理，其实就是对任务进行管理。就绪任务时，把任务控制块中任务状态置为就绪态，同时根据任务优先级把该任务放到相应的链表中(多条就绪链表)，并有资格抢占处理器资源。阻塞任务时把该任务置为阻塞态，并从某个就绪链表中摘掉该任务，加入到阻塞链表中。任务唤醒时把任务状态置为就绪态，相应的是任务阻塞的逆过程，从阻塞链表中摘除该任务控制块，并添加到相应的就绪链表中。优先级的修改是对就绪链表进行增删的操作，首先摘掉原任务所在的就绪链表，修改任务控制块中优先级数，最后该任务控制块添加到相应的就绪链表中。任务删除时，根据任务状态，删除链表中的任务控制块，回收其所有资源。上述操作设计可在Forth堆栈处理器中运行eForth程序的指令文件中。

任务创建、删除、就绪、阻塞、唤醒、修改优先级等操作不允许被打断，属于原语操作，需要系统禁止响应中断。

任务调度Forth程序如下。

(1) dispatch //任务的调度

(2) task_now @ @ 1= if /*判断该任务是否为运行态， 若是运行态需要把该任务控制块放到链表末尾处*/

(3) -1 task_now @ !

(4) task_now @ 4H + @

(5) task_now @ 10H + @ dup +

(6) priority_list + ! then

(7) look_most_priority //查找任务占用处理器

(8) next_task ! //存放即将占用CPU的TCB

(9) r> task_now @ eH + ! //_PC断点保护

(10) sp@ task_now @ 8H + !//参数栈断点保护

(11) rp@ 1H-task_now @ aH + ! //返回栈断点保护

(12) base @ 1H rshift //数基值保存

(13) task_now @ cH + c!

(14) next_task @ task_now !

(15) 1H task_now @ ! //置选中任务为运行态

(16) task_now @ 8H + @ sp! // 参数栈断点恢复

(17) task_now @ aH + @ rp! //返回栈断点恢复

(18) task_now @ cH + c@ dup + base ! //数基值恢复

(19) task_now @ eH + @ >r exit； //_PC断点恢复

任务调度时进行任务的切换，需要保存任务断点、寻找即将占用处理器资源的任务、任务断点恢复，代码(9)、(10)、(11)、(12)和(13)表示原任务断点保护，代码(7)表示查找下一个占用CPU资源的任务，在D中留下该任务的控制块，代码(16)、(17)、(18)和(19)表示即将执行的任务断点恢复。

实验对比对象黄忠建等设计的是一种基于寄存器处理器的Forth实时多任务调度[12]，该系统支持实时多任务的运行，以中断的方式响应突发事件，支持中断嵌套，但是该系统只支持软实时性任务，无法完成要求严格的强实时性任务。

文献[12]在Atmega328芯片上以16 MHz的时钟频率运行，并且文献[12]提到任务的响应时间、任务上下文切换时间和最大关中断时间是影响实时系统主要的指标。本实验测试了Task2的最大任务响应(突发事件开始时间到任务开始运行之间的最大时间，包括最大关中断时间和任务响应时间)、任务上下文切换、关中断时间。如图9所示。

图9 实时任务TASK2响应时间测试

终端任务TASK1状态下创建了实时任务TASK2(包括显示clk_n的值和一个32次的累加)，按键中断模拟突发事件，此时允许响应中断(最大响应时间时需要加上最大关中断时间)，中断服务程序第一条程序是记录当前clk_n_1的值，然后就绪任务TASK2，立马进行调度，抢占终端任务TASK1。TASK2运行的第一条程序是记录当前clk_n_2的值。所以实时任务TASK2的响应时间=(clk_n_2-clk_n_1)*62.5ns+最大关中断时间。同样方法本实验测量了任务上下文切换时间和最大关中断时间。

与文献[12]作对比，得到表1实时任务重要性能指标对比。

表1 实时任务重要指标性能对比/μs

文献[12]的任务响应时间、任务上下文切换时间、最大关中断时间分别为2133 μs、60 μs、1687 μs，基于堆栈处理器的Forth实时多任务调度的实时任务响应时间、任务上下文切换时间、最大关中断时间分别为46.69 μs、13.44 μs、21.75 μs。实时多任务架构的堆栈处理器的实时任务响应时间、任务上下文时间和最大关中断时间非常快，相比于基于寄存器处理器的Forth实时多任务调度，能完成任务结束时间有严格约束的实时任务。

另外本文在Xilinx Spartan-6 FPGA实验板中以100 MHz的时钟频率运行时测得基于堆栈处理器的Forth实时多任务调度实时任务响应、上下文切换、最大关中断时间分别为7.47 μs、2.15 μs、3.48 μs。

4 结束语

本文利用ALU指令集中空闲位置设计了适合实时多任务的sp!、rp!、t→[R]、timer_on、timer_off、intrpt_on、intrpt_off和clk_n指令。引入计时器为分时调度提供“滴答”时标，通过简单的中断机制为实时调度提供启停信号。采用多任务堆栈技术，加深堆栈深度，使每个实时任务都拥有独立的堆栈空间，并且支持多个非实时任务共用同一硬件堆栈。实验方面，本文设计了基于优先级的抢占式与时间片轮转调度，可实现实时多任务调度。通过增加的指令clk_n统计系统时钟跳转次数，测量出最大任务响应、最大任务上下文切换和最大关中断时系统时钟跳转次数。通过与基于寄存器处理器的Forth实时多任务调度作比较，得出以基于堆栈处理器的Forth实时多任务调度实时任务响应时间快，任务上下文切换时间短，关中断完成迅速等特点。实验结果表明，该设计是一种快速低切换开销的Forth堆栈处理器架构，可满足任务启动/结束时间有严格约束的实时任务，对当前Forth堆栈处理器研究发展具有一定的现实意义。

快速低切换开销的Forth堆栈处理器架构还有很大的发展空间，下一步将会在本文研究的基础上，对主从式异构多核Forth堆栈处理器如何进行快速低切换开销的实时多任务调度进行研究。