[OS] Process

4.1 process 基本概念

Process為處理程序

• 程式做I/O時，System Call會產生I/O Process，所以在大部份情況， 程式都有兩個或以上個process。
• Passive Entity: 程式
• Active Entity: process
• Job Step: 可以視為程式，並且內部有2個以上的process
• 若不細分也可稱為Task: Multitasking => multiprogramming
• 平行
  • pseudo Parallelism: 透過單個CPU模擬平行，concurrent
  • True Parallelism: 多個CPU

process 的組成

• 機器碼
• 資料
• 資源: RAM, file..
• Stack: 中斷後需要透過stack保存狀態
• Status: PC, CPU register, process state
• Process ID

注: Abstract Machine => Virtual Machine

狀態

當單一CPU時，僅能有一個Process在Processor執行

• Ready state: 系統包含ready queue處理不同process等待，有0到多個process
  • Dispatch => queue front的process轉換成Running state
• Running state: 只有一個Process可以佔有CPU，有0或1的process
  • Time Out => 回到 Ready state
  • I/O Block或Wait Event => 進入 block state
• Blocked state: 放置於 Blocked queue(或array)，有0到多個process
  • Wake Up => 等待完成後回到 Ready state，並且放到ready queue

Context Switch

將CPU切換給另一個Process使用，透過中斷處理。

Context Switch發生在當前Process:

• timeout: 切換入Ready並dispatch process
• I/O, Event: 切換入Blocked並dispatch
• Terminated: terminate當前process並且dispatch

中斷方式

1. save CPU status與一般中斷相同
2. 執行CPU排程工作
3. restore CPU status時將預定process狀態放入CPU
4. 執行process

Process control blcok (PCB)

也稱為Process Descriptor，保存process的相關內容， 一個資料結構保存Process的資料，PID為獨一無二。

4.2 Process 排程

CPU Scheduler(Short term scheduler)用於管理ready queue與分派process給CPU

注: fork process時，等待child process terminates才將原process排入ready queue

各種排程器

• Long term Scheduler: 將process由disk移入Main memory，進入ready queue， 控制Multiprogramming的程式數量
• 中程排程器: 將process由Main Memory移入disk中，減少multiprogramming數量。
  • swap out (roll out, page out)
  • swap in
• short term scheduler: 管理佔有CPU被Process佔有的工作

I/O bound, CPU bound process

• I/O bound: I/O 時間 > 計算時間
• CPU bound: I/O 時間 < 計算時間

情況

• all I/O bound: cpu排程器無負荷
• all cpu bound: 極為緩慢，用完time slice

4.3 process operating

shell等待直到輸入， shell輸入命令後透過fork產生另外一個shell process， 並且新的process會以預計開啟的程式取代當前process的內容。

處理元功能

System call

• fork
• execve
• wait: parent process等待children process全部執行完畢之後， 由block切換到readly
• exit: 控制權回到OS
• abort: 結束process，並且有Cascading Termination

fork

process產生新的process，其程式碼與資源相同， 新的process由fork之後繼續執行。

• parent process: pid != 0
• children process: pid = 0

execve

透過預定開啟的程式的process蓋過當前的處理元。

4.4 合作process

可以影響或被影響的process之間為cooperating process。

ex: execve產生的process彼此之間為合作process

• concurrent process: 並行處理元，在time sharing環境process都輪流佔有CPU time slice。
• Independent Process: 相對於cooperating process，不受其他process影響的。

process 互助的目的

• information sharing
• Computation speedup
• Modularity
• convenience

合作處理元範例

• pipe: cat file file2 | sort

Producer and Consumer

Producer 與 Consumer的架構， 由於process為非同步因此中間必須有buffer， 選兩個process找出當中的關係。

buffer透過ring buffer(circuler buffer)處理

• producer: 產生資料，若buffer滿的話，必須讓producer wait
• consumer: 使用資料，若buffer為空，必須讓consumer wait

注: 由於設備有時間差，為了避免完全填滿或空buffer， 透過經驗法則去決定何時wait，如7分滿或3分滿時。

