# OS-Chap3 - Process_行程
###### tags: `作業系統 Operating System note`, `110-1`, `2021`
###### 參考資料 : [行程間的溝通](http://debussy.im.nuu.edu.tw/sjchen/OS/97Spring/Ch_7.pdf), [作業系統筆記](https://chentsungyu.github.io/2020/03/21/OS/%5BOS%5D%20%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1%E7%AD%86%E8%A8%98-Process/), [作業系統-Process](https://www.namepluto.com/%E4%BD%9C%E6%A5%AD%E7%B3%BB%E7%B5%B1-process/), [作業系統簡介(下)](http://enews.open2u.com.tw/~noupd/book_up/1746/8719.htm)

# Contents
[TOC]

---
# Process Concept
## Process v.s. Program
- Process = 行程。**正在執行中的程式。**
- 主動。
- **一個 program** 在 **memory(記憶體)** 中執行。
- 帶有 program counter，用來指出下一個指令的位置。
- Program = 程式
- 被動。
- 以 binary 的方式儲存在 disk (硬碟)中。

:star2: **一個 program，可以是多個 processes**
:star: ∵ 多個使用者再執行同個 program

>>>>>>>>>>>>>>>>>>>>>>>>> -----

## 一個 Process 包含的東西
- Code Segment(=Text Section)
- 程式碼、PC、暫存器…。
- Data Section(資料區間)
- 全域變數(Global Variables)
> - uninitialize : BSS
> - initialize :
- Stack
- 暫時性資料
- 方便使用後直接 pop 掉(結束)
- ex. 區域變數(Local Variables)
- ex. 函式的參數(Function parameters)
- Heap
- 動態配置記憶體(變數/類別class)
- Current Activity
- Program Counter(計數器) : 存放下個被執行 program 的 address
- Processor register : 就是處理器的暫存器

## Five state of Process
### Process STD → 行程狀態圖
>- Process State Transition Diagram
- 描述 **Process 由開始到結束的生命週期 (Life-Cycle)**，而一個Process在此週期中會經歷數種狀態。


- ### Transition :
1. new → ready
- admitted : 引入/產生一個新的 program 到電腦執行。
> - OS 在此時會確認有沒有足夠的資源去 create process，也會檢查權限(Protection)，成功的話進入 Ready
2. ready → running
- schedular dispatch : 從 memory 挑選一個 process 到 CPU 執行。
3. running → terminate :white_check_mark:
- exit : process 完成他的 task/ job，就結束。
4. running → ready :heavy_check_mark:
- 發生**短暫中止**時。
- interrupt/ 被高 priority process 插隊/ CPU Time Quantum 超過。
5. running → waiting (block) :white_check_mark:
- 發生**較長時間的中止**時。
- wait for resource available
- wait for I/O or event completion
6. waiting → ready :heavy_check_mark:
- I/O or event completion

:white_check_mark: 為 process **主動**放棄執行權 **non-preemptive**
:heavy_check_mark: 為 process 被動放棄執行權 preemptive

:exclamation: 若一個系統只有 process **主動** 放棄執行權，並重新進行排程時，此系統為 **non-preemptive** ，反之則稱為 preemptive :exclamation:
> ref to chap 5 scheduling

- ### State
- new：產生新的 Process
- 準備要將 Program load 到 memory，initial 各個 section
- ready：
- Process 競爭 CPU，在 queue 裡面等著被 OS schedule 後，被分配至CPU執行。
- 當 I/O 事件結束 or 執行期間(running)被Interrupt ， Process 都會回到ready狀態
- running：執行中的 Process
- wating：當有其他事件(Event)發生時，(ex.週邊設備的I/O)，會進入暫時等待的狀態。
:heavy_exclamation_mark:Process此時雖然還在記憶體中，但不在Ready Queue
- terminated：Process執行結束

- ### Queue
> - 同下方 scheduling queue
- Job Queue : 系統中的所有的 Process 形成的隊伍(list)
- Ready Queue : 放在記憶體中多個 Process 形成的隊伍(list)，準備隨時可以被分配至 CPU 內執行(running)

