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

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

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

　　1.1 算法原理

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

　　pi=pmax-Si （1）

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

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

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

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

　　1.1.2 搶占閾值的確定

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

　　1.2 算法流程

　　算法流程如下：

　?。?）算法初始化；

　?。?）檢測是否有主設備請求總線(xiàn)服務(wù)，有則初始化主設備（假設為T(mén)i）的參數（優(yōu)先級pi=pmax；切換閾值hi=hmax；空閑時(shí)間Si），并加入等待服務(wù)主設備隊列T′中；

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

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

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

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

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

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

　?。?）算法結束。

　　1.3 算法實(shí)現

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

　　（1）優(yōu)先級調節器

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

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

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

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

　?。?）帶寬調節器

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

　?。?）總線(xiàn)傳輸控制器

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

　?。?）算法控制模塊

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

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

　　2 實(shí)驗及結果分析

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

　　2.1 實(shí)驗平臺

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

　　2.2 實(shí)驗結果

　　首先，定義兩種性能指標：

　?。?）服務(wù)請求截止期錯失率MDP（Missed Deadline Percentage）=“所有截止期錯失的總線(xiàn)服務(wù)請求/所有主設備總線(xiàn)服務(wù)請求之和”。

　?。?）服務(wù)切換次數SSN（Service Switch Num）=“從未完成的總線(xiàn)服務(wù)請求到搶占的總線(xiàn)服務(wù)請求切換次數”+“從完成總線(xiàn)服務(wù)請求到另一總線(xiàn)服務(wù)請求的切換次數”。

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

　?。?）對于不同總線(xiàn)負載ρ

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

　　（2）對于不同比例系數α

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

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

　　2.3 試驗結果分析

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

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