4.5 Thread

Process (Heavy Weight Process, HWP) 遇到的問題

• 多個Process在執行相同程式，使得消耗的記憶體比較多。
• Context Switch時，相同程式不同process切換降低了性能 ( Address Space 的切換)。

Thread (Light Weight Process, LWP)

• Process有1個與以上個Thread
• 不需要中斷: Process切換需要中斷
• 共用 Address Space
  • Code Section
  • Data Section
  • 資源
• 不共用
  • PC
  • Register Set
  • Stack Space

優點:

1. 執行相同的流程
2. 讓Context Switch低代價: 可以讓n個function concurrent

特性:

• 不必生成格外的Address Space，並且依附Process生成與結束
• 快速的 Context Switch
• 由於資料共用，不必 Inter Process Communication (IPC)
• 無法保護共享資料資料

分類

• User Thread
  • 編寫應用程式的thread
  • Thread Scheduler: library大多提供 Context Switch， 不必中斷使OS對Process Constext Switch
  • Process 分配本身的 time slice 給不同 Thread
  • I/O 中斷: 可能導致 Process 當中所有的 thread 被 block
• Kernel Thread
  • Kernel 管理的 Thread
  • 必須消耗中斷 (System Call) 的成本
  • 由OS排程: Thread 一個 Time slice
  • I/O 中斷: Thread 各自 block (OS 各自排程)

參見

• Kernel Threads and User Threads
• OS Process & Thread (user/kernel) 筆記

Multithreading Models

• Many to one: 多個 User thread 映射到 一個 kernel thread (Soleris Thread, JVM)， Process Block 時導致多個 Thread 無法執行。
• One to one: 缺少 Thread 的優點(NT kernel)
• Many to Many: Block 時保有其他 thread 能夠執行
  • Thread 必須依附在 Lightweight Process (Solaris OS定義: program 可生成多個 LWP，不同於先前的 LWP 定義)
  • Lightweight Process Mapping 到 kernel thread
  • Lightweight Process 的 time slice 分配給依附的 thread

補充

• Hyper Thread: 單核心模擬成兩個CPU，執行兩個thread
• Round Robin: time sharing，並且透過Java Based Round Robin Scheduler (優先級最高)， 其能夠控制裡面thread 的 priority高低。

4.6 Inter Process Communication

parent process 與 children proces 透過作業系統通訊，處理 process communication， 與Synchronize。

透過 IPC System call 處理，並且透過 Two way handshaking 的方式處理， 以同步 Process。

• Sender 會 blocked 直到 receiver ACK
• Timeout: 避免 Process 通訊出錯時，導致無窮等待，透過 time interrupt。
• Scrambled Messages: 雜訊導致訊息出錯
  • 檢查是否出錯
    • parity: odd, even，通常在硬體當中設計，並且計算1的數量，檢查錯誤
    • Checksum: 通常透過軟體實做
    • Cyclical Redundancy Check (CRC)¹
  • 檢查並且修復
    • Error Correction Codeing: 需要透過更多個 bit 來檢查是否出錯。
• Exception Condition Handling (Error Recovery): 透過系統通知與Timeout
• Client/Server Model: client請求server的服務

Remote Procedure Call

RPC，也可稱為Remote Process Communication，兩個 Process 在不同電腦傳輸通訊， 如網路等。

IPC 也可以以包含RPC來解釋。

類型

• Direct communication: 兩個Process，並且需要等待
• Indirect communication: 可以主動傳送，並且處理多個Process

實現方法

• Common event flags: 透過中斷的手法處理
• Mail box: Indirect communication，並且透過電腦的資源，如Shared Memory下去處理。
• Shared memory
• shared file

關於 buffer

• Zero Capacity (Rendezvous Synchronization): 無 buffer，並且資料會遺失， 並且先執行 Receiver 再執行 Sender
• Bound Buffer: 有固定的大小，透過 ring buffer 資料結構實做
• Unbound Buffer: 有固定的大小，但是消耗性能 (不斷 Assign 新的記憶體)

---

Operating System