一种基于最小空闲时间优先的片上总线仲裁算法实现

　　对于包含多主设备的片上系统，采用共享总线的结构具有实现简单和硬件开销较少的优势，已成为设计的主要手段。在共享总线结构中，多个总线主设备竞争使用总线控制权，不可避免地会产生竞争和冲突，为有效解决冲突，设计了总线仲裁器来决定总线上哪个主设备获得总线的使用权。但是，各总线主设备会有不同的实时性和带宽的要求，所以，总线仲裁器必须采取合理的策略和高性能的调度算法来满足各主设备的要求。目前，常用的总线仲裁算法有：固定/动态优先权算法FP/DP（Fix/Dynamic Priority）、时分复用算法TDMA（Time DivisiON Multiple Access）、时间片轮转算法RR（Round Robin）和彩票算法（Lottery）。该算法在收集主设备请求（服务时间和截止时间等）特性参数和总线传输状态信息的基础上，通过PT-LSF算法的调度结果，实时动态地改变主设备优先权，以满足主设备强实时性要求。

　　1 基于最小空闲时间优先的总线仲裁算法原理及实现

　　1.1 算法原理

　　记空闲时间Si定义为从当前时刻t直到其截止期di的时间与其剩余服务时间ci（t）之间的差，则最小空闲时间优先调度算法的策略是：按照主设备的空闲时间动态地分配优先级p，可由式（1）确定：

　　pi=pmax-Si    （1）

　　空闲时间越短，主设备的优先级就越高，因此选择具有最小空闲时间的主设备获得总线的使用权。假设某个主设备Ti发出请求总线服务请求时，总线正被具有更高优先级的其他主设备Tj所占用，从而阻止了Ti使用总线。随着时间的推移，Ti的空闲时间严格单调递减直至小于正占用总线的主设备Tj的空闲时间时，按照调度策略，总线必须切换到服务Ti。

　　1.1.1 总线颠簸现象

　　总线（Bus）是计算机各种功能部件之间传送信息的公共通信干线，它是由导线组成的传输线束， 按照计算机所传输的信息种类，计算机的总线可以划分为数据总线、地址总线和控制总线，分别用来传输数据、数据地址和控制信号。总线是一种内部结构，它是CPU、内存、输入、输出设备传递信息的公用通道，主机的各个部件通过总线相连接，外部设备通过相应的接口电路再与总线相连接，从而形成了计算机硬件系统。在计算机系统中，各个部件之间传送信息的公共通路叫总线，微型计算机是以总线结构来连接各个功能部件的。

　　由于等待主设备的空闲时间随时间严格递减，当有多个任务等待主设备时，其空闲时间不断变化，所以会出现多个主设备相互交叉抢占总线服务的现象。每次抢占都发生一次总线切换，造成总线服务颠簸现象。颠簸现象的产生主要是因为等待服务主设备Ti的空闲时间Si一旦小于服务主设备Tj的空闲时间Sj，就马上进行总线服务切换，所以选择合适的切换时机可以有效地解决颠簸现象。本文引入抢占阈值来扩展最小空闲时间优先服务的总线仲裁算法。

　　1.1.2 抢占阈值的确定

　　记pi为主设备Ti的优先级，hi为主设备Ti的切换阈值。根据之前的分析，主设备的优先值越大，其优先级就越高，所以主设备的切换阈值必须大于其优先值，即hi>pi。因为pi的值是动态变化的，所以hi值不能事先确定，需要随时间进行动态修改。考虑到总线仲裁过程实时性要求很高，hi值的确定不宜过于复杂，所以本文采用线性法来设计。对于任意Ti，hi的值由式（2）确定：

　　1.2 算法流程

　　算法流程如下：

　　（1）算法初始化；

　　（2）检测是否有主设备请求总线服务，有则初始化主设备（假设为Ti）的参数（优先级pi=pmax；切换阈值hi=hmax；空闲时间Si），并加入等待服务主设备队列T′中；

　　（3）对T′中的每个主设备计算Si；

