# Process
:::danger

:::spoiler

[TOC]
:::
## 一、Process 簡介
:::success
行程(process)是電腦中已執行程式(program)的實體。現代面向執行緒設計的系統中，行程本身不是基本執行單位，而是執行緒的容器。行程需要一些資源才能完成工作，如CPU使用時間、記憶體、檔案以及I/O裝置。:::
:::
:::info
- 名詞解釋：

- 整批系統環境，行程稱為工作（jobs）。
- 分時系統環境，行程稱為使用者程式（user progams）或任務（tasks）。
- 在多數情況，工作與行程是同義詞，但行程（process）已較為人接受

:::

### [重要!] process 各狀態轉換關係圖。
- 
:::danger

行程在執行時，狀態(state)會改變。所謂狀態，就是指行程目前的動作：

**1. new：行程新產生中。
2. running：正在執行。
3. waiting：等待某事發生，例如等待使用者輸入完成。亦稱「阻塞」（blocked）
4. ready：排班中，等待CPU。
5. terminated：完成執行。**
:::
### process 在記憶體中的配置：
:::info

- stack : 存放函數的參數、區域變數`local variable`,`return variable`等。(會稱作 stack 是由於其配置遵守 ==LIFO==)
- heap : 一般由程式設計師分配釋放，執行時才會知道配置大小，如 `malloc`/`new` 和 `free`/`delete`。(注意其資料結構不是 DS 中的 heap 而是 link-list)
- BSS : 未初始化的靜態變數
- data : 全域變數`global varibale`、靜態變數`static variable`
- text/code : 常量字元串
:::

:::warning

**[重要!]** process 在記憶體中的配置圖
:::

[例題] 配置練習

int a=0;   //global 初始化區
char *p1;  //global 未初始化區
main(){
    int b;             // stack
    char s[]="abc";    // stack
    char *p2;          // stack
    char *p3="123456"; // 123456\0 在常量區，p3在stack。
    static int c=0;   // global (static) 初始化區
    p1 = (char*)malloc(10);
    p2 = (char*)malloc(20);  //分配得來得10和20位元組的區域在heap
    strcpy(p1,"123456");  
    //123456\0 在常量區，編譯器可能會將它與 p3 中的 123456\0 優化成一個地方。
}

## 二、Context Switch
:::success

讓多個 process 可以分享單一個 CPU 資源的計算過程。當 CPU Context Switch 到另一個 process，系統會儲存舊 process 的狀態並載入新 process 的狀態。Context switch 的時間是 overhead，耗時根據硬體配備而不同。
:::
:::info

交換的時機有以下幾種：

1. 多工
2. 中斷處理
3. 用戶態或者內核態的交換 (可能)
:::
### Process Control Block (PCB) :
:::success

作業系統核心中一種資料結構，當在切換 process 時，會把未做完的 process 相關資訊記錄在 PCB 裡。
:::

PBC 紀錄的資訊結構圖。

:::info

- Process Scheduling Queue：OS 在 Process Scheduling Queue 中維護所有的 PCB。

- Job queue − This queue keeps all the processes in the system.
- Ready queue – in main memory, ready and waiting to execute
- Device queues – waiting for an I/O device
:::


Process Scheduling Queue 示意圖。

## 三、Scheduler

### 1. Long-Term Scheduler (或稱 Job Scheduler) <font color = "red">[new—>ready]</font>
:::info

- 從 job queue 中挑選合適的 jobs，並將之載入到記憶體內準備執行。
- 通常適用於 Batch System (大型機房)，但不適用於 Time-Sharing System。
- 可調控 Multiprogramming Degree
- 可調合 CPU-Bound 與 I/O Bound processes 之混合比例
- 執行頻率最低
:::

### 2. Short-Term Scheduler (或稱 CPU Scheduler) <font color = "red"> [ready—>running]</font>
:::info

- 從 Ready Queue 挑選高優先度的 Process，使之獲得 CPU 控制權執行
- Batch System 和 Time-Sharing 均需要
- 執行頻率最高
:::

### 3. Medium-Term Scheduler <font color = "red"> [virtual memory]</font>
:::info

- 當記憶體空間不足，且又有其它 Process 欲進入記憶體執行，此時該 Scheduler 必須挑選某些 Process 將其 Swap Out 到磁碟中以空出記憶體空間，待記憶體有足夠空間再將其 swap in 記憶體中繼續執行。
- 通常用在 Time Sharing System。
- 減少 Multiprogramming Degree
- 可調合 I/O Bound 與 CPU Bound 的比例
:::

### <font color = "red">[重要]</font> I/O bound vs CPU bound
:::info

- I/O-bound process – spends more time doing I/O than computations, many short CPU bursts. ex : 等待鍵盤輸入的程式
- CPU-bound process – spends more time doing computations; few very long CPU bursts. ex: 壓縮程式
:::

## 四、對 Process 的操作
:::success

parent process 會建立 children processes，而 children processes 又可以成為 parent processes 建立其他 processes 而形成樹狀結構。
:::


:::info

- Each process has a unique PID, Some special PIDs :

- 0 : scheduler
- 1 : init
- 2 : pageout
:::

