一種基于最小空閑時(shí)間優(yōu)先的片上總線仲裁算法實(shí)現(xiàn)

　　對(duì)于包含多主設(shè)備的片上系統(tǒng)，采用共享總線的結(jié)構(gòu)具有實(shí)現(xiàn)簡(jiǎn)單和硬件開銷較少的優(yōu)勢(shì)，已成為設(shè)計(jì)的主要手段。在共享總線結(jié)構(gòu)中，多個(gè)總線主設(shè)備競(jìng)爭(zhēng)使用總線控制權(quán)，不可避免地會(huì)產(chǎn)生競(jìng)爭(zhēng)和沖突，為有效解決沖突，設(shè)計(jì)了總線仲裁器來決定總線上哪個(gè)主設(shè)備獲得總線的使用權(quán)。但是，各總線主設(shè)備會(huì)有不同的實(shí)時(shí)性和帶寬的要求，所以，總線仲裁器必須采取合理的策略和高性能的調(diào)度算法來滿足各主設(shè)備的要求。目前，常用的總線仲裁算法有：固定/動(dòng)態(tài)優(yōu)先權(quán)算法FP/DP（Fix/Dynamic Priority）、時(shí)分復(fù)用算法TDMA（Time DivisiON Multiple Access）、時(shí)間片輪轉(zhuǎn)算法RR（Round Robin）和彩票算法（Lottery）。該算法在收集主設(shè)備請(qǐng)求（服務(wù)時(shí)間和截止時(shí)間等）特性參數(shù)和總線傳輸狀態(tài)信息的基礎(chǔ)上，通過PT-LSF算法的調(diào)度結(jié)果，實(shí)時(shí)動(dòng)態(tài)地改變主設(shè)備優(yōu)先權(quán)，以滿足主設(shè)備強(qiáng)實(shí)時(shí)性要求。

　　1 基于最小空閑時(shí)間優(yōu)先的總線仲裁算法原理及實(shí)現(xiàn)

　　1.1 算法原理

　　記空閑時(shí)間Si定義為從當(dāng)前時(shí)刻t直到其截止期di的時(shí)間與其剩余服務(wù)時(shí)間ci（t）之間的差，則最小空閑時(shí)間優(yōu)先調(diào)度算法的策略是：按照主設(shè)備的空閑時(shí)間動(dòng)態(tài)地分配優(yōu)先級(jí)p，可由式（1）確定：

　　pi=pmax-Si （1）

　　空閑時(shí)間越短，主設(shè)備的優(yōu)先級(jí)就越高，因此選擇具有最小空閑時(shí)間的主設(shè)備獲得總線的使用權(quán)。假設(shè)某個(gè)主設(shè)備Ti發(fā)出請(qǐng)求總線服務(wù)請(qǐng)求時(shí)，總線正被具有更高優(yōu)先級(jí)的其他主設(shè)備Tj所占用，從而阻止了Ti使用總線。隨著時(shí)間的推移，Ti的空閑時(shí)間嚴(yán)格單調(diào)遞減直至小于正占用總線的主設(shè)備Tj的空閑時(shí)間時(shí)，按照調(diào)度策略，總線必須切換到服務(wù)Ti。

　　1.1.1 總線顛簸現(xiàn)象

　　總線（Bus）是計(jì)算機(jī)各種功能部件之間傳送信息的公共通信干線，它是由導(dǎo)線組成的傳輸線束， 按照計(jì)算機(jī)所傳輸?shù)男畔⒎N類，計(jì)算機(jī)的總線可以劃分為數(shù)據(jù)總線、地址總線和控制總線，分別用來傳輸數(shù)據(jù)、數(shù)據(jù)地址和控制信號(hào)?？偩€是一種內(nèi)部結(jié)構(gòu)，它是CPU、內(nèi)存、輸入、輸出設(shè)備傳遞信息的公用通道，主機(jī)的各個(gè)部件通過總線相連接，外部設(shè)備通過相應(yīng)的接口電路再與總線相連接，從而形成了計(jì)算機(jī)硬件系統(tǒng)。在計(jì)算機(jī)系統(tǒng)中，各個(gè)部件之間傳送信息的公共通路叫總線，微型計(jì)算機(jī)是以總線結(jié)構(gòu)來連接各個(gè)功能部件的。

