筆記

第十五周作業+筆記

匯流排仲裁簡介

　 　系統中多個設備或模組可能同時申請對匯流排的使用權，為避免產生匯流排衝突，需由匯流排仲裁機構合理地控制和管理系統中需要佔用匯流排的申請者，

在多個申請者同 時提出匯流排請求時，以一定的優先演算法仲裁哪個應獲得對匯流排的使用權。匯流排判優控制按照仲裁控制機構的設置可分為集中控制和分散控制兩種。

其中就集中控制而 言，常用的匯流排仲裁方式有：菊輪鍊仲裁、二維仲裁、同步通信方式、非同步通信方式和半同步通信方式。

　　連接到匯流排上的功能模組有主動和被動兩種形態，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.分散式仲裁不需要中央仲裁器，每個潛在的主方功能模組都有自己的仲裁號和仲裁器。當它們有 匯流排請求時，

把它們唯一的仲裁號發送到共用的仲裁匯流排上，每個仲裁器將仲裁匯流排上得到的號與自己的號進行比較。

如果仲裁匯流排上的號大，則它的匯流排請求不予 回應，並撤銷它的仲裁號。最後，獲勝者的仲裁號保留在仲裁匯流排上。

顯然，分散式仲裁是以優先順序仲裁策略為基礎。

HW-1.用筆記上的end-to-end與point-to-point的圖,利用該圖的概念找出實際例子 2.何謂 encapsulation請解釋

1.用筆記上的end-to-end與point-to-point的圖,利用該圖的概念找出實際例子
end-to-end
         端到端流程是從客戶需求端出發，到滿足客戶需求端，提供端到端服務，端到端的輸入端是市場，輸出端也是市場。這個端到端必須非常快捷，非常有效，中間沒有阻礙，流程可以很順暢。若達到這麼快速的服務，可以降低許多成本的問題。其實，端到端的改革就是進行內部最簡單的管理體系的改變，形成最精簡的流程。
EX:

    坐火車從台南直達台北，中間沒有停靠任何城市

point-to-point

           點對點通訊協定 (PPP) 是一組標準的通訊協定，可讓不同廠商的遠端存取軟體交互運作。啟用 PPP 的連線可以利用任何產業標準的 PPP 伺服器撥入遠端網路。PPP 從其它廠商所出品之合乎 PPP 標準的遠端存取軟體接收呼叫，並且提供網路存取權。PPP 標準也容許使用舊標準 (如 SLIP) 無法使用的進階功能。PPP 支援數種驗證方法及資料壓縮與加密。藉運用 PPP 的大部份功能，整個登入順序將可予以自動化。PPP 還支援多種 LAN 通訊協定。您可以使用 TCP/IP 或 IPX 作為網路通訊協定。在 Itanium 型版本的 Windows 作業系統上無法使用 IPX/SPX 通訊協定。PPP 是用於安全虛擬私人綱路 (VPN) 連線之 點對點通道通訊協定 (PPTP) 及 第二層通道通訊協定 (L2TP) 通訊協定的基礎。PPP 是大多數遠端存取計算的主要標準。

EX:坐區間車，每個站都要停

2.何謂 encapsulation請解釋
       封裝是物件導向中四大特色之一，簡單來說封裝就是適度的將資訊隱藏(Information Hiding)，避免外界不當使用。在抽象化的過程，善加將定義類別中的屬性跟方法封裝，有利於日後系統維護時造成的許多不必要的問題。

封裝手法：提供受控制的間接操作取代不受控制的直接存取。在系統中最怕的就是不受控制的狀態發生，這對日後的維護非常頭疼，邏輯錯誤在龐大的程式當中要找出來，有時還真的像是大海撈針。

封裝最主要的兩個優勢：

1.避免不必要的資料存取現象發生。利用封裝可以適度的將資料進行適度資訊隱藏。如此避免不必要的存取，進而發生問題。
2.適度將製作細節封裝可以降低ripple effect(漣波效益)，避免日後修改一問題所帶來的連帶效應過大。如此在日後可增加系統的可擴充性、易維護性。

HW 1.Cookie產生的隱私權與法律問題 2. A.P2P架構筆記(3) 的式子用不等式求出 B.把數字或上網收詢數據帶入 P2P架構筆記(3) 的式子 ,並畫出CS架構與P2P架構的圖