:heavy_check_mark: 同個時間，一次只可以有一個 process 在 running 中執行:heavy_check_mark:
:heavy_check_mark: 同個時間，可以有多個 processes 在 ready 和 waiting 中執行:heavy_check_mark:

#### 此 STD 是針對 CPU 這項資源，且 data 都在 Memory中。

## Process management
- ### PCB(Process Control Block)行程控制表
> = TCB(Task Control Block)
- 存在 memory 中。
- 每個 process 都有各自的一個 PCB。
- **用來記錄該 process 在被 context switch 前的資訊。**

## PCB 包含以下資訊

- Pointer : 連接下一個 PCB (?)
- Process State (行程的狀態)
- process 在哪一個狀態
- ex. ready, waiting, running
- Process number = Process ID (Process identify)
- Process counter
- 指明該 process 下一個要執行的指令 address。
- 在尚未要被 context switch 前，只會存和 PCB 頭的相對位置。
- 當準備被 context switch 前，會將 PCB head 的位置加上目前的相對位置，再存回此。
- CPU register
- CPU scheduling information
- priorities : Process 的優先順序
- memory manegement
- memory limit
- 0x00~0xC0000000 : memory
(可連接至上方 : Process 包含的東西/Current Activity/Process register 的圖片)
- accounting infor.
- 用掉多少 CPU 的時間
- 使用 CPU 的最大時間量
- I/O status infor.(list of open file)
- 尚未完成的I/O Request還有哪些
- 還在 I/O Queue中排隊之Process的編號

#### :heavy_exclamation_mark: OS 為了管理Process 方便，會存一份 PCB 在 OS 所在之 Monitor Area 中。:heavy_exclamation_mark:

## Context Switch
- 轉換 CPU 至另一個 process 時(p0→1)，必須將舊 process 的狀態存起來(存入PCB0)，再載入新 process (從PCB1)的 data 至 CPU
- Context Switch 所花費的時間對系統而言是 **額外的浪費 (overhead)**。
- 因為在 switch 的過程中，系統所做的事是不具有生産力的工作。
- Context Switch 的速度
- 主要取決於 **硬體 (hardware)** 支援的程度。
>- #### Solution to decrease context switch burder
> 1. 提供多套 Register Sets
> - 毎個Process皆可有自已的Register Set (若Register數量夠多)
> - 當需要做Context Switching時，**OS只要切換 Register Set 的指標**到新Process即可
> - 速度快(不會用到 memory 存取)、但不適用 register 數量少的系統
> 
> 2. 用 thread 代替 process
> - 毎個 Process 都有自己的 PDB(私有)，這些私有資訊會佔用 register。
> - **Threads之間彼此可以共享Memory Space** (ex. Code Section,
Data Section, Open File)
> - ∴ Context Switch 時**不須大量的 Memory Access**
> 3. register 有限時
> - 當Register有限時，視哪一種類的Process切換較頻繁。
> - System Processes 與 User Processes 都有自已的Register Set
> ∴當 User Process 與 System Process 之間 Context Switch 時，**OS只要改變Register Set的 pointer 即可**。
> 

# Threads(線程)

---

# Process Scheduling
- Multiprogramming : CPU一直在running，達到最大效能
- Time sharing : 一直切換 CPU 執行的process，讓使用者覺得在互動
- processes 必須等到 CPU free 才能被重新排程

## Scheduling Queue
- process 在不同的 queue 做切換（在state的切換）
- Job Queue（New state）
- 在 disk 等待被抓入 ready 的所有行程
- Ready Queue（Ready State）
- 在 memory 等待抓進去 running 的行程集合(process set)
- Device Queue（Wait State）
- 等待 I/O device 的行程集合(process set)

# Process Scheduling (行程的排程)--大排程
> 為了讓 CPU 發揮最大的效益，需 process scheduler 決定分配哪個 process 能使用CPU___猜。


