<style>
H2{color:#BF0060 !important;}
H3{color:#009393 !important;}
p{color:Black !important;}
li strong {color:#4682b4 !important;}
</style>

# Distributed system
## **Intro**
### **3 type of Parallel system (not distributed)**
* **Multiprocessor**
* `UMA : direct access to shared memory`
* same latency from P to M
* <img src="https://i.imgur.com/bk7inUK.png" width = "300"/></img>
* `Interconnection`
* Bus-base
* potential performance bottleneck
* 用 cache 解決瓶頸
* <img src="https://i.imgur.com/vySimQv.png" width = "300"/></img>
* Switched-base
* omega switching 較省錢
* <img src="https://i.imgur.com/a6elCXZ.png" width = "500"/></img>
* **Multicomputer parallel**
* `NUMA : NO direct access to shared memory`
* Not uniform memory access
* <img src="https://i.imgur.com/67C9k59.png" width = "300"/></img>
* Processors should be tightly coupled (ㄧ樣電腦)
* No common clock : 無法同步
* `Interconnection`
* <img src="https://i.imgur.com/lMde91g.png" width = "500"/></img>
* **Array processor**
* `專門用途：ex 矩陣運算`
* <img src="https://i.imgur.com/Emrd4kw.png" width = "400"/></img>
* co-located, tightly coupled, common system clock
### **Distributed system (DS)**
* **Typical view**
* <img src="https://i.imgur.com/OGj6g2M.png" width = "300"/></img>
* 跟 multicomputer 不同處 : 電腦異質性
* **OS**
* <img src="https://i.imgur.com/SuzWKiD.png" width = "600"/></img>
* <img src="https://i.imgur.com/8xhJz3t.png" width = "300"/></img>

* `Distributed OS`
* 將 homogeneous multicomputers 的 processors 統一管理
* `Network OS`
* Loosely-coupled OS for heterogeneous multicomputers
* 應用範例
<img src="https://i.imgur.com/lqyyLIn.png" width = "300"/></img>
* **communication means**
* `OS abstraction `
* 目的：讓 Distributed Shared Memory ---(透過OS)---> 看起來像一塊 shared memory / virtual memory
* 問題 : 資料在其他電腦導致 page fault，需透過 communication 要求資料 => poor performance，因此不常用
<img src="https://i.imgur.com/dr5pZSK.png" width = "300"/></img>
* `Programming language abstraction`
* 目的 : 讓 user 感覺 function call 像 local call
* 實作 : Remote Procedure Call (RPC) (poor choice)
* `Message-oriented communications`
* Message-passing model
* socket programming
### **Remote Procedure Call (RPC)**
* **示意圖**
* <img src="https://i.imgur.com/FQY6Xq4.png" width = "300"/></img>
* **RPC system 配備**
* `stub generator` (protocol compiler)
* Stubs perform the conversion of the parameters, ==packing arguments and results== into msgs.

* Procedure
* 
* Call

* Return

* `run-time library`
* Naming
* ex : 透過 hostname(向DNS要IP), port 找到 RPC
* Decide transport-level protocol for RPC
* TCP : inefficient
* UDP : efficient, but need providing reliability to the RPC
* timeout/retry 機制
* 發送 Keep-alive 訊息
* Fragmentations for large args
* **Problem**
* `Reference parameters (pointers...)處理`
* simple sol1 :
* forbid using reference params
* simple sol2 :
* Copy the referenced memory to server and change the pointer.
* Then AND the results send back with the referenced memory.
* 同步問題：未回傳但 client 端又 write 這塊 referenced memory.
* Better sol :
* Send the pointer to the server
* Server 執行程式，但需要 write referenced memory 時，交由 client 端修改
* `Byte ordering`
* 16-bit/32-bit integers
* Little-endian(intel) or Big-endian(Sparc)
* 例如 129.240.71.213
* HEX : 0x81 0xf0 0x47 0x8b
* Little-endian : 0x81f0478b
* Big-endian : 0x8b47f081
* Network 採用 Big-endian
* Sun’s RPC package 使用 eXternal Data Representation (XDR) 檢查 endian
* intel x86 需要 XDR 轉 little-endian
<img src="https://i.imgur.com/BWS7CC0.png" width = "300"/></img>
* `Synchrony`
* RPCs 可做成 synchronous 或 asynchronous
<img src="https://i.imgur.com/qCLLfYf.png" width = "800"/></img>

## **Message Passing models**
### **Msg passing vs. others**

* | | OS abstraction| Programming language abstraction | Msg passing|
| -------- | -------- | -------- | -------- |
|| 將 distributed memory 包裝成 shared memory | 包裝成 function call ||
|溝通方式| Processors communicate via shared data variables space|RPC|exchaning msgs|

### **primitive Send() and Receive()**
* There are User buffer & Kernal buffer
* <img src="https://i.imgur.com/dIMhWDE.png" width = "250"/></img> <img src="https://i.imgur.com/6Dt26Zo.png" width = "350"/></img>

### **Primitive 分類**
* **1. Sender & Receiver 之間**
* 分成 ==Synchrnous or Asynchrnous==
| send | receive|
| ---- | ------ |
| Syn / Asyn | Syn |

* `Synchronous send`
* 目的：確保對方收到
* 分類：根據 send() completes 時間
* (1) Receipt-based : 收到對方發的 Ack
* (2) Delivery-based : 送達對方 process
* `Asynchronous send`
* Send() completes when data 已從 usr copied 到 kernal buffer
* No-handshake，不理會對方是否收到
* `Note`：send() completion time 從小到大
* Asyn send < Receipt-based Syn < Delivery-based Syn

* **2. OS & process 之間**
* 分成 ==blocking or non-blocking==

| send | receive|
| ---- | ------ |
| b / non-b | b / non-b |
* `Blocking`
* Application call 下去後，要等到 primitive send()/receive() 完成才 return
* `Non-blocking`
* Application call 下去，立刻 return
* (1) Send : 還沒 copy 到 kernal buffer 就return (even before data copied out of user buffer)
* (2) Receive: 資料還沒來就 return (even before data may have arrived from the sender)
* Note : 此處的 non-blocking 類似 asynchrnous IO 完全不等的概念
* Review :
* asyn IO 以外都算 syn IO，因為其他人在 recvfrom 從 kernel 複製資料到 user 時都會被 block。
* non-blocking IO 雖然也是立刻 return，但需 polling 得知完成與否 (過陣子再來找你，某種意義上仍是wait)，asynchrnous 意義上才是真正完全不等你，task 完成會發 signal 通知
## **Socket Programming**
### **TCP connection**
* **3-way handshake of Establishment**
* ```sequence
Note left of client: socket, connect\n(active open)SYN_SENT
Note right of server: socket, bind, listen\n Listen(passive open)\n accept
client->server: SYN(j)
Note right of server: SYN_RCVD\n放進incomplete connection
server-->client: SYN(k), Ack(j+1)
Note left of client: connetz returns\n Established
client->server: Ack(k+1)
Note right of server: Established\n accept returns

* **TCP Connection Release**
    * ```sequence
        Note left of A: data flow from A \nto B is terminated
        A->B: FIN(SEQ=x)
        B->A: Ack(x+1)
        Note right of B:half-closed 半關閉\n把 result buffer 清空
        B->A: data
        B-->A :...
        B->A:FIN(y)
        A->B:Ack(y+1)
        Note right of B:data flow from B \ntoA is terminated

* **4-way handshake of Terminsation**
    * ```sequence
        Note left of client: close\n(active close)FIN_WAIT1
        client->server: FIN(m)
        Note right of server: CLOSE_WAIT(passive close)\n read returns 0
        server-->client: Ack(m+1)
        Note left of client: FIN_WAIT2
        Note right of server:close\nLAST_ACK
        server-->client: Fin(n)
        Note left of client: TIME_WAIT\nclose after 1~4 mins
        client->server: Ack(n+1)
        Note right of server: CLOSED
        Note left of client: CLOSED
        
###### tags: `OS`