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）。就是因為這樣類似「以訛傳訛」
的運作方式，所以會產生一些問題，但幸好這些問題都已經
有了對應的解決方案。

第八周筆記

第八周作業

1.用筆記上的end-to-end與point-to-point的圖,利用該圖的概念找出實際例子



DAS -> full redundant disk array ( end - to - end)

而其方式可經過數台的 FC switch，

DAS -> FC switch1 ,FC switch1->full redundant disk array

DAS -> FC switch2 ,FC switch2->full redundant disk array

DAS -> FC switch3 ,FC switch3->full redundant disk array　　(point - to -point)










2.何謂 encapsulation請解釋




在物件導向程式設計方法中，封裝（英語：Encapsulation）是指，一種將抽象性函式介面的實作細節部份包裝、隱藏起來的方法。同時，它也是一種防止外界呼叫端，去存取物件內部實作細節的手段，這個手段是由程式語言本身來提供的。這兩個概念有一些不同，但通常被混合使用。封裝被視為是物件導向的四項原則之一。

適當的封裝，可以將物件使用介面的程式實作部份隱藏起來，不讓使用者看到，同時確保使用者無法任意更改物件內部的重要資料。它可以讓程式碼更容易理解與維護，也加強了程式碼的安全性。




運用encapulation封裝有什麼樣的優點呢？


1.可以避免不必要的資料存取現象發生，

　封裝可以將資料適度隱藏，避免存取到不必要的資料，而造成問題。

2.製作適當的細節封裝可以降低ripple effect（漣波效益），

　意思就是避免日後修改一個問題所帶來的連帶效應過大。

筆記

第七週作業

Cookie產生的隱私權與法律問題

當你造訪某些網站的時候，網站的伺服器會在你的電腦裡塞入一些值（資料）暫存在你的點腦裏面，這些被暫存進你電腦裡的這些值（資料）就稱為Cookie。
這些值可以讓網站的伺服器讀取，並且傳送特地畫面到你的電腦中，以利提供客製化的服務並提升及簡化瀏覽程序。，ex. GOOGLE帳戶。
Cookies可分作兩類：永久cookies及暫存cookies（即工作階段cookies）。永久cookies會以檔案形式儲存於您的電腦或流動裝置中少於12個月；工作階段cookies則只作暫時儲存，在您關閉瀏覽器工作階段後隨即消失。

當在某些網站上（例如FaceBook）點選記住我，則伺服器將會使用永久Cookie儲存我們的選擇。
此外某些網站會使用工作階段Cookie以方便使用產品篩選功能，檢查造訪者是否有登入。


coolie的技術因為不是完全的妥當，所以引發了不少隱私權可能被侵害的爭議，其整理如下：

1.非自主性的暴露網路行徑

2.無預測可能性的流出個人資料，有被不當利用之可能

可能觸及的法律：

洩漏業不上知悉他人秘密罪、洩漏業務上知悉工商秘密罪、洩漏公務上知悉工商秘密罪、洩漏電腦秘密罪等等。


    2. A.P2P架構筆記(3) 的式子用不等式求出B.把數字或上網收詢數據帶入 P2P架構筆記(3) 的式子 ,並畫出CS架構與P2P架構的圖

作業6

1.FTP的使用流程與解釋

FTP：File Transfer Protocol (client and server)，它是一種獲得網際網路世界普遍採用的通訊協定之一


FTP 伺服器種類大致可分為「匿名式」和「非匿名式」兩種。

• 匿名式的FTP 

這就是俗稱的 FTP 站，在這些 FTP 站裡面存放著各式各樣的檔案，如共享軟體、免費軟體 ... 供 Internet 使用者取用。這些 FTP 站都是開放式的，又稱為「匿名式 FTP 伺服器」（Anonymous FTP Server），因為這些站都有開放一個叫做Anonymous Account（匿名帳號）的公用帳號供大家使用，所以任何人都能登入。當您連上匿名式的 FTP 站時，只要以 Anonymous為username，以您的 E-Mail 位址為 password，即可合法登入，進行檔案傳輸。

• 非匿名式的FTP 

並非所有 Internet 上的工作站或主機，都允許匿名式的登入進行檔案傳輸。對於那些非匿名式的 FTP Server，您就得擁有該 Server 的使用權。取得帳號及密碼後，才能以該 username 和 password 登入，進行檔案傳輸，而且所傳遞的檔案也只限於您擁有存取權的檔案。


FTP有兩種使用模式：主動和被動。
主動模式要求客戶端和伺服器端同時開啟並且監聽一個埠以建立連線。在這種情況下，客戶端由於安裝了防火牆會產生一些問題。所以，創立了被動模式。被動模式只要求伺服器端產生一個監聽相應埠的行程，這樣就可以繞過客戶端安裝了防火牆的問題。
一個主動模式的FTP連線建立要遵循以下步驟：