　　由于等待主設(shè)備的空閑時(shí)間隨時(shí)間嚴(yán)格遞減，當(dāng)有多個(gè)任務(wù)等待主設(shè)備時(shí)，其空閑時(shí)間不斷變化，所以會(huì)出現(xiàn)多個(gè)主設(shè)備相互交叉搶占總線服務(wù)的現(xiàn)象。每次搶占都發(fā)生一次總線切換，造成總線服務(wù)顛簸現(xiàn)象。顛簸現(xiàn)象的產(chǎn)生主要是因?yàn)榈却?wù)主設(shè)備Ti的空閑時(shí)間Si一旦小于服務(wù)主設(shè)備Tj的空閑時(shí)間Sj，就馬上進(jìn)行總線服務(wù)切換，所以選擇合適的切換時(shí)機(jī)可以有效地解決顛簸現(xiàn)象。本文引入搶占閾值來擴(kuò)展最小空閑時(shí)間優(yōu)先服務(wù)的總線仲裁算法。

　　1.1.2 搶占閾值的確定

　　記pi為主設(shè)備Ti的優(yōu)先級(jí)，hi為主設(shè)備Ti的切換閾值。根據(jù)之前的分析，主設(shè)備的優(yōu)先值越大，其優(yōu)先級(jí)就越高，所以主設(shè)備的切換閾值必須大于其優(yōu)先值，即hi>pi。因?yàn)閜i的值是動(dòng)態(tài)變化的，所以hi值不能事先確定，需要隨時(shí)間進(jìn)行動(dòng)態(tài)修改?？紤]到總線仲裁過程實(shí)時(shí)性要求很高，hi值的確定不宜過于復(fù)雜，所以本文采用線性法來設(shè)計(jì)。對(duì)于任意Ti，hi的值由式（2）確定：

　　1.2 算法流程

　　算法流程如下：

　?。?）算法初始化；

　　（2）檢測(cè)是否有主設(shè)備請(qǐng)求總線服務(wù)，有則初始化主設(shè)備（假設(shè)為Ti）的參數(shù)（優(yōu)先級(jí)pi=pmax；切換閾值hi=hmax；空閑時(shí)間Si），并加入等待服務(wù)主設(shè)備隊(duì)列T′中；

　?。?）對(duì)T′中的每個(gè)主設(shè)備計(jì)算Si；

　?。?）判斷總線是否正在服務(wù)，是則轉(zhuǎn)（5），否則轉(zhuǎn)（7）；

　?。?）對(duì)T′中的所有Ti，計(jì)算Si-Sj，結(jié)果小于0則加入就緒服務(wù)主設(shè)備隊(duì)列T″中，轉(zhuǎn)（6）；

　　（6）判斷T″是否為空，是則轉(zhuǎn)（9），否則對(duì)T″中的每個(gè)主設(shè)備計(jì)算pi=pi-hj，如果max（pi）>0設(shè)置Ti的優(yōu)先級(jí)最高，減小pj，轉(zhuǎn)（7）；

　?。?）對(duì)優(yōu)先級(jí)最高的Ti進(jìn)行服務(wù)，轉(zhuǎn)（8）；

　?。?）修改各主設(shè)備參數(shù)，按照式（1）修改pi，式（2）修改hi；判斷T′中的主設(shè)備是否服務(wù)完，是則轉(zhuǎn)（9），否則轉(zhuǎn)（2）；

　?。?）算法結(jié)束。

　　1.3 算法實(shí)現(xiàn)

　　基于閾值的最小空閑時(shí)間優(yōu)先服務(wù)的片上總線仲裁算法由4個(gè)基本模塊組成：算法控制模塊、優(yōu)先級(jí)調(diào)節(jié)器、帶寬調(diào)節(jié)器和總線傳輸控制器。另外，算法所需的主設(shè)備訪問總線特性參數(shù)（服務(wù)時(shí)間、截止時(shí)間等）和總線服務(wù)參數(shù)信息由信號(hào)提取模塊完成，信號(hào)的控制和實(shí)際數(shù)據(jù)的傳輸由信號(hào)授權(quán)模塊完成，其總體結(jié)構(gòu)如圖1所示。

