---
# System prepended metadata

title: OS Chpater3
tags: [作業系統]

---

# OS Chpater3
###### tags: `作業系統`
:warning: <font color=#ffa07a>橘色字體標題為老師強調要背的</font>

## *Process Concept*
Program : 通常以 **executable file** 的型態存放在 disk 中 (*passive*)
    
:arrow_down: loaded into memory

**Process** : 一個正在執行的program (*active*)

:::success
#### When program is loaded into memory
![](https://i.imgur.com/J3fS1by.png)

- 返回位址及參數傳遞放在stack

- 動態配置記憶體放在heap

- 全域變數放在data

- 當程式碼轉成組合語言之後儲存在text
:::

## <font color=#ffa07a>*Memory Layout of a C program*</font>
![](https://i.imgur.com/7Rm7eu0.png)
---

![](https://i.imgur.com/f5pFKxp.png)
:::success
- function中的static變數 :arrow_forward: 配置於global data裡的uninitialized data中，只有這個function可以存取

- 如果data area是static的話 : 這個變數只有這個檔案可以存取到
:::

## <font color=#ffa07a>*Process State*</font>
![](https://i.imgur.com/3RKdani.png)
:::success
- New : 載入時，新的process產生
- Running : 指令正在被執行
- Waiting : process正在等待某個事件發生
- Ready : process正在等待被指派到CPU
- Terminated : process執行完成
:::

:::info
- running :arrow_right: 執行結束 :arrow_right: terminated

- running :arrow_right: I/O :arrow_right: waiting

- running :arrow_right: interrupt / 分配時間到了(clock時脈) :arrow_right: ready(等待再被排進去)
:::

## *Process Control Block(PCB)*
- 別稱 : **task control block**
- 何為PCB : process的各種資訊

![](https://i.imgur.com/AIX6qr4.png)

## *Process Scheduling*
當process停止執行，但它又還沒完成整個執行的時候它就必須等待再一次被執行，又因為不是只有一個process要被執行，所以就必須對每一個process排隊

:::success
#### scheduling queues
- Ready queue : 進入ready state之後有ready queue
- Wait queue : 進入waiting state之後有wating queue，通常會有不同條的queue
:::

## *CPU Switch From Process to Process*
**context switch** 
: 當CPU要交換process執行的時候，它會透過context switch先將舊的process狀態儲存到PCB，再載入新的process之前的狀態繼續
![](https://i.imgur.com/DylEa3l.png)

## *Process Creation*
- **parent process**可產生**children process**, 而每一個新產生的process都可以再產生其他process, 進而產生tree的結構
- 系統透過**process identifier(pid)** 來辨識不同process
- 在unix系統中
	- **fork()** 
	    : 用來產生new process
	- **exec()** 
	    : 載入new process，替換掉原先process的memory
	- Parent process 呼叫 **wait()** 等待child process完成
	- 當child process完成後呼叫 **exit()**
![](https://i.imgur.com/WG6Fh3Q.png)

## <font color=#ffa07a>*C Program Nest-Forking Process*</font>
:warning: 這邊的code最好自己tracing過一次 (~~但我看不太懂:shit::shit::shit:~~
![](https://i.imgur.com/i3hwRG1.png)

## *Process Termination*
- 當process已經結束，而parent process尚未呼叫wait()，此process稱為**zombie**。一旦parent process呼叫wait()，zombie process的pid和儲存在PCB上的狀態就會被釋放。

- 若沒有parent process呼叫wait()，則該process成為**orphan**。通常系統會自動成為其parent process，使orphan可以被terminated

## Interprocess Communication (IPC)
- process可被分為
	- **independent process** 獨立行程
	- **cooperating process** 合作行程
- 系統支援cooperating process 原因如下:
	- Information sharing 資訊共享
	- Computation speedup 加速運算
	- Modularity 模組化
- cooperating process 需要有 **interprocess communication (IPC)** 的機制，讓彼此間交換資料
- IPC 有兩種基本模式
	- **shared memory**
	- **message passing**
![](https://i.imgur.com/IkVFI7i.png)

## Interprocess Communication – Shared Memory
- Producer-Consumer Problem
    - producer process 產生資訊
    - consumer process 消耗資訊
- 建立一個包含數個欄位的共用緩衝區(buffer)，提供producer和consumer來讀寫，而buffer的類型大致可分為以下兩種:
    - **bounded buffer** 
        : 有限緩衝區，buffer大小固定。
    - **unbounded buffer** 
        : 無限緩衝區，對buffer大小沒有限制，producer可以不斷產生新的欄位。

![](https://i.imgur.com/mNHMpYQ.png)

## Interprocess Communication – Message Passing
- Message Passing至少需提供以下兩種操作:
    - **send**(message)
    - **receive**(message)
- 若 P 和 Q 要溝通，須先建立**communication link**
    - **direct communication** 
        : 指定接收者與傳送者的名稱
        - e.g. send(P, message);  receive(Q, message)
        
    - **indirect communication** :
        1. 產生一個新的mailbox (A)
        2. 經由mailbox傳送訊息
        3. 完成後刪除mailbox
        - e.g. send(A, message);  receive(A, message)

## Synchronization
- **synchronous** 又稱 **blocking**
    - **blocking send**
        : the sender is blocked until the message is received
    - **blocking receive**
        : the receiver is  blocked until a message is available
- **asynchronous** 又稱 **non-blocking**
    - **non-blocking send**
        :  the sender sends the message and continue
    - **non-blocking receive**
        : the receiver receives a valid message or null message
- If both send and receive are blocking, we have a **rendezvous**

## Buffering
1. **Zero capacity** 
    ~ no messages are queued on a link.Sender must wait for receiver (rendezvous)
2. Bounded capacity 
    ~ finite length of n messages Sender must wait if link full
3. Unbounded capacity 
    ~ infinite length Sender never waits

## Examples of IPC Systems - POSIX
- POSIX shared memory，在POSIX系統實作共用記憶體
    1. shm_open() 建立共用記憶體物件
        : e.g. shm_fd = **shm_open**(name, O CREAT | O RDWR, 0666);
    2. ftruncate() 設定物件大小
        : e.g. ftruncate(shm_fd, 4096); 
    3. mmap()
        : 建立一個包含shared memory物件的對映檔案，利用mmap()回傳的pointer，存取shared memory

## Pipes
- 在實作pipes時，有四個issues須考慮:
    1. pipe是否允許單向或雙向通訊 unidirectional or bidirectiona
    2. 若pipe為雙向通訊，那是半雙工或是全雙 half or full-duplex (資料是否可以同時在兩個方向傳輸)
    3. 兩個行程是否需存在關係 (e.g. **parent-child**)
    4. 是否需透過網路通訊
### Ordinary Pipes
- Producer writes to one end (the **write-end** of the pipe)
- Consumer reads from the other end (the **read-end** of the pipe)
- Communication is unidirectional
- Windows calls these **anonymous pipes** (匿名管道)
![](https://i.imgur.com/bFNpBmf.png)

### Named Pipes
- Named Pipes are more powerful than ordinary pipes
- Communication is bidirectional
- No parent-child relationship is necessary between the communicating processes
- Several processes can use the named pipe for communication
- Provided on both UNIX and Windows systems

## Communications in Client-Server Systems
- Sockets
- Remote Procedure Calls (RPC)

### Sockets
- **socket** is defined as an endpoint for communication
- Concatenation of IP address and **port**
- The socket *161.25.19.8:1625* refers to port *1625* on host *161.25.19.8*
- All ports below 1024 are *well known*, used for standard services
- Special IP address 127.0.0.1 (**loopback**) to refer to system on which process is running
![](https://i.imgur.com/d4iuBOZ.png)

### Remote Procedure Calls
- 透過middleware實現
- **Stub**
    - client-side proxy for the actual procedure on the server
    - stub 由client端提供，當 client端需遠程連線時，由RPC系統呼叫適當的 stub ，透過 stub 將參數傳遞給 server ，並且 **marshalls** the parameters(重排參數)，協調統一參數格式
- 在 Windows 系統中，stubs code 是由 **Microsoft Interface Definition Language (MIDL)** 寫的規格編譯而成
- data 會以**External Data Representation (XDL)** 的方式呈現，以利在 **Big-endian** 或 **Little-endian** 的架構下的皆可使用
- Remote communication has more failure scenarios than local . Messages can be delivered **exactly once** rather than **at most once**
- OS typically provides a rendezvous (or **matchmaker**, portmaker) service to connect client and server
> - 解釋一下上面兩點 : 因遠端通訊比起local更容易失敗(掉封包)，因此我們希望message至少能送達一次，而不是最多只能送一次。解決辦法是透過matchmaker作為媒人，RPC會先與matchmaker通訊，並透過matchmaker得到port後，才利用port向server進行procedure call

![](https://i.imgur.com/DrlfqjP.png)