　　（4）判断总线是否正在服务，是则转（5），否则转（7）；

　　（5）对T′中的所有Ti，计算Si-Sj，结果小于0则加入就绪服务主设备队列T″中，转（6）；

　　（6）判断T″是否为空，是则转（9），否则对T″中的每个主设备计算pi=pi-hj，如果max（pi）>0设置Ti的优先级最高，减小pj，转（7）；

　　（7）对优先级最高的Ti进行服务，转（8）；

　　（8）修改各主设备参数，按照式（1）修改pi，式（2）修改hi；判断T′中的主设备是否服务完，是则转（9），否则转（2）；

　　（9）算法结束。

　　1.3 算法实现

　　基于阈值的最小空闲时间优先服务的片上总线仲裁算法由4个基本模块组成：算法控制模块、优先级调节器、带宽调节器和总线传输控制器。另外，算法所需的主设备访问总线特性参数（服务时间、截止时间等）和总线服务参数信息由信号提取模块完成，信号的控制和实际数据的传输由信号授权模块完成，其总体结构如图1所示。

　　（1）优先级调节器

　　该模块的主要作用是实现对主设备优先级的动态调节，以满足主设备的实时性要求。该模块从信号提取模块中获得各个主设备实时性相关的参数（主设备请求总线服务时间、最大截止时间、请求访问从设备的地址及从设备传输响应时间等），然后进行简单的处理后，传入算法控制模块，经过算法控制模块的运算，最终得到各个主设备调整后的优先级。优先级调节器根据该结果通过信号授权模块动态调整各个主设备的优先级。

　　进程是有优先级的。如果即将被运行的进程的优先级比正在运行的进程的优先级高，则系统可以强行剥夺正在运行的进程的CPU，让优先级高的进程先运行。

　　HSRP参数，用于支持某个LAN网段中某个HSRP组中的活动HSRP路由器选择。缺省优先级是100。每组内优先级最高的路由器会被选为该组的活动转发路由器。

　　但是由于具有降低优先级的任务长时间占用共享资源，造成申请该资源的优先级最高的进程始终处于等待状态，此时其他比占用资源优先级高但比等待资源进程优先级低的进程将获得处理器的使用权，并先于优先级最高的处于等待状态的进程先结束，称这种现象为优先级反转。

　　（2）带宽调节器

　　该模块的主要作用是监视总线上主设备实际传输带宽和由算法控制的应该配置带宽之间的变化，实时反馈信息给算法控制模块来保证带宽精确分配。该模块从信号提取模块中获得各个主设备带宽要求相关的参数（主设备每次数据传输的长度、主设备带宽需求以及总线带宽利用情况等），然后进行简单的处理，传入算法控制模块，经过算法控制模块的运算，最终得到各个主设备调整后的带宽要求，带宽调节器根据该结果通过信号授权模块动态调整各个主设备的带宽配置。

　　（3）总线传输控制器

　　该模块的主要作用是监视总线带宽的状态，准确预测出各设备请求的响应时间，并将该结果传入算法控制模块，经过算法控制模块的运算，得到新的总线带宽分配方案。总线传输控制器通过信号授权模块来协调各个主设备使用总线。

　　（4）算法控制模块

　　算法控制模块的硬件逻辑包括：时间片定时器、判据寄存器组、比较逻辑和算法控制状态机。其中，判据寄存器组的初始值通过离线计算获得，在总线服务过程时，通过主设备特性参数提取模块获得实时参数值，作为新的判据寄存器数据提供给算法控制状态机。比较逻辑负责对算法运行产生的新结果与判据寄存器组进行比较，并对判据寄存器组内的数据进行更新。

　　算法控制状态机采用Mealy有限状态机来实现总线仲裁算法流程，完成对各主设备的优先级、带宽分配等属性的动态调节。另外对各主设备请求使用总线服务进行仲裁，实现各主设备协调使用总线所提供的服务。

　　2 实验及结果分析

