---
# System prepended metadata

title: Distributed system
tags: [OS]

---

<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
            * ![](https://i.imgur.com/RV5X6uU.png)
            * Call
            ![](https://i.imgur.com/p23rmZE.png)

            * Return
            ![](https://i.imgur.com/RTMV3Of.png)

        * `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`