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

　　对于包含多主设备的片上系统，采用共享总线的结构具有实现简单和硬件开销较少的优势，已成为设计的主要手段。在共享总线结构中，多个总线主设备竞争使用总线控制权，不可避免地会产生竞争和冲突，为有效解决冲突，设计了总线仲裁器来决定总线上哪个主设备获得总线的使用权。但是，各总线主设备会有不同的实时性和带宽的要求，所以，总线仲裁器必须采取合理的策略和高性能的调度算法来满足各主设备的要求。目前，常用的总线仲裁算法有：固定/动态优先权算法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）优先级调节器

该模块的主要作用是实现对主设备优先级的动态调节，以满足主设备的实时性要求。该模块从信号提取模块中获得