## Long-Term Scheduler
- 亦稱 Job Scheduler
- 從 job queue 挑選合適的 process ，能從 disk(磁碟) 排進 memory。(以控制 memory 內 process 的數量)
⇨ Control Multiprogramming Degree __(視CPU或Mem.的使用率高低而定)
- 從 disk(磁碟) load 進 memory 的時間，相較於 memory 之間傳遞資料(Short-Term Scheduler) 所花費的時間長。
- ### disk → memory
> - 執行頻率最低
> - 通常適用於Batch System，但不適用於Time-Sharing及Real-Time System。
> - 可調合CPU-Bound與I/O Bound之混合比例 (∵可視資源負荷決定載入Job與否)。
> UNIX/NT 沒有此 scheduler

## Short-Term Scheduler
- 亦稱 CPU Scheduler
- **Ready → Running**
- 決定 memory 中的哪個 process 能排進 CPU running
- 只作 memory 進入 CPU 的決定，花費的時間極短
- ### memory → CPU (?)
> - 執行頻率最高
> - ∵毎個Process執行時狀況很多，如：不同情況的中斷…等。
> - 各種系統均需要 (Batch System, Time-Sharing, Real-Time System)
> - ∵毎種系統都有CPU嘛。
> - 無法調整 Multiprogramming Degree 及 I/O Bound 與CPU Bound Job 之混合比例

## Medium-Term Scheduler
- **Virtual Memory** ????
- 保留long-term scheduler功能
- 採Swap(交換)的形式，將放在 memory(Ready Queue) 中的 Process 搬回 Disk(Job Queue)
- Swapping
- swap out : 從 memory 移除 process
- swap in : 被 swap out 的process 再放回 memory
- 目的 : 當記憶體內的行程太多，導致電腦的效能變差時，要將一些行程從 memory 移出，以減少行程搶用系統的 CPU ，以降低 multiprogramming process 的數量 (degree)。
- ### disk ↔ memory