1.Cookie產生的隱私權與法律問題
           Cookie是一種能夠讓網站伺服器把資料儲存在客戶端的硬碟,或是由客戶端的硬碟取出資料的一種技術,Cookie能夠追蹤客戶端在網站上的移動路徑。cookie儲存於您的電腦或流動裝置中的小型文字檔案，系統會在您後續瀏覽網頁時擷取cookies。H&M使用cookies以提升及簡化瀏覽程序，我們不會使用cookies儲存個人資料，亦不會向第三方透露資訊。 Cookies可分作兩類：永久cookies及暫存cookies（即工作階段cookies）。永久cookies會以檔案形式儲存於您的電腦或流動裝置中少於12個月；工作階段cookies則只作暫時儲存，在您關閉瀏覽器工作階段後隨即消失。我們會使用永久cookies儲存您的起始頁面選擇。如您登入時選擇「記住我」，我們亦會使用永久cookies儲存您的資料。此外，我們會使用工作階段cookies，方便您使用產品篩選功能，以及檢查您有否登入。

可能觸及的法律：

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

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

HW 1.FTP的使用流程與解釋 2.recursive call vs iterated call 之差別性(用N階來做舉例兩者之間的差異)

1.FTP的使用流程與解釋
  文件傳輸協議（File Transfer Protocol, FTP）是一個用於在兩台裝有不同作業系統的機器中傳輸電腦文件的軟體標準。它屬於網路協議組的應用層。FTP是一個8位的客戶端-伺服器協議，能操作任何類型的文件而不需要進一步處理，就像MIME或Unencode一樣。但是，FTP有著極高的延時，這意味著，從開始請求到第一次接收需求數據之間的時間會非常長，並且不時的必需執行一些冗長的登陸進程


主動模式（Active Mode）
FTP Client 隨機選擇的TCP port（通常＞1024）呼叫FTP server 的port 21請求連線。進行「TCP Three-Way Handshake」當順利完成「TCPThree-Way Handshake」之後，便建立「命令連線」的通道，這個連線通道僅能進行FTP 的「指令」。
   

被動模式（Passive Mode）
建立「命令連線」的通道的方式和主動模式一樣，但是如果需要資料傳送，就是要建立「資料連線」通道時，Client 會送出PASV（Passive）指令，告訴FTP Server，要利用被動模式建立「資料連線」通道。
當 FTP Server 收到PASV 指令時，便會在某個>1024 port 上Listen，等待

FTP Client 來建立資料連線通道，並利用命令連線通道告知FTP
Client：「我在那個Port 上等你連線」。
然後 FTP Client 會隨機再選一個>1024 的port 向FTP Server 所告知port進行Three-Way Handshake 並建立「資料連線」通道連線。因為這種「資料連線」通道建立方式是FTP Server 被動等FTP Client 來連線，故稱為「被動模式（Active Mode）」。

2.recursive call vs iterated call 之差別性(用N階來做舉例兩者之間的差異)
   recursive:
      所謂遞迴就是允許一個 Procedure 或 Function 呼叫自己本身。當然，他不能無限制地呼叫自己，否則將造成無窮迴圈，所以它都會伴隨一個「終止狀況」(Termination Condition)，當程序執行至此終止狀況成立時，便不再呼叫自己，而獲得所求，並傳遞迴呼叫端。

iterated:

      概念上，就是有某 個變數，它的值被一次又一次地代換成新的數值， 而每次代換之後都做同樣的動作。 通常程式語言提供三種迭代的語法：for 迴圈、while 迴圈和 do-until 迴圈。 在此我們先講 for 迴圈 (for-loop)。 技術上，我們要學習各種程式語言所提供的迭代語法。

HW 1.找一個HTML語法的 (Client-Server) programming 然後對這支程式內容做解釋 2.如何提高Cache的hit ratio?

1.找一個HTML語法的 (Client-Server) programming 然後對這支程式內容做解釋
    <!-- 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 -->

讓網頁具有 Google 搜尋功能

標準語法:<a href="想連結網址">連結地的名稱</a>＝＝＝可與其它網站連結

2.如何提高Cache的hit ratio?

     絕大部分CPU都有一個cache，許多CPU還有二級cache（相對於一級cache，二級cache容量大一些，但是速度慢一些）。如果在訪問數據時，數據沒有在cache中，則成為cache沒有命中（cache miss），這是需要將數據從內存加載到cache中，這個過程非常慢，因此要盡量保證cache的命中。

如果提高cache的命中率呢？要將頻繁訪問的數據集中存放：將頻繁訪問的數據按照順序保存，而不要使用指針。這樣，最常用的數據會盡可能的保存在一級cache中。順序訪問數據：在cache miss後，包含需要訪問數據在內的一段數據會被加載到cache中，如果順序訪問，就可以提高cache的命中。避免同時遍歷多個比較大的數據buffer：多個緩衝區在cache上互相衝突對導致cache miss的概率提高。

HW-1.IPC相關應用與解釋 2.program counter 如何時做 在電腦中應用在哪 3.找一個Socket programming 然後對這支程式內容做解釋