　　（1）優(yōu)先級(jí)調(diào)節(jié)器

　　該模塊的主要作用是實(shí)現(xiàn)對(duì)主設(shè)備優(yōu)先級(jí)的動(dòng)態(tài)調(diào)節(jié)，以滿足主設(shè)備的實(shí)時(shí)性要求。該模塊從信號(hào)提取模塊中獲得各個(gè)主設(shè)備實(shí)時(shí)性相關(guān)的參數(shù)（主設(shè)備請(qǐng)求總線服務(wù)時(shí)間、最大截止時(shí)間、請(qǐng)求訪問從設(shè)備的地址及從設(shè)備傳輸響應(yīng)時(shí)間等），然后進(jìn)行簡(jiǎn)單的處理后，傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算，最終得到各個(gè)主設(shè)備調(diào)整后的優(yōu)先級(jí)。優(yōu)先級(jí)調(diào)節(jié)器根據(jù)該結(jié)果通過信號(hào)授權(quán)模塊動(dòng)態(tài)調(diào)整各個(gè)主設(shè)備的優(yōu)先級(jí)。

　　進(jìn)程是有優(yōu)先級(jí)的。如果即將被運(yùn)行的進(jìn)程的優(yōu)先級(jí)比正在運(yùn)行的進(jìn)程的優(yōu)先級(jí)高，則系統(tǒng)可以強(qiáng)行剝奪正在運(yùn)行的進(jìn)程的CPU，讓優(yōu)先級(jí)高的進(jìn)程先運(yùn)行。

　　HSRP參數(shù)，用于支持某個(gè)LAN網(wǎng)段中某個(gè)HSRP組中的活動(dòng)HSRP路由器選擇。缺省優(yōu)先級(jí)是100。每組內(nèi)優(yōu)先級(jí)最高的路由器會(huì)被選為該組的活動(dòng)轉(zhuǎn)發(fā)路由器。

　　但是由于具有降低優(yōu)先級(jí)的任務(wù)長時(shí)間占用共享資源，造成申請(qǐng)?jiān)撡Y源的優(yōu)先級(jí)最高的進(jìn)程始終處于等待狀態(tài)，此時(shí)其他比占用資源優(yōu)先級(jí)高但比等待資源進(jìn)程優(yōu)先級(jí)低的進(jìn)程將獲得處理器的使用權(quán)，并先于優(yōu)先級(jí)最高的處于等待狀態(tài)的進(jìn)程先結(jié)束，稱這種現(xiàn)象為優(yōu)先級(jí)反轉(zhuǎn)。

　?。?）帶寬調(diào)節(jié)器

　　該模塊的主要作用是監(jiān)視總線上主設(shè)備實(shí)際傳輸帶寬和由算法控制的應(yīng)該配置帶寬之間的變化，實(shí)時(shí)反饋信息給算法控制模塊來保證帶寬精確分配。該模塊從信號(hào)提取模塊中獲得各個(gè)主設(shè)備帶寬要求相關(guān)的參數(shù)（主設(shè)備每次數(shù)據(jù)傳輸?shù)拈L度、主設(shè)備帶寬需求以及總線帶寬利用情況等），然后進(jìn)行簡(jiǎn)單的處理，傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算，最終得到各個(gè)主設(shè)備調(diào)整后的帶寬要求，帶寬調(diào)節(jié)器根據(jù)該結(jié)果通過信號(hào)授權(quán)模塊動(dòng)態(tài)調(diào)整各個(gè)主設(shè)備的帶寬配置。

　　（3）總線傳輸控制器

　　該模塊的主要作用是監(jiān)視總線帶寬的狀態(tài)，準(zhǔn)確預(yù)測(cè)出各設(shè)備請(qǐng)求的響應(yīng)時(shí)間，并將該結(jié)果傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算，得到新的總線帶寬分配方案。總線傳輸控制器通過信號(hào)授權(quán)模塊來協(xié)調(diào)各個(gè)主設(shè)備使用總線。