> - 執行頻率介於Long-Term與Short-Term之間
> - 用於 Time-Sharing System (Real Time, Batch不用)
> - 可調控 Multiprogramming Degree
> - 可調合I/O Bound與CPU Bound的比例 (當Long-Term Scheduler有誤判之時!!

---

# Operation of Processes(Processes 的操作)
## Creation
- parent process 創建 children processes(單個/多個)，形成 process tree。
- child process 和 parent process 的差異
- 每個 process 有 unique id
- 第一個關聯性，child process 建立之後，所需的 resources 由誰提供：
- share all : parent 和 child 可以看到一模一樣的 content
- subset : 行程配部份資源給子行程
- ex. global variable 看得到，動態 variable 看不到
- shared none : 父子行程無共享資源
- 兩個看到的東西完全不一樣

:heavy_check_mark: resource 不是 parent process 提供，就是 OS 提供

- 第二個關聯性，Parent 生出 child proces 後，兩者的互動模式：
1. execute concurrently : 父子同時執行 process
- 交給 OS Scheduling 決定
2. parent 等到 child 執行完(terminate)
- = parent process 做了 fork 之後，就會進到 waiting queue 裡面

- 第三個關聯性，child process 的工作項目：
- Old implementation : child 完全 copy parent( = duplicate)
- Current implementation : Copy-on-write 的方式去儲存 ，run time,，修改值的時候再做分家

### 相關的 system call
- fork()
- Memory space of fork()

> - parent process 和 child process 有各自獨立的 memory space
> ref. [fork()](https://burweisnote.blogspot.com/2017/09/fork.html)
- execlp()
- Load a new binary file into memory ，舊的 code 丟了
- ex. 在 web download 其他 file(ex.ppt, pdf ...)，下載完成後要開啟時，會連到其他file 做開啟的動作。(開啟後就不甘 web 的事 = 不甘 parent process 的事)
- wait()
- 通常是 concurrently 執行，所以可以透過 waiting 調整
- parents 會等待其中一個 child processes 執行完成
#### fork()、execlp() memory space 的 Example


## Termination

### 相關的 system call
- exit()
- abort()
- wait()

# Important!!!
## Orphan(孤兒) && Zombie(殭屍)
- parent 死了(terminate)，child 會變 orphan(孤兒)！
- parent 睡了(sleep)，child 事情做完會變 zombie(殭屍)！

---

# IPC(Inter-Process Communication)
- 分為 independent 和 cooperating
> - indepensent
> - 不受其他 processes 的影響，或無法影響其他 processes 的執行。
> - 獨立的Process之間不會有任何共享資料。
>
> - cooperating
> - 會受到其他 processes 的影響，或影響其他 processes 的執行。
> - 故 Process 之間會有共享的資料，需要有進行資訊交換的管道。
> - processes 之間合作的理由
> 1. infor. sharing
> 2. speedup computation
> 3. Modularity
> 以模組化的方式建構 system ，讓 system 分配它的功能到各個 processes。
> 4. Convenience
> ex. 單一使用者同時做編輯、列印、編譯。

## Model(常見作法)

### Message passing
- Process 間使用 kernel 中的 shared memory 產生連接通道(communication link#→message queue)溝通。
> (非藉助共享變數 shared variables)
- 做 communication 的過程如下 → OS提供的東西
1. 建立 communication link → 會有 communication link 存在 processes 之間
2. 傳遞/交換信息(message) → send/receive messge
3. 傳輸完畢 → release link
- :heavy_exclamation_mark: **若傳遞少 data 較沒效率**

>#### 實作 Communication Link 的方式
>- Physical:
- Shared memory
- Hardware bus
- Network
>- Logical:
- Direct or indirect
- Synchronous or asynchronous
- Automatic or explicit buffering

#### 通訊(Communication)的方式
- #### direct (直接傳訊息)

- #### indirect (間接傳遞)

| Direct | Indirect |
|:---------------------------------------------------:|:--------------------------------------------------:|
| 建立 link 用 send/receive 傳送訊息 | 訊息從 mailbox 裡直接接收(**只能共享mailbox**資料) |
| 為自動建立 (established automatically) | 每個mailbox都有個獨特的ID(unique id) |
| 一個Link剛好連接一對Process(One-to-One) | 一對process之間，可能存在多條Link |
| 每個行程必須要明確地命名 | 要建立連結，只能是行程共享郵箱 |
| Link 可以是 unidirectional，但通常是 bi-directional | Link 可能是 unidirectional 或 bi-directional |

- 間接傳遞(indirect)的過程中，通訊的同步非常重要，分作兩種形式：
- blocking
- Blocking send：訊息傳遞出去，Process被Block阻擋，直到對方訊息收到才可再傳送。
- Blocking receive：不做任何動作，直到訊息送來，再回傳收到的資訊。
- non-blocking
- Non-blocking send：不管對方有無收到訊息，持續發送訊息給對方。
- Non-blocking receive：接收者只接收有效訊息，或是沒有訊息。

### Shared Memory
- process 之間利用 shared memory 交換資訊、彼此溝通。(**非使用 kernel提供的 space**)
- 使用記憶體位置(memory address)來存取 data
- 利用 read/write 資料來完成資訊交換
- :heavy_exclamation_mark: OS只提供 shared memory space，行程間的 **sychronization** 則需要由 programmer(user) 負責，OS不提供額外的資源。
#### → producer會把資料放進buffer內(write)
#### → consumer會去同一個buffer把資料取出來(read)

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ---
| | Share Memory | Message Passing |
| -------- |:----------------------------------------:| ---------------------------------------------------- |
| 溝通方式 | 共享一部分的記憶體(透過共享變數存取資料) | Process 之間建立 Communication Link |
| 共享性 | 共享變數所有 process 皆可存取 | process 間有專屬的 Link，不會隨意被其他 Process 共用 |

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ---

## Producer-Consumer Problem