1. 客戶端開啟一個隨機的埠（埠號大於1024，在這裡，我們稱它為x），同時一個FTP行程連線至伺服器的21號命令埠。此時，該tcp連線的來源地埠為客戶端指定的隨機埠x，目的地埠（遠端埠）為伺服器上的21號埠。 
2. 客戶端開始監聽埠（x+1），同時向伺服器發送一個埠命令（透過伺服器的21號命令埠），此命令告訴伺服器客戶端正在監聽的埠號並且已準備好從此埠接收資料。這個埠就是我們所知的資料埠。 
3. 伺服器開啟20號源埠並且建立和客戶端資料埠的連線。此時，來源地的埠為20，遠端資料(目的地)埠為（x+1）。 
4. 客戶端透過原生的資料埠建立一個和伺服器20號埠的連線，然後向伺服器發送一個應答，告訴伺服器它已經建立好了一個連線。 

(參考自維基百科)


2.recursive call vs iterated call 之差別性(用N階來做舉例兩者之間的差異)


 Recursive call : 遞回呼叫，在函數之中可呼叫函數本身。函數再進行遞回呼叫時，載期所使用的變數被堆積在堆疊區域，每次執行return敘述，函數在該層呼叫中所使用的變數就從堆疊返回。每次執行return敘述，問題範圍縮小，具有一個中止遞回之條件。


Iterated call: 反覆運算，重複反饋過程的活動，其目的通常是為了逼近所需的目標或結果。美一次對過程的重複被稱為一次「迭代」，而每一次迭代得到的結果會被用來做為下一次迭代的初始執。

課堂筆記

第五周作業

1.找一個HTML語法的 (Client-Server) programming 然後對這支程式內容做解釋
ans:


讓網頁具有 Google 搜尋功能
標準語法:<a href="想連結網址">連結地的名稱</a>＝＝＝可與其它網站連結

<!-- Search Google -->
<center>
<form method=get action="http://www.google.com/search">
<table bgcolor="#FFFFFF"><tr><td>
<a href="http://www.google.com">
<img src="http://www.google.com/logos/Logo_40wht.gif" border="0"
alt="Google" align="absmiddle"></a>
<input type=text name=q size=31 maxlength=255 value="">
<input type=hidden name=ie value=Big5>
<input type=hidden name=oe value=Big5>
<input type=hidden name=hl value=zh-TW>
<input type=submit name=btnG value="Google搜尋">
</td></tr></table>
</form>
</center>
<!-- Search Google -->



2.如何提高Cache的hit ratio?
一個是提高db_block_buffers的值，也就是擴大數據緩衝區的值，讓塊aged out of memory的機率變小,讓更多的塊住入緩存，這是一種明顯的提高數據塊內存訪問命中率的方法。一個是根據訪問的特徵，使用不同的塊大小，設置不同塊所對應緩衝區的大小，且不同塊之間緩衝區的使用互部影響。

第三周筆記

Transparent 與 Virtual 的應用

Transparent透通 ： 實際上有，但使用起來好像沒有


         應用：Transparent Proxy
         什麼是Transparent Proxy?
         一般來說，我們為了節省網路頻寬、加快網路瀏覽速度更甚者為了達到控制
         公司內部的網頁瀏覽情況等等時會使用proxy server，但是假設公司內部有
         一千台電腦，使用電腦的人又是電腦白痴的時候，為了不要浪費時間教會
         使用者如何設定瀏覽器Proxy或者是要節省這些功夫，最快的方法就是在網
         路出口的地方像是NAT伺服器或者L4 switch上面，將這些流量自動的導
         到proxy server上面。這樣一來，使用者完全不需要做任何設定，瀏覽網
         頁時自動就會透過ProxyServer連線出去，對使用者來說，這個proxy就像
         是透明的一樣，完全感覺不到它的存在。



Virtual虛擬：實際上沒有，但使用起來好像有

         應用：Java 的 Virtual Stack Machine
         執行Java應用程式必須安裝Java Runtime Environment（JRE），JRE內部有一個Java虛擬
         機器（Java Virtual Machine，JVM）以及一些標準的類別庫（Class Library）。透過JVM的
         虛擬機器才能在電腦系統執行Java應用程式（Java Application）。

         機器是真實的一個物件，但在這裡，他使用起來好像是有這個東西，但實際上它不是實
        體是不存在的。
           

         

EBCDIC

EBCDIC是 Extended Binary Coded Decimal Interchange Code的擴增二進制十進制交換碼的縮寫。

是一個於1963~1964年，由IBM公司所推出的字元編碼表。
一個EBCDIC包含一個位元組，也就是八個位元。
可以表示出256個不同的字元。

由於EBCDIC是根據早期打孔機的二進化十進數(Binary Coded Decimal；BCD)方式排列而成。英文字母不是連續排列，中間出現斷層，而編碼的方式也沒有甚麼邏輯可言，所以會造成使用者的使用困難，非常難使用。因此使用便利性並不如ASCII碼及ASCII碼的祖師大哥Unicode。