　?。?）算法控制模塊

　　算法控制模塊的硬件邏輯包括：時(shí)間片定時(shí)器、判據(jù)寄存器組、比較邏輯和算法控制狀態(tài)機(jī)。其中，判據(jù)寄存器組的初始值通過離線計(jì)算獲得，在總線服務(wù)過程時(shí)，通過主設(shè)備特性參數(shù)提取模塊獲得實(shí)時(shí)參數(shù)值，作為新的判據(jù)寄存器數(shù)據(jù)提供給算法控制狀態(tài)機(jī)。比較邏輯負(fù)責(zé)對(duì)算法運(yùn)行產(chǎn)生的新結(jié)果與判據(jù)寄存器組進(jìn)行比較，并對(duì)判據(jù)寄存器組內(nèi)的數(shù)據(jù)進(jìn)行更新。

　　算法控制狀態(tài)機(jī)采用Mealy有限狀態(tài)機(jī)來實(shí)現(xiàn)總線仲裁算法流程，完成對(duì)各主設(shè)備的優(yōu)先級(jí)、帶寬分配等屬性的動(dòng)態(tài)調(diào)節(jié)。另外對(duì)各主設(shè)備請(qǐng)求使用總線服務(wù)進(jìn)行仲裁，實(shí)現(xiàn)各主設(shè)備協(xié)調(diào)使用總線所提供的服務(wù)。

　　2 實(shí)驗(yàn)及結(jié)果分析

　　為驗(yàn)證基于閾值的最小空閑時(shí)間優(yōu)先服務(wù)總線仲裁器的性能，本文對(duì)基于動(dòng)態(tài)優(yōu)先級(jí)的仲裁器、基于時(shí)間輪轉(zhuǎn)的仲裁器和本文提出的仲裁器進(jìn)行了實(shí)驗(yàn)，并進(jìn)行了比較。

　　2.1 實(shí)驗(yàn)平臺(tái)

　　實(shí)驗(yàn)硬件平臺(tái)為Core 2 Duo CPU（主頻為2 GHz），內(nèi)存4 GB，操作系統(tǒng)是Windows XP，仿真軟件使用ModelSim6.4。在實(shí)驗(yàn)平臺(tái)上，共實(shí)現(xiàn)了6個(gè)主設(shè)備、1個(gè)從設(shè)備和1個(gè)總線仲裁器。6個(gè)主設(shè)備的類型和相關(guān)參數(shù)如表1所示（在表1中，R表示有實(shí)時(shí)性要求，NR表示沒有實(shí)時(shí)性要求；B表示有帶寬要求，NB表示沒有帶寬要求）。

　　2.2 實(shí)驗(yàn)結(jié)果

　　首先，定義兩種性能指標(biāo)：

　?。?）服務(wù)請(qǐng)求截止期錯(cuò)失率MDP（Missed Deadline Percentage）=“所有截止期錯(cuò)失的總線服務(wù)請(qǐng)求/所有主設(shè)備總線服務(wù)請(qǐng)求之和”。

　　（2）服務(wù)切換次數(shù)SSN（Service Switch Num）=“從未完成的總線服務(wù)請(qǐng)求到搶占的總線服務(wù)請(qǐng)求切換次數(shù)”+“從完成總線服務(wù)請(qǐng)求到另一總線服務(wù)請(qǐng)求的切換次數(shù)”。

　　在此基礎(chǔ)上，對(duì)表1中所示的6個(gè)主設(shè)備分別采用4種總線仲裁算法進(jìn)行仿真實(shí)驗(yàn)，得到如下結(jié)果。

　?。?）對(duì)于不同總線負(fù)載ρ