1.IPC相關應用與解釋
         進程間通信（IPC，Inter-Process Communication），指至少兩個進程或線程間傳送數據或信號的一些技術或方法。線程是計算機系統分配資源的最小單位。每個進程都有自己的一部分獨立的系統資源，彼此是隔離的。為了能使不同的進程互相訪問資源並進行協調工作，才有了進程間通信。這些進程可以運行在同一計算機上或網絡連接的不同計算機上。進程間通信技術包括消息傳遞、同步、共享內存和遠程過程調用。IPC是一種標準的Unix通信機制。
  

實作:命名和匿名管道，信號標共享，內存消息隊列.....

2.program counter 如何時做 在電腦中應用在哪(需寫出與compiler and linking loader and assmbler 之間的關係)
          程序計數器（英語：Program counter），或在某些 電腦中稱為指令指標（Instruction Pointer），是在電腦 處理器中的一個 暫存器，用來指示電腦正在執行的指令序列。依照特定機器的細節而不同，他可能是保存著正在被執行的指令，也可能是下一個要執行指令的地址。程式計數器在每個指令週期會自動地增加，所以指令會正常地從暫存器中連續地被取出。某些指令，像是跳躍和子程序呼叫，會中斷程序執行的序列，將新的數值內容存放到程序計數器中。在大部分的處理器，指令指標都是在提取程式指令後就被立即增加；也就是說跳躍指令的目的位址，是由跳躍指令的運算元加上跳躍指令之後下一個指令的位址 (位元或位元組，是電腦形態而定) 來獲得目的地。

3.找一個Socket programming 然後對這支程式內容做解釋
       

主從式架構模型(Client/Server model)

        每個網路應用程式都有一個通訊端點，一種端點是用戶端，另一種是伺服器。根據定義，用戶端會先送出第一個封包，由一個伺服器接收。在初步接觸後，用戶端和伺服器均能開始收送資料。

依據socket所提供的服務來將它分類，然而在用戶端和伺服器上的這兩個sockets必須是同一類才能互相通訊，也就是說，他們必須都是stream(TCP)或都是datagram(UDP)。用戶端的應用程式必須要能找到並識別伺服器的socket，而伺服器會將它的socket命名以讓用戶端識別，就TCP/IP而言，一個socket name包括了IP位址、連結埠編號、以及協定本身。用戶端可用Windows Sockets的名稱伺服函式來查到標準伺服器的連結埠編號，而如果知道伺服器的主機名，則可以Windows Sockets的主機名稱分析函式，來查得伺服器的IP。當用戶端socket成功地聯繫上伺服器端之socket後，這兩者便形成一個“結合”(association)。在此時，每個socket都可以由它的名字及對方的名字所形成的組合加以識別。這個結合包括五個要素：所用的協定、用戶端IP位址、用戶端連結埠號碼、伺服器端IP位址、伺服器端連結埠號碼。這個“結合”的觀念並不只是Windows Sockets程式設計的基礎，它也是一般網路通訊的重要觀念。在結合中的資訊可識別及引導封包通過網路，從這一端的程式傳至另一端。

所有的網路應用程式皆可分為五個步驟：

• 開啟一個socket :
          Socket是通訊的端點，好比是電腦的網路介面卡，使得網路應用程式可以像介面卡插在主機板上一樣，插入網路中。一般說來你只會有一片網路卡在電腦中，但是你可以有許多sockets，而且它們也可以同時使用一片網路卡。用戶端與伺服器端都需要一個socket以存取網路資料，使用socket()函式呼叫就可開啟一個socket。(如圖一所示)
• 為socket命名:
            伺服器端的程式必須為它的socket命名，這樣用戶端才能找到並正確地辨識出它的socket，如果伺服器沒有替它的socket命名，則協定堆疊會拒絕用戶端要通訊的請求。要幫socket取名必須設定三個參數：協定、連結埠號碼、及位址，而用戶端就要用這些值來和伺服器建立連結。要為socket命名，伺服器必須為socket位址結構設初始值並呼叫bind()函式，以指定本身連結埠號碼和IP位址，完成命名的工作。
• 與另一個socket結合:
            假設我們在用戶端與伺服器端均開啟一個socket，並至少為伺服器端的socket命名。接下來伺服器要準備接收封包，而用戶端要準備發送封包，當此準備工作完成後，此兩端的sockets就叫建立一個”結合”(association)。如何為結合此兩端的socket做準備呢?在WinSock API中提供了幾個函式來完成此動作。在伺服器端則以呼叫listen()來準備接受用戶端送來的連結要求，如果收到連線要求，則開啟另一個新的socket來和用戶端進行連線(使用accept()函式)；而在用戶端則是呼叫connect()函式與伺服器端的socket完成結合。