ASCII碼

甚麼是ASCII碼?
ASCII碼是American Standard Code Information Interchange的縮寫。
用來制定電腦中每個符號對應的代碼，這種代碼也可以稱做是電腦的內碼（Code）。

每個ASCII碼占了一個位元組，而每個位元組有８個位元，所以每個位元組可以表示2的8次，
也就是256個字元，但數字0~255中，較高的位元（128~255）並沒有被使用到，
所以後來又將這些位元也編入ASCII碼中，成為八個位元的延伸ASCII碼（Extended ASCII）。

延伸的ASCII碼裡加上了許多數學與表格框線等特殊符號，成為目前最常用的內碼。

計算機網路上課筆記(未整理)

甚麼是Overhead?

Overhead是多餘的或間接的時間計算，記憶題及頻寬所需要達到特定的目標或其他資源的任意組合。
簡單的來說就是為了達到一個目標所付出的代價，而這個代價可以是時間、金錢、或任何資源。

例如：
為了安全上的目的將封包加密，結果變得比原來還大、傳輸時間也變長。這些為了安全上的目的而產生的負擔就可以稱為是Overhead。
假設今天有200K的資料要傳輸，但在傳輸的過程中，我們會加上各種header，例如TCP/IP，會令整個封包大小變大（產生負擔），但是會得到TCP/IP，的好處，譬如說傳輸效率會變好（目的）。

二分搜尋法與二元樹

敘述何謂二分搜尋法? 自己設一個數列來做舉例 並告訴我二分搜尋怎麼使用

在二分搜尋法中，從一個已經排序的數列(依大小)中間開始尋找某數
如果中間那數比所要尋找的數還要小，由於已經排列，左邊的數一定都比中間的那個數還要小，因此就不用浪費時間再搜尋左邊的數了。如果中間的數比要搜尋的數要來的大，那也就不需要再搜尋左邊了。

下面產生的數列為隨機產生

Ｃ：


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void quickSort(int[], int, int);
int binarySearch(int[], int);

int main(void) {
    srand(time(NULL));

    int number[MAX] = {0};

    int i;
    for(i = 0; i < MAX; i++) {
        number[i] = rand() % 100;
    }

    quickSort(number, 0, MAX-1);

    printf("數列：");
    for(i = 0; i < MAX; i++)
        printf("%d ", number[i]);

    int find;
    printf("\n輸入尋找對象：");
    scanf("%d", &find);

    if((i = binarySearch(number, find)) >= 0)
        printf("找到數字於索引 %d ", i);
    else
        printf("\n找不到指定數");

    printf("\n");

    return 0;
}

int binarySearch(int number[], int find) {
    int low = 0;
    int upper = MAX - 1;
    while(low <= upper) {
        int mid = (low+upper) / 2;
        if(number[mid] < find)
            low = mid+1;
        else if(number[mid] > find)
            upper = mid - 1;
        else
            return mid;
    }
    return -1;
}

void quickSort(int number[], int left, int right) {
    if(left < right) {
        int s = number[(left+right)/2];
        int i = left - 1;
        int j = right + 1;

        while(1) {
            while(number[++i] < s) ;  // 向右找
            while(number[--j] > s) ;  // 向左找
            if(i >= j)
                break;
            SWAP(number[i], number[j]);
        }

        quickSort(number, left, i-1);   // 對左邊進行遞迴
        quickSort(number, j+1, right);  // 對右邊進行遞迴
    }
}

還有何謂二元樹(binary tree)? 並舉例作圖

二元樹是一種有限節點的集合。是每個節點最多有兩個子樹的樹結構（左子樹、右子樹），節點也可以是空的。

雞兔同籠;數學與算術的差別

問題：雞兔同籠，雞和兔共有10隻，但只有26隻腳，求雞和兔各有幾隻？

算數解法：

設雞有10隻，兔有0隻

所以腳共有 10x2=20隻 (不符合問題的26隻腳)

設雞有9隻，兔有1隻

所以腳共有 9x2+1x4=22 隻 (不符合問題的26隻腳)

設雞有8隻，兔有2隻

所以腳共有 8x2+2x4=24 隻 (不符合問題的26隻腳)

設雞有7隻，兔有3隻

所以腳共有 7x2+3x4=26 隻

答案：雞有7隻，兔有3隻

數學解法：

設雞有x隻，兔有y隻

我們能列出

 x + y = 10 (雞+兔共有10隻)  及  2x + 4y = 26 (雞的腳+兔的腳共有26隻)

x + y = 10  ─①

2x + 4y = 26 ─②

①    -  ( ② /2 )

得

-y = -3

y = 3 代回 ①

得

x + 3 = 10

x = 7

答案：雞有7隻，兔有3隻