OS 筆記 - CH4 Process 介紹 (上)
OS 筆記系列 CH4 - Process (上篇)
此章節介紹
- Process 定義
- Thread 定義 (淺談)
- Process Control Block (PCB)
- Context Switch
- 為何需要 Process Scheduling，和 常見 Schedulers
- Long-Term, Mid-Term, Short-Term
- Operations on Process
- Process creation and termination
- Interprocess Communication
- Share memory, Message passing, Remote Procedure call
抱歉沒有介紹排班演算法等等那邊，因為時間不夠寫
那邊看過就會了，誰能插隊誰不能插隊背一下
然後再背一句 " RR+Priority 時 Priority 無作用 " 這樣就行
Multilevel 兩個背一下
Process Concept
def : A program in execution ，又稱 job, task 等
- Program : passive entity : binary stored in disk
- Process : active entity : a program in execution in memory
是 OS 分配 資源 之對象單位 ( Thread 是 OS 分配 CPU Time 的對象單位 )
Process 含有
- Code Segment (text section)
- Data section : Global variables
- static variables 也算
- (補充) 其中還有再分 Initialized Data Segment 和 Uninitialized Data Segment
前者存放已經有明確初始化的 global 和 static 變數。
後者又稱 bss，包含未明確初始的global 和 static 變數，
當執行程式時會將其這區段的記憶體初始為零，只紀錄大小
等 run time 的時候利用 program loader 分配。
- Stack : temporary variables (local variables) and functions
- (補充) functions 包含 parameters 和 return address
之所以會在 stack，正是因為寫完 code 就固定好那些參數的 size 了，很好操作
- (補充) functions 包含 parameters 和 return address
- Heap : dynamic allocated variables or classes (malloc 出來的記憶體也是)
- Current activity : Program Counter, PID, P_State ,CPU Register contents
- PC 放在 Text 內 = Code segment
- Register contents : 當你被 switch 掉的時候就必須要備份下來
- A set of associated resources : e.g. open file handlers, socket port
講個有趣的，助教有次 pc^2 設定錯誤，學長解題連開始執行都被拒絕。
後來他把變數全部弄在 Global 就過關了，原因為何 ?
因為助教把 Heap 設定的太小，malloc 直接炸開
然而，把變數設在 Global 的話，屬於 Data Section，就沒問題了。找了幾個版本的比對一下，改了個圖，情況大概是這樣。
- 舉例
![圖源 : Mage]()
Thread Concept
放在這邊單純做比較使用，後面章節會更詳細介紹 Thread。
又稱為 Lightweight process : basic unit of CPU utilization (CPU 的最小單位)
Thread 間可以共用某塊 Memory，同個 Process 內 Thread 共享以下
- Code Section
- Date Section (用 global 去溝通)
- OS Source (open files, signals)
但，每個 Thread 的以下是獨立的
- Thread ID
- Program Counter
- Register set : 執行 instruction 時位置可能不同
- Stack = function 和 local 等等 temporary data
Process State
五大 States 版本
- New : 準備要將 Program load 到 memory，initial 各個 section
- admit : OS 在此時會確認有沒有足夠的資源去 create process，也會檢查權限(Protection)，成功的話進入 Ready
- Ready : Process 競爭 CPU，在 queue 裡面等待被 OS 排程、選中
- scheduler (選中) dispatch ( load 到 CPU ) 接著進入 Running
- Running : 執行程式
- 有一個情況會回 Ready : Interrupt --> 像是被 Timer 趕出來
- 另一個情況會去 Waiting : 要做 I/O
- 完成就直接跳 Terminated
- Waiting : process 想做 I/O 或其他原因造成 idle
- 此狀態又稱 Blocked，教材不同稱呼不同
- 如果進了 wait state，會被安排在 waiting queue，並且不會佔用 CPU 資源
- waiting queue 有很多種，有些是自己 sleep，有些是想要做 I/O。
- 完成之後回去 Ready State
- Terminated : 完成了
- 另外，我覺得 Mage 大的比喻十分不錯，真的。
另外，針對實際狀況其實還有 7 State 版本。
交大比較強調，補習班也有教，其實算夾雜 swap 章節觀念，所以也在此作補充。
七大 States 版本
補習班喜歡叫 Waiting State 為 Blocked State，但我改不過來，夾雜使用抱歉。
另外，這邊有點亂，要多想，撐住 ...
- 新增了 swap 到 Disk 的情形，其中也跟 Priority 有關。
- Blocked Suspend : 原本在 Blocked (Waiting) 待著，但 Waiting Queue 太滿了，所以有些 Process 必須被 Swap out 到 Disk 上。
- 決定要不要移動是 Medium-term scheduler 的決定。
- red OS 要檢查是不是正在做 I/O，如果正在做 I/O 要等他做完。
也就是說，不是所有 waiting queue 的都能 swap out。
或是 OS 先用 OS 的 buffer 幫他暫存起來，他 swap in 再交還給 process 的 memory。
- Ready Suspend : event occurred 或 I/O Complete，但仍然在 Disk 等待。
**新增了這些後，可能會多增加哪些路線 ? **
- Ready → Ready Suspend
- Memory 空間不足，又有 Priority 更高的 Process 出現，那就有犧牲者要被 suspend，由 Mid-Term Scheduler Swap out 到 Disk。
- 或是，在 Waiting State 的 Priority 都高於 Ready State 的，且 OS 覺得(?) 他們都快 I/O Complete 了
- Ready Suspend → Ready
- Memory 空間問題獲得改善，幫他 Swap in 回去。
- Running → Ready Suspend
- red Poor Design
- 簡單來說就是有個 Blocked Suspend 的超級 VVVIP 超想要先做，直接把 Running 的 Swap out。
- Blocked Suspend → Blocked
- red Poor Design
- Blocked Suspend 有個超級 VVVIP 又想要趕緊回去做事了。Ready State 的候補就是 Suspend Ready，所以只要 這個 VVVIP 的 Priority 比他們都高，就能直接 " 特殊 swap in " 回 Blocked (Waiting) State，接回 I/O 然後回 Ready。
- 說是 特殊 Swap In 因為正常的 Swap in 是 Ready Suspend → Ready
- 補充 : UNIX STD，書上的
Process Control Block
- 每個 Proces，OS 幫他 Create 一個 table，叫 PCB，來紀錄各項資訊
- 這個物件放到 Queue 裡面，用 Link-Listed 串 (用 PCB Pointer)
- 放在 Memory 裡面。而且是 Kernel Space 的，因為只有 OS 需要知道
- 較敏感的一定在 Kernel Space (前三項)，其餘可能在 User Space
- 紀錄以下
- Process state, PID
- Program counter
- CPU registers
- CPU scheduling information (e.g. priority)
- Memory-management information
- 為了要做 Protection, e.g. base/limit register
- 這個只有在 running 的時候才會 load 到 register，因為 Reg 很少很寶貴
- I/O status information : 你正在做哪一個 Device 的 I/O
- 不同 I/O Device 有不同 waiting queue
- Accounting information : 開 File 等
Context Switch
- def : Kernel saves the state of the old process and loads the saved state for the new process
- 流程 :
- Process0 收到 interrupt (Hardware) 或是 Process 想要 Syscall，就會觸發 Context Switch
- 然後 Process0 就 idle ㄌ
- save all state 到 PCB0
- load another PCB1
- Process1 這時都還是 idle
- 假設 Process0 好了，就要再做一次 Context Switch
- Process0 收到 interrupt (Hardware) 或是 Process 想要 Syscall，就會觸發 Context Switch
- 瓶頸 :
- Context Switch 是 purely overhead，無法避免。
- Switch Time 關乎於
- memory speed
- number of register (越多要 copy 就會越久)
- --- 然而以上都很難改善 ---
- existence of special instructions
OS 和 CPU 可能有特別合作，一看到 save/load 就知道要全部都轉移 - hardware support (常見)
* multiple sets of registers 一次記好多程式的狀態，免寫 memory，直接改 pointer - 或是想要 Multi-Programming 可以用 Mult-Threading 去代替
Why Process Scheduling
- 什麼場何會用到 ?
- Multiprogramming : maximize CPU utilization
- Time sharing : 達成 interactive (互動) 的效果
- Queue 也分不少種，有 Queue 故 Schedule 在。
- Job queue : (比較早期的OS，memory 有限) 從 program → 成為 process
- Ready queue : 從 ready → running，誰去使用 CPU
- 也可能不只一個，可能有 level 1 2 3
- Device queue : (Wait State) I/O Device queue 有很多種，看要進入哪種狀態
Schedulers
- Short-Term Scheduler (就是 CPU scheduler)
- **Short → 很頻繁 ! ** (很多程式要執行)
- selects which process should be executed and allocated CPU
- Ready state → Run state
- Long-Term Scheduler (job scheduler)
- 很久，秒 or 分鐘，launch process 才會需要
- selects which processes should be loaded into memory and brought into the ready queue
- New state → Ready state (甚至還沒被變成 Process 呢)
- Medium-Term Scheduler
- 在考慮 : 什麼時候把 process Swap 回 disk ? (為了空出 memory)
- 跟 Virtual memory 有關 !
- selects which processes should be ** swapped in/out memory**
- Ready state → Wait state
- 在這邊這樣寫，其實是指 Ready → Ready Suspend，見 7 State STD
- 在考慮 : 什麼時候把 process Swap 回 disk ? (為了空出 memory)
Long-Term Scheduler
- 控制 degree(數量) of multiprogramming
(確認多少程式在 memory)
- degree 太少 → CPU idle
- Select a good mix of CPU-bound & I/O-bound
- 希望 CPU 和 I/O 時間能 overlap (差不多重疊，同時都有事做)
- 常見考題 : CPU Bound 多 → 需要 CPU 的 Process 很多 → I/O 優先權比較高 (避免永遠排不到)
- 並不是只有 Long-Term 才能調配，其實 Mid-Term 也能哦
- 現在的 OS，你錢夠，memory 夠， Long-Term 的功能就越來越淡，變成 mid-term 的工作
- Batch System 採用，但是 Real-Time 及 Time-Sharing 不採用
( 我要做 I/O 就給我做 I/O，別檔我 ! )
Short-Term Scheduler
- Execute quite frequently (e.g. once per 100ms 超短)，頻率超高
- 制定參考 : 大概多久 Timer 要 Reschedule
- 必須確保公平、效率 (你不能讓一個人無止盡等下去)
- 但又不能算太久，overhead (選的時間) 控制在一定的範圍內
- 看 Priority 來挑，所以所有系統都適用。
Medium-Term Scheduler
- Swap Out : Removing processes from memory to reduce the degree of multiprogramming
- 在 Time-Sharing System 就會用上，工作量實在太高，
每個都在掛機
- 在 Time-Sharing System 就會用上，工作量實在太高，
- Swap In : Disk → Memory
- 目的 : 改善 process mix (CPU、I/O)，free up memory (degree太高 減少一下)
- Most modern OS doesn’t have medium-term scheduler because having sufficient physical memory or using virtual memory
- 註，此句來自於 周教授 PPT，實際是否如此待查證。
Dispatcher & Dispatch Latency
雖然我們說，是 Short-Term Scheduler 挑選出誰該從 Ready State 到 Running State，
但是是 Dispatcher 負責將 CPU 控制權交給被選中的 Process。步驟 :
- Context Switch
- Change mode from Kernel mode → User Mode
- Jump to the entry of selected process (像是 PC 該指的位置)
以上時間總和就是 Dispatch Latency，能的話當然盡量短。
比較 ( from Mage Note )
- Interrupt Latency : 決定 Interrupt 時間 + Context Switch + ISR 執行
- Dispatch Latency : 停目前的 Process + 準備新 Process 所需資源 + Context Switch
Operations on Processes
- Proceess 本身，User 怎麼 Create，怎麼讓他們溝通。
Tree of Process
- 每個 Process 都有 PID
- 不管什麼系統，都一定是有第一個 Process 然後創造其他的，所以一定可以話成 Tree
Process Creation
- parent 和 child 會有種關連性，這個部分可以由設計者決定，以下介紹 3 種
- Resource sharing
- e.g. create a new process，此 child 是否可以存取 parent 已經打開的檔案 ?
- share all ? subset ? 完全分家 ?
- 執行順序
- 同時 ? Parent wait until children terminate ?
- Address space
- memory content 是否是完全把 parent 所有東西都複製過去 ? (做一樣的事)
- communication via sharing variable
- 還是指定 child 做某些事 ? child has a program loaded into it. PC 重設
- communication via message passsing
- memory content 是否是完全把 parent 所有東西都複製過去 ? (做一樣的事)
(實例) UNIX/Linux Process Creation, Termination
fork system call
- The new process duplicates the address space of its parent (一模一樣)
- Child & Parent execute concurrently after fork (從該點繼續執行)
- parent 的 return 值是 child PID，child 得到的是 0
execlp system call
- Load a new binary file into memory ，舊的 code 丟了
wait system call
- 通常是 concurrently 執行，所以可以透過 waiting 調整
Memory space of fork():
- Old implementation : 無腦完全 copy
- Current implementation : Copy-on-write，run time,，修改值的時候再做分家
- memory 章節會再提及
exit system call
- all resource, including physical & virtual memory, open files, I/O buffers 都歸還 OS
abort
- Childern 如果拿了太多資源或是其他原因讓你想砍，可以用 abort 去砍。
- 不能砍 parent，不然自己也會掛 ( 從 parent node 以下全死 )
- e.g. console 用 Ctrl+C 就是砍 console，所以 console 生的子程式就能一起被砍
- kill 也能砍 process，但是需要權限
補充 vfork():
- 與 fork 類似，但是 child 與 parent 共用記憶體。
改東西會直接改到 parent 的東西，而 parent 會等到 child 結束或 exec 走才繼續執行。
很少用，除非確定 child 很快結束，不然 fork 已經有 copy-on-write 了，共用 memory 的優勢 fork 也有了。 - 基本上 除了 PID 之外的記憶體都共用。
不過如果在 vfork() 後的程式碼有動到跟指標有關的會 crash (如果 initial 在 vfork之前)。
原因 : 因為 child 要先結束 parent 才會動，結果 child free 掉了 parent 的 pointer ...
- 與 fork 類似，但是 child 與 parent 共用記憶體。
補充 clone():
By contrast with fork(), these system calls provide more precise control over what pieces of execution context are shared between the calling process and the child process.
For example, using these system calls, the caller can control whether or not the two processes share the virtual address space, the table of file descriptors, and the table of signal handlers.
clone()是Linux獨有的，簡單來說可以用更多參數來指定共用內容，理論上是更彈性版本的 fork()
Process Terminal
Mage 筆記之補充
由於 exec(), wait(), exit() 等指令使用時機關係，parent 和 child 在結束時可能會有幾種可能。
Normal : parent 會呼叫 wait() 等待 child 完成任務。
不過，雖然 child 結束了，資源也釋放了，但 PCB 的資訊還是會留著 (稱為 Zombie Process)
在 parent 結束之後 OS 會結束 parent，砍了 process tree，child 才會跟 parent 一起釋放。Zombie : 如果 Parent 事情太多要一直做，沒空 wait()，那 child 就會真的當 zombie。
對於此種問題，在實做上的解法可以是使用 SIGNAL 做溝通，或者是做兩次 fork() 來達成
- parent fork 出 child，child 再 fork 孫子，child call exit()，孫子變成孤兒
於是 OS 會找 init process (總之就是個管理員) 接管孫子。
這個 init process 會定期呼叫 wait() 來回收各地的 zombie。
- Orphan : 如果今天 parent 比 child 還早做完 ? 那這個 process 改叫做 orphan (孤兒)
不過 init process 也會接手回收。
Interprocess Communication (IPC)
- IPC : multiple threads 或 多 processes 的 溝通機制
- Independent process : 邊緣 process
- 與其相對的叫 Cooperating process
Communication Methods
先簡單了解一下 主要的特性
Shared memory
- 要做 synchronization，超麻煩
- 但是就是快
- Use memory address to access data
- Not **require any kernel intervention at all ** (100年電機丙第5題)
Message passing
- 慢，所以小資料比較適用，以及跨電腦一定用這個
- Use send/recv message (回想一下 socket)
- Implemented by system call
- 會用一些 API 來達成
- 是 blocking-send (當 zero capacity buffer 的時候)，因為 Sender 會被卡住 ...
Sockets
- IP, Port
- 傳輸 unstructured stream of bytes (沒有資料型態)
Remote Procedure Calls (RPC)
- 直接 call 別人的 Procedure Calls
- Client : val = server.method(A, B)
- 直接 call 別人的 Procedure Calls
Shared memory
- 要能 create 一塊區域出來可以 share
- 要 call system call 才有權限去 create
- synchronization 要 program 自己去調配，OS 不管你
Consumer & Producer Problem
- Consumer 拿資料，Producer 生資料
- 如果沒資料，Consumer 不能去拿；如果滿了，Producer 不能再生產 アタシ、再生產
- global : BufSize, buffer, in, out
- 有個很重要的關鍵 : empty 的條件是 in = out
如果你剛好滿了，in++，於是就又會跑到跟 out 同個位置。
這時實際情況是全滿，但可能會被判定成 empty
所以 full 的條件應該是 ( in+1 )%B = out 就該通知已滿，進入 busy waiting- 浪費一格是必須的
- 後面學到 locking 可以免犧牲
Message passing
因為有 "一方 call send 一方 call receive 才會傳輸" 的特性，可以用來確保同步化
(接通了，你我都在線上，一起開始走)Implement 細節
- phyiscal (hardware)
- logical
- 方向性，Direct or Indirect communication
- blocking or nonblocking (call了之後是否完全做完才return)
- 其他等等，像是 是否只是先傳 reference 才慢慢 copy
Direct communication
- 當 call function 建 link 的時候，OS 就會建好，不用再另外 call
- one-to-one，這是一種 **"限制"**，無法做到 broadcast 或 group 對話
- limited modularity : 這個 channel 的對話者已經確定了，無法更改，想要改通話對象必須重建
Indirect communication
- 有個 Mailbox，大家投信且不用指定對象，以及大家去收信但又不用管是誰寄的
- 也就是，Many-to-Many
- Mailbox 其實是個程式，用自己的 memory 去管理 (如果是 OS，就是用 kernel memory)
- 可能有很多 Mailbox，每個 ID 都是獨立的 (很像分縣市)
- 有同步問題。
- 解決 :
- Solution 1 : 只能最多兩個人在 -> 爛方法，等同 one-to-one
- Solution 2 : 用 locking，只能一個一個人 access 資料，接受多個 link 但是要等候
- Solution 3 : 可以同時 call，detect 是否有兩人同時 receive，如果有就擋其中一個，幫他們排隊。
- 解決 :
Synchronization 問題
- send 和 receiver 都可能會是 Blocking 或 Nonblocking，所以總共四種組合
- 如果 ... Nonblocking send，結果 receiver 還沒準備好怎辦 ?
所以中間的 Mailbox 其實會有個 Buffer 先接信- 如果 buffer 只有 0 1 兩種情況，等同 blocking send/receive
- bounded buffer : 滿了的話 sender 就會被 blocked
- unbounded buffer : sender never blocks
Remote Procedure Calls
- 特色就是可以 call 對方端的 function 而且 parameter 可以用 Data Structure
- 提供 RPC 的 Library 會有小的程式 run 在兩端幫忙溝通 (處理那些轉型態)
- 此問題叫 parameter marshaling，例如 int 是多少 bit 在不同平台不一樣
- client 的叫 Stub, server 叫 skeleton
![]()
Review
P.12
What’s the definition of a process?
a program in executionWhat’s the difference between process and thread?
Process 擁有自己的 section，而 thread 可以共有 data section, code section, OS Source 來達到輕量化。What’s PCB? its contents?
Process state, Program counter, CPU registersThe kinds of process state ?
new, ready, running, waiting, terminatedWhat’s context switch? (背一下)
Kernel saves the state of the old process and loads the saved state for the new process我覺得這種寫法也可以
把 CPU 上正在執行的 process，switch 成另外一個 process 的動作就叫做 context switch。
P.30
- What’s long-term scheduler? features? 負責調配 CPU 和 I/O 的工作量比例，選擇適當的工作從 disk 搬到 memory，久久才做一次
- What’s short-term scheduler? features? 負責根據排班器的 Priority 挑選誰該從 Ready State 到 Runnning State，做的頻率很高
- What’s medium-term scheduler? features? 負責在記憶體不足的時後決定誰該被 swap in/out，
- What’s the different between duplicate address space and load program? Their commands? fork 和 exec 的差別，一個是執行原本 parent 的工作，後者則是執行被指派到的其他工作
P.52
- Shared memory vs. Message-passing system ? 前者速度快，但是要處理同步問題；後者速度慢，但是可以確保同步
- Direct vs. Indirect message-passing system ? 前者是 1對1 溝通，後者是 sender 不指定接收者，接收者透過 mailboxes 看到也不會在意誰是 sender
- Blocking vs. Non-Blocking ? 前者是暫停 Process 等 I/O 做完才繼續做下去，後者是 I/O 做多少就 return 多少
- Socket vs. RPC ? 前者是傳 binary stream 給對方，不能指定資料型態，後者是 call 對方的 function，且雙方會有輔助程式幫忙處理型態問題，故可以使用 Data Structure
附註
這份量有點多 ...
這篇主要是注重 Prcoess 基礎結構、運做和溝通方式。
下篇會介紹 排程演算法，以及效能的估計。
參考
Mage 大的筆記、薛至文教授 PPT、周至遠教授 PPT (Process Chap and 10D)
geeksforgeeks、MLab、Ping's blog、yovan OS 筆記、PCB儲存、imgur、Zombie補充
END
-----------------------------------
2019.11.04