　　为验证基于阈值的最小空闲时间优先服务总线仲裁器的性能，本文对基于动态优先级的仲裁器、基于时间轮转的仲裁器和本文提出的仲裁器进行了实验，并进行了比较。

　　2.1 实验平台

　　实验硬件平台为Core 2 Duo CPU（主频为2 GHz），内存4 GB，操作系统是Windows XP，仿真软件使用ModelSim6.4。在实验平台上，共实现了6个主设备、1个从设备和1个总线仲裁器。6个主设备的类型和相关参数如表1所示（在表1中，R表示有实时性要求，NR表示没有实时性要求；B表示有带宽要求，NB表示没有带宽要求）。

　　2.2 实验结果

　　首先，定义两种性能指标：

　　（1）服务请求截止期错失率MDP（Missed Deadline Percentage）=“所有截止期错失的总线服务请求/所有主设备总线服务请求之和”。

　　（2）服务切换次数SSN（Service Switch Num）=“从未完成的总线服务请求到抢占的总线服务请求切换次数”+“从完成总线服务请求到另一总线服务请求的切换次数”。

　　在此基础上，对表1中所示的6个主设备分别采用4种总线仲裁算法进行仿真实验，得到如下结果。

　　（1）对于不同总线负载ρ

　　取公式（2）中的α=5，图2和图3分别表示对于不同总线负载ρ（0.5≤ρ≤2.0）情况下，4种总线仲裁算法的MDP比较。其中图2是在每个主设备请求100个总线服务下的MDP，图3是每个主设备请求200个总线服务下的MDP。从图2和图3中可以看出，最小空闲时间优先总线仲裁器得到的MDP要明显小于其他两种总线仲裁器。当ρ≤1时，最小空闲时间总线仲裁器可以保证每个主设备都满足其总线服务截止期要求；当ρ>1时，会出现主设备部分总线服务请求不能满足其服务截止期要求的情况，但其MDP要明显小于其他两种总线仲裁器。

　　（2）对于不同比例系数α

　　取ρ=1.3，图4和图5分别给出了在不同比例系数α时的MDP和SSN变化情况。

　　从图4中可以看出，对于MDP的影响，并不是抢占次数越多（比例系数α越小）调度效果就越好，而是当α=12时，MDP最小；而当α=1时，MDP达到最大。从图5中可以看出，SSN的值随着ρ的变大而逐渐变小，但是，当α的值大到一定量时，SSN的值变化不明显；当α接近1时，SSN变化显着。究其原因，从公式（2）中可以看出：当α=1时，hi=pi，即主设备的抢占阈值等于其优先级，则抢占阈值就没有起到作用，即变成了完全抢占模式，该情况下，主设备频繁地抢占总线服务，。以上两种情况都会造成总线服务质量的下降，所以，比例系数α的选择应当保证MDP最小的情况下，相应的SSN值不能太大，结合图4和图5可以看出，α=12为最优比例系数。

　　2.3 试验结果分析

　　在PT-LSF算法中，总线仲裁器在收集主设备请求特性参数和总线传输状态信息基础上，结合主设备请求总线服务的缓急程度来实时地改变主设备优先权，以满足主设备强实时性要求。通过与常用的动态优先级算法、时间片轮转算法和Lottery算法的实验分析比较可以看出，本文提出的PT-LSF算法在服务请求截止期错失率（MDP）上有显着优势。另外，在PT-LSF算法中，使总线服务达到最优时，并不是抢占次数越多（比例系数α越大）越好，而是取一个中间合适值。在本文中，系统最大优先级为16，最小优先级为1，最优比例系数α为12，该结果为抢占阈值比例系数？琢的确定提供了实验依据。

　　本文提出了基于最小空闲时间优先的总线仲裁算法，并给出了算法的实现流程和组成结构。将其与动态优先级算法、时间片轮转算法和Lottery算法进行比较。实验结果显示：该总线仲裁算法在MDP方面比其他两种算法平均减少了43.8%，能更好地保证主设备的强实时要求。该总线仲裁算法对于共享总线的片上系统设计具有重要的参考价值。