### Process 建立的一些議題
:::info

- 工作類型：與 parent 相同、與 parent 不同
- Resource sharing : 全部分享、部分分享、全部不分享
- Execution : parent child 同時執行、parent 等 child
- Address space : 和 parent 相同、child 有其他 program 載入其中。
:::

### Process 操作有關的 system call
:::warning

1. fork() : 此 system call 用以建立 child process，child process 與 parent 占用不同的記憶體，但最初 child 的 code section、data section 內容均自 parent copy。
2. exit() : 此 system call 即終止process，exit() return 0 為正常終止，-1 為不正常終止。
3. execlp() : 此system call 用以載入特定的 Binary code file 讓 process 執行，即 process之code section 為此 Binary code content。
4. wait() : 此 system call 用以強制 process 暫停知道某事件發生後才往下執行。
:::

### 建立 process 流程圖。

:::info

- Process Termination

- child 執行完要求 OS 刪除自己 (exit)，child 傳輸結果給 parent (via wait)，資源由OS回收。
- parent 終止執行中的 child process (abort)
- parent 比 child 先終止 : 則 child 可能一並終止或由 OS/祖先 供應資源而存活下來。
:::

### [注意] 孤兒與殭屍
:::danger

<font color="blue">**Parent** </font> 死了，<font color='red'>Child</font> 會變 <font color="purple" >orphan(孤兒)</font>，<font color="blue">**Parent**</font> 睡了，<font color ='red'>Child</font> 事情做完會變<font color ="red">**zombie(殭屍)**</font>!!
:::

### [用心去感覺] fork() vs vfork()
:::info

- Linux 程式設計下常用到的 **fork()**，功能是從 parent process 複制一個 child process，這是在有支援 MMU 的環境下才能使用。
- 像 uclinux，就不能用 **fork()** 只能用 **vfork()**，因為 fork 的實作是利用 copy-on-write，因此一定要有 MMU。

- **fork()** : process 內容整份複製，呼叫 fork() 後的 parent process 會和新產生的 child process concurrent 執行。
- **vfork()** : call、data 和 stack 都是看 parent 原有的，呼叫 vfork() 後的 parent process 會被暫停，直到被複製出來的 child process 執行了 exec() 或 exit()。
:::
:::warning

[例題] C Program Forking Separate Process

int main(){
 Pid_t pid; 
 /* fork another process */
 pid = fork();

 if (pid < 0){ /* 錯誤發生：傳回-1(負值)給kernel parent */  
  fprintf(stderr, "Fork Failed"); 
  exit(-1); 
 } 
 else if (pid == 0){ /* child 收到 fork 傳回值是 0 */ 
  execlp("/bin/ls", "ls", NULL);   
  /* (目錄, 檔名, 參數) ，若 child 要做特定工作則必須執行 execlp() 載入需要的工作。*/
 }
 else { /* parent 收到傳回值是 child 的編號  */ 
   wait (NULL);  
   /* parent 等 child 直到 child 做完 */
  printf ("Child Complete”);  
  /* parent 有 child 的 pid 所以有權力殺了 child */
  exit(0); 
 }

}

:::

## 五、Inter-Process Communication, IPC
:::success

一般 processes 可以分成不互相影響的 independent process 和可互相影響的 cooperating process。實際上使用 multiple process 的時機大多是處理事件或在背景做其他事。

- ie1 : 等使用者輸入時可繼續計算
- ie2 : 在背景執行磁碟重組作業
:::
:::info

常見的 IPC 有以下兩種：

- shared memory
- message Passing
:::

- 

兩個常見的 IPC。

### 1. IPC - Shared memory - Producer Consumer Problem
:::success

To synchronize a producer and a consumer via shared memory.
:::

#### Shared data :
:::warning

#define BUFFER_SIZE 10
Typedef struct{
 ...
}item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

只能使用 BUFFER_SIZE - 1 個元素。 (要空一個buffer以區別全空與全滿)

- 全空：in, out 指向同一空元素
- 全滿：in 指向 out 前一空元素，(in + 1) % BUFFER SIZE == out

答案在 concurrent 時正確，但 busy waiting 效能不好，尤其在單一 CPU 上 。

:::
### 2. IPC - Message Passing
:::info

- Processes communicate with each other without resorting to shared variables .
:::

#### Direct communication
:::info

- Processes must name each other explicitly : send (P, message), receive(Q, message). exactly one pair link, usually bi-directional.
:::

#### Indirect communication
:::info

- 不是直接寄給其他 process 而是寄到他家信箱 (also referred to as ports)，每個 mailbox 有一個特殊 id，一次可以連多個 process 但只能寄給一個 process，系統會自動選一個寄，然後告訴寄件者收件者是誰。

- 傳回給寄件者的信有三種情況：

- 0 : 等
- bounded : 滿了就要等
- unbound : 無限 buffer 不用等
:::
:::warning

信件者間的同步問題：

- **Blocking is considered synchronous** : Blocking send has the sender block until the message is received.
- **Non-blocking is considered asynchronous** : Non-blocking send has the sender send the message and continue.
:::