• 在sockets間收送資料:
              此時我們已經在用戶端和伺服器的sockets間建立了結合，也就是說，我們已經可以開始收送資料了。如何收送資料呢?在一個已連結的socket上收送資料可呼叫recv()與send()來完成；而在一個無連結的socket上收送資料可呼叫recvfrom()與sendto()來完成。
• 關閉socket
          當用戶端完成收送資料且往後並不會在使用時，必須關閉socket，對TCP socket而言，關閉socket除了將socket的資源還給協定堆疊，此外並嘗試將以建立的連結關閉。但對UDP socket而言，則是單純地將資源還給協定堆疊。關閉socket可呼叫closesocket()來完成。

TCP Socket Connection

UDP Socket Connectoin

圖一 Socket程式簡圖

HW.舉例 transparent and virtual的應用

 transparent：透通
           意思：實際上有，但是使用時感覺它好像不存在
           例：開車時，你不必了解車的內部構造，零件 .你也可以開車
 virtual：虛擬
           意思：實際不存在，但在使用時存在
              例：虛擬記憶體，你並沒有那麼多的記憶體，但你卻能使用到它

HW4 請描述ASCII的功能 與 EBCDIC的功能?

ASCII的功能

        美國信息交換標準代碼( American Standard Code for Information Interchange, ASCII )簡潔的說就是用7位數字來表示字母或其他符號。在計算機中，所有的數據在存儲和運算時都要使用二進制數表示（因為計算機用高電平和低電平分別表示1和0），例如，象a、b、c、d這樣的52個字母（包括大寫）、以及0、1等數字還有一些常用的符號（例如*、#、@等）在計算機中存儲時也要使用二進制數來表示，而具體用哪些二進制數字表示哪個符號，當然每個人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那麼大家就必須使用相同的編碼規則，於是美國有關的標準化組織就出台了所謂的ASCII編碼，統一規定了上述常用符號用哪些二進制數來表示。

EBCDIC的功能

  主要用在IBM計算機中的EBCDIC代碼(Extended Binary Coded Decimal Interchange Code)。它採用8位碼,有256個編碼狀態,但只選用其中一部分。0-9十個數字符的高4位編碼為1111,低4位仍為0000-1001。大、小寫英文字母的編碼同樣滿足正常的排序要求,而且有簡單的對應關係,即同一個字母的大小寫的編碼值僅最高的第二位的值不同,易於識別與變換。

HW3-何謂overhead?

何謂overhead?

     所謂的Overhead就是指電腦在運作上所作出多餘的動作以人的動作作為例子，走路時只要一隻腳保持在前方就可以往前邁進。然而，當你走路時，將腳抬高30度，再右走15公分，再向左走15公分，再往前邁進。如此一來，向右15公分，再向左15公分這個舉動就是多餘的。如此的動作在計算機(電腦)上，就是Overhead。

HW2-敘述何謂二分搜尋法? 自己設一個數列來做舉例 並告訴我二分搜尋怎麼使用 還有何謂二元樹(binary tree)? 並舉例作圖~

何謂二分搜尋法?

       用以搜尋已排序的一串資料。其原理為將欲搜尋的值，與所有資料的中間值(中位數)做比對。

舉例:我用[ 10 12 15 14 13 11 16]來做二分搜尋法，先利用各種排序法(快速排序，選擇排序，泡沫排序，循序排序...)將資料做大小排列成[ 10 11 12 13 14 15 16 ]

 我要如何找到12這個數字呢?

      由於中間值13大於搜索值12。因此我們可以知道，在13之後的資料皆大於搜索值12，接著，由於13之前資料中的中間值1小大於搜索值12。我們可以知道，在11之前的資料皆小於搜索值12。最後我們就找到了搜索值12。

     圖:

          第一次[ 10 11 12 13 14 15 16 ]

          第二次[ 10 11 12 ]

          第三次[ 12 ]

在二元樹中 我該怎麼在樹中查到我要的數字呢?

      (1)從樹的樹根 (root) 開始，和每個節點比較

    (2)如果現在這個數字，比現在這個節點的數字小，往左邊的子樹 (sub-tree) 走，否則就往右走

       (3)重覆步驟(2) ，比較新遇到的節點，和現在輸入的數字。如果已經走到樹的結尾，就停止。

        圖:                         13

                               11          15

                         10     12  14      16     

                                                 

   

HW1-雞兔同籠的問題

雞兔同籠,有10個頭,32條腿,雞、兔各有幾隻?

算數:
      如果全部都是兔子,總共有4*10=40條腿,可是實際上只有32條腿,少了8條腿,所以"全部    都是兔子"的假設錯誤,而且可推得當中有4隻雞,答案是4隻雞和6隻兔.

數學:
      假設雞有X隻,兔有Y隻,可得{x+y=10      
                                      {2x+4y=32
      故解x=4,y=6
      =>雞有4隻,兔有6隻