　　取公式（2）中的α=5，圖2和圖3分別表示對(duì)于不同總線負(fù)載ρ（0.5≤ρ≤2.0）情況下，4種總線仲裁算法的MDP比較。其中圖2是在每個(gè)主設(shè)備請(qǐng)求100個(gè)總線服務(wù)下的MDP，圖3是每個(gè)主設(shè)備請(qǐng)求200個(gè)總線服務(wù)下的MDP。從圖2和圖3中可以看出，最小空閑時(shí)間優(yōu)先總線仲裁器得到的MDP要明顯小于其他兩種總線仲裁器。當(dāng)ρ≤1時(shí)，最小空閑時(shí)間總線仲裁器可以保證每個(gè)主設(shè)備都滿足其總線服務(wù)截止期要求；當(dāng)ρ>1時(shí)，會(huì)出現(xiàn)主設(shè)備部分總線服務(wù)請(qǐng)求不能滿足其服務(wù)截止期要求的情況，但其MDP要明顯小于其他兩種總線仲裁器。

　　（2）對(duì)于不同比例系數(shù)α

　　取ρ=1.3，圖4和圖5分別給出了在不同比例系數(shù)α?xí)r的MDP和SSN變化情況。

　　從圖4中可以看出，對(duì)于MDP的影響，并不是搶占次數(shù)越多（比例系數(shù)α越小）調(diào)度效果就越好，而是當(dāng)α=12時(shí)，MDP最??；而當(dāng)α=1時(shí)，MDP達(dá)到最大。從圖5中可以看出，SSN的值隨著ρ的變大而逐漸變小，但是，當(dāng)α的值大到一定量時(shí)，SSN的值變化不明顯；當(dāng)α接近1時(shí)，SSN變化顯著。究其原因，從公式（2）中可以看出：當(dāng)α=1時(shí)，hi=pi，即主設(shè)備的搶占閾值等于其優(yōu)先級(jí)，則搶占閾值就沒有起到作用，即變成了完全搶占模式，該情況下，主設(shè)備頻繁地?fù)屨伎偩€服務(wù)，。以上兩種情況都會(huì)造成總線服務(wù)質(zhì)量的下降，所以，比例系數(shù)α的選擇應(yīng)當(dāng)保證MDP最小的情況下，相應(yīng)的SSN值不能太大，結(jié)合圖4和圖5可以看出，α=12為最優(yōu)比例系數(shù)。

　　2.3 試驗(yàn)結(jié)果分析

　　在PT-LSF算法中，總線仲裁器在收集主設(shè)備請(qǐng)求特性參數(shù)和總線傳輸狀態(tài)信息基礎(chǔ)上，結(jié)合主設(shè)備請(qǐng)求總線服務(wù)的緩急程度來實(shí)時(shí)地改變主設(shè)備優(yōu)先權(quán)，以滿足主設(shè)備強(qiáng)實(shí)時(shí)性要求。通過與常用的動(dòng)態(tài)優(yōu)先級(jí)算法、時(shí)間片輪轉(zhuǎn)算法和Lottery算法的實(shí)驗(yàn)分析比較可以看出，本文提出的PT-LSF算法在服務(wù)請(qǐng)求截止期錯(cuò)失率（MDP）上有顯著優(yōu)勢(shì)。另外，在PT-LSF算法中，使總線服務(wù)達(dá)到最優(yōu)時(shí)，并不是搶占次數(shù)越多（比例系數(shù)α越大）越好，而是取一個(gè)中間合適值。在本文中，系統(tǒng)最大優(yōu)先級(jí)為16，最小優(yōu)先級(jí)為1，最優(yōu)比例系數(shù)α為12，該結(jié)果為搶占閾值比例系數(shù)？琢的確定提供了實(shí)驗(yàn)依據(jù)。

　　本文提出了基于最小空閑時(shí)間優(yōu)先的總線仲裁算法，并給出了算法的實(shí)現(xiàn)流程和組成結(jié)構(gòu)。將其與動(dòng)態(tài)優(yōu)先級(jí)算法、時(shí)間片輪轉(zhuǎn)算法和Lottery算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果顯示：該總線仲裁算法在MDP方面比其他兩種算法平均減少了43.8%，能更好地保證主設(shè)備的強(qiáng)實(shí)時(shí)要求。該總線仲裁算法對(duì)于共享總線的片上系統(tǒng)設(shè)計(jì)具有重要的參考價(jià)值。