# Chapter 3 整理
>筆記裡整理不夠好的地方請直接幫我修改><，感謝
>[name=YJ][color=#e2416a]
[TOC]
## Process Concept
### Process 和 Program 的差別？
* Process：active，正在 memory 裡執行的程式
* Program：passive，存在 disk 裡的 binary file
### Process 的組成：
* Code segment : 程式碼、字串、方法這些會被重複呼叫且不會改變的部分
* Data section：拿來放 global variable
* Stack：放 local variable
* 一塊空間流
* Heap：放 dynamic variable
* Meta data：管理 process 的資料，存在 <a href = '#PCBProcess-Control-Block-行程控制區塊'>PCB</a>
* Program Counter 內所存的位址，就是 CPU 下一步要執行工作的 memory address
* 透過base和limit register，可以得知程式在 memory 中的範圍
* A set of resource : 存在 <a href = '#PCBProcess-Control-Block-行程控制區塊'>PCB</a> ，開file、使用電腦系統上的resources時需要一個token或者reference，所以可以知道開了多少file或者使用多少socket的ports
> Program怎麼變成Process?
> load and initialize，要把program load到memory，把memory space中的五個contents(code放程式碼、data放global variable、stack放區域變數、heap放dynamic variable、和一個給stack、heap增長的空間)全部create出來，做一些initialization
memory也要做分配，哪些memory是給這個process
> Heap需要小心管理(```c++```中用指標)，不會再用到的要把空間釋放掉，否則會有memory leak
### Process 和 Threads 差在哪？
* Thread 又叫做 lightweight process，是 CPU 執行的最小單位
* lightweight的意思？
因為每一個 thread 執行的位置可以不同，也可以執行不同的 function，只需要針對一些獨特的事情去管理，大家都一樣的部份可以直接共用，所以空間可以很小
* 共通點：Thread 和 Process 的管理方式和長相相似
* 差異：thread 可拿來做 shared memory 的溝通
* 哪些部份可以做 memory 的溝通？
code section、data section、OS resource，只要一個 thread 開，另外一個就可以拿這個 file 的 pointer，對這個 file 做 read/write 的動作
也就是說，在寫 multi-thread programming 的時候，就用 global variable 來做溝通（如果是 allocate 在 heap 中，只要有 pointer，任何的 thread 都可以讀取裡面的資料）
* 為什麼剩下的部分不能 share？
因為 thread 要能夠獨立執行，必須要有自己的 program counter、register set、stack、thread ID、```state```，OS 才知道是 process 下的哪個 thread
* 以 Chapter 3 來說，雖然講的都是 process，不同的 OS，管理 thread 的方式會有些不同，但以大方向來說，管理 process 和管理 thread 的方式是一樣的
### Process 的 Cycle
Process的life cycle，分成五個states，要知道 5 個 state 轉換動作的原因
* **New**
* 這個階段要做很多事情：把 program load 到 memory 裡面、把 process 的五個 code segment 全部 create、initialize 到 memory 中，memory 也要做分配
* ==admitted==
- 由long-term scheduler負責
- 狀況：
1. memory 的空間不夠，就沒有辦法做 new，process 就會被 kill 掉
2. 沒有 permission，作業系統要做 protection，有些程式在權限不夠的情況下是不能執行的
3. 可以進到 ready state：空間夠、且有權限時，會進到 ready queue
* **Ready**
* 存在 memory 的 ready queue，等著被 OS 排程去使用 CPU
* process 放到 queue 上面是怎麼操作的？
實際上只是把 <a href = '#PCBProcess-Control-Block-行程控制區塊'>PCB</a> 放到 queue 裡面，而不是放 process 本體，怎麼實現 queue？用 linked list 的方式，每個 PCB 的 pointer 會指向下一個 PCB
* ==CPU scheduler dispatch==
* CPU scheduler 指的是從 ready queue 中挑選 process，把它放到 running state，dispatch 指的是被 OS 選到後，會 load 到 CPU，進入 running state
* 在 running state 就代表這個 process 已經是可以執行的，不能執行的會被放在 waiting queue
* **Running**
* 被 OS 選中可以使用 CPU，把 instruction 送到 CPU 裡去執行
* ==interrupt → 從 running state 回到 ready queue==
* 為了做 time sharing system，有一個 timer 會 launch 或 fire，原來的 process 會被迫切換給 OS 的 scheduler，固定讓主控權可以回到 OS
* ==I/O or event wait → 從 running state 回到 waiting queue==
狀況：
1. 因為要做 I/O，所以放掉 CPU 的執行權，原來的 process 會被放在 waiting queue
2. process 自己 call 了 system call，原來的 process 會被放在 waiting queue
* ==exit==
執行完後直接離開 → terminated
* **Waiting**
* 如果這個 process 現在需要的是做 I/O，沒有要使用 CPU，就進到 waiting state，等到做完 I/O，需要 CPU 時，才會重新放到 ready queue
* ==I/O or event completion → 從 waiting queue 回到 ready queue==
等到 I/O 結束，或者 system call 的時間到了，OS 再把它移回 ready queue
* 靠**interrupt**來通知OS event做完了
* **Terminated**
* new 的動作反過來，把所有資源放掉，讓 OS 可以給其他 process 使用這些資源
### PCB(Process Control Block, 行程控制區塊)
**將 Process Cycle 實現的方式**
>定義：OS 為方便管理 process，把 process 相關資訊集合整理，放在一個紀錄單位之中，叫做 PCB
>[name=YJ][color=#e2416a]
* 組成：
1. ```PID```
> 照理來講應該要有，但是老師沒提到，圖中的 process number 應該就是 PID
> [name=YJ][color=#e2416a]
2. Process State
3. Program Counter
4. CPU register
5. CPU Scheduling information
process priority
6. Memory Management
只有 process 在 running state 時，base/limit register 的值才會從 memory load 到 HW 的 register
7. I/O status
現在在哪個 I/O device，不同的 I/O 有不同的 waiting queue
8. Accounting
開了多少個 file
### Context Switching (內文轉換)
>定義：當一個 process 需要等待 I/O、或是被 interrupt，在 CPU 交給另一個 process 之前，需儲存舊 process 的 PCB，載入新 process 的 PCB，這一連串的動作就叫做 Context Switching
>[name=YJ][color=#e2416a]
* 流程
1. 假設原來在執行的 process 叫 P~0~
2. 當有一個 interrupt 或 system call，開始做 context switch：
* 把 P~0~ 在 CPU 裡執行的狀態，全部存到 PCB
* 再把新的 process (P~1~) 的狀態 load 到 CPU
* 補充：對於 P~0~、P~1~ 而言，做 context switch 時，兩支程式都是閒置狀態，裡面的程式碼沒有被執行到
3. Context Switch 完成後，P~1~ 開始 running
* 也就是執行 P~1~ 裡的 instruction，把 program counter 設到要執行的位置
4. P~1~ 執行完，要把執行權轉回 P~0~
* 再做一次 context switch
* 說明
* Context Switch 的過程中，兩個 process 都在 idle，造成 CPU cycle 的浪費 (==overhead==)，但都是為了把 CPU 資源 share 給所有的 process，才能做到即時的 response
* 既然不能避免 context switch，那就要想辦法把 switch 的時間縮短，有以下幾個方法：
1. 提高 memory 的速度
2. 減少 register 的數量
register 減少，需要存取的數量就少，時間就少，但這部分無法解決，因為現在的電腦系統都希望 register 越多越好
3. 用一個指令把這一連串的動作包在一起
4. Hardware Support
這是最常用的方法，讓 CPU 有好幾組 set 的 register，可以一次記四、五支程式 的狀態在 register 中，這樣在做 context switch 時，只是把一個 register 的值搬到另外一個 register，減少經過 memory 存取的次數
### 回顧
* What’s the definition of a process?
在memory中的程式
<a href="#Process-Concept">process</a>
* What’s the difference between process and thread?
process在memory中會有五個區塊，由下到上分別是:code segment放程式碼、data放全域變數、stack放區域變數、空間流給stack和heap動態增長、heap放會需要被額外控管的實體變數或物件
thread是CPU執行的最小單元
一個process可以對應到很多個threads，而每支thread可以共用很多部分，只需要針對thread ID、program counter、register set、stack額外去開空間，所以可以很輕量
<a href="#Process-和-Threads-差在哪？">Process-和-Threads-差在哪？ </a>
* What’s PCB? its contents?
* Process state
* Program counter
* CPU registers
需要被用來控制Process的參數全部都可以寫在PCB中，會被存在kernel space
<a href = '#PCBProcess-Control-Block-行程控制區塊'>PCB</a>
* The kinds of process state?
* New, Ready, Running, Waiting, Terminated
* What’s context switch?
## Process Scheduling
>* Multiprogramming （多元程式規劃）
> 定義：
1. 系統載入多個 process 到 memory 中
2. 以並行或是平行方式同時執行
3. 當一 process 需要 I/O，CPU 將交給另一個 process 使用 → 使 CPU 的使用率最大化
>* Time Sharing（分時系統）
> * 定義：
多個 process 可輪流使用 CPU 一段固定時間（time slice），當給予的時間一結束就另一個 process 執行
> * 效果：
各 process 皆以為擁有專屬的系統
> * 特色：
注重公平、反應時間、互動性
>
>[name=YJ][color=#e2416a]
### Process Scheduling Queues
* Job Queue (New State)
早期電腦 memory 有限，誰能夠從 program 狀態 load 到 new state(launch)，什麼時候允許 program load 到 memory 成為 process
* Ready Queue (Ready State)
load 到 memory 後，會被放進 ready queue，等 OS Scheduler 決定誰可以去使用 CPU
* Device Queue (Wait State)
每一個 device 會有自己的 queue，可以知道 process 在做哪一個 device 的 I/O，例如自己 call sleep() 或是有其他的 interrupt，那會有其他 waiting queue 的存在
Queue 的管理如圖所示
說明：
* 會有一個 ready queue for CPU，很多個 I/O 的 waiting queue，看是哪個 device 或 disk，會有自己獨立的 queue，利用 PCB 中的 pointer 串起來
* ready queue 可能會有 level 1、level 2、level 3，取決於 Scheduling Algorithm 自身管理方式
* queue 之間的 tail 和 head 都有串起來，比較容易做 reordering，不同的 Scheduling Algorithm，可能會 dynamically 決定 ordering (run time做調整)，需要其他 pointer 串起來，變成雙向或把前、後記起來
### Process Scheduling Diagram
說明：
* Ready queue 中的 process 會等待被 load 進 CPU
* Waiting queue 發生的原因有很多種，OS 會有專門的 queue 去處理這些 event 的發生：
* I/O request
* 若自己發出 I/O request，這時候會被放到 I/O queue，等到做完 I/O，會 throw 一個 interrupt 回來，OS就會把它放回 ready queue
* ex: call printf()，會被放到 monitor queue
* time slice expired
* timer的 alarm 被 fire，會從 CPU(running state) 直接回到 ready queue
* 這是為了確保主控權可以回到OS的手上
* fork a child
* process 可以自己 create process
* 程式內為什麼會有這麼多 process，是因為有一個 parent 和 children 的關係，有一個 tree
* 在Linux中，create process的動作叫做"fork"
有兩種實做方式
(1)可能自己繼續執行讓children等Parent執行完在執行
(2)先讓children先執行，原來的Parent process會被放在waiting queue，等到Children執行完，才可以再回到ready queue執行
* wait for an interrupt
* ex: call sleep() 的 system call
* sleep 100ms → 告訴 OS，100 ms 之後，幫我 fire 一個 interrupt，把我自己給 wake up 起來
* call sleep() 的 process 會被放在 waiting queue 裡，等著 interrupt 的發生，才可以回到 ready queue 裡面
### Scheduler
把下圖跟前面講的 [state](https://hackmd.io/4pxdfl71SBSnGHHqMOZIgg#Process-%E7%9A%84-Cycle) 串在在一起：
說明：
* CPU 中的 process 是 running state
* 搶 CPU 需要 CPU Scheduling 來排程
* CPU Scheduling 又稱為 Short-term（很頻繁），因為 time sharing，每幾個 ms 就有一個 alarm 產生，打斷執行的程式，把 OS 的 CPU Scheduling 叫起來，重新排程，頻率非常高，非常快就要做 rescheduling 的動作
* memory 中的 processes 是 ready state，等待著 OS 把它排程到 CPU 中執行
* 如果 process 在 memory 中但還不能立刻被執行，就算 CPU 空了也無法執行 process 的話，就是在 waiting queue 中
* 進入 waiting queue 有幾個可能：
1. 因為自己，自己要等別人
ex：自己call I/O、sleep() 的 system call
2. 因為別人，被別人 interrupt 而要被迫做 Context Switch
* 還在 disk 中的 program，有機會成為 process 的話，就會變成 new state，只是被create and initiate，但還沒有準備好放到 CPU 中還在 disk 上，等著搶位置進到 memory
>疑問：create and initiate 是包在 new state 裡，還沒變成 process 之前怎麼會被 create 和 initiate？
>這個部份是對你修改的筆記提出疑問：）
>[name=YJ][color=#e2416a]
* 搶 memory 需要 Job Scheduling
* Job Scheduling 又稱為 Long-term，相較於 CPU 排程，可能幾秒或幾分鐘才要做一次排程，因為是由使用者（人在幾秒鐘後才會 create 一個 process）launch process，才會需要排程進到memory，時間相較於 ms 較長
* 所以使用者的 Program 能否 load 到 memory 中是由 Long-term scheduler決定
* 圖裡還有一個 Job Swapping：
* swap: 把 memory content 踢回 disk 去
* Medium-term scheduler：因為 memory 有限，會把 disk 的一塊空間拿來當 memory 使用，當 memory 不夠時，Medium-term scheduler 要把一些 process，從 memory 踢回 disk
* 當 ready 的 process 從 memory swap 回 disk 時，進入 waiting state（但是以 memory content 形式，不是檔案形式），當 memory 有空，或是 process 要被執行時，OS 再把 process 的 memory content 搬回 memory 等著被執行（回到ready state）
Scheduler 種類：
* **Short-term scheduler (短期 Scheduler)**
CPU Scheduler，memory 中的 process 等著被排程而進入 CPU 被執行
> 又稱 Process Scheduler、CPU Scheduler
> 目的：從 ready queue 中挑出 highest-priority process，並分派 CPU 給這個 process
> [name=YJ][color=#e2416a]
特色：
1. 執行頻率：最高
2. 注重 wait time
* 很多 process 在 ready queue 裡面，要等著使用CPU，我們定義效能的方式就是用「平均大家等了多少時間」
* ex：大家都不喜歡等很久，買食物、用餐上，平均來講希望越短越好
* 不同的 Scheduling Algorithm 在相同的人進來的情況下（同樣的順序、不同排程的演算法），平均得到的等待時間會不一樣，如果演算法設計得好，定義下的 wait time 效能會變得更好
3. 注重 fairness
* 有 priority 或者是 round-robin（循環制）的 Scheduling Algorithm，為了確保 fairness，就會希望每個 process 等待的時間能夠盡量一樣，有時候平均很低不代表大家都高興
* ex：經濟上，國家收入好不代表國民很均富
* 以圖裡中間那段文字來說明：
:::info
→ if 10 ms for picking a job, 100 ms for such a pick,
→ overhead = 10/100 = 10%
* 假如 100ms 就要做一次 Scheduling，每一次 Algorithm 只 run 10 個ms，那 overhead 就是 10%，CPU 有 10% 的時間根本沒在幫使用者做事情
* 如果 100ms 就要做一次 Scheduling，而 Algorithm 要 run100ms，原本希望 CPU 要 run 100% 的使用率，結果一半的時間都不在做使用者要它做的事情，那當然會覺得這台電腦很慢
:::
* 所以 Short-Term Scheduler 很重要，Short-Term Scheduler 的決定會直接影響到程式執行的效能和使用者看到的 response time（interactive 的速度），計算時間也不能太長，processes很多時，掃一遍所需要花的時間會非常驚人
* **Long-term scheduler (長期 Scheduler)**
Job Scheduling，有新的程式被產生，要排程進入 memory
> 又稱 Job Scheduling，目的是從 Job Queue 中挑出一些 Jobs，要排程進入 memory，ready for execution
> [name=YJ][color=#e2416a]
特色：
1. 控制電腦的 "degree of multiprogramming"
* 什麼是 degree of multiprogramming？
這台電腦上，目前有多少個程式在 memory 裡面，這會控制電腦的 memory 內部要有幾個 process，這個值不能太高也不能太低
* degree 太少時，CPU 會 idle，早期 batch 的 degree always=1，CPU 一直等I/O，Utilization 很低
* degree 太高時，會產生 Trashing 的問題，太多 process 在爭搶很有限的 memory，結果大家就在 disk 和 memory 之間一直做 swapping，所以電腦基本上還是在做I/O
* 所以 Long-term Scheduler 要控制 new 的 program 到底能不能被放到 memory，其實就是在控制 degree of multiprogramming
2. 執行的頻率：三種 Scheduling 中最低
* Long-term 是由使用者來 driven，若沒有新的 process 被 create，Long-term Scheduler 就沒有事情需要做
3. 調控 CPU-Bound 和 I/O-Bound 的混合比例
* memory 的目的是希望程式執行 CPU 和 I/O 的時間可以 Overlap，CPU 執行的時間要差不多跟 I/O 執行的時間一樣，這樣 CPU 跟 I/O 才都會有事情可以做
* 如果 load 進來的程式都是 CPU-bound（只需要執行CPU的instruction，只是加減這些純計算的操作），就算 load 很多在 memory 裡面，CPU 還是會非常忙碌，而 I/O device 還是放在那裡沒有做事，CPU 跟 I/O沒有overlap。只有使用到 CPU，I/O 的 bandwidth 就浪費掉了
* 反過來說，如果 load 進來的程式都是 I/O-bound（沒有人要做 CPU，每個都在 call printf()、scanf()），所有的程式都在等 I/O 的事情，因為 I/O 很慢，而 CPU 執行很快，卻一直都在 idle，這樣也不行
* 因為是使用者 create 的程式，有機會一次來的全部都是 CPU-bound 的程式或突然間來很多 I/O-bound 的程式，所以 Long-term Scheduler 要讓選進來的 process 在做 CPU 跟 I/O 的時間上，盡量可以 balance，讓 CPU 跟 I/O 都可以忙碌地做事，兩邊都不會 idle，使用率才可以增加
4. Long-term Scheduler 的角色已經慢慢淡化
* 因為 memory 足夠，只要使用者說要執行 Program，利用 memory 加上 virtual memory 的概念，process 都能直接 load 到 memory 再說，所以對於新的電腦來說，已經不太需要 Long-term Scheduler，可以把需要執行的 program，全部 new 到 memory 中，這個角色就會變成 Medium-term Scheduler 要做的事情
> 補充：
>
>
>| | I/O Bounded Job| CPU Bounded Job |
>| :--------: | :--------: | :--------: |
>| 定義 | 須大量 I/O 操作，少量 CPU 計算 | 須大量 CPU 操作，少量 I/O 計算 |
>| 速度限制 | 受限於 I/O device 的效能 | 受限於 CPU 的效能 |
>| Buffering | input：CPU 常面對空的 Buff<br>output：CPU 常面對滿的 Buff | input：I/O 常面對滿的 Buff<br>output：I/O 常面對空的 Buff |
>[name=YJ][color=#e2416a]
* **Medium-term scheduler (中期 Scheduler)**
swap memory 的 process 到 disk 上，或者把 disk 上的 program 放到 memory
> 定義：當 memory space 不足時，挑選部分 process，swap out 到 disk，等到 memory space 有多餘空間時，再 swap in 到 memory 中
> [name=YJ][color=#e2416a]
- swap out 是把process從memory再把它搬回到disk上(記得這邊是memory content的型式)，為什麼要搬是因為要控制degree of multiprogramming
- swap in: 讓等在disk的process可以回到memory，重新等著被排程給CPU做執行
因為有swap out，有時候memory的空間會空出來，這時候要把某些程序給切換回來
特色：
1. 調控 CPU-Bound 和 I/O-Bound 的混合比例
* CPU 跟 I/O 全部 load 到 memory，可是可以再去挑哪些 process 應該留在 memory，而哪些應該離開進到 disk 中，可以去控制 ratio 的部分
* 現在的電腦沒有 Long-Term Scheduler，所以使用者要 new 的 process 都不會刻意去拒絕，會全部放到 memory 中，但進來之後如果要再做進一步的管理，就要靠 Medium-Term Scheduler
* 實際上的 memory 空間還是很小，只是 disk 很大而已
2. 控制電腦的 "degree of multiprogramming"
* 當太多人去搶 memory 時，degree of multiprogramming 太高，可以用這個方式來減少 degree，把 memory 讓出來，給真的在等著被 CPU 執行的 process 使用，而不是讓memory 的空間被在 waiting state 的 process 所佔有
> Scheduler 整理：
> [name=YJ][color=#e2416a]
## Operations on Processes
pid (Process identifier)：只要 process 被 create 出來，就會被 assign 一個 unique ID，以利辨認
> 老師補充：ps -ael 指令，可以 list 出所有 process 的 PID，是哪個 program create 的，和它的 parent 是誰
>
**Tree of Process**
* Process 透過 parent-children 方式產生，也就是一開始執行程式只有一個 process，透過這個process，再去產生其他 process，形成樹狀圖關係
### Process Creation
* 第一個關聯性，child process 建立之後，所需的 resource 由誰提供：
* parent 和 child 可以看到一模一樣的 content
* 或是說 global variable 看得到，動態 variable 看不到
* 甚至是說兩個看到的東西完全不一樣
所以 resource 不是 parent process 提供，就是 OS 提供
* 第二個關聯性，Parent 生出 child proces 後，兩者的互動模式：
* 法一：Concurrent Execution
也就是交給 OS Scheduling 決定
* 法二：parent 等到 child process 執行完
* 對應狀態：process 做了 fork 之後，就會進到 waiting queue 裡面
* 第三個關聯性，child process 的工作項目：
* 與 parent 相同工作：memory content 完全複製到 children (duplicate)
* 複製不只代表 copy 整份 memory content，還有 program counter，也就是說你程式執行到第三行的時候，create 了一個 children，這個 children 就要從第三行開始執行，所以會分不出來 parent 和 children，因為兩者的行為和 code 完全一樣，唯一的不同在於，他們的 address 不一樣
* 與 parent 不同工作：children 被 create 的時候順便給他 load 一份新的 code，重設 program content
### Implementation of Process Creation on UNIX/Linux
* fork()
* 定義：fork() 是用來建立 child process，並 return child process 的 PID
* 如果 fork() 成功：
* return 0 給 child process
為什麼 return 0？因為它是被產生出來的，沒有自己的 child
* return PID 給 parent
* 這時候 parent 和 children 的關聯性是一模一樣的，parent 在 fork() 之前所載的資訊，全部 copy 一份到 children
* parent 和 children 的執行順序交給 OS 決定，所以都有可能誰先誰後，這樣 parent 就不用放到 waiting queue，較符合使用者的需求和希望
* 父母知道小孩是誰，小孩不一定知道父母是誰，但可以 call 別的 system call 去問 OS
* execlp()
* execlp() 把 child 原來的 memory content 做 reset，放新的 program 進去
* ==問題：為甚麼還是要先呼叫 fork()？== create 是因為要跟 OS 註冊 PID，索取一個 memory 的 空間、 還有 幫他們開 PCB
* 
* wait()
* 用來暫停 process 執行直到某個 event 發生（ex：child terminated）
* Linux是 concurrent 執行，如果 programmer 不想交給 OS 決定你目前的 parent 和 children 的執行順序，要 call wait system call，強迫把 parent process 放進 waiting queue，但這個 function call 是 programmer 視需求而下的，並非 OS
### Unix/Linux Process Creation
把前面三個 implementation 圖像化：
* **Originally**
* 這是系統目前的狀態
* A、B 分別代表 A、B program 的 memory space
* **Afeter A does fork**
* program A call 了 fork，產生一個 child
* A's child 比原來的 A 小，可以從兩種實作方法去解釋：
* 第一種是比較 naive (幼稚) 的作法：就是 exactly copy ( duplicate )，全部 copy，但很多相同的資料何必再複製，浪費空間呢?
* 第二種實作方式 (現在的實作是採用第二種方法)：copy-on-write，只會 copy 值會被改掉的部分 ex: program counter、基本執行的值
* 但是對於使用者來說，他們看到的 content 是一模一樣，實際上 OS 會動手叫去省掉記憶體空間
* **After the child does an execlp**
* 如果想要有一個新的 process 去 run 別的 binary code，就得先呼叫 fork function 再讓 child 呼叫 execlp function
* 把原來的內容取代掉，也就是 code segment 會把它 load 別的程式碼，這時候 child 的大小、內容就會跟 A 完全無關了
### 程式執行：
建立一個程式，建立一個 child process 執行 ls 命令，且 parent 要等到 child terminated 後，才印出 "child completes"
```clike=
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main() {
int A;
A = fork(); //1
if(A==0) { //2
printf("This is from child process.\n");
execlp("/bin/ls","ls",NULL); //3
}else {
printf("This is from parent process.\n");
int status;
int pid = wait(&status); //4 5 6
printf("Child %d completes.", pid);
}
printf("process ends %d.\n", A); //7
}
```
* 詳細解釋：
1. 這裡的 fork 是 "C library" 的 function call，會再去 call 到 OS 的 function call。
範例本身就是一支 process，執行 fork() 之後，OS 又會再做一支跟範例一模一樣的 process，各自都有自己的 program counter
2. 現在有兩個 process 長的一模一樣，但 return 值不一樣，兩個 process 各自執行不同部分，如果是 parent 的話，return 值就不會是 0，它會跳到 else 的部分，child 就反過來，會去執行 if 的部分
3. **if**： child 呼叫 execlp() 之後，會把自己原來的程式碼整個清掉，去執行 execlp function 指定的 binary file
```
"bin/ls" 是 binary file 的位置
"ls" 是 linux 指令，把所在資料夾所有檔案都 list 出來
child 在這個範例裡面負責執行 ls 的指令，把 bin 資料夾的東西都 list 出來，
執行完 list 就結束了，後面的程式碼就不執行了
```
4. **else**：```pid``` → 等待哪個 process 的 pid，這裡比較需要搞清楚的一點是說，可以一次 create 很多 process，這裡也沒有指定要等哪個 child process，所以只要有任一個 child 完成，就會丟回那個 pid 給 parent，parent 就會 break 了
5. **else**：```wait``` → 雖然 child 呼叫 execlp 之後已經和原來的樣子不一樣了，但還是同一支 process，所以 parent 還是 wait 那一支 child process
6. **else**：```&status``` → &status 是要去看 system call 裡面的 stack，老師的程式碼有省略一些，不過去看 linux 的話，的確會要求你放 status pointer 當作參數，目的是要告訴 system 目前 process 的 status 是甚麼
ex: error fail, success
7. 這行只會被 parent 執行
雖然最後一行指令是在 if-else 的區塊外，但child 已經執行 execlp 了，變成完全不同的程式，所以不會執行最後一行
* **Output 說明：**
```clike=
This is from child process.
This is from parent process
//第一二行的 output 有可能會對調，因為這時候是
//採 concurrent 機制，由 OS 決定現在要讓誰 run
a.out hello.c readme.txt
//第三行 output 是 child 呼叫 execlp 的結果，一定是執行 ls
//為什麼不是 output parent 執行的結果？
//因為 parent 呼叫了 wait function，所以parent 一定會等
//child 執行完才去執行，所以第三行一定是child 執行 execlp 的結果
//(but but 也有可能跑到第二行啦，但一定會在 parent 執行之前出現)
Child 32185 completes
process endc 32185
//等到 child 執行完了，parent 就可以 output 第四五行了
```
真實執行結果：
### Process Termination
### 回顧
## IPC (Interprocess Communication)
* 定義：多個 process/thread 內部要去溝通，都統稱叫做 IPC
* 沒有溝通的 process 叫做 independent process，cooperating process 則反之
* ==Process 之間為什麼需要溝通？==
* information sharing
* computation speedup (not always true...)
* 平行程式：透過很多的 process (thread) 來解決同一個問題/計算
解同一個問題，可以加速
解同一個問題，需要溝通
* convenience (performs several tasks at one time)
* 像 web server，一個 user 對一個 process，就可以很容易去管理這些 connection
* modularity
* 最標準的例子就是 microkernal (modularized OS)，他把所有的 component 放在 user space，並 component 透過 IPC 來做溝通
### Communication Methods
* [Shared Memory](https://hackmd.io/s/SyMfTeZkE#Shared-Memory)
* [Consumer & Producer Problem](https://hackmd.io/s/SyMfTeZkE#%E5%A6%82%E4%BD%95%E8%A7%A3%E6%B1%BA-Consumer-amp-Producer-Problem%EF%BC%9F)
* [Message Passing](https://hackmd.io/s/SyMfTeZkE#Message-Passing)
* [Sockets](https://hackmd.io/s/SyMfTeZkE#Socket)
* [Remote Procedure Calls](https://hackmd.io/s/SyMfTeZkE#Remotw-Procedure-Calls)
#### Shared Memory
> 定義：指多個 process 藉由 pointer 去 access 相同的 memory 做 read/write，來達到共享的效果
> [name=YJ][color=#e2416a]
使用的唯一條件：要有辦法 create 一個 process 和 OS 之間可以共用的 memory 空間出來
但因為 OS 的 protection 機制，不同的 process 不可能會有 shared space，所以有專門的 system call 來處理，所以可以去 create 共用的空間出來
* 流程：
1. 向OS提出建立共享空間需求
要去溝通的 process，自己去 call system call，向OS提出建立共享空間需求
2. 向OS提出存取共享空間要求
透過這塊空間去溝通的 process，同樣要再去 call 另外一個 system call 叫 attach，跟 OS 告知要去用這塊空間
**上面的步驟都是要讓所有狀況都在 OS 的管理之下，所以 system call 都要負責告知那些 memory 空間是可以被 share 的**
當 OS 幫你 create 出來之後，就什麼事也不會幫你做了，使用者要自己去決定怎麼使用和管理這塊空間，要 allocate 怎麼樣的 data structure、pointer、data 等等的，兩邊的 process 都要協議好，OS 不幫你做，**OS 只負責不擋你這個 process 去取用 shared memory**
如果有兩個或以上的 process 同時想 write 這塊空間的時候，就會產生 synchronization 的問題，因為你不知道會發生什麼事，不知道結果為何
> 什麼是 Synchronization（同步）？
> Process 因為某些event 的發生而被迫 waiting，無法往下執行，必須等其他 protcess do something 後，才有機會往下執行
> [name=YJ][color=#e2416a]
#### 如何解決 Consumer & Producer Problem？
* 想處理的問題：shared memory 要怎麼去處理 synchronization 而不會造成錯誤
* 思路：
假設有兩支程式要共用一塊 memory 的 buffer
producer → 負責產生 information
consumer → 負責把 information 拿掉
#### Message Passing
> 定義：當 process 之間無法共享 memory，須利用 message passing 方式溝通
> [name=YJ][color=#e2416a]
#### Shared Memory & Message Passing 比較
#### Socket
#### Remotw Procedure Calls
Sign in with Wallet
Connect another wallet