HW15

匯流排仲裁

匯流排仲裁簡介

　 　系統中多個設備或模組可能同時申請對匯流排的使用權，為避免產生匯流排衝突，需由匯流排仲裁機構合理地控制和管理系統中需要佔用匯流排的申請者，在多個申請者同 時提出匯流排請求時，以一定的優先演算法仲裁哪個應獲得對匯流排的使用權。匯流排判優控制按照仲裁控制機構的設置可分為集中控制和分散控制兩種。其中就集中控制而 言，常用的匯流排仲裁方式有：菊輪鍊仲裁、二維仲裁、同步通信方式、非同步通信方式和半同步通信方式。

　　連接到匯流排上的功能模組有主動和被動兩種形態，CPU可以做主方也可以做從方，而存取器模組只能用作從方。主方可以啟動一個匯流排週期，而從方只能響應主方的請求。對多個主設備提出的佔用匯流排請求，一般採用優先順序或公平策略進行仲裁。

仲裁方式分類

　　按照匯流排仲裁電路的位置不同，仲裁方式分為集中式仲裁和分散式仲裁兩類：

　　1.集中式匯流排仲裁的控制邏輯基本集中在一處，需要中央仲裁器，分為鏈式查詢方式、計數器定時查詢方式、獨立請求方式；

　　(1) 鏈式查詢方式

　　鏈式查詢方式的主要特點：匯流排授權信號BG串列地從一個I/O介面傳送到下一個I/O介面。假 如BG到達的介面無匯流排請求，則繼續往下查詢；假如BG到達的介面有匯流排請求，BG信號便不再往下查詢，該I/O介面獲得了匯流排控制權。離中央仲裁器最近 的設備具有最高優先順序，通過介面的優先順序排隊電路來實現。

　　鏈式查詢方式的優點: 只用很少幾根線就能按一定優先次序實現匯流排仲裁，很容易擴充設備。

　　鏈式查詢方式的缺點: 對詢問鏈的電路故障很敏感，如果第i個設備的介面中有關鏈的電路有故障，那麼第i個以後的設備都不能進行工作。查詢鏈的優先順序是固定的，如果優先順序高的設備出現頻繁的請求時，優先順序較低的設備可能長期不能使用匯流排。

　　(2)計數器定時查詢方式

　　匯流排上的任一設備要求使用匯流排時，通過BR線發出匯流排請求。中央仲裁器接到請求信號以後，在 BS線為“0”的情況下讓計數器開始計數，計數值通過一組位址線發向各設備。每個設備介面都有一個設備位址判別電路，當位址線上的計數值與請求匯流排的設備 位址相一致時，該設備 置“1”BS線，獲得了匯流排使用權，此時中止計數查詢。

　　每次計數可以從“0”開始，也可以從中止點開始。如果從“0”開始，各設備的優先次序與鏈式查詢法相同，優先順序的順序是固定的。如果從中止點開始，則每個設備使用匯流排的優先順序相等。

　　計數器的初值也可用程式來設置，這可以方便地改變優先次序，但這種靈活性是以增加線數為代價的。

　　(3)獨立請求方式

　　每一個共用匯流排的設備均有一對匯流排請求線BRi和匯流排授權線BGi。當設備要求使用匯流排時，便發出該設備的請求信號。中央仲裁器中的排隊電路決定首先回應哪個設備的請求，給設備以授權信號BGi。

　　獨立請求方式的優點：響應時間快，確定優先響應的設備所花費的時間少，用不著一個設備接一個設備地查詢。其次，對優先次序的控制相當靈活，可以預先固定也可以通過程式來改變優先次序；還可以用遮罩(禁止)某個請求的辦法，不回應來自無效設備的請求。

　　2.分散式仲裁不需要中央仲裁器，每個潛在的主方功能模組都有自己的仲裁號和仲裁器。當它們有 匯流排請求時，把它們唯一的仲裁號發送到共用的仲裁匯流排上，每個仲裁器將仲裁匯流排上得到的號與自己的號進行比較。如果仲裁匯流排上的號大，則它的匯流排請求不予 回應，並撤銷它的仲裁號。最後，獲勝者的仲裁號保留在仲裁匯流排上。顯然，分散式仲裁是以優先順序仲裁策略為基礎。

13筆記

13周作業

1.在Link state routing 中可能會出現 oscillation 的問題
   請說明此問題，並提出一種解決辦法。
所有的路由器(router)都會頻繁的向交通指揮中心報告交通狀況。
所以，交通指揮中心完全掌握所有的路由資訊，其中包括有沒有
新的路由器加入，哪裡線路擁塞，哪個路由器剛剛掛了，哪些路
段有交通管制，哪些路段要收費，哪一條是高速公路，哪一條是
市區道路等等非常詳細的全區域的地圖與交通狀況。交通指揮中
心很可能是一個或多個路由器來擔任，當車子帶著需求由IN出發
，交通指揮中心就會幫忙車子決定OUT和全程的最佳路徑；或者
只要車子帶著OUT的地址由IN出發，無需交代需求為何，交通指
揮中心也會幫忙車子決定全程的最佳路徑。

Link state routing algorithm 通過主動測試鄰接節點的狀態，定
期地將相鄰節點的狀態信息傳送給所有節點，每個節點都有完整的
網絡拓撲信息，然後計算到每個節點的最佳路徑。而oscillation
problem 是因為存在多個交通指揮中心而造成的問題。

解決方案:
善用雙層式網路架構，並且切割成多個 Area ，這樣每個 Area 中的
網路就會比較簡單，同一個 Area 中的Link-State 路由演算法計算次
數也會比較少，而且 Routing Table 和各種資料庫中的資料筆數也會
比較少。




2.在 distance vector 中可能會出現 bad news travel slower 的問題
   請說明此問題，並提出一種解決辦法。
Distance Vector路由演算法與Link State路由演算法最大的不同就是
，Link State演算法只會傳遞少部分更新的路由資料，而且會把這樣的
更新資料傳遞到各個路由器設備內，而Distance Vector路由演算法則
會傳遞整份的資料，而且只會傳遞給鄰近的路由器設備而已。不過，即
使路由資料沒有任何的改變，Distance Vector也會將整份路由資料發
送出來，而這裡所謂的整份路由資料，指的就是發送端路由器設備中
Routing Table的完整資料，當鄰近的路由器設備收到這整份路由資料後
，會開始比較已知的路由路徑，並把有更新過的資料同步至本地端路由器
設備中，因為這種方式 都會假設接收到的資料一定是比自己還要新的資料
，所以這種方式通常也被稱為「謠言路由方式」（Routing by rumor）
。就是因為這樣類似「以訛傳訛」的運作方式，所以會產生很多問題。

當鄰近的路由器設備收到這整份路由資料之後，會開始比
較已知的路由路徑，並把有更新過的資料同步的本地端路
由器設備中。由於這種方式都會假設接收到的資料一定是
比自己還要新的資料，所以通常也被稱為「謠言路由方式」
（Routing by rumor）。就是因為這樣類似「以訛傳訛」
的運作方式，所以會產生一些問題，但幸好這些問題都已經
有了對